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
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
STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving
Fikes, R. E., & Nilsson, N. J. (1971) · Artificial Intelligence · doi:10.1016/0004-3702(71)90010-5 · Cited by 4,882
Evaluating Large Language Models Trained on Code
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. D. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021) · arXiv · doi:10.48550/arxiv.2107.03374 · Cited by 1,436
“More recently, language models have also fueled progress towards the longstanding challenge of program synthesis (Simon, 1963; Manna & Waldinger, 1971), spurred by the presence of code in large datasets (Husain et al., 2019; Gao et al., 2020) and the resulting programming capabilities of language…”
BackgroundCompetition-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
Structured Programming with go to Statements
Knuth, D. E. (1974) · ACM Computing Surveys · doi:10.1145/356635.356640 · Cited by 678
Combinatorial sketching for finite programs
Solar-Lezama, A., Tancau, L., Bodík, R., Seshia, S., & Saraswat, V. (2006) · ASPLOS XII · doi:10.1145/1168857.1168907 · Cited by 922
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
