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
Recursive functions of symbolic expressions and their computation by machine, Part I
McCarthy, J. (1960) · Communications of the ACM · doi:10.1145/367177.367199 · Cited by 1,635
Principal type-schemes for functional programs
Damas, L., & Milner, R. (1982) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/582153.582176 · Cited by 1,100
The "Wake-Sleep" Algorithm for Unsupervised Neural Networks
Hinton, G. E., Dayan, P., Frey, B. J., & Neal, R. M. (1995) · Science · doi:10.1126/science.7761831 · Cited by 1,070
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/1926385.1926423 · Cited by 1,039
Scientific Discovery: Computational Explorations of the Creative Processes
Pat Langley, B., Simon, H. A., Bradshaw, G. L., & Żytkow, J. M. (1987) · Medical Entomology and Zoology · Cited by 802
Simplify: a theorem prover for program checking
Detlefs, D., Nelson, G., & Saxe, J. B. (2005) · Journal of the ACM · doi:10.1145/1066100.1066102 · Cited by 788
DeepCoder: Learning to Write ProgramsPreprint
Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., & Tarlow, D. (2016) · International Conference on Learning Representations · doi:10.48550/arxiv.1611.01989 · Cited by 641
Heuristic and analytic processes in reasoning*
Evans, J. S. B. T. (1984) · British Journal of Psychology · doi:10.1111/j.2044-8295.1984.tb01915.x · Cited by 619
Wadler, P. L. (1990) · ACM Conference on LISP and Functional Programming (LFP) · doi:10.1145/91556.91592 · Cited by 586
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581
Synthesizing data structure transformations from input-output examples
Feser, J., Chaudhuri, S., & Dillig, I. (2015) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2737924.2737977 · Cited by 250
Tate, R., Stepp, M., Tatlock, Z., & Lerner, S. (2009) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/1480881.1480915 · Cited by 198
Program synthesis from polymorphic refinement types
Polikarpova, N., Kuraj, I., & Solar-Lezama, A. (2016) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2908080.2908093 · Cited by 189
Self-citationMeta-interpretive learning of higher-order dyadic datalog: predicate invention revisited
Muggleton, S. H., Lin, D., & Tamaddoni-Nezhad, A. (2015) · Machine Learning · doi:10.1007/s10994-014-5471-y · Cited by 184
RobustFill: Neural Program Learning under Noisy I/OPreprint
Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed, A., & Kohli, P. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.07469 · Cited by 174
Synthesizing Programs for Images using Reinforced Adversarial LearningPreprint
Ganin, Y., Kulkarni, T. D., Babuschkin, I., Eslami, S. M. A., & Vinyals, O. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.01118 · Cited by 168
Ultra-Strong Machine Learning: comprehensibility of programs learned with ILP
Muggleton, S., Schmid, U., Zeller, C., Tamaddoni‐Nezhad, A., & Besold, T. R. (2018) · Machine Learning · doi:10.1007/s10994-018-5707-3 · Cited by 116
A Machine Learning Framework for Programming by Example
Menon, A. K., Tamuz, O., Gulwani, S., Lampson, B., & Kalai, A. T. (2013) · Cited by 112
Novel positional encodings to enable tree-based transformers
Shiv, V. L., & Quirk, C. (2019) · neural information processing systems · Cited by 92
Learning Programs: A Hierarchical Bayesian Approach
Liang, P., Jordan, M. I., & Klein, D. (2010) · Cited by 80
Accelerating search-based program synthesis using learned probabilistic models
Lee, W., Heo, K., Rajeev Alur, A., & Naik, M. (2018) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3192366.3192410 · Cited by 78
Write, Execute, Assess: Program Synthesis with a REPL
Ellis, K., Nye, M., Pu, Y., Sosa, F., Tenenbaum, J., & Solar-Lezama, A. (2019) · arXiv · doi:10.48550/arxiv.1906.04604 · Cited by 65
Self-citationBeyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs
Lázaro-Gredilla, M., Lin, D., Guntupalli, J. S., & George, D. (2019) · Science Robotics · doi:10.1126/scirobotics.aav3150 · Cited by 63
Program Synthesis and Semantic Parsing with Learned Code IdiomsPreprint
Shin, E. C. R., Allamanis, M., Brockschmidt, M., & Polozov, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.10816 · Cited by 55
Variational Bayesian Grammar Induction for Natural Language
Kurihara, K., & Sato, T. (2006) · Lecture notes in computer science · doi:10.1007/11872436_8 · Cited by 55
Bias reformulation for one-shot function induction
Dianhuan, L., Eyal, D., Kevin, E., Joshua, T., & Stephen, M. (2014) · Frontiers in Artificial Intelligence and Applications · doi:10.3233/978-1-61499-419-0-525 · Cited by 53
Self-citationExecution-Guided Neural Program Synthesis.
Chen, X., Liu, C., & Song, D. X. (2018) · International Conference on Learning Representations · Cited by 52
Learning to Infer Program SketchesPreprint
Nye, M., Hewitt, L., Tenenbaum, J. B., & Solar-Lezama, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.06349 · Cited by 49
Self-citationFlashMeta: a framework for inductive program synthesis
Polozov, O., & Gulwani, S. (2015) · ACM SIGPLAN Notices · doi:10.1145/2858965.2814310 · Cited by 48
HOUDINI: Lifelong Learning as Program SynthesisPreprint
Valkov, L., Chaudhari, D., Srivastava, A., Sutton, C. A., & Chaudhuri, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.00218 · Cited by 47
Bootstrap Learning via Modular Concept Discovery
Dechter, E., Malmaud, J., Adams, R. P., & Tenenbaum, J. B. (2014) · Cited by 43
Self-citationNeural Program Search: Solving Programming Tasks from Description and ExamplesPreprint
Polosukhin, I., & Skidanov, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.04335 · Cited by 43
SyGuS-Comp 2017: Results and Analysis
Rajeev Alur, A., Fisman, D., Singh, R., & Solar-Lezama, A. (2017) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.260.9 · Cited by 36
Self-citationScientific discovery as problem solving
Simon, H. A. (1992) · International Studies in the Philosophy of Science · doi:10.1080/02698599208573403 · Cited by 35
Playgol: Learning Programs Through Play
Cropper, A. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/841 · Cited by 30
Seshia, S. A. (2012) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/2228360.2228425 · Cited by 29
Accelerating search-based program synthesis using learned probabilistic models
Lee, W., Heo, K., Rajeev Alur, A., & Naik, M. (2018) · ACM SIGPLAN Notices · doi:10.1145/3296979.3192410 · Cited by 28
Bias reformulation for one-shot function induction
Lin, D., Dechter, E., Ellis, K., Tenenbaum, J. B., & Muggleton, S. (2014) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 24
Self-citationInducing Probabilistic Programs by Bayesian Program MergingPreprint
Hwang, I., Stuhlmüller, A., & Goodman, N. D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.5667 · Cited by 17
Library learning for neurally-guided Bayesian program induction
Ellis, K., Morales, L., Sablé-Meyer, M., Solar-Lezama, A., & Tenenbaum, J. B. (2018) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 13
Self-citationCumulative Learning in the Lambda Calculus
Henderson, R. (2013) · doi:10.25560/24759 · Cited by 8
Learning to learn generative programs with Memoised Wake-SleepPreprint
Hewitt, L., Le, T., & Tenenbaum, J. B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.03132 · Cited by 8
Self-citationLearning Web-based Procedures by Reasoning over Explanations and Demonstrations in Context
Srivastava, S., Polozov, O., Jojić, N., & Meek, C. (2020) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2020.acl-main.684 · Cited by 2
(1988) · Bulletin of Science Technology & Society · doi:10.1177/027046768800800417 · Cited by 2
Hancock, P. (2004) · Journal of Functional Programming · doi:10.1017/s0956796804245324 · Cited by 1
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
