article

Free access

The automatic synthesis of recursive programs

Authors:

Zohar Manna,

Richard WaldingerAuthors Info & Claims

ACM SIGPLAN Notices, Volume 12, Issue 8

Pages 29 - 36

https://doi.org/10.1145/872734.806929

Published: 01 August 1977 Publication History

PDF eReader

Abstract

We describe a deductive technique for the automatic construction of recursive programs to meet given input-output specifications. These specifications express what conditions the output of the desired program is expected to satisfy. The deductive technique involves transforming the specifications by a collection of rules, summoned by pattern-directed function invocation. Some of these transformation rules express the semantics of the subject domain; others represent more general programming techniques. The rules that introduce conditional expressions and recursive calls into the program are discussed in some detail.

The deductive techniques described are embedded in a running system called SYNSYS. This system accepts specifications expressed in high-level descriptive language and attempts to transform them into a corresponding LISP program. The transformation rules are expressed in the QLISP programming language. The synthesis of two programs performed by the system are presented.

This research was supported in part by the Advanced Research Projects Agency of the Department of Defense under Contract MDA903-76-C-0206, by the National Science Foundation under Grant DCR72-03737 A01, by the Office of Naval Research under Contracts N00014-76-C-0687 and N00014-75-C-0816; and by a grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.

The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of Stanford University, Stanford Research Institute, or the U.S. Government.

References

[1]

Barstow, D. R. and E. Kant {Oct. 1976},Observations on the interaction between coding and efficiency knowledge in the PSI program synthesis system, Proceedings of the Second International Conference on Software Engineering, San Francisco, Ca., pp. 19-31.

Digital Library

Google Scholar

[2]

Biedsoe, W. W., and M. Tyson {1977},Typing and proof by cases in program verification, in Machine Intelligence 8: Machine Representations of Knowledge, (E. W. Elcock and D. Michie, editors), Ellis Horwood, Edinburgh, Scotland (to appear).

Google Scholar

[3]

Boyer, R. S., and J S. Moore {Jan. 1975},Proving theorems about LISP functions, JACM, Vol. 22, No. 1, pp. 129-144.

Digital Library

Google Scholar

[4]

Burstall, R. M. and J. Darlington {April 1975},Some transformations for developing recursive programs, Proceedings of the International Conference on Reliable Software, Los Angeles, Ca., pp. 465-472.

Digital Library

Google Scholar

[5]

Darlington, J. {July 1975},Applications of program transformation to program synthesis, Colloques IRIA on Proving and Improving Programs, Arc et Senans, France, pp. 133-144.

Google Scholar

[6]

Dijkstra, E. W. {1976},A discipline of programming, Prentice-Hall, Englewood Cliffs, N. J.

Digital Library

Google Scholar

[7]

Manna, Z. and R. Waldinger {1975},Knowledge and reasoning in program synthesis, Artificial Intelligence, Vol. 6, No. 2, pp. 175-208.

Crossref

Google Scholar

[8]

Siklossy, L. {1974},The synthesis of programs from their properties, and the insane heuristic, Proceedings of the Third Texas Conference on Computing Systems, Austin, Texas.

Google Scholar

[9]

Waldinger, R. J. {1977},Achieveing several goals simultaneously, in Machine Intelligence 8: Machine Representations of Knowledge, (E. W. Elcock and D. Michie, editors), Ellis Horwood, Edinburgh, Scotland (to appear).

Google Scholar

[10]

Warren, D. H. D. {July 1976},Generating conditional plans and programs, Proceedings of Conference on Artificial Intelligence and Simulation on Behaviour, Edinburgh, Scotland, pp. 344-354.

Google Scholar

[11]

Wegbreit, B {Sept. 1975},Goal-directed program transformation, Research report, Xerox Research Center, Palo Alto, Ca.

Google Scholar

[12]

Wilber, B. M . {Mar. 1976},A QLISP reference manual, Technical note, Stanford Research Institute, Menlo Park, Ca.

Google Scholar

[13]

Wirth, N. {1976},Algorithms + data structures &equil; programs, Prentice-Hall Inc., Englewood Cliffs, N.J.

Digital Library

Google Scholar

Cited By

View all

