The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Program Synthesis
Abstract
Program synthesis is the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in the form of some specification. Since the inception of AI in the 1950s, this problem has been considered the holy grail of Computer Science. Despite inherent challenges in the problem such as ambiguity of user intent and a typically enormous search space of programs, the field of program synthesis has developed many different techniques that enable program synthesis in different real-life application domains. It is now used successfully in software engineering, biological discovery, computer-aided education, end-user programming, and data cleaning. In the last decade, several applications of synthesis in the field of programming by examples have been deployed in mass-market industrial products. This survey is a general overview of the state-of-the-art approaches to program synthesis, its applications, and subfields. We discuss the general principles common to all modern synthesis approaches such as syntactic bias, oracle-guided inductive search, and optimization techniques. We then present a literature review covering the four most common state-of-the-art techniques in program synthesis: enumerative search, constraint solving, stochastic search, and deduction-based programming by examples. We conclude with a brief list of future horizons for the field.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Genetic programming as a means for programming computers by natural selection
Koza, J. (1994) · Statistics and Computing · doi:10.1007/bf00175355 · Cited by 1,685
Muggleton, S. (1991) · New Generation Computing · doi:10.1007/bf03037089 · Cited by 1,044
Toward automatic program synthesis
Manna, Z., & Waldinger, R. J. (1971) · Communications of the ACM · doi:10.1145/362566.362568 · Cited by 285
Meta-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
Meta-interpretive learning: application to grammatical inference
Muggleton, S. H., Lin, D., Pahlavi, N., & Tamaddoni-Nezhad, A. (2014) · Machine Learning · doi:10.1007/s10994-013-5358-3 · Cited by 120
Cited by
Competition-level code generation with AlphaCode
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., et al. (2022) · Science · doi:10.1126/science.abq1158 · Cited by 1,043
Competition-Level Code Generation with AlphaCode
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Lago, A. D., et al. (2022) · arXiv · doi:10.48550/arxiv.2203.07814 · Cited by 1,043
Large language models for software engineering: survey and open problems
Fan, A., Gokkaya, B., Harman, M., Lyubarskiy, M., Sengupta, S., Yoo, S., & Zhang, J. M. (2023) · 2023 IEEE/ACM International Conference on Software Engineering: Future of Software Engineering (ICSE-FoSE) · doi:10.1109/icse-fose59343.2023.00008 · Cited by 650
Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models
Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., et al. (2022) · arXiv · doi:10.48550/arxiv.2206.04615 · Cited by 569
Large Language Models for Software Engineering: Survey and Open Problems
Fan, A., Gokkaya, B., Harman, M., Lyubarskiy, M., Sengupta, S., Yoo, S., & Zhang, J. M. (2023) · arXiv · doi:10.48550/arxiv.2310.03533 · Cited by 523
An Empirical Study of the Non-Determinism of ChatGPT in Code Generation
Ouyang, S., Zhang, J. M., Harman, M., & Wang, M. (2025) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3697010 · Cited by 258
Lau, S., & Guo, P. (2023) · Proceedings of the 2023 ACM Conference on International Computing Education Research V.1 · doi:10.1145/3568813.3600138 · Cited by 241
Fuzz4ALL: Universal Fuzzing with Large Language Models
Xia, C. S., Paltenghi, M., Le Tian, J., Pradel, M., & Zhang, L. (2024) · Proceedings of the IEEE/ACM 46th International Conference on Software Engineering · doi:10.1145/3597503.3639121 · Cited by 229
Big code != big vocabulary: open-vocabulary models for source code
Karampatsis, R.-M., Babii, H., Robbes, R., Sutton, C., & Janes, A. (2020) · Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering · doi:10.1145/3377811.3380342 · Cited by 182
No Need to Lift a Finger Anymore? Assessing the Quality of Code Generation by ChatGPT
Liu, Z., Tang, Y., Luo, X., Zhou, Y., & Zhang, L. F. (2024) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2024.3392499 · Cited by 128
LLM-Based Test-Driven Interactive Code Generation: User Study and Empirical Evaluation
Fakhoury, S., Naik, A., Sakkas, G., Chakraborty, S., & Lahiri, S. K. (2024) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2024.3428972 · Cited by 120
MultiPL-E: A Scalable and Polyglot Approach to Benchmarking Neural Code Generation
Cassano, F., Gouwar, J., Nguyen, D., Nguyen, S., Phipps-Costin, L., Pinckney, D., Yee, M.-H., Zi, Y., Anderson, C. J., Feldman, M. Q., et al. (2023) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2023.3267446 · Cited by 394
Inductive Logic Programming At 30: A New Introduction
Cropper, A., & Dumančić, S. (2022) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.13507 · Cited by 83
Synchromesh: Reliable code generation from pre-trained language models
Poesia, G., Polozov, O., Le, V., Tiwari, A., Soares, G., Meek, C., & Gulwani, S. (2022) · arXiv · doi:10.48550/arxiv.2201.11227 · Cited by 72
Self-citationPaTAT: Human-AI Collaborative Qualitative Coding with Explainable Interactive Rule Synthesis
Gebreegziabher, S. A., Zhang, Z., Tang, X., Meng, Y., Glassman, E. L., & Li, T. J.-J. (2023) · Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3544548.3581352 · Cited by 72
An Empirical Study of Code Smells in Transformer-based Code Generation Techniques
Siddiq, M. L., Majumder, S. H., Mim, M. R., Jajodia, S., & Santos, J. C. S. (2022) · 2022 IEEE 22nd International Working Conference on Source Code Analysis and Manipulation (SCAM) · doi:10.1109/scam55253.2022.00014 · Cited by 70
The future of AI-driven software engineering
Terragni, V., Vella, A., Roop, P., & Blincoe, K. (2025) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3715003 · Cited by 62
Clover: Closed-Loop Verifiable Code Generation
Sun, C., Sheng, Y., Padon, O., & Barrett, C. (2024) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-65112-0_7 · Cited by 43
Towards AI-Assisted Synthesis of Verified Dafny Methods
Misu, M. R. H., Lopes, C. V., Ma, I., & Noble, J. (2024) · Proceedings of the ACM on Software Engineering · doi:10.1145/3643763 · Cited by 38
Benchmark Data Contamination of Large Language Models: A Survey
Xu, C., Guan, S., Greene, D., & Kechadi, M.-T. (2024) · arXiv · doi:10.48550/arxiv.2406.04244 · Cited by 22
Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems
Dalrymple, D. "., Skalse, J., Bengio, Y., Russell, S., Tegmark, M., Seshia, S., Omohundro, S., Szegedy, C., Goldhaber, B., Ammann, N., et al. (2024) · arXiv · doi:10.48550/arxiv.2405.06624 · Cited by 12
Computing Education Research Today
Fincher, S. A., Tenenberg, J., Dorn, B., Hundhausen, C., McCartney, R., & Murphy, L. (2019) · The Cambridge Handbook of Computing Education Research · doi:10.1017/9781108654555.003 · Cited by 7
LILO: Learning Interpretable Libraries by Compressing and Documenting Code
Grand, G., Wong, L., Bowers, M., Olausson, T. X., Liu, M., Tenenbaum, J. B., & Andreas, J. (2023) · arXiv · doi:10.48550/arxiv.2310.19791 · Cited by 2
Zhou, C., Zhang, X., Song, D., Chen, X., Gu, W., Ma, H., Tian, Y., Zhang, M., & Hu, L. (2025) · arXiv · doi:10.48550/arxiv.2502.09183 · Cited by 18
PatchWorld: Gradient-Free Optimization of Executable World Models for Agent Environments
Bai, J., Guo, Y., Dong, Y., Xiong, J., Zheng, T., Li, Y., Fang, T., Li, Y., Gao, Y., Huang, H., et al. (2026) · arXiv · doi:10.48550/arxiv.2605.30880
Agentic Synthesis against Counterexample-Supplemented Sketches
Castle, M., & Rubeck, E. (2026) · arXiv · doi:10.48550/arxiv.2607.15854
Metadata
- Authors
- Gulwani, S., Polozov, O., & Singh, R.
- Venue
- Foundations and Trends in Programming Languages
- Publisher
- Emerald
- Published
- 2017-07-11
- Volume
- 4
- Issue
- 1-2
- Pages
- 1-119
- ISSN
- 2325-1107 (ISSN-L)
- 2325-1131
- OpenAlex
- W4229675450
- Cited by
- 319
- References
- 5
- FWCI
- 17.38
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
