Topic
Implement a program transformation
Description
For a given language of your choice, implement either a program optimization or a program refactoring which requires some non-trivial program analysis. You can use a concrete or an abstract syntax. That is, you can skip parsing, if you like because this is no longer of interest. You may want to use concrete syntax though because it may simplify your testing challenge.
Please make a proposal within the first week of the assignment by sending an email to softlang@uni-koblenz. Your proposal is either confirmed (if it is clear and original), or rejected (if it is an insult or you had about the same idea as in some previously received proposal), or conditionally accepted (subject to processing some feedback and resubmitting the proposal for confirmation).
Illustrative options
- Let's opt for the Factorial Language (FL) which was discussed in the lecture on refactoring. Let's implement a refactoring for extracting a function from a focus subexpression. Such a transformation requires indeed a non-trivial analysis because a) the name for the new function must be checked not to be in use and b) the free names in the focused subexpression need to be determined so that they can be turned into parameters of the extracted function and are appropriately passed as arguments via the function application that replaces the focused subexpression. Note: you may need to expand FL a little to have enough expressiveness for somewhat interesting refactoring examples.
- Let's opt for a simple imperative language with expressiveness for structured programming on ints and Booleans and arrays. Implement some optimization of loop fusion, which can, for example, optimize the following example:
Original program:
// Test code for filling array a is omitted.
int s = 0;
int p = 1;
for (i=0; i<a.length; i++)
s += a[i];
for (j=0; j<a.length; j++)
p *= a[j];
Optimized program:
// Test code for filling array a is omitted.
int s = 0;
int p = 1;
for (i=0; i<a.length; i++) {
s += a[i];
p *= a[i];
}
Technology options
- Rascal
- LLVM (with focus on analysis)
- Stratego/XT et al.
- TXL
- Kiama
- JastAdd (if rewrites are used)
- ANTLR (if tree grammars are used)
- Haskell (if Strafunski or SYB is used)
General logistics
See the course page for deadlines and conditions on successfully completing the assignments.