Program Transformation

Ist

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

   * [[%ATTACHURL%/IST-PT1.pdf][IST-PT1.pdf]]: A Taxonomy of Program Transformation

   * [[%ATTACHURL%/IST-PT2.pdf][IST-PT2.pdf]]: Partial Evaluation

   * [[%ATTACHURL%/IST-PT3.pdf][IST-PT3.pdf]]: Partial Evaluation: Binding Time Annotation & Spec

   * [[%ATTACHURL%/IST-PT4.pdf][IST-PT4.pdf]]: Program Transformation by Term Rewriting

Some introductory articles on these topics

   * [[http://www.dina.dk/~sestoft/pebook/pebook.html][Partial Evaluation and Automatic Program Generation]] -- N.D. Jones, C.K. Gomard, and P. Sestoft

      * [[%ATTACHURL%/PE-Ch1.ps][PE-Ch1.ps]]: Chapter 1 of Partial Evaluation book

   * [[http://www.cse.ogi.edu/~sheard/papers/challengesInMetaProg.ps][Accomplishments and Research Challenges in Meta-Programming]] by [[http://www.cse.ogi.edu/~sheard/][Tim Sheard]]

   * [[http://www.stratego-language.org/twiki/bin/view/Stratego/BuildingProgramOptimizersWithRewritingStrategies][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).

   * [[%ATTACHURL%/trs.tig][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
<verbatim>
   c1 * x1 * ... * xn +  c2 * y1 * ... * yn + .... + cn * z1 * ... * zn 
</verbatim>
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:
<verbatim>
   PlusZero : 
      [[ x + 0 ]] -> [[ x ]]
   Distribution :
      [[ (x + y) * z ]] -> [[ (x * z) + (y * z) ]]
</verbatim>

-- Main.EelcoVisser - 26 Sep 2002

Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
pdf	IST-PT1.pdf	manage	146.4 K	27 Sep 2002 - 15:20	EelcoVisser	A Taxonomy of Program Transformation
pdf	IST-PT2.pdf	manage	142.0 K	27 Sep 2002 - 15:21	EelcoVisser	Partial Evaluation
pdf	IST-PT3.pdf	manage	208.6 K	27 Sep 2002 - 15:22	EelcoVisser	Partial Evaluation: Binding Time Annotation & Spec
pdf	IST-PT4.pdf	manage	76.3 K	27 Sep 2002 - 15:29	EelcoVisser	Program Transformation by Term Rewriting
ps	PE-Ch1.ps	manage	436.2 K	26 Sep 2002 - 04:03	EelcoVisser	Chapter 1 of Partial Evaluation book
tig	trs.tig	manage	4.0 K	27 Sep 2002 - 15:52	EelcoVisser	Implementation of term rewriting in Tiger