DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning

existing areas (however, please still apply even if your research isn't in these areas). The project will be financed by my current company which has made extensive use of deep learning for the past 4 years. You will have access to the >100 top-end GPUs owned by this company. The job will be structured as a research residency program in the first year, with the hope of transitioning successful candidates into full-time roles. In your application, please include a high-level research proposal stating what you would work on. To apply, email me at : not_a_cat at fastmail. co[m].

range of programs, and obtain as much info as possible about program structure without actually running the program. I've come across LISP-without-macros in Dreamcoder (https://arxiv.org/abs/2006.08381), BF++ (https://arxiv.org/abs/2101.09571), and a couple of others which I can't remember right now. I think the APL family (APL/J/K) would interesting because fewer characters to generate, but each character has a lot of meaning. Right now I'm looking at flow-based programming (FBP) for this: In FBP the control flow is explicit - the program code describes a directed acyclic graph (DAG), so comparing program structure becomes straightforward (subgraph isomorphism with some heuristics). I'm writing a toy FBP language that draws images (https://github.com/mayahq/flatland), with which I aim to test what these models understand.

before being corrected by Eurisko." Lenat did not know much about the game and its search space was intractable for the AI. The combination of both was able to come up with unique solutions counter-intuitive to humans. From a certain perspective, Eurisko could also be viewed as on the path to some next iteration of programming that never quite arrived. That is, programming languages stalled in the 70s, as Alan Kay notes in: http://worrydream.com/EarlyHistoryOfSmalltalk/ A look beyond OOP as we know it today can also be done by thinking about late-binding. Prolog's great idea is that it doesn't need binding to values in order to carry out computations [Col *]. The variable is an object and a web of partial results can be built to be filled in when a binding is finally found. Eurisko [Lenat *] constructs its methods—and modifies its basic strategies—as it tries to solve a problem. Instead of a problem looking for methods, the methods look for problems—and Eurisko looks for the methods of the methods. This has been called "opportunistic programming"—I think of it as a drive for more enlightenment, in which problems get resolved as part of the process. This higher computational finesse will be needed as the next paradigm shift—that of pervasive networking—takes place over the next five years. Objects will gradually become active agents and will travel the networks in search of useful information and tools for their managers. Objects brought back into a computational environment from halfway around the world will not be able to configure themselves by direct protocol matching as do objects today. Instead, the objects will carry much more information about themselves in a form that permits inferential docking. Some of the ongoing work in specification can be turned to this task [Guttag ][Goguen]. Tongue in cheek, I once characterized progress in programming languages as kind of "sunspot" theory, in which major advances took place about every 11 years. We started with machine code in 1950, then in 1956 FORTRAN came along as a "better old thing" which if looked at as "almost a new thing" became the precursor of ALGOL-60 in 1961. In 1966, SIMULA was the "better old thing," which if looked at as "almost a new thing" became the precursor of Smalltalk in 1972. Everything seemed set up to confirm the "theory" once more: in 1978 Eurisko was in place as the "better old thing" that was "almost a new thing". But 1983—and the whole decade—came and went without the "new thing". Of course, such a theory is silly anyway—and yet, I think the enormous commercialization of personal computing has smothered much of the kind of work that used to go on in universities and research labs, by sucking the talented kids towards practical applications. I believe Eurisko operates on very similar principles as PI, which is detailed here:http://bactra.org/reviews/hhnt-induction/ in a fascinating review by Shalizi. > Unlike the classifier system, which acts on raw binary strings, PI rules and representations are Lisp expressions, and there are more structured representations of concepts, which are however still basically rule clusters. Again unlike the classifier system, which gets new rules by using a genetic algorithm on existing ones, PI has a number of specific inductive mechanisms --- specialization, generalization, abduction, and concept formation --- which are intended to be reminiscent of conscious experience, unlike the GA. PI was invented by Holland, who is more famously known for his contributions to genetic algorithms and evolutionary computation. Those algorithms were meant to be used in a system like PI and not in the stand alone manner typical of today. Learning Classifier Systems being simplified versions of PI, are probably the closest concept to Eurisko in semi-active use. DreamCoder: https://arxiv.org/abs/2006.08381 is the latest development along this investigatory and very much underexplored path to Machine intelligence.

recent introduction to the field of program synthesis research which is still dominated by non-neural approaches and for very good reasons. I linked to another paper that shows an example of a system of the non-neural kind that is common in program synthesis. I pointed out that regardless of the one and only benchmark on which the LLM-based systems have been tested that are listed in the article above, the approach of code generation by LLM is primitive compared to the sophisticated search and testing strategies developed by the wider prorgam sythesis community over the years. Again, see Gulwani at al. for examples. The proposed approach is also primitive compared to existing, earlier neural program synthesis approaches, i.e. program synthesis approaches that do use a neural network, but not an LLM, for example DreamCoder [https://arxiv.org/abs/2006.08381] or everything from Dawn Song's group [https://sunblaze-ucb.github.io/program-synthesis/index.html] - none of which I'm affiliated with in any way, btw. If you're looking for the state of the art in program synthesis, look elsewhere than LLM-based systems like the one in the article above. Even if you're looking for the state of the art in neural program synthesis, look elsewhere. What is described in the article above is a first, faltering step in a direction that may still yield some good results in the future. Or it may not. But it's nothing impressive for the time being. >> Unpublish paper and results? Gulwani et al is a technical report but it's a staple reference in the field, and an easy introduction to outsiders. As far as I can tell, neither AlphaCode, nor CodeRL (the Salesforce model described in the article) have been the subject of published work. The article above is linking to an arxiv preprint.

program induction by neural networks that I am aware of is the work of Dawn Song's group at Berkeley [1] and of Joshua Tenenbaum's group at MIT. I can't find a handy link to a compilation of the latter group's work but the Dreamcoder paper in the paperswithcode search you linked to was an interesting milestone [2]. There is a lot of work on neuro-symbolic approaches to program induction, for example see the recent (two weeks ago) NeSy workshop [3], part of the first International Joint Conference on Learning and Reasoning for some new work in that burgeoning field. Statistical Relational AI combines symbolic with probabilistic learning; see the STAR-AI workshop [4] also at IJCLR. If you're interested in recent developments on the front of program induction (again, learning programs from examples) then IJCRL is the conference to keep an eye on. _______ [1] https://sunblaze-ucb.github.io/program-synthesis/index.html [2] https://arxiv.org/abs/2006.08381 [3] https://sites.google.com/view/nesy20/home [4] https://starai.cs.kuleuven.be/2021/