Program transformation entails modifying programs. Many software engineering tasks can be achieved by automatically
transforming programs (or specifications, or documents). There are many different ways in which programs can be transformed. Whole research and user communities form around special kinds of program transformations, e.g., compiler optimizations, reverse engineering, aspect-oriented programming, to name a few.
First I give an impression of the reach of program transformation by means of a Taxonomy of Program Transformation. Then I focus on one specific kind of transformation, namely Partial Evaluation. Finally, we look at the application of Term Rewriting to program transformation.
The slides of the lectures
- IST-PT3.pdf: Partial Evaluation: Binding Time Annotation & Spec
Some introductory articles on these topics
- PE-Ch1.ps: Chapter 1 of Partial Evaluation book
Starting points for further exploration
A -- Transformation Taxonomy
you can find a demonstration of the application of various program transformations on Tiger programs. You can choose programs from a list, and apply transformations to the selected program. You will then get the result of the transformation besided the original program.
The transformations have been named
For this assignment you should find out what the transformations do. The transformations correspond to one of the transformations listed below. Your answer should
to one of the transformations listed below, and briefly describe what the transformation achieves. You can illustrate this using fragments from programs, but you should try to describe the transformation in a more general manner.
- Bound Variable Renaming
- Canonical (side-effect) free expressions
- Escaping Variables Analysis
- Function Inlining
- Running Compiled Program
- Tail Recursion Elimination
- Trace Instrumentation
- Translation to Intermediate Representation
B -- Partial Evaluation
Create a reasonable binding time annotation for the rewrite functions in the program explained in the lecture and specialize the function to a small rewrite system (for example the rewrite system consisting of two rules in the program).
- trs.tig: Implementation of term rewriting in Tiger
C -- Term Rewriting
Give a term rewrite system (set of rewrite rules) to simplify arithmetic expressions to additive normal form, that is expressions should get the
c1 * x1 * ... * xn + c2 * y1 * ... * yn + .... + cn * z1 * ... * zn
c=s are constants and the =xi
Some examples of rewrite rules that you may find useful are:
[[ x + 0 ]] -> [[ x ]]
[[ (x + y) * z ]] -> [[ (x * z) + (y * z) ]]
- 26 Sep 2002