Novikov FNovoseltsev V(2010)Interpretable program specification languageProgramming and Computing Software10.1134/S036176881001007X36:1(48-57)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1134/S036176881001007X
Green CBarstow D(1986)On Program Synthesis Knowledge**This research was supported in part by the Advanced Research Projects Agency under ARPA Order 2494, Contract MDA903–76–C–0206, and in part by the National Science Foundation under NSF Grant MCS 77–05740. A major portion of the work described herein was done while the authors were in the Computer Science Department of Stanford University. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of Stanford University, Yale University, Systems Control Inc. or the U.S. Government.Readings in Artificial Intelligence and Software Engineering10.1016/B978-0-934613-12-5.50039-2(455-474)Online publication date: 1986
https://doi.org/10.1016/B978-0-934613-12-5.50039-2
Nepeivoda N(1984)Semantics of algorithmic languagesJournal of Soviet Mathematics10.1007/BF0110165125:6(1558-1606)Online publication date: Jun-1984
https://doi.org/10.1007/BF01101651
Show More Cited By

Index Terms

The automatic synthesis of recursive programs

Recommendations

The automatic synthesis of recursive programs
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

We describe a deductive technique for the automatic construction of recursive programs to meet given input-output specifications. These specifications express what conditions the output of the desired program is expected to satisfy. The deductive ...
The automatic synthesis of recursive programs
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

We describe a deductive technique for the automatic construction of recursive programs to meet given input-output specifications. These specifications express what conditions the output of the desired program is expected to satisfy. The deductive ...
The automatic synthesis of systems of recursive programs
IJCAI'77: Proceedings of the 5th international joint conference on Artificial intelligence - Volume 1

A technique is presented for constructing, a program from given specifications. The basic approach is to transform the specifications repeatedly, according to certain rules, until the desired program is produced. Two important transformation rules are ...

Comments

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 12, Issue 8

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

August 1977

179 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/872734

Issue’s Table of Contents

Proceedings of the 1977 symposium on Artificial intelligence and programming languages
August 1977
185 pages
ISBN:9781450378741
DOI:10.1145/800228
Chairman:
James Low

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1977

Published in SIGPLAN Volume 12, Issue 8

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)20

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Novikov FNovoseltsev V(2010)Interpretable program specification languageProgramming and Computing Software10.1134/S036176881001007X36:1(48-57)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1134/S036176881001007X
Green CBarstow D(1986)On Program Synthesis Knowledge**This research was supported in part by the Advanced Research Projects Agency under ARPA Order 2494, Contract MDA903–76–C–0206, and in part by the National Science Foundation under NSF Grant MCS 77–05740. A major portion of the work described herein was done while the authors were in the Computer Science Department of Stanford University. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of Stanford University, Yale University, Systems Control Inc. or the U.S. Government.Readings in Artificial Intelligence and Software Engineering10.1016/B978-0-934613-12-5.50039-2(455-474)Online publication date: 1986
https://doi.org/10.1016/B978-0-934613-12-5.50039-2
Nepeivoda N(1984)Semantics of algorithmic languagesJournal of Soviet Mathematics10.1007/BF0110165125:6(1558-1606)Online publication date: Jun-1984
https://doi.org/10.1007/BF01101651
Sato T(2005)An equivalence preserving first order unfold/fold transformation systemAlgebraic and Logic Programming10.1007/3-540-53162-9_38(173-188)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-53162-9_38
Hogger C(2005)Goal-oriented derivation of logic programsMathematical Foundations of Computer Science 197810.1007/3-540-08921-7_74(267-276)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08921-7_74
Partsch HSteinbrüggen R(1983)Program Transformation SystemsACM Computing Surveys10.1145/356914.35691715:3(199-236)Online publication date: 1-Sep-1983
https://dl.acm.org/doi/10.1145/356914.356917
Basu S(1980)A Note on Synthesis of Inductive AssertionsIEEE Transactions on Software Engineering10.1109/TSE.1980.2304606:1(32-39)Online publication date: 1-Jan-1980
https://dl.acm.org/doi/10.1109/TSE.1980.230460
(1978)BIBLIOGRAPHYPattern-Directed Inference Systems10.1016/B978-0-12-737550-2.50036-1(603-646)Online publication date: 1978
https://doi.org/10.1016/B978-0-12-737550-2.50036-1
Ulrich JMoll R(1977)Program synthesis by analogyACM SIGART Bulletin10.1145/872736.806928(22-28)Online publication date: 1-Aug-1977
https://dl.acm.org/doi/10.1145/872736.806928
Ulrich JMoll R(1977)Program synthesis by analogyACM SIGPLAN Notices10.1145/872734.80692812:8(22-28)Online publication date: 1-Aug-1977
https://dl.acm.org/doi/10.1145/872734.806928
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations