program synthesis
In plain wordsGetting a computer to write a program automatically from a description of what the program should do — a logical specification, a few input–output examples or a request in plain language.
The automatic generation of a program from a statement of what it must do: a formal logical specification (deductive synthesis), input–output examples (programming by example, or inductive synthesis), a partial program with holes (sketching), a reference implementation, or a natural-language description. Classical approaches extract programs from constructive proofs, search enumeratively over programs in a domain-specific language while pruning by types and equivalence, or encode the search as a constraint problem for SMTsatisfiability modulo theories, n.: An extension of logic-puzzle solving that also understands arithmetic, arrays and other data types, so it can check whether conditions in software, such as 'x + y > 10 and x < 3', can ever be met. solvers, as in counterexample-guided inductive synthesis (CEGIS). Spreadsheet features such as Excel's Flash Fill brought programming by example to millions of users. Since 2021 the field has been dominated by large language modelslarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code. trained on code (code generationcode generation, n.: Having an AI write computer code from a description in plain language, from finishing a single line as you type to building whole programs.), increasingly combined with execution feedback, tests, verifiers and evolutionary search, as in FunSearchFunSearch, prop. n.: A Google DeepMind method that discovered new mathematical constructions by having a language model repeatedly rewrite short computer programs, keeping the versions that scored best. and AlphaEvolveAlphaEvolve, prop. n.: A Google DeepMind system that combines AI language models with an evolution-like search to invent and improve computer programs, finding new results in mathematics and computing.. Inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge. and genetic programminggenetic programming, n.: Using simulated evolution to write computer programs: random programs compete at a task, and the best are combined and mutated over many generations until one does the task well. are related traditions.
Given three examples of reformatted dates, the synthesizer produced a one-line transformation that handles all 40,000 rows.
Origin
Alonzo Church posed the synthesis of circuits from logical specifications in 1957. Cordell Green (1969) and Zohar Manna and Richard Waldinger (1971–1980) developed deductive synthesis from theorem proving, and Phillip Summers (1977) synthesized Lisp programs from examples; Sumit Gulwani's Flash Fill (2011) and code-trained language models such as Codex (2021) brought synthesis into everyday use.
Usage note
Often used interchangeably with code generation, but 'synthesis' traditionally implies a guarantee: the output provably meets the specification or at least reproduces every given example.
Related
- code generationcode generation, n.: Having an AI write computer code from a description in plain language, from finishing a single line as you type to building whole programs.
- inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge.
- genetic programminggenetic programming, n.: Using simulated evolution to write computer programs: random programs compete at a task, and the best are combined and mutated over many generations until one does the task well.
- satisfiability modulo theoriessatisfiability modulo theories, n.: An extension of logic-puzzle solving that also understands arithmetic, arrays and other data types, so it can check whether conditions in software, such as 'x + y > 10 and x < 3', can ever be met.
- neuro-symbolic AIneuro-symbolic AI, n.: AI that combines neural networks, which learn patterns from data, with symbolic methods, which follow explicit rules and logic, aiming for systems that both learn flexibly and reason reliably.
- AlphaEvolveAlphaEvolve, prop. n.: A Google DeepMind system that combines AI language models with an evolution-like search to invent and improve computer programs, finding new results in mathematics and computing.
- FunSearchFunSearch, prop. n.: A Google DeepMind method that discovered new mathematical constructions by having a language model repeatedly rewrite short computer programs, keeping the versions that scored best.
Sources
- Manna, Z. & Waldinger, R. (1980). A Deductive Approach to Program Synthesis. ACM Transactions on Programming Languages and Systems 2(1), 90–121.
- Gulwani, S., Polozov, O. & Singh, R. (2017). Program Synthesis. Foundations and Trends in Programming Languages 4(1–2), 1–119.
Mentioned in
ARC-AGIARC-AGI, prop. n.: Puzzles made of colored grids — and, since 2026, small video-game-like worlds — that people solve easily but AI long found hard, designed to test whether a machine can learn a new skill from just a few examples., code executioncode execution, n.: Letting an AI write a small program and actually run it — to do math, analyze a spreadsheet or test its own code — then use the real output instead of guessing., code generationcode generation, n.: Having an AI write computer code from a description in plain language, from finishing a single line as you type to building whole programs., inductive reasoninginductive reasoning, n.: Reasoning from particular examples to a general rule or prediction — every swan I have seen is white, so swans are probably white — which is useful but can always turn out wrong., neuro-symbolic AIneuro-symbolic AI, n.: AI that combines neural networks, which learn patterns from data, with symbolic methods, which follow explicit rules and logic, aiming for systems that both learn flexibly and reason reliably., AlphaEvolveAlphaEvolve, prop. n.: A Google DeepMind system that combines AI language models with an evolution-like search to invent and improve computer programs, finding new results in mathematics and computing., François CholletFrançois Chollet, prop. n.: A French software engineer who created Keras, a popular tool for building neural networks, and the ARC benchmark, which tests whether AI can solve kinds of puzzles it has never seen., FunSearchFunSearch, prop. n.: A Google DeepMind method that discovered new mathematical constructions by having a language model repeatedly rewrite short computer programs, keeping the versions that scored best., genetic programminggenetic programming, n.: Using simulated evolution to write computer programs: random programs compete at a task, and the best are combined and mutated over many generations until one does the task well., inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge., semantic parsingsemantic parsing, n.: Translating a sentence into a precise, machine-executable form — such as a database query or a logical formula — so that a computer can act on what was asked., symbolic regressionsymbolic regression, n.: Getting a computer to discover a readable mathematical formula, such as a law of physics, that fits a set of measurements, instead of only fitting numbers into a formula chosen in advance.