PT Course

Center for ST

Center

Page

Web

Wiki

# Assignment Staged Transformations And Type Unifying Strategies

Pt04

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

### 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