Constraint based program transformation theory

The FermaT Transformation Engine is an industrial strength toolset for the migration ofAssembler and Cobol based legacy systems to C. It uses an intermediate language and severaldozen mathematical proven transformations to raise the abstraction level of a sourcecode or to restructure and simplify it as needed. The actual program transformation processwith the aid of this toolset is semi-automated which means that a maintainer has notonly to apply one transformation after another but also to evaluate the transformation result.This can be a very difficult task especially if the given program is very large and if alot of transformations have to be applied. Moreover, it cannot be assured that a transformationtarget will be achieved because it relies on the decisions taken by the respectivemaintainer which in turn are based on his personal knowledge. Even a small mistake canlead to a failure of the entire program transformation process which usually causes an extensiveand time consuming backtrack. Furthermore, it is difficult to compare the resultsof different transformation sequences applied on the same program. To put it briefly, themanual approach is inflexible and often hard to use especially for maintainers with littleknowledge about transformation theory.There already exist different approaches to solve these well known problems and tosimplify the accessibility of the FermaT Transformation Engine. One recently presentedapproach is based on a particular prediction technique whereas another is based on varioussearch tactics. Both intend to automatise the program transformation process. However,the approaches solve some problems but not without introducing others. On the one hand,the prediction based approach is very fast but often not able to provide a transformationsequence which achieves the defined program transformation targets. The results dependa lot on the algorithms which analyse the given program and on the knowledge which isavailable to make the right decisions during the program transformation process. On theother hand, the search based approach usually finds suitable results in terms of the giventarget but only in combination with small programs and short transformation sequences.It is simply not possible to perform an extensive search on a large-scale program in reasonabletime.To solve the described problems and to extend the operating range of the FermaTTransformation Engine, this thesis proposes a constraint based program transformationsystem. The approach is semi-automated and provides the possibility to outline an entireprogram transformation process on the basis of constraints and transformation schemes.In this context, a constraint is a condition which has to be satisfied at some point duringthe application of a transformation sequence whereas a transformation scheme defines thesearch space which consists of a set of transformation sequences. After the constraintsand the scheme have been defined, the system uses a unique knowledge-based predictiontechnique followed by a particular search tactic to reduce the number of transformationsequences within the search space and to find a transformation sequence which is applicableand which satisfies the given constraints. Moreover, it is possible to describe thosetransformation schemes with the aid of a formal language.The presented thesis will provide a definition and a classification of constraints forprogram transformations. It will discuss capabilities and effects of transformations andtheir value to define transformation sets. The modelling of program transformation processeswith the aid of transformation schemes which in turn are based on finite automatawill be presented and the inclusion of constraints into these schemes will be explained. Aformal language to describe transformation schemes will be introduced and the automatedconstruction of these schemes from the language will be shown. Furthermore, the thesiswill discuss a unique prediction technique which uses the capabilities of transformations,an evaluation of the transformation sequences on the basis of transformation effects and aparticular search tactic which is related to linear and tree search tactics.The practical value of the presented approach will be proven with the aid of threemedium-scale case studies. The first one will show how to raise the abstraction levelwhereas the second one will show how to decrease the complexity of a particular program.The third one will show how to increase the execution speed of a selected program.Moreover, the work will be summarised and evaluated on the basis of the research questions.Its limitations will be disclosed and some suggestion for future work will be made.