Lab Assignments

The lab work for the course is divided in two parts. In the first part you learn the basic techniques of program transformation with rewriting strategies (3 weeks). In the second part you apply these techniques in the construction of a partial evaluator for Tiger programs (4 weeks). The assignments are done using the Stratego program transformation language, see CourseSoftware.

Assignment 1 (Week 2 - 4)

Deadline: Tuesday, January 28, 2003

This series of exercises is designed to explore various program transformation techniques. The results should be handed in together.

The following package provides a skeleton for the exercises.

• progtrans-a-0.1.tar.gz

The package should be handed in in the same format after changing the package name to your login. The package should be built using following commands

• ./configure --prefix=`pwd` --with-xt=/usr --with-tiger=/usr
• make
• make check

Specifications of the each part will be provided on this page.

Simplifying Expresssions

• simple syntax definition
• derive signature
• derive pretty-printer
• write simplification rules using innermost
• set-up simple transformation pipeline using Makefile

• Specification

Concrete Syntax

• reimplement the transformation rules using concrete syntax
• staged simplification of arithmetic expressions using simple strategies

Understanding Strategies

• write a number of small (traversal) strategies

• Specification

Composing Transformation Systems

• Profiler: write a transformation that instruments Tiger programs with code to measure the performance (call frequency) of programs.

• Specification

Assignment 2 (Week 5 - 8)

Deadline: Monday, February 24, 2003

Write a partial evaluator for Tiger programs.

Restrictions

The following restrictions are imposed on Tiger programs:

• no arrays
• no assignments to record fields

Case Study

The target for the partial evaluator is the specialization of the intepreter of term rewrite systems trs.tig. The partial evaluator should be able to specialize this interpreter to any rewrite system.

Constant Record Propagation

• extend the constant propagation with propagation of constant records.

• Specification

Copy Propagation

• extend the constant propagation with propagation of variables and records with variables.

• Specification

Unfolding Function Calls

• extend the the copy propagation transformation with unfolding of function calls

• Specification