Introduction

This article got inspired by watching CodeDreamer video by Yannic Kilcher. CodeDreamer Paper

The goal is to explore all currently working aproaches to program synthesis and review all appraoches that didn’t worked in the past as I think it might be possible to create it curently.

Also got motivated by watching recent episode of Lex Fridman interview with John Carmack who belives that it shoudl be possible to create something akin to AGI by 2030 with 55-60% cerntainty.

I am even more bullish but I lack a little skills and knowledge in this domain, that’s why I’m foolishy joining this quest for the holy grail of programming - universal automaton

What is program synthesis

CSE 507 - Computer-Aided Reasoning for Software

The challenge according to CodeDreamer authors

A key challenge for program induction going forward is to handle more pervasive noise and uncertainty, by leaning more heavily on probabilistic and neural AI approaches (5, 43, 44). Recent research has explored program induction with various hybrid neuro-symbolic representations (45–49), and integrating these approaches with the library learning and bootstrapping capacities of DreamCoder could be especially valuable going forward.

Seems like their paper is based on Helmholtz machine

Also seems like “Kevin Ellis” is quite inerested in this stuff.

5 - Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338, 2015.
44 - Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471, 2016.

Spotted that Agnieszka Grabska-Barwinska is one of authors that work for DeepMind.

Unfortunatelly DeepMind doesn’t want to hire me so I have to beat em all. Good that I am bored.

General review of aproaches to program synthesis

Neural like Codex, CodeGen => There exist stuff like Codex, probabilistic/compression
Combinatorial / Search like DreamCoder => search through space of all possible programs
Genetic programming => some mutation of code, some way of exploring embedding also - need to learn more about these aproaches

What new stuff we got that didn’t exist in the past?

Big data -> there’s ton of existing code one could reuse if could match context, again I feel like that’s what Codex is good at
NNs -> ability to guide search and discover good heuristics in complex search spaces as demonstrated as AlphaZero

General idea of solution to universal automaton

Use DreamCoder way combined with this Language Models Can Teach Themselves to Program Better
Add some ideas from DeepMind AlphaCode => filtering
Add some ideas from SalesForce CodeGen => convesational ideas
Maybe review JEPA paper
I feel like starting with something akin to DreamCoder is correct apraoch
But instead let add NN to propose programs and generate “hallucinations” (from existing human code bases)

Extract biggest dataset possible of sudo-pure functions

Would be great to somehow grep all of Github for all pure function that exist and add then generate some possible input-output combinations of those and put them all in library.

Best if we could use language that marks functions as pure to bootstrap.

Benchmarks motherfucker

Ok, need some benchmarks. Will use some ready ones after I implement most basic stuff.

https://github.com/hendrycks/apps -> From text description but also have example tests which we could use

But before we should have ability to reproduce something like lodash