Viewing a Program Transformation System at Work

How to decrease labor and improve reliability in the development of efficient implementations of nonnumerical algorithms and labor intensive software is an increasingly important problem as the demand for computer technology shifts from easier applications to more complex algorithmic ones; e.g., optimizing compilers for supercomputers, intricate data structures to implement efficient solutions to operations research problems, search and analysis algorithms in genetic engineering, complex software tools for workstations, design automation, etc. It is also a difficult problem that is not solved by current CASE tools and software management disciplines, which are oriented towards data processing and other applications, where the implementation and a prediction of its resource utilization follow more directly from the specification. Recently, Cai and Paige reported experiments suggesting a way to implement nonnumerical algorithms in C at a programming rate (i.e., source lines per second) that is at least five times greater than a conventional approach in which C programs are written entirely by hand [12]. The runtime performance of the C programs produced by this new approach was shown to be comparable to good hand code. The proposed software development methodology makes use of fully automatic, generic program transformations that capture algorithm design principles. This paper discusses some of the ideas underlying the transformational methodology, and illustrates these ideas through explanatory examples of the APTS system at work