The DOI matches its Crossref record; 23 of the 24 references it cites were found in a registry or an index.
Toward automatic program synthesis
Open accessAbstract
An elementary outline of the theorem-proving approach to automatic program synthesis is given, without dwelling on technical details. The method is illustrated by the automatic construction of both recursive and iterative programs operating on natural numbers, lists, and trees. In order to construct a program satisfying certain specifications, a theorem induced by those specifications is proved, and the desired program is extracted from the proof. The same technique is applied to transform recursively defined functions into iterative programs, frequently with a major gain in efficiency. It is emphasized that in order to construct a program with loops or with recursion, the principle of mathematical induction must be applied. The relation between the version of the induction rule used and the form of the program constructed is explored in some detail.
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.
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?
The cited source says what the claim attributes to it.
In the citing paper
“Using user-specified constraints, program synthesis (or source code generation) automatically generates source code in a programming language (Waldinger et al. 1969; Manna and Waldinger 1971).”
From Large language models (LLMs): survey, technical frameworks, and future challenges (2024) · cites this paper as Manna and Waldinger 1971
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
A Machine-Oriented Logic Based on the Resolution Principle
Robinson, J. A. (1965) · Journal of the ACM · doi:10.1145/321250.321253 · Cited by 4,012
An Introduction to Mathematical Logic
Mendelson, E. (2005) · A K Peters/CRC Press eBooks · doi:10.1201/b13782-17 · Cited by 1,739
Assigning meanings to programs
Floyd, R. W. (1967) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/019/0235771 · Cited by 1,411
A Basis for a Mathematical Theory of Computation )
Mccarthy, J. (1963) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(08)72018-4 · Cited by 695
Towards a Mathematical Science of Computation
McCarthy, J. (1993) · Studies in cognitive systems · doi:10.1007/978-94-011-1793-7_2 · Cited by 529
Green, C. (1981) · Elsevier eBooks · doi:10.1016/b978-0-934613-03-3.50019-2 · Cited by 459
Proving Properties of Programs by Structural Induction
Burstall, R. M. (1969) · The Computer Journal · doi:10.1093/comjnl/12.1.41 · Cited by 326
Application of Theorem Proving to Problem Solving
Green, C. (1969) · doi:10.21236/ada459656 · Cited by 290
King, J. C. (1970) · IFIP Congress · Cited by 208
Introduction to Mathematical Logic.
Evans, T. V., & Mendelson, E. (1966) · American Mathematical Monthly · doi:10.2307/2313586 · Cited by 187
Flagged first, then by citations
1 of the 24 references couldn’t be matched to a known paper.
Research works printed but not linked: 8
- Brice , C. , and Derksen , J . A heuristically guided equality rule in a resolution theorem prover. Tech. Note 45 , Stanford Res. Inst. , Artificial Intelligence Group , Menlo Park , Calif. Brice, C., and Derksen, J. A heuristically guided equality rule in a resolution theorem prover. Tech. Note 45, Stanford Res. Inst., Artificial Intelligence Group, Menlo Park, Calif.
- Burstall , R. M Formal description of program structure and semantics in first-order logic . In Machine Intelligence 5 , Meltzer and Michie, Eds., Edinburgh U. Press , Edinburgh , 1970 , pp. 79 - 98 . ----. Formal description of program structure and semantics in first-order logic. In Machine Intelligence 5, Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, 1970, pp. 79-98.
- Hayes , P. J. A machine-oriented formulation of the extended functional calculus. Memo 62, Stanford Artificial Intelligence Proj., Stanford U., Stanford , Calif. , 1969 . Also appeared as Metamathematics Unit Report, U. of Edinburgh, Scotland. Hayes, P. J. A machine-oriented formulation of the extended functional calculus. Memo 62, Stanford Artificial Intelligence Proj., Stanford U., Stanford, Calif., 1969. Also appeared as Metamathematics Unit Report, U. of Edinburgh, Scotland.
- Manna , Z Properties of programs and partial function logic . In Machine Intelligence 5 , Meltzer and Michie, Eds., Edinburgh U. Press , Edinburgh , 1970 , pp. 79 - 98 . ----, and McCarthy, J. Properties of programs and partial function logic. In Machine Intelligence 5, Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, 1970, pp. 79-98.
- McCarthy , J. Predicate calculus with "undefined" as a truth-value. Memo 1 , Stanford Artificial Intelligence Proj. Stanford U. , 1963 . ----. Predicate calculus with "undefined" as a truth-value. Memo 1, Stanford Artificial Intelligence Proj. Stanford U., 1963.
- Park , D. Fixpoint induction and proofs of program properties . In Machine Intelligence 5 . Meltzer and Michie, Eds., Edinburgh U. Press , Edinburgh , pp. 59 - 78 . Park, D. Fixpoint induction and proofs of program properties. In Machine Intelligence 5. Meltzer and Michie, Eds., Edinburgh U. Press, Edinburgh, pp. 59-78.
- Patterson , M. S. and Hewitt , C. E . Comparative Schematology, Part 1. Artificial Intel. Memo No. 201 , Mrr , 1970 . Patterson, M. S. and Hewitt, C. E. Comparative Schematology, Part 1. Artificial Intel. Memo No. 201, Mrr, 1970.
- Scott , D. A type-theoretical alternative to CUCH , ISWlM, OWHY. Unpublished memo , 1969 . Scott, D. A type-theoretical alternative to CUCH, ISWlM, OWHY. Unpublished memo, 1969.
Cited by
Sorted by citations
Items 201–285 of 285
Special Issue on Syntax-Guided Synthesis Preface
Fisman, D., Singh, R., & Solar-Lezama, A. (2021) · Formal Methods in System Design · doi:10.1007/s10703-021-00386-0 · Cited by 2
Constructive Mathematics and Computer-Assisted Reasoning Systems
Hayashi, S. (1990) · Springer eBooks · doi:10.1007/978-1-4613-0609-2_4 · Cited by 2
Kátai, Z., & Iclănzan, D. (2025) · Acta Universitatis Sapientiae Informatica · doi:10.47745/ausi-2024-0014 · Cited by 1
Automatic Synthesis of Specialized Hash Functions
Hoffmann, R. B., Faé, L. G., Griebler, D., Li, X. D., & Pereira, F. M. Q. (2025) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3696443.3708940 · Cited by 1
Miura, K., Akama, K., Mabuchi, H., Koike, H., & Miura, K. (2013) · Institutional Repositories DataBase (IRDB) · Cited by 1
Fischer-Heselhaus, S., & Brüne, P. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-52426-4_14 · Cited by 1
Program Synthesis and Natural Language Processing: A Systematic Literature Review
Ramírez-Rueda, R., Benítez–Guerrero, E., Mezura-Godoy, C., & Bárcenas, E. (2023) · International Conference in Software Engineering Research and Innovation (CONISOFT) · doi:10.1109/conisoft58849.2023.00042 · Cited by 1
On Principles of Software Engineering – Role of the Inductive Inference
Samuelis, L. (2012) · Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu · doi:10.5277/e-inf120106 · Cited by 1
Khan, S. M. U., & He, W. (2018) · The International Journal of Advanced Manufacturing Technology · doi:10.1007/s00170-018-2089-4 · Cited by 1
NL2Code: A Corpus and Semantic Parser for Natural Language to Code
Ettifouri, E. H., Dahhane, W., Berrajaa, A., Bouchentouf, T., & Rahmoun, M. (2020) · Lecture notes in electrical engineering · doi:10.1007/978-3-030-53187-4_65 · Cited by 1
PASTA: Synthesizing Object State Transformers for Dynamic Software Updates
Zhao, Z., Jiang, Y., Xu, C., Gu, T., & Ma, X. (2021) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1109/icse-companion52605.2021.00094 · Cited by 1
Extraktion und Verifikation von Programmen durch Analyse formaler Beweise
Alexi, W. (1986) · Informatik-Fachberichte · doi:10.1007/978-3-642-71145-9_11 · Cited by 1
Rule-based Methodologies for the Specification and Analysis of Complex Computing Systems
Baggi, M. (2010) · doi:10.4995/thesis/10251/8964 · Cited by 1
Konsistenzprüfung der Wissensbasis des Medizinischen Expertensystems Cadiag-1
Barachini, F., & Adlassnig, K.-P. (1985) · Informatik-Fachberichte · doi:10.1007/978-3-642-70639-4_73 · Cited by 1
Barachini, F., & Adlassnig, K.-P. (1985) · Informatik-Fachberichte · doi:10.1007/978-3-642-46552-9_1 · Cited by 1
Program synthesis based on Boyer-Moore theorem proving techniques
Yong-qiang, S., Lu, R., & Bi, H. (1985) · ACM Annual Conference on Computer Science (CSC) · doi:10.1145/320599.320709 · Cited by 1
Theory of computing in computer science education
Fischer, P. C. (1971) · AFIPS Fall Joint Computer Conference (FJCC) · doi:10.1145/1478873.1478986 · Cited by 1
Automatic Programming of Finite State Linear Programs
Pnueli, A., & Slutzki, G. (1981) · SIAM Journal on Computing · doi:10.1137/0210038 · Cited by 1
Nilsson, N. J. (1984) · doi:10.1609/aimag.v5i1.424 · Cited by 1
Deductive Synthesis and Repair
Kneuss, E. (2016) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-6878 · Cited by 1
Knowledge and reasoning in program synthesis
Manna, Z., & Waldinger, R. J. (1975) · International Joint Conference on Artificial Intelligence · Cited by 1
Self-citationStructured programming and automatic program synthesis
Lee, R. C. T., & Chang, S. K. (1974) · ACM SIGPLAN Notices · doi:10.1145/942572.807046 · Cited by 1
Complete Program Synthesis for Linear Arithmetic
Mayer, M. (2010) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 1
Application of proof theory to the problem of construction of correct programs
Николаевич, Н. Н. (1979) · Cybernetics · doi:10.1007/bf01069330 · Cited by 1
Extracting Information from Logical Proofs
Mayoh, B. H. (1974) · Springer eBooks · doi:10.1007/978-94-010-2191-3_6 · Cited by 1
Concurrency in proof normalization and logic programming
Goto, S. (1985)
A method for program synthesis
Szöts, M., & Csizmazia, S. (1982) · Lecture notes in computer science · doi:10.1007/3-540-11494-7_24
LA LÓGICA EN LAS CIENCIAS COMPUTACIONALES
Édgar Serna, M. (2013) · Revista Educación en Ingeniería · doi:10.26507/rei.v8n15.233
A strategy for automatically generating programs in the lucid programming language
Johnson, S. C. (1987) · NASA Technical Reports Server (NASA)
The Evolution of Procedural Knowledge
Miller, M. L. (1975) · DSpace@MIT (Massachusetts Institute of Technology)
Deriving Programs that Develop Programs
Kreitz, C. (2001)
Bemerkungen zum Modellbegriff und zur Realisierung von Modellen
Schmidt, J. W. (1974) · Lecture notes in computer science · doi:10.1007/3-540-06907-0_73
Dérivation de programmes impératifs à partir de spécifications algébriques
Guerte, Y. (1996) · HAL
A Proof-Theoretic Account of Primitive Recursion and Primitive Iteration
Chiarabini, L., & Olivier Danvy, A. (2011) · DOAJ (DOAJ: Directory of Open Access Journals) · doi:10.6092/issn.1972-5787/2225
A new approach to program verification
Sinha, B. P., & Srimani, P. K. (1984) · Computers & Electrical Engineering · doi:10.1016/0045-7906(84)90009-0
Extraction of a program from deduction and its regularity. I
Tauts, A. (1985) · Cybernetics and Systems Analysis · doi:10.1007/bf01075120
Correia, A. R. S., Iyoda, J., & Silva, C. T. L. L. (2014) · International Journal in Foundations of Computer Science & Technology · doi:10.5121/ijfcst.2014.4302
Towards the formal description of operating systems
Neuhold, E. J. (1973) · ACM SIGPLAN Notices · doi:10.1145/390014.808299
On the way to practical program synthesis
Tyugu, �. K. (1977) · Cybernetics and Systems Analysis · doi:10.1007/bf01070417
Proof normalization with nonstandard objects
Goto, S. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90186-6
On pattern recognition and description using many sorted predicate calculi
Glanc, A. (1973) · ACM Annual Conference · doi:10.1145/800192.805792
Automatic theorem proving based on resolution
Pirotte, A. (1973) · Annual Review in Automatic Programming · doi:10.1016/0066-4138(73)90001-3
Automatic insertion of indexing instructions in program synthesis
Biermann, A. W. (1978) · International Journal of Parallel Programming · doi:10.1007/bf00991940
Deductive Question Answering, Problem Solving, and Program Synthesis
Chang, C.-L., & LEE, R. C.-T. (1973) · Elsevier eBooks · doi:10.1016/b978-0-08-091728-3.50016-3
Effective testing for concurrency bugs
da Fonseca, S. (2015) · Publications of the UdS (Saarland University) · doi:10.22028/d291-26605
Automatical synthesis of programs with recursions
Beltiukov, A. P. (2006) · Springer eBooks · doi:10.1007/bfb0039723
On transformation of logic specifications into procedural programs
Lin, J., Juang, J., & Yau, S. S. (2003) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/tai.1989.65331
A THEORETICAL FOUNDATION OF A PROGRAMMING BY EXAMPLES
Haraguchi, M. (1979) · Memoirs of the Faculty of Science Kyushu University Series A Mathematics · doi:10.2206/kyushumfs.33.237
Formal program developments directed by operational properties evaluation
Aït‐Ameur, Y. (2003) · Proceedings/Proceedings of the ... International Conference on Software Engineering and Knowledge Engineering · doi:10.1109/seke.1992.227955
Ballis, D., Baggi, M., & Falaschi, M. (2010)
Programming Layout by Manipulation
Hottelier, T. (2014) · eScholarship (California Digital Library)
From Decision Procedures to Synthesis Procedures
Piskač, R. (2015) · International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) · doi:10.1109/synasc.2015.78
Drachsler-Cohen, D., & Yahav, E. (2017)
Constructing Programs from Example -el
Krishnaswamy, R. (1976)
Automatic program synthesis via synthesis of loop-free segments
Duran, J. W. (1979) · International Workshop on Managing Requirements Knowledge (MARK) · doi:10.1109/mark.1979.8817062
Human-Neural Net Collaborative Programming
Zhou, P., Wu, Y., & Zhao, C. (2020) · Asia Service Sciences and Software Engineering Conference (ASSE) · doi:10.1145/3399871.3399882
Formal Fields: A Framework to Automate Code Generation Across DomainsPreprint
Basaldúa, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.14075
Abstraction, Generalization, and Embodiment in Neural Program Synthesis
Shin, E. C. R. (2020) · eScholarship (California Digital Library)
Synthesis of layout engines from relational constraints
Hottelier, T., & Bodík, R. (2015) · ACM SIGPLAN Notices · doi:10.1145/2858965.2814291
Code Generation with Hybrid of Structural and Semantic Features Retrieval
Yang, K., Yu, H., Fan, G., Huang, Z., & Zhou, Z. (2022) · International Journal of Software Engineering and Knowledge Engineering · doi:10.1142/s0218194022500267
(1993) · Elsevier eBooks · doi:10.1016/b978-0-08-036214-4.50025-7
A knowledge-based code generator generator
Fraser, C. W. (1977) · ACM SIGPLAN Notices · doi:10.1145/872734.806941
(1973) · Elsevier eBooks · doi:10.1016/b978-0-08-091728-3.50020-5
Automatic Theorem Proving Based on Resolution
PIROTTE, A. (1974) · International Tracts in Computer Science and Technology and Their Application · doi:10.1016/b978-0-08-017806-6.50009-2
Bauer, M. (1986) · Elsevier eBooks · doi:10.1016/b978-0-934613-12-5.50029-x
(1986) · Elsevier eBooks · doi:10.1016/b978-0-934613-12-5.50050-1
O Computador para o Século 21: Desafios de Segurança e Privacidade após 25 Anos
de Oliveira, L. W., Pereira, F. M. B., Misoczki, R., Aranha, D. F., Borges, F., Nogueira, M., & Wangham, M. S. (2017) · doi:10.5753/sbc.8410.6.1
Program synthesis algorithm based on context consistency heuristic
Dou, Q., Pan, H., Tang, H., Jiang, P., & Wang, H. (2023) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-023-01925-3
Code Generation Based on Quality-Aware Reordering
Yuan, S., & Yu, L. (2024) · International Conference on Intelligent Computing and Signal Processing (ICSP) · doi:10.1109/icsp62122.2024.10743331
de Diego, Á. G., & Wotawa, F. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-80889-0_5
Processor Verification by Equivalent Program Execution
Klemmer, L., & Grosse, D. J. (2025) · Springer eBooks · doi:10.1007/978-3-031-83093-8_3
Le, H., Nguyen, P., Do, H., Nguyen, T., Pham, T., Nguyen-Duc, A., & Quan, T. (2026) · Array · doi:10.1016/j.array.2026.101137
Advances in Reinforcement Learning for Intelligent Program Synthesis
Zhang, J., & Gu, B. (2025) · International Conference on Neural Networks, Information and Communication Engineering (NNICE) · doi:10.1109/nnice64954.2025.11064548
A Little Help Goes a Long Way: Tutoring LLMs in Solving Competitive Programming Through Hints
Zhang, Y., Dong, W., Liu, J., Wang, S., Wang, D., Ma, T., Li, Y., & Yang, K. (2025) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2025.3614204
Synthesis Benchmarks for Automated Reasoning
Hajdú, M., Hozzová, P., Kovács, L., Воронков, А., Wagner, E. M., & Žilinčík, R. S. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-07021-0_2
Nogueira, R. P., Vieira, M. P. A., & Campos, J. R. (2025) · Proceedings/Proceedings - International Symposium on Software Reliability Engineering · doi:10.1109/issre66568.2025.00036
Sinking the Bloat in Genetic Programming Using Equality Saturation
Miranda, L., Fernandes, M. C., Francesquini, E., & de França, F. O. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-23005-8_9
Kátai, Z., & Iclănzan, D. (2026) · Acta Universitatis Sapientiae Informatica · doi:10.1007/s44427-026-00033-8
GP and LLMs for Program Synthesis: No Clear Winners
Hernandez, J. G., Saini, A. K., Ketron, G., & Moore, J. H. (2026) · Genetic and evolutionary computation · doi:10.1007/978-981-95-6398-2_9 · Cited by 1
Matsutani, Y., Nitta, Y., & Sugimoto, M. (2026) · ACM Transactions on Interactive Intelligent Systems · doi:10.1145/3845606
Zabaleta, E., Santana, R., & Lozano, J. A. (2026) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec69861.2026.11727322
Comfusy: A Tool for Complete Functional Synthesis Tool Presentation
Kunčak, V., Mayer, M., & Piskač, R. (2010)
Computer Program Fault Detection and Correction.
Margolis, S. L. (1972)
Metadata
- Authors
- Manna, Z., & Waldinger, R. J.
- Affiliations
- Stanford University (US)
- SRI International (US)
- Venue
- Communications of the ACM
- Published
- 1971-03
- Volume
- 14
- Issue
- 3
- Pages
- 151-165
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2037237472
- Cited by
- 285
- References
- 24
- Citations by year
- 2026: 7 · 2025: 17 · 2024: 10 · 2023: 12 · 2022: 5 · 2021: 12 · 2020: 14 · 2019: 8 · 2018: 9 · 2017: 11 · 2016: 5 · 2015: 6 · 2014: 9 · 2013: 12 · 2012: 7
- FWCI
- 21.08
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- program synthesis, theorem proving, mathematical induction, recursive programs, iterative programs, program transformation, specification-based synthesis, lists, trees, natural numbers
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