Program Transformation

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.

Reading

The slides of the lectures

• IST-PT1.pdf: A Taxonomy of Program Transformation

• IST-PT2.pdf: Partial Evaluation

• IST-PT3.pdf: Partial Evaluation: Binding Time Annotation & Spec

• IST-PT4.pdf: Program Transformation by Term Rewriting

Some introductory articles on these topics

• Partial Evaluation and Automatic Program Generation -- N.D. Jones, C.K. Gomard, and P. Sestoft

• • PE-Ch1.ps: Chapter 1 of Partial Evaluation book

• Accomplishments and Research Challenges in Meta-Programming by Tim Sheard

• Building Program Optimizers with Rewriting Strategies -- Eelco Visser

Starting points for further exploration

• http://www.program-transformation.org: web site surveying program transformation

• http://www.stratego-language.org: home page of Stratego, a language for program transformation

Assignment

A -- Transformation Taxonomy

At http://losser.st-lab.cs.uu.nl/~visser/cgi-bin/transform-demo 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 Transformation A, Transformation B, etc.

For this assignment you should find out what the transformations do. The transformations correspond to one of the transformations listed below. Your answer should link each Transformation X 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
• Compilation
• Desugaring
• Escaping Variables Analysis
• Function Inlining
• Interpreting
• Pretty-printing
• Running Compiled Program
• Tail Recursion Elimination
• Trace Instrumentation
• Translation to Intermediate Representation
• Typechecking

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 form

   c1 * x1 * ... * xn +  c2 * y1 * ... * yn + .... + cn * z1 * ... * zn 

where the c=s are constants and the =xi, yi, and zi are variables. Some examples of rewrite rules that you may find useful are:

   PlusZero : 
      [[ x + 0 ]] -> [[ x ]]
   Distribution :
      [[ (x + y) * z ]] -> [[ (x * z) + (y * z) ]]

-- EelcoVisser - 26 Sep 2002