Toward automatic program synthesis
Zohar Manna, Richard J. Waldinger · Communications of the ACM · 1971
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.
Cited by 284 works. doi:10.1145/362566.362568 Open-access PDF
Authors
References
- A Machine-Oriented Logic Based on the Resolution Principle
- An Introduction to Mathematical Logic
- Assigning meanings to programs
- Experiments with a Heuristic Compiler
- A Basis for a Mathematical Theory of Computation )
- APPLICATION OF THEOREM PROVING TO PROBLEM SOLVING**This research is a part of Project Defender and was supported by the Advanced Research Projects Agency of the Department of Defense and was monitored by Rome Air Development Center under Contracts AF 30(602)-4147 and F30602-69-C-0056.††This preprint is a preliminary version and is subject to modification prior to publication.
- Towards a Mathematical Science of Computation
- Proving Properties of Programs by Structural Induction
- The use of theorem-proving techniques in question-answering systems
- Experiments with a deductive question-answering program