A Transformation System for Developing Recursive Programs-英文文献.pdf

A Transformation System for Developing Recursive Programs R. M. BURSTALL AND JOHN DARLINGTON Umversityof Edinburgh, Edinburgh, Scotland ABSTRACT A system of rules for transforming programs is described, with the programs in the form of recurslon equations An imtlally very simple, lucid, and hopefully correct program is transformed into a more efficient one by altering the recurslon 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 mampulatlon system is indicated KEYWORDSANDPHRASES program transformation, program manipulation, optimization, recursion CRCATEGORIES 3 69, 4 12, 4 22, 5 24, 5 25 1. Introduction We present here a system for transforming programs, where the programs are expressed as first order recursion equations. This recursive form seems well adapted to manipula- tion, much more so than the usual Algol-style form of program, and our transformation system consists of just a few simple rules together with a strategy for applying them. Despite their simphcity, these rules produce some interesting changes in the programs. The overall aim of our investigation has been to help people to write correct programs which are easy to alter. To produce such programs it seems advtsable to adopt a l u o d , mathematical, and abstract programming style. If one takes this really seriously, at- tempting to free ones mind from considerations of computational effioency, there may be a heavy penalty in program