A Transformation System for Developing Recursive Programs
Rod M. Burstall, John Darlington · Journal of the ACM · 1977
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.
Cited by 1,300 works. doi:10.1145/321992.321996 Open-access PDF
Authors
References
- Proof of correctness of data representations
- Structured Programming with go to Statements
- Algorithm 245: Treesort
- Proof of Correctness of Data Representations
- Proving Theorems about LISP Functions
- A system which automatically improves programs
- Knowledge and reasoning in program synthesis
- Correctness-preserving program transformations
- Semantics and axiomatics of a simple recursive language.
- Interactive program verification using virtual programs