{ "id": "epy8aem999", "slug": "program-synthesis", "title": "Program synthesis", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Non-geographic · 2001 to 2020: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms" } ] } ], "excerpt": "Program synthesis is the task of automatically finding a program that satisfies a user's intent given as a specification, long called the holy grail of computer science.", "snippet": "Program synthesis is the task of automatically finding a program that satisfies a user's intent given as a specification, long called the holy grail of computer science.", "node": "technology.computing.ai.algorithms", "markdown": "# Program synthesis\n\nProgram synthesis is the task of automatically finding an executable program that satisfies a user's intent expressed as a specification, such as input-output examples, a logical formula, or a partial program with holes.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) Since the beginnings of AI in the 1950s it has been called the holy grail of computer science,[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) and its modern form rests on the systematic derivation of a program from a specification.[2](https://doi.org/10.1145/357084.357090)\n\n| Key fact | Detail |\n|---|---|\n| Definition | Automatic construction of a program in some language that satisfies a user intent given as a specification[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) |\n| Specification forms | Formulas, reference implementations, input-output pairs, traces, demonstrations, or syntactic sketches[3](https://www.cs.cmu.edu/~aldrich/courses/17-355-18sp/notes/notes13-synthesis.pdf) |\n| Main search techniques | Enumerative search, constraint solving, stochastic search, and deduction[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) |\n| Canonical problem format | SyGuS: a background theory, a logical correctness formula, and a grammar of candidate expressions[4](https://acg.cis.upenn.edu/papers/fmcad13_sygus.pdf) |\n| Mass-market deployment | FlashFill shipped in Microsoft Excel 2013; FlashExtract in PowerShell for Windows 10[5](https://doi.org/10.1145/2858965.2814310) |\n| Symbolic solver performance | cvc5 solved 137 of 148 SyGuS-IF 2.1 benchmarks within 10 minutes, all verified correct[6](https://arxiv.org/html/2603.20264) |\n| LLM performance | A 137B-parameter model solved 59.6% of MBPP few-shot; fine-tuning added about 10 percentage points[7](https://doi.org/10.48550/arxiv.2108.07732) |\n\n## How it works\n\nA synthesizer is described along three dimensions: the intent (the specification), the program space (usually a domain-specific language, DSL), and the search technique that finds a program in that space matching the intent.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) The specification may be a formula, a reference implementation, input-output pairs, traces, demonstrations, or a syntactic sketch.[3](https://www.cs.cmu.edu/~aldrich/courses/17-355-18sp/notes/notes13-synthesis.pdf)\n\nFour search paradigms dominate. Enumerative search is bottom-up, generating smaller sub-expressions before larger ones and pruning with examples; deductive search is top-down, fixing the top of an expression and searching for its sub-expressions.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) Constraint-based (component-based) synthesis encodes the components and their connections as constraints over well-formedness and functionality, calls an SMT solver, and reconstructs the program from the satisfying assignment.[3](https://www.cs.cmu.edu/~aldrich/courses/17-355-18sp/notes/notes13-synthesis.pdf) [Stochastic](https://www.edgepedia.org/stochastic) search and deduction complete the set.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf)\n\nThe correctness guarantee depends on the paradigm: a deductively synthesized program is provably correct by construction, while an inductively synthesized one is only a hypothesis consistent with the examples seen.[8](https://arxiv.org/pdf/2508.00013) Counterexample-guided inductive synthesis (CEGIS) closes this gap by alternating an inductive learner with a verifier that returns counterexamples on which the current candidate fails.[8](https://arxiv.org/pdf/2508.00013)\n\n## How it is done\n\nThe most standardized workflow is syntax-guided synthesis (SyGuS). A problem instance has four parts: a base theory, typed synthesis functions whose bodies are to be synthesized, a per-function grammar constraining the syntax, and a semantic constraint formula that must hold universally.[9](https://sygus-org.github.io/assets/pdf/SyGuS-IF.pdf) The input format is closely modeled on SMT-Lib2, with commands such as (set-logic LIA), (synth-fun ...), (constraint ...), and (check-synth); supported logics include LIA (linear integer arithmetic), BV (bit-vectors), Reals, and Arrays.[9](https://sygus-org.github.io/assets/pdf/SyGuS-IF.pdf)\n\nThe SyGuS paper describes three instantiations of CEGIS: an enumerative technique that generates candidates of increasing size pruned by input-output examples, a symbolic technique that encodes parse trees as constraints for an SMT solver, and stochastic search.[4](https://acg.cis.upenn.edu/papers/fmcad13_sygus.pdf)\n\n## Origin\n\nThe idea of identifying algorithms with proofs was suggested early in constructive mathematics, and automatic synthesis systems appeared shortly after the first theorem provers; pioneer work by C. Green and R. Waldinger followed around 1969.[10](https://www.cs.cornell.edu/info/people/kreitz/PDF/98kluwer-synthesis.pdf) Zohar Manna and Richard J. Waldinger then developed the deductive framework across a series of papers: \"Toward automatic program synthesis\" (Communications of the ACM, 1971),[11](https://doi.org/10.1145/362566.362568) \"Synthesis: Dreams → Programs\" (IEEE Transactions on Software Engineering, 1979),[12](https://doi.org/10.1109/tse.1979.234198) and \"A Deductive Approach to Program Synthesis\" (ACM TOPLAS, 1980), which treats synthesis as theorem proving combining transformation rules, unification, and mathematical induction.[2](https://doi.org/10.1145/357084.357090) They applied the method to the unification algorithm in 1981.[13](https://doi.org/10.21236/ada107328)\n\nThe field was very active until the early 1980s, when approaches failed to scale and activity dropped with the advent of logic programming; large-scale synthesis later became possible with the KIDS system, which came close to a commercial breakthrough.[10](https://www.cs.cornell.edu/info/people/kreitz/PDF/98kluwer-synthesis.pdf) The modern revival began with combinatorial sketching for finite programs (Solar-Lezama and colleagues, 2006),[14](https://doi.org/10.1145/1168917.1168907) and the SyGuS formalization in 2013.[4](https://acg.cis.upenn.edu/papers/fmcad13_sygus.pdf)\n\n## Variants\n\nSketch lets programmers write a partial program that encodes the solution structure while leaving low-level details, specified by a reference implementation or test routines, to the synthesizer; its three distinguishing language features are unknown constants, harnesses, and generator functions.[15](https://people.csail.mit.edu/asolar/papers/Solar-Lezama09.pdf) FlashFill synthesizes string-processing programs from input-output examples (Gulwani, 2011),[16](https://doi.org/10.1145/1925844.1926423) and the FlashMeta/PROSE framework (Polozov and Gulwani, 2015) implements the D4 methodology of data-driven domain-specific deduction, whose primary innovation is witness functions that propagate an example-based specification on a DSL operator down into specifications on its parameters.[5](https://doi.org/10.1145/2858965.2814310) Rosette is a virtual machine for solver-aided programming; together with Sketch and PROSE it counts among the most popular synthesis frameworks.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf)\n\nNeurosymbolic variants pair learning with search. DeepCoder (Balog and colleagues, 2016) trains a neural predictor of program components to accelerate symbolic search.[17](https://doi.org/10.48550/arxiv.1611.01989) SketchAdapt (Nye and colleagues, 2019) uses a learned sketch generator to guide beam search and falls back to fast enumeration for hard-to-recognize parts, learning the division of labor without direct supervision.[18](https://doi.org/10.48550/arxiv.1902.06349) Large language models can also act as direct synthesizers: a 137B-parameter model synthesized solutions to 59.6% of MBPP problems using few-shot learning.[7](https://doi.org/10.48550/arxiv.2108.07732) Hybrids integrate LLM calls into enumerative search: HySynth (Barke and colleagues, 2024) uses a context-free LLM approximation for guiding program synthesis.[19](https://doi.org/10.48550/arxiv.2405.15880)\n\n## Applications\n\nFlashFill shipped as a feature in [Microsoft Excel](https://www.edgepedia.org/microsoft-excel) 2013 and FlashExtract in PowerShell for Windows 10; developing a robust FlashFill prototype took one year, and the Excel product team needed six more months to make it production-ready.[5](https://doi.org/10.1145/2858965.2814310) Over the last decade several programming-by-example systems have been deployed in mass-market industrial products.[1](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf) SyGuS unified a set of prior efforts under one problem format: program sketching, synthesis of loop-free programs, Excel macro synthesis from examples, program de-obfuscation, and super-optimization, the last rooted in Massalin's 1987 superoptimizer for brute-force discovery of minimal instruction sequences.[4](https://acg.cis.upenn.edu/papers/fmcad13_sygus.pdf) • [20](https://doi.org/10.1145/36205.36194)\n\n## Limitations and alternatives\n\nAmbiguity is the main obstacle in programming by examples: a limited set of I/O examples under-specifies the intent, so many consistent programs behave differently on unseen inputs.[8](https://arxiv.org/pdf/2508.00013) Search scales exponentially with program size; synthesizers manage this with minimal, highly constrained DSLs, observational-equivalence pruning, and witness-function deduction.[8](https://arxiv.org/pdf/2508.00013) SyGuS restricts specifications to SMT-expressible theories, limiting domains with arbitrary semantics such as CSS selectors.[5](https://doi.org/10.1145/2858965.2814310) LLMs often fail syntactically, and augmented testing cut pass@k by up to 19.3 to 28.9% across 26 LLMs, with over 10% of original [HumanEval](https://www.edgepedia.org/humaneval) ground-truth solutions themselves incorrectly implemented; pass@k says nothing about code quality, security, or maintainability.[6](https://arxiv.org/html/2603.20264) • [21](https://proceedings.neurips.cc/paper_files/paper/2023/file/43e9d647ccd3e4b7b5baab53f0368686-Paper-Conference.pdf) • [22](https://link.springer.com/article/10.1007/s10489-026-07230-0)\n\nInductive logic programming induces a logic program generalizing examples and background knowledge, with efficient search of a large hypothesis space as its fundamental problem; Popper works in generate-test-constrain stages, and most neural ILP approaches need metarules and fail to support predicate invention, recursion, and abduction.[23](https://link.springer.com/article/10.1007/s10994-021-06089-1) Schema-guided synthesis moves difficult proof obligations offline at schema design time, giving a much smaller search space than deductive synthesis; inductive synthesis from examples risks over-generalization (the universal predicate subsuming all concatenation examples), for which negative examples are a general remedy.[24](https://webperso.info.ucl.ac.be/~yde/Papers/lopstr04.pdf)\n\nHybrid systems now integrate verification and constraints into generation: constraint-guided decoding injects syntactic and semantic constraints into token sampling, ARCHCODE showed that explicit preconditions and postconditions as prompting constraints improve accuracy, and ROCODE integrates backtracking with program analysis.[22](https://link.springer.com/article/10.1007/s10489-026-07230-0) In the SyGuS domain, a hybrid integrating LLM calls into weighted probabilistic enumerative search improves on both cvc5 and GPT-3.5 alone.[6](https://arxiv.org/html/2603.20264) A review of 67 papers on search-based synthesis found such approaches need less training data than LLMs and enforce grammar constraints, but scale poorly and produce less readable code, motivating LLM-plus-search combinations.[25](https://www.mdpi.com/2078-2489/16/5/401) Human natural-language feedback about code halved the error rate of a large model's initial predictions.[7](https://doi.org/10.48550/arxiv.2108.07732)\n\n## References\n\n1. [Program Synthesis (Gulwani, Polozov, Singh, Foundations and Trends in Programming Languages survey, full PDF)](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/program_synthesis_now.pdf)\n2. [Zohar Manna, Richard Waldinger (1980). A Deductive Approach to Program Synthesis. ACM Transactions on Programming Languages and Systems.](https://doi.org/10.1145/357084.357090)\n3. [Lecture Notes: Program Synthesis (CMU 17-355)](https://www.cs.cmu.edu/~aldrich/courses/17-355-18sp/notes/notes13-synthesis.pdf)\n4. [Syntax-Guided Synthesis (Alur et al., FMCAD 2013)](https://acg.cis.upenn.edu/papers/fmcad13_sygus.pdf)\n5. [Oleksandr Polozov, Sumit Gulwani (2015). FlashMeta: a framework for inductive program synthesis. ACM SIGPLAN Notices.](https://doi.org/10.1145/2858965.2814310)\n6. [Can LLMs Perform Synthesis? (LLMs vs. symbolic tools on SyGuS, LTL, TLA+, ACL2s)](https://arxiv.org/html/2603.20264)\n7. [Austin, Jacob and colleagues (2021). Program Synthesis with Large Language Models. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2108.07732)\n8. [Comparative literature review of program synthesis paradigms (arXiv survey, 2025)](https://arxiv.org/pdf/2508.00013)\n9. [Language to Specify Syntax-Guided Synthesis Problems (SyGuS-IF)](https://sygus-org.github.io/assets/pdf/SyGuS-IF.pdf)\n10. [Program synthesis chapter (Kreitz, Kluwer volume, 1998)](https://www.cs.cornell.edu/info/people/kreitz/PDF/98kluwer-synthesis.pdf)\n11. [Zohar Manna, Richard J. Waldinger (1971). Toward automatic program synthesis. Communications of the ACM.](https://doi.org/10.1145/362566.362568)\n12. [Z. Manna, R. Waldinger (1979). Synthesis: Dreams → Programs. IEEE Transactions on Software Engineering.](https://doi.org/10.1109/tse.1979.234198)\n13. [Zohar Manna, Richard Waldinger (1981). Deductive Synthesis of the Unification Algorithm,. .](https://doi.org/10.21236/ada107328)\n14. [Armando Solar-Lezama and colleagues (2006). Combinatorial sketching for finite programs. ACM SIGOPS Operating Systems Review.](https://doi.org/10.1145/1168917.1168907)\n15. [The Sketching Approach to Program Synthesis (Solar-Lezama, MIT)](https://people.csail.mit.edu/asolar/papers/Solar-Lezama09.pdf)\n16. [Sumit Gulwani (2011). Automating string processing in spreadsheets using input-output examples. ACM SIGPLAN Notices.](https://doi.org/10.1145/1925844.1926423)\n17. [Balog, Matej and colleagues (2016). DeepCoder: Learning to Write Programs. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1611.01989)\n18. [Nye, Maxwell and colleagues (2019). Learning to Infer Program Sketches. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1902.06349)\n19. [Barke, Shraddha and colleagues (2024). HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2405.15880)\n20. [Henry Massalin (1987). Superoptimizer: a look at the smallest program. ACM SIGPLAN Notices.](https://doi.org/10.1145/36205.36194)\n21. [Is Your Code Generated by ChatGPT Really Correct? (EvalPlus / HumanEval+, NeurIPS 2023)](https://proceedings.neurips.cc/paper_files/paper/2023/file/43e9d647ccd3e4b7b5baab53f0368686-Paper-Conference.pdf)\n22. [Code generation with large language models: a survey from neural program synthesis to autonomous software development (Applied Intelligence, Springer)](https://link.springer.com/article/10.1007/s10489-026-07230-0)\n23. [Inductive logic programming at 30 (Machine Learning journal)](https://link.springer.com/article/10.1007/s10994-021-06089-1)\n24. [Synthesis of Programs in Computational Logic (LOPSTR 2004)](https://webperso.info.ucl.ac.be/~yde/Papers/lopstr04.pdf)\n25. [Review and Mapping of Search-Based Approaches for Program Synthesis (Information, 2025)](https://www.mdpi.com/2078-2489/16/5/401)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.cmu.edu/~aldrich/courses/17-355-18sp/notes/notes13-synthesis.pdf", "https://www.cs.cornell.edu/info/people/kreitz/PDF/98kluwer-synthesis.pdf" ], "url": "https://www.edgepedia.org/program-synthesis", "markdown_url": "https://www.edgepedia.org/program-synthesis.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Program synthesis\", Edgepedia (EdgeChat), https://www.edgepedia.org/program-synthesis. Edgepedia Community License 1.0.", "credit_md": "\"[Program synthesis](https://www.edgepedia.org/program-synthesis)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/program-synthesis](https://www.edgepedia.org/program-synthesis). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Program synthesis\", Edgepedia (EdgeChat), https://www.edgepedia.org/program-synthesis. Edgepedia Community License 1.0.", "speakable": "Program synthesis is the task of automatically finding a program that satisfies a user's intent given as a specification, long called the holy grail of computer science." }