Assignment Staged Transformations And Type Unifying Strategies

This assignment consists of two parts. First, you will implement a staged transformations that achieves polynomial reordering. This is a continuation of the previous assignment. Second, you will practice with the type-unifying strategies by implementing some small exercises.

Part 1: Staged Transformations: Sequence of Normal Forms

Resources

In Section 7.6 the idiom of `staged cascading transformations' is described as a sequence of innermost normalizations:

  simplify = 
    innermost(A1 + ... + Ak)
    ; innermost(B1 + ... + Bl)
    ; ...
    ; innermost(C1 + ... + Cm)

This idiom is applied in 'sequence of canonical forms' transformation style of TAMPR described in Section 7.4. Read this section first.

Tiger Subset

In this part of the assignment, we assume the following subset of Tiger:

regular tree grammar
  start Exp
  productions
    Exp -> Int(<string>)
    Exp -> Var(<string>)

    Exp -> Plus(Exp,Exp)
    Exp -> Times(Exp,Exp)
    Exp -> Power(Exp,Exp)

Notice that we do not consider the UMinus and Minus constructs.

Assignment

Write a set of rewrite rules for achieving the polynomial reordering described in section 7.4, for Tiger expressions. Thus, the Tiger polynomial in y

(x**2 + 2 * x + 1) * y**2 + (x**2 + 9) * y + (20*x**2 + 18*x + 18)

should be turned into the following polynomial in x:

(y ** 2 + y + 20) * x ** 2 + (2 * y ** 2 + 18) * x + (y ** 2 + 9 * y + 18)

Transformation Setup

Download the tar.gz template for this assignment and unpack it in a fresh directory (tar zxvf template-sa5.tar.gz). The tarball contains:

• Makefile for compiling the transformation and applying checks
• Template Stratego module factorout.str
• Regular tree grammar for our Tiger Subset.rtg
• Tiger.rtree
• A subdirectory checks which contains some simple and one more

advanced test. The expected output is in *.exp files. Use make check to run the checks. You must extend the test suite yourself.

The Stratego module factorout.str already contains an entry-point, the main strategies and some basic rewrite rules. Use the command make to compile the module. This program should be extended with appropriate sets of rewrite rules.

Note that some of the definitions are parameterized with a term argument x which represents the name of the variable to be factored out.

The Makefile explains how you should invoke your tool by hand, if you want to. You can also enter make test.fou to apply the tool to test.tig. In the Makefile, you can change the verbosity to 2 if you want see intermediate results.

Part 1: Helper Strategies and Tips

This section gives some tips and helper strategies. It sketches how you can implement this part of the assignment, but it is not a complete specification of everything that you have to do. You have to find this out by yourself by adding new tests and thinking about the transformations.

Sum of Monomonials

In this transformation you have to do several important things. Note that you have already done some of this in the ANF assignment.

• First of all, you have to push Times down (or, in other words: lift Plus)
• Commute constants to the left
• Let all expressions associate in the same way
• Decompose more complex Power applications. You can use the following test for that:

  is-atomic = Var(id) + Int(id)

Make sure that this stage works reasonably before you continue. The following stages might be more complicated (or even impossible) if this phase doesn't work very well.

Commute Factors Right

In this part, you have to move all the factors to the right of each multiplication series. Check that your implementation works for multiplications of three or more expressions!

You can use the following test, which determines whether an expression is x or a power of x.

  is-factor(|x) =
    ?Var(x) + ?Power(Var(x), Int(_))

Collect by Power

Collecting multiplications by power can be done by sorting them. The following strategy can be used to determine the exponent of a multiplication:

  exponent-of(|x) =
    factor-of(|x); Snd; ?Int(<string-to-int>) <+ !0

This strategy uses factor-of, which disects an expression of the general form *(e, **(x, i)) into the coefficient e and the exponent i.

  factor-of(|x) :
    Times(e, Power(Var(x), Int(i))) -> (e, Int(i))

  factor-of(|x) :
    Times(e, Var(x)) -> (e, Int("1"))

  factor-of(|x) :
    Power(Var(x), Int(i)) -> (Int("1"), Int(i))

  factor-of(|x) :
    Var(x) -> (Int("1"), Int("1"))   

Now, you can test whether the exponent of expressions e2 is greater than the exponent of expression e1 as follows:

<gt> (<exponent-of(|x)> e2, <exponent-of(|x)> e1)

Factor Out

The actual out-factoring can reuse the factor-of that was given in the previous section. Rewrite adjacent multiplications if the exponent of both expressions is equivalent. Also, evaluate the constant expressions that this might produce. Some basic laws can make the result more attractive.

Part 2: Type Unifying Strategies

Resources

• Section 10.4: Type Unifying Strategies
• API Documentation of the Stratego Library. See module collect.

Assignment

Create a module type-unify-tests.str. Implement strategies for the following type-unifying strategies and implement some tests using sunit. We use the full Tiger language in this exercise.

1. Count the number of function declarations in a Tiger program.
2. Compute the sum of all numbers in a tree.
3. Collect all variables uses nodes (Var(_)).
4. Collect all variables uses, but not those on the left-hand side of assignments (i.e x := y + 1 should only return y) and not those that identify a function in a function call (e.g. f in f()).
5. Collect all outermost (aka topmost) function calls.
6. Collect all free variables in a Tiger expression (including function variables and left-hand sides of assignments)
7. Collect all undefined functions