CoChat
Sign Up
Cited by 125Evolutionary Algorithms and ApplicationsAI-based Problem Solving and PlanningTeaching and Learning Programming

DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning

Open access
Ellis, Kevin, Wong, Lionel, Nye, Maxwell, Sablé-Meyer, Mathias, Cary, Luc, Anaya Pozo, Lore, Hewitt, Luke, Solar-Lezama, Armando +1 more·2023·Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
DOI 10.1098/rsta.2022.0050
Open this paper in CoChat — free accountOpen PDF

Abstract

Expert problem-solving is driven by powerful languages for thinking about problems and their solutions. Acquiring expertise means learning these languages—systems of concepts, alongside the skills to use them. We present DreamCoder, a system that learns to solve problems by writing programs. It builds expertise by creating domain-specific programming languages for expressing domain concepts, together with neural networks to guide the search for programs within these languages. A ‘wake–sleep’ learning algorithm alternately extends the language with new symbolic abstractions and trains the neural network on imagined and replayed problems. DreamCoder solves both classic inductive programming tasks and creative tasks such as drawing pictures and building scenes. It rediscovers the basics of modern functional programming, vector algebra and classical physics, including Newton’s and Coulomb’s laws. Concepts are built compositionally from those learned earlier, yielding multilayered symbolic representations that are interpretable and transferrable to new tasks, while still growing scalably and flexibly with experience. This article is part of a discussion meeting issue ‘Cognitive artificial intelligence’.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1098/rsta.2022.0050

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Many contemporary program synthesis methods involve learning algorithms, e.g., using neural network heuristics, guided by oracles such as formal verifiers or LLMs to accelerate the learning process.

    “Many contemporary program synthesis methods involve learning algorithms, e.g., using neural network heuristics, guided by oracles such as formal verifiers or LLMs to accerelate the learning process (Ellis et al., 2023;Grand et al., 2023).”

    From Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems (2024) · cites this paper as Ellis et al., 2023

    The Introduction and §2 (Wake/sleep program learning; page unavailable) describe neural networks that guide program search and speed up problem-solving. The cited paper does not support the added claim that formal verifiers or LLMs serve as oracles guiding that learning process. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • This pattern is highly characteristic of more traditional symbolic systems, which also prefer solutions with low description length and have been engineered specifically to 'refactor' their representations during training to decrease description length of more general concepts.

    “This pattern is highly characteristic of more traditional symbolic systems, which also prefer solutions with low description length [63] and have been engineered specifically to ‘refactor’ their representations during training to decrease description length of more general concepts [64].”

    From Symbols and grounding in large language models (2023) · cites this paper as [64]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 63 · Cited by 125

