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
Part 1: Staged Transformations: Sequence of Normal Forms
In Section 7.6 the idiom of `staged cascading transformations' is
described as a sequence of innermost normalizations:
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.
In this part of the assignment, we assume the following subset of
regular tree grammar
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
Write a set of rewrite rules for achieving the polynomial reordering
described in section 7.4, for Tiger expressions. Thus, the Tiger
(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
(y ** 2 + y + 20) * x ** 2 + (2 * y ** 2 + 18) * x + (y ** 2 + 9 * y + 18)
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
- Regular tree grammar for our Tiger
- A subdirectory
checks which contains some simple and one more
advanced test. The expected output is in
to run the checks. You must extend the test suite yourself.
The Stratego module
already contains an entry-point,
the main strategies and some basic rewrite rules. Use the command
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
which represents the name of the variable to be factored
explains how you should invoke your tool by hand, if
you want to. You can also enter
to apply the tool to
. 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
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
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
- 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
or a power of
?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
factor-of(|x); Snd; ?Int(<string-to-int>) <+ !0
This strategy uses
, which disects an expression of the
*(e, **(x, i))
into the coefficient
Times(e, Power(Var(x), Int(i))) -> (e, Int(i))
Times(e, Var(x)) -> (e, Int("1"))
Power(Var(x), Int(i)) -> (Int("1"), Int(i))
Var(x) -> (Int("1"), Int("1"))
Now, you can test whether the exponent of expressions
than the exponent of expression
<gt> (<exponent-of(|x)> e2, <exponent-of(|x)> e1)
The actual out-factoring can reuse the
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
Create a module
. Implement strategies for the following type-unifying strategies and implement some tests using
. We use the full Tiger language in this exercise.
- Count the number of function declarations in a Tiger program.
- Compute the sum of all numbers in a tree.
- Collect all variables uses nodes (
- 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.
- Collect all outermost (aka topmost) function calls.
- Collect all free variables in a Tiger expression (including function variables and left-hand sides of assignments)
- Collect all undefined functions