Transformation Project

The final assignment for the program transformation course is a little research project in which you have to implement a transformation in Stratego with teams of two students.

Study the following projects and discuss with Eelco Visser about an appropriate project for you.

Study the literature to find out what transformation is required.

Final product:

• working implementation (for identified subset if necessary)
• paper documenting the transformation and solution
• presentation

Language Embedding

Embedding of XQuery/XPath/XSLT in Java

Create an embedding (ala MetaBorg? ) of one or all of these languages in Java and develop an assimilation to plain Java.

Resources:

• http://www.w3.org/TR/xquery/
• http://www.w3.org/TR/xpath
• http://www.w3.org/TR/xslt

Refactoring

Strategies for device driver evolution

Encode changes to device driver code as a strategy. Model the problem in Tiger (based on slides and paper), and come up with ways to define the transformations in Stratego.

Resources:

• Tarantula: Killing Driver Bugs Before They Hatch. Julia L. Lawall, Gilles Muller and Richard Urunuela. http://aosd.net/2005/workshops/acp4is/crc/lawall.pdf
• Slides (ask me)

Java Refactoring

Refactoring is a transformation to improve the design of a program. Implement several refactorings for Java in Stratego using java-front. Include at least Extract Method.

Resources:

• http://www.refactoring.com/
• http://c2.com/cgi/wiki?WikiPagesAboutRefactoring

Note: Refactoring is really an interactive process that requires to a region in the code. To emulate this you can extend the syntax of Java to indicate the selected region.

Desugaring / Weaving

Lifting Inner Classes in Java

Implement a transformation that lifts inner classes to top-level. This requires that any local variables visible in the lifted inner class is passed on to the constructor of the lifted class.

Resources:

• Lambda-Lifting in Quadratic Time http://danae.uni-muenster.de/lehre/kuchen/JFLP/articles/2004/A2004-01/JFLP-A2004-01.pdf

• Pizza papers: http://pizzacompiler.sourceforge.net/doc/papers.html

AspectJ

Implement a (subset of) AspectJ? aspect weaving.

Reousces:

• AspectOrientedProgramming

AspectTiger

Create an extension of Tiger with aspects (a la AspectJ? ) and Implement aspect weaving as a preprocessor.

Reousces:

• AspectOrientedProgramming

Optimizations

Simplification of conditional expressions

Develop a simplifier for pure Tiger expressions including arithmetic and relational operators and if-then-else. Simplify by constant folding and other appropriate laws. The challenge is to take into account the Boolean expressions in the condition of the if-then-else. For example, in the expression 'if x = 0 then e1 else e2', the expression e1 can be optimized knowing that x equals 0 and e2 can be transforming knowing the negation of that expression. Consider equalities, inequalities, conjunctions and disjunctions. Extend this with common-subexpression elimination as described in the paper by De Moor and Secher.

Resources:

• Bernd Fischer (NASA/Ames)

• O. de Moor and J. P. Secher. Common subexpression elimination of conditional expressions, 2001. Submitted to TOPLAS. http://web.comlab.ox.ac.uk/oucl/work/oege.de.moor/papers/d2l.ps.gz

Partial evaluation with records and arrays (alias analysis)

Extend Tiger partial evaluator to cope with records and arrays.

Resources:

• M. Bravenboer, A. van Dam, K. Olmos, and E. Visser. Program Transformation with Scoped Dynamic Rewrite Rules. Fundamenta Informaticae, 2005. Section 8 defines a simple online partial evaluator that forms the basis of your partial evaluator.
• PartialEvaluators

Inlining and tail call and tail recursion elimination

Extend your Tiger compiler with these optimizations at different stages in compilation.

Resources:

• http://c2.com/cgi/wiki?TailCallOptimization