The DOI matches its Crossref record, with a small difference in title or year; 55 of the 56 references it cites were found in a registry or an index.
DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning
Open accessAbstract
We present a system for inductive program synthesis called DreamCoder, which inputs a corpus of synthesis problems each specified by one or a few examples, and automatically derives a library of program components and a neural search policy that can be used to efficiently solve other similar synthesis problems. The library and search policy bootstrap each other iteratively through a variant of "wake-sleep" approximate Bayesian learning. A new refactoring algorithm based on E-graph matching identifies common sub-components across synthesized programs, building a progressively deepening library of abstractions capturing the structure of the input domain. We evaluate on eight domains including classic program synthesis areas and AI tasks such as planning, inverse graphics, and equation discovery. We show that jointly learning the library and neural search policy leads to solving more problems, and solving them more quickly.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“Indeed, recently an external generative model that created “dream-like” input helped train a DNN to produce the code behind a given mathematical mapping.148”
From The overfitted brain: Dreams evolved to assist generalization (2021) · cites this paper as [148]
In the citing paper
“The evidence for this possibility comes from common methods in deep learning that improve generalization, such as dropout,126 domain randomization,144 and the use of input data created by stochastic stimulation of generative models,148 which together bear striking similarities to the properties of dreams.”
From The overfitted brain: Dreams evolved to assist generalization (2021) · cites this paper as [148]
Citations
Cites
Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation
Cho, K., van Merrienboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., & Bengio, Y. (2014) · Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.3115/v1/d14-1179 · Cited by 25,545
Prototypical Networks for Few-shot LearningPreprint
Snell, J., Swersky, K., & Zemel, R. S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.05175 · Cited by 6,245
Categorization and Representation of Physics Problems by Experts and Novices*
Chi, M. T. H., Feltovich, P. J., & Glaser, R. (1981) · Cognitive Science · doi:10.1207/s15516709cog0502_2 · Cited by 5,248
Distilling Free-Form Natural Laws from Experimental Data
Schmidt, M., & Lipson, H. (2009) · Science · doi:10.1126/science.1165893 · Cited by 3,327
Domain randomization for transferring deep neural networks from simulation to the real world
Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., & Abbeel, P. (2017) · 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2017.8202133 · Cited by 3,124 · cited 1×
“8E), compositionally recombining latent building blocks and motifs acquired from the training data in ways never seen in its waking experience, but ideal for training a broadly generalizable recognition model [55].”
BackgroundBetween MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., & Singh, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00052-1 · Cited by 3,119
Human-level concept learning through probabilistic program induction
Lake, B. M., Salakhutdinov, R., & Tenenbaum, J. B. (2015) · Science · doi:10.1126/science.aab3050 · Cited by 2,817 · cited 1×
“Inductive program synthesis ś synthesizing programs given one or more examples of their behavior ś has emerged as both a practical tool for automating end-user programming tasks [20, 43, 51], and a route to building more robust, interpretable, generalizable and sample-efficient learning systems in artificial intellige…”
MethodSelf-citationPattern recognition and machine learning
(2007) · Choice Reviews Online · doi:10.5860/choice.44-5091 · Cited by 2,783
Types and Programming Languages
Pierce, B. C. (2002) · Cited by 2,226
(2014) · doi:10.4324/9781315799681 · Cited by 2,174
Research works printed but not linked: 3
- Jacob Devlin Rudy R Bunel Rishabh Singh Matthew Hausknecht and Pushmeet Kohli. 2017. Neural Program Meta-Induction. In NIPS. Jacob Devlin Rudy R Bunel Rishabh Singh Matthew Hausknecht and Pushmeet Kohli. 2017. Neural Program Meta-Induction. In NIPS.
- Diederik P Kingma and Jimmy Ba . 2014 . Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. · arXiv
- Stuart J. Russell and Peter Norvig . 2003 . Artificial Intelligence : A Modern Approach (2 ed.). Pearson Education . isbn:0137903952 Stuart J. Russell and Peter Norvig. 2003. Artificial Intelligence: A Modern Approach (2 ed.). Pearson Education. isbn:0137903952
Cited by
Sorted by citations
Discovering causal relations and equations from data
Camps‐Valls, G., Gerhardus, A., Ninad, U., Varando, G., Martius, G., Balaguer‐Ballester, E., Vinuesa, R., Díaz, E., Zanna, L., & Runge, J. (2023) · Physics Reports · doi:10.1016/j.physrep.2023.10.005 · Cited by 159
DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning
Ellis, K., Wong, L., Nye, M., Sablé-Meyer, M., Cary, L., Anaya Pozo, L., Hewitt, L., Solar-Lezama, A., & Tenenbaum, J. B. (2023) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2022.0050 · Cited by 125
Self-citationReplay and compositional computation
Kurth-Nelson, Z. L., Behrens, T. E. J., Wayne, G., Miller, K. J., Luettgau, L., Dolan, R. J., Liu, Y., & Schwartenbeck, P. (2023) · Neuron · doi:10.1016/j.neuron.2022.12.028 · Cited by 100
A language of thought for the mental representation of geometric shapesPreprint
Sablé-Meyer, M., Ellis, K., Tenenbaum, J. B., & Dehaene, S. (2021) · PsyArXiv (OSF Preprints) · doi:10.1016/j.cogpsych.2022.101527 · Cited by 112
Self-citationBuilding machines that learn and think with people
Collins, K. M., Sucholutsky, I., Bhatt, U., Chandra, K., Wong, L., Lee, M., Zhang, C. E., Zhi‐Xuan, T., Ho, M. K., Mansinghka, V. K., et al. (2024) · Nature Human Behaviour · doi:10.1038/s41562-024-01991-9 · Cited by 125
Self-citation
Metadata
- Authors
- Ellis, K., Wong, C., Nye, M., Sablé-Meyer, M., Morales, L., Hewitt, L., Cary, L., Solar-Lezama, A., & Tenenbaum, J. B.
- Affiliations
- Cornell University (US)
- Massachusetts Institute of Technology (US)
- Collège de France (FR)
- ORCID
- Venue
- Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
- Publisher
- ACM
- Published
- 2021-06-18
- Pages
- 835-850
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W3174357804
- Cited by
- 103
- References
- 56
- Citations by year
- 2026: 14 · 2025: 24 · 2024: 18 · 2023: 30 · 2022: 10 · 2021: 7
- FWCI
- 7.51
- Type
- conference paper
- Language
- en
- Open access
- green
- hdl.handle.net
- Locations
- ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (publishedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- Funders
- National Science Foundation (1918839 and 1231216)
- Air Force Office of Scientific Research (FA9550-16-1-0012)
- 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 program synthesis, bootstrapping, refactoring, program abstraction, planning, inverse graphics, equation discovery
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