Research works printed but not linked: 50

  1. Liang P, Jordan MI, Klein D. 2011 Learning dependency-based compositional semantics. ACL 49, 590-599.
  2. Kulkarni TD, Kohli P, Tenenbaum JB, Mansinghka V. 2015 Picture: a probabilistic programming language for scene perception. In Proc. 2015 IEEE Conference on Computer Vision and Pattern Recognition, Boston, MA, 07-12 June 2015, pp. 4390-4399. New York, NY: IEEE.
  3. Chater N, Oaksford M. 2013 Programs as causal models: speculations on mental programs and mental representation. Cogn. Sci. 37, 1171-1191. (doi:10.1111/cogs.12062) · DOI
  4. Gulwani S. 2011 Automating string processing in spreadsheets using input-output examples. In POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Austin, TX, 26-28 January 2011, pp. 317-330. New York, NY: ACM.
  5. Lázaro-Gredilla M, Lin D, Guntupalli JS, George D. 2019 Beyond imitation: zero-shot task transfer on robots by learning concepts as cognitive programs. Sci. Rob. 4, eaav3150. (doi:10.1126/scirobotics.aav3150) · DOI
  6. Devlin J, Bunel RR, Singh R, Hausknecht M, Kohli P. 2017 Neural program meta-induction. NIPS 31, 2077-2085.
  7. Dudai Y, Karni A, Born J. 2015 The consolidation and transformation of memory. Neuron 88, 20-32. (doi:10.1016/j.neuron.2015.09.004) · DOI · Paper page
  8. Fosse MJ, Fosse R, Hobson JA, Stickgold RJ. 2003 Dreaming and episodic memory: a functional dissociation? J. Cogn. Neurosci. 15, 1-9. (doi:10.1162/089892903321107774) · DOI · Paper page
  9. Hinton GE, Dayan P, Frey BJ, Neal RM. 1995 The 'wake-sleep' algorithm for unsupervised neural networks. Science 268, 1158-1161. (doi:10.1126/science.7761831) · DOI · Paper page
  10. Dumancic S, Guns T, Cropper A. 2021 Knowledge refactoring for inductive program synthesis. Proc. AAAI Conf. on Artif. Intell. 35, 7271-7278. (doi:10.1609/aaai.v35i8.16893) · DOI · Paper page
  11. Dechter E, Malmaud J, Adams RP, Tenenbaum JB. 2013 Bootstrap learning via modular concept discovery. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China, 3-9 August 2013, pp. 1302-1309. Washington, DC: AAAI Press.
  12. Balog M, Gaunt AL, Brockschmidt M, Nowozin S, Tarlow D. 2016 Deepcoder: learning to write programs. ICLR 2017, Toulouse, France, 24-26 April 2016. (doi:10.48550/arXiv.1611.01989) · DOI
  13. Devlin J, Uesato J, Bhupatiraju S, Singh R, Mohamed A-R, Kohli P. 2017 Robustfill: neural program learning under noisy i/o. In ICML'17: Proceedings of the 34th International Conference on Machine Learning, Sydney, Australia, 6 August 2017, pp. 990-998. New York, NY: ACM.
  14. Ellis K, Morales L, Sablé-Meyer M, Solar-Lezama A, Tenenbaum J. 2018 Library learning for neurally-guided bayesian program induction. In NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montréal, Canada, 2-8 December 2018, pp. 7816-7826. New York, NY: ACM.
  15. Lau T, Wolfman SA, Domingos P, Weld DS. 2003 Programming by demonstration using version space algebra. Mach. Learn. 53, 111-156. (doi:10.1023/A:1025671410623) · DOI
  16. Mitchell TM. 1977 Version spaces: a candidate elimination approach to rule learning. In IJCAI'77: Proceedings of the 5th international joint conference on Artificial intelligence, Cambridge, MA, 22-25 August 1977, pp. 305-310. Washington, DC: AAAI.
  17. Polozov O, Gulwani S. 2015 Flashmeta: a framework for inductive program synthesis. ACM SIGPLAN Not. 50, 107-126. (doi:10.1145/2858965.2814310) · DOI
  18. Tate R, Stepp M, Tatlock Z, Lerner S. 2009 Equality saturation: a new approach to optimization. ACM SIGPLAN Notices 44, 264-276.
  19. Cao D, Kunkel R, Nandi C, Willsey M, Tatlock Z, Polikarpova N. 2023 Babble: learning better abstractions with e-graphs and anti-unification. POPL 7, 396-424. (doi:10.1145/3571207) · DOI
  20. Alur R, Fisman D, Singh R, Solar-Lezama A. Sygus-comp 2017: results and analysis. (http:// arxiv.org/abs/1711.11438). 2017. · arXiv
  21. Raven J. 2003 Raven progressive matrices. In Handbook of nonverbal assessment (ed. S McCallum), pp. 223-237. Cham, Switzerland: Springer.
  22. Marcus GF, Vijayan S, Rao SB, Vishton PM. 1999 Rule learning by seven-month-old infants. Science 283, 77-80. (doi:10.1126/science.283.5398.77) royalsocietypublishing.org/journal/rsta Phil. Trans. R. Soc. A 381: 20220050 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . · DOI
  23. Hewitt L, Le TA, Tenenbaum J. 2020 Learning to learn generative programs with memoised wake-sleep. In Uncertainty in Artificial Intelligence PMLR volume 124. (http://proceedings. mlr.press/v124/hewitt20a/hewitt20a.pdf)
  24. Kriegeskorte N, Mur M, Bandettini PA. 2008 Representational similarity analysis- connecting the branches of systems neuroscience. Front. Syst. Neurosci. 2, 4. (doi:10.3389/ neuro.06.004.2008) · DOI · Paper page
  25. Chi MTH, Feltovich PJ, Glaser R. 1981 Categorization and representation of physics problems by experts and novices. Cogn. Sci. 5, 121-152. (doi:10.1207/s15516709cog0502_2) · DOI · Paper page
  26. Chi MTH, Glaser R, Farr MJ. 1988 The nature of expertise. London, UK: Taylor & Francis Group.
  27. Langley P. 1987 Scientific discovery: computational explorations of the creative processes. Cambridge, MA: MIT Press.
  28. Schmidt M, Lipson H. 2009 Distilling free-form natural laws from experimental data. Science 324, 81-85. (doi:10.1126/science.1165893) · DOI
  29. Gibbons J. 2003 Origami programming. In The fun of programming (eds J Gibbons, O de Moor). London, UK: Red Globe Press.
  30. Ellis K, Ritchie D, Solar-Lezama A, Tenenbaum JB. 2018 Learning to infer graphics programs from hand-drawn images. In NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montréal, Canada, 2-8 December 2018, pp. 6062-6071. New York, NY: ACM.
  31. Graves A et al. 2016 Hybrid computing using a neural network with dynamic external memory. Nature 538, 471. (doi:10.1038/nature20101) · DOI · Paper page
  32. Valkov L, Chaudhari D, Srivastava A, Sutton C, Chaudhuri S. 2018 Houdini: lifelong learning as program synthesis. NeurIPS 31, 8701-8712.
  33. Andreas J, Rohrbach M, Darrell T, Klein D. 2016 Neural module networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, 27-30 June 2016, pp. 39-48. New York, NY: IEEE.
  34. Manhaeve R, Dumancic S, Kimmig A, Demeester T, Raedt LD. 2018 Deepproblog: neural probabilistic logic programming. In NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montréal, Canada, 2-8 December 2018. New York, NY: ACM.
  35. Young H, Bastani O, Naik M. 2019 Learning neurosymbolic generative models via program synthesis. ICML 42, 7144-7153.
  36. Feinman R, Lake BM. 2020 Generating new concepts with hybrid neuro-symbolic models. In Proceedings of the Annual Meeting of the Cognitive Science Society, Virtual, 29 July -1 August 2020. Seattle, WA: Cognitive Science Society.
  37. Evans JSBT. 1984 Heuristic and analytic processes in reasoning. Br. J. Psychol. 75, 451-468. (doi:10.1111/j.2044-8295.1984.tb01915.x) · DOI
  38. Wong C, Ellis K, Tenenbaum JB, Andreas J. 2021 Leveraging language to learn program abstractions and search heuristics. In Proceedings of the 38th International Conference on Machine Learning, Virtual, 18-24 July 2021, pp. 11 193-11 204. PMLR.
  39. Tian L, Ellis K, Kryven M, Tenenbaum J. 2020 Learning abstract structure for drawing by efficient motor program induction. NeurIPS 33, 2686-2697.
  40. Kumar S et al. 2022 Using natural language and program abstractions to instill human inductive biases in machines. NeurIPS 35, 167-180.
  41. Ellis K, Albright A, Solar-Lezama A, Tenenbaum JB, O'Donnell TJ. 2022 Synthesizing theories of human language with bayesian program induction. Nat. Commun. 13, 5024. (doi:10.1038/s41467-022-32012-w) royalsocietypublishing.org/journal/rsta Phil. Trans. R. Soc. A 381: 20220050 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . · DOI
  42. Wong C, McCarthy WP, Grand G, Friedman Y, Tenenbaum JB, Andreas J, Hawkins RD, Fan JE. 2022 Identifying concept libraries from language about object structure. In Proceedings of the Annual Meeting of the Cognitive Science society. Preprint.
  43. Markman EM, Wachtel GF. 1988 Children's use of mutual exclusivity to constrain the meanings of words. Cognit. Psychol. 20, 121-157. (doi:10.1016/0010-0285(88)90017-5) · DOI
  44. Hutter M. 2004 Universal artificial intelligence: sequential decisions based on algorithmic probability. Berlin, Heidelberg: Springer Science & Business Media.
  45. Fodor JA. 1975 The language of thought, vol. 5. Cambridge, MA: Harvard University Press.
  46. Piantadosi ST. 2011 Learning and the language of thought. PhD thesis, MIT.
  47. Solar Lezama A. 2008 Program synthesis by sketching. PhD thesis.
  48. Lake BM, Ullman TD, Tenenbaum JB, Gershman SJ. 2017 Building machines that learn and think like people. Behav. Brain Sci. 40, e253. (doi:10.1017/S0140525X16001837) · DOI · Paper page
  49. Spelke ES, Breinlinger K, Macomber J, Jacobson K. 1992 Origins of knowledge. Psychol. Rev. 99, 605. (doi:10.1037/0033-295X.99.4.605) · DOI
  50. Carey S. 2011 The origin of concepts: a précis. Behav. Brain Sci. 34, 113. (doi:10.1017/ S0140525X10000919) · DOI

Authors
Ellis, K., Wong, L., Nye, M., Sablé-Meyer, M., Cary, L., Anaya Pozo, L., Hewitt, L., Solar-Lezama, A., & Tenenbaum, J. B.
Affiliations
  • Cornell University (US)
  • Massachusetts Institute of Technology (US)
  • Collège de France (FR)
  • MIT, Cambridge, MA, USA
Corresponding author
Ellis, Kevin
ORCID
Venue
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
Publisher
The Royal Society
Published
2023-06-05
Volume
381
Issue
2251
Pages
20220050-20220050
ISSN
  • 1364-503X (ISSN-L)
  • 1471-2962
DOI
10.1098/rsta.2022.0050
OpenAlex
W3034789704
Cited by
125
References
63
Citations by year
2026: 17 · 2025: 18 · 2024: 19 · 2023: 18 · 2022: 15 · 2021: 29 · 2020: 9
FWCI
6.79
Type
journal article
Language
en
Open access
Licence
royalsociety.org/journals/ethics-policies/data-sharing-mining/ (tdm)
Locations
  • Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (1918839)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
Keywords
inductive programming, domain-specific languages, symbolic abstraction, compositional representations, program search, functional programming, vector algebra, Newton's laws of motion, Coulomb's law, generative AI, cognitive artificial intelligence

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review