System for developing programs by transformation

Abstract

Much of the difficulty of programming can be attributed to the clash between the goal of efficiency and other desirable goals, such as clarity, reliability and modifiability. This thesis proposes program transformation as a suitable methodology for program development to circumvent this difficulty.

Following this methodology, a program is developed by first writing a simple straightforws. rd solution to the problem, unhampered by efficiency considerations. Efficiency is then introduced in a separate step by transforming the simple solution.

In order that this be a practical methodology, transformation of large programs must be possible to perform reliably and easily This thesis presents an implemented machine-based transformation system which attempts to realise these needs.

The system is based on a concise and powerful transformation method due to Burstall and Darlington. The emphasis of the system is on making it easy for the user to control the system through a transformation. Guidance is expressed in a command language, so that commands may be saved and re-run, modified, or viewed as documentation together with the initial program.

The level at which guidance is given is higher that the low-level underlying manipulations. Techniques for organising the transformation of large programs at even higher levels are presented. Some non trivial programs and their transformation as achieved using the system illustrate these features.