article

Free access

A Transformation System for Developing Recursive Programs

Authors:

R. M. Burstall,

John DarlingtonAuthors Info & Claims

Journal of the ACM (JACM), Volume 24, Issue 1

Pages 44 - 67

https://doi.org/10.1145/321992.321996

Published: 01 January 1977 Publication History

Abstract

A system of rules for transforming programs is described, with the programs in the form of recursion equations. An initially very simple, lucid, and hopefully correct program is transformed into a more efficient one by altering the recursion structure. Illustrative examples of program transformations are given, and a tentative implementation is described. Alternative structures for programs are shown, and a possible initial phase for an automatic or semiautomatic program-manipulation system is indicated.

References

[1]

AualN, R Some generahsatlon heuristics m proofs by reduction Proc IRIA Symp Proving and Improving Programs, Arc-et-Senans, France, 1975, pp 197-208

[2]

BORER, R S, AND MOORE, JS Proving theorems about LISP functions J ACM 22, 1 (Jan 1975), 129- 144

[3]

CHEATnAM, T E JR, AND WEGBREIT, B A laboratory for the study of automating programming Proc AFIPS 1972 SjCC; Vol 40, AFIPS Press, Montvale, N.J., pp 11-21

[4]

COURCELLE, B, AND VUILLEMIN, J Semantics and axtomattcs of a simple recurswe language Proc Sixth Annual ACM Symp Theory of Comptg, 1974, pp 13-26

[5]

DARLINGTON~ J A semantm approach to automatic program tmprovement Ph D Th, Dep Artif lntel, U of Edinburgh, Edinburgh, 1972

[6]

DARLINGTON, J, AND BURSTALL, R M A system which automatically improves programs Proc Third Int Joint Conf on Artlf Intel, Stanford, Cahf, 1973, pp. 479-485. (To appear m Acta Informattca, 1976.)

[7]

DARLINGTON, J Application of program transformation to program synthesis Proc IRIA Symp Proving and Improving Programs, Arc-et-Senans, France. 1975. pp 133-144

[8]

FLOYD, R.W Algorithm 245, TREESORT 3 Comm ACM 7, 12 (Dec 1964), 701-702

[9]

GERUART, S L Correctness-preserving program transformauons Conf Rec Second Symp Prlnoples of Programming Languages, Palo Alto, Calif, 1975, pp 54-66

[10]

HOARE, C A R Proof of correctness of data representations Acta Informat~ca 1 (1972), 271-278

[11]

KNUTH, D E Structured programming w~th go to statements ACM Computmg Surveys 6, 4 (1974), 261-301

[12]

MANNA, Z., AND WALDINGER, R Knowledge and reasoning m program synthesis Arttf Intel J 6, 2 (1975), 175-208

[13]

Moo~E, JS Introducing Iteration into the pure LISP theorem prover CSL-74-3, Xerox Palo Alto Res Ctr, Palo Alto, Callf, 1975

[14]

PLOTKIN, G Budding in equational theories Machme lntelhgence 7, B Meltzer and D. Michle, Eds, Edinburgh U Press, Edinburgh, 1972, pp 73-90

[15]

ToPoR, R W Interactive program verification using virtual programs Ph D Th, Dep Artff Intel, U of Edinburgh, Edinburgh, 1975

Cited By

Cheng LParreaux L(2024)The Ultimate Conditional SyntaxProceedings of the ACM on Programming Languages10.1145/36897468:OOPSLA2(988-1017)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689746
Chen YParreaux L(2024)The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data StructuresProceedings of the ACM on Programming Languages10.1145/36746348:ICFP(249-283)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674634
Wolfram D(2024)Solving Generalized Fibonacci RecurrencesThe Fibonacci Quarterly10.1080/00150517.1998.1242894836:2(129-145)Online publication date: 25-Sep-2024
https://doi.org/10.1080/00150517.1998.12428948
Show More Cited By

Index Terms

A Transformation System for Developing Recursive Programs
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Recursion
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Program schemes

Recommendations

Some transformations for developing recursive programs
International Conference on Reliable Software

The paper describes a system of rules for transforming programs, the programs being in the form of recursion equations. The idea is to start with a very simple, lucid and hopefully correct program, then to transform it into a more efficient one by ...
Some transformations for developing recursive programs
Proceedings of the international conference on Reliable software

The paper describes a system of rules for transforming programs, the programs being in the form of recursion equations. The idea is to start with a very simple, lucid and hopefully correct program, then to transform it into a more efficient one by ...
Applications of the TAMPR transformation system
IW-FM'98: Proceedings of the 2nd Irish conference on Formal Methods

In this paper we present an overview of the uses of the TAMPR transformation system and present experience with using transformation in industrial applications. TAMPR is a fully automatic, rewrite-rule based program transformation system. From its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 24, Issue 1

Jan. 1977

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321992

Issue’s Table of Contents

Copyright © 1977 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1977

Published in JACM Volume 24, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,206
Total Citations
View Citations
2,031
Total Downloads

Downloads (Last 12 months)266
Downloads (Last 6 weeks)32

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng LParreaux L(2024)The Ultimate Conditional SyntaxProceedings of the ACM on Programming Languages10.1145/36897468:OOPSLA2(988-1017)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689746
Chen YParreaux L(2024)The Long Way to Deforestation: A Type Inference and Elaboration Technique for Removing Intermediate Data StructuresProceedings of the ACM on Programming Languages10.1145/36746348:ICFP(249-283)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674634
Wolfram D(2024)Solving Generalized Fibonacci RecurrencesThe Fibonacci Quarterly10.1080/00150517.1998.1242894836:2(129-145)Online publication date: 25-Sep-2024
https://doi.org/10.1080/00150517.1998.12428948
Faisal Al Ameen MKobayashi NSato R(2024)Asynchronous unfold/fold transformation for fixpoint logicScience of Computer Programming10.1016/j.scico.2023.103014231:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.scico.2023.103014
Farzan ANicolet V(2024)Partial bounding for recursive function synthesisFormal Methods in System Design10.1007/s10703-023-00417-y63:1-3(172-205)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10703-023-00417-y
Barwell ABrown CSarkar S(2024)Towards Specification-Guarded RefactoringLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_9(149-165)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71294-4_9
Bowers MOlausson TWong LGrand GTenenbaum JEllis KSolar-Lezama A(2023)Top-Down Synthesis for Library LearningProceedings of the ACM on Programming Languages10.1145/35712347:POPL(1182-1213)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571234
Yang MZhang D(2023)Deep Reinforcement Learning Guided Decision Tree Learning For Program Synthesis2023 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER56733.2023.00112(925-932)Online publication date: Mar-2023
https://doi.org/10.1109/SANER56733.2023.00112
Fan AGokkaya BHarman MLyubarskiy MSengupta SYoo SZhang J(2023)Large Language Models for Software Engineering: Survey and Open Problems2023 IEEE/ACM International Conference on Software Engineering: Future of Software Engineering (ICSE-FoSE)10.1109/ICSE-FoSE59343.2023.00008(31-53)Online publication date: 14-May-2023
https://doi.org/10.1109/ICSE-FoSE59343.2023.00008
DANVY O(2023)Folding left and right matters: Direct style, accumulators, and continuationsJournal of Functional Programming10.1017/S095679682200015633Online publication date: 14-Feb-2023
https://doi.org/10.1017/S0956796822000156
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents