On Program Transformations

In understanding complex algorithms, the notions of encapsulation and modularization have played a key role. An algorithm is broken into several parts or modules, and understanding of each part is independent of others. In addition, each part contains details that are not needed by other parts and so can be hidden from them. Programming languages provide support for encapsulation and modularization in many different forms. Early programming languages provided the procedure and function as a means for modularization. Later, files were introduced as a means of modularizing programs. More sophisticated mechanisms were then introduced, like modules, packages, structures, and classes. In all these cases, the interface to a module remained the procedure or function call. Programs that use such modules contain calls to functions and procedures for communicating with a module. Ideally, using the operations that are provided by a module should be done in exactly the same way as using operations that are provided by modules should be easy to intermix. In addition, substituting one module for another that has the same functionality but different implementation should involve a minimal amount of effort. Recently, a new programming language, Polya, has been designed, which attempts to support modularization and at the same time incorporate the operations that are provided by the modules in the programming language itself. This is done by a sophisticated type-definition facility and a mechanism for transforming programs at the source-program level. This thesis studies mechanisms for program transformation at the source program level, in the context of Polya. Program transformation is based on a set of transformation rules that prescribe how a part of a program is to be transformed, and a set of directives that prescribe which program variables are to be transformed. We first give an algorithm for processing program transformations as described by the transform construct. The algorithm constructs a coordinate transformation of an abstract program based on a set of transforms and transform directives for transforming program variables. We then study the problem of transforming expressions that have compound types. Both the type constructor and the component expressions of the original expression may be transformed. No extra rules need be added to the bodies of transforms that transform the type constructor and the component expressions. In the sequel we investigate the problem of transforming procedures and functions that have parameters that need to be transformed. Finally, the problem of transforming program-transformation rules is studied. The program transformation techniques are applied to two well-known algorithms. The algorithms are source programs, which are subsequently transformed to programs of conventional programming languages, and then compiled and run