## Assignment

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)
```

Use this idiom to implement the 'sequence of canonical forms' transformation style of TAMPR described in Section 7.4. In particular, write a set of rewrite rules for achieving the polynomial reordering described in that section, 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

This should be achieved by means of the following program:

```------------------------------------------------
module factorout
imports lib Tiger
strategies

main =
io-wrap(factorout-options,
factorout(|<get-config>"--factor")
)

factorout-options =
ArgOption("--factor"
, <set-config>("--factor", <id>)
,"--factor")

factorout(|x) =
sum-of-monomonials
; commute-right(|x)
; collect-by-power(|x)
; factor-out(|x)

sum-of-monomonials =
innermost(RulesA)

commute-right(|x) =
innermost(RulesB)

collect-by-power(|x) =
innermost(RulesC)

factor-out(|x) =
innermost(RulesD)
------------------------------------------------
```

This program should be extended with appropriate sets of rewrite rules for `RulesA` to `RulesD`.

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

Use concrete syntax to define the rewrite rules.

### Applying the transformation

The transformation should be applied in the following pipeline (add slashes at the end of the lines):
```  parse-tiger -i \$<
| Tiger-Desugar
| Tiger-Rename
| ./factorout --factor x
| TAS-Format
| Tiger-Ensugar
| pp-tiger -o \$@
```

It should be possible to select a different variable to factor out.

### Submission

Submit the following files

• Makefile
• factout.str : the transformation program
• polynomial%.tig : Tiger expressions to test the transformation
• polynomial%.exp : expected outputs

The makefile should implement the following targets

• factorout : compilation of the program
• %.fou : applies transformation to a Tiger program
• clean
• check : checks transformation for several example expressions

## Tips

### Levels of Complexity

As usual it is not necessary to submit a complete solution, but the more cases your transformation can handle, the higher your grade. Make sure your transformation is always correct.

Write a set of example Tiger expressions with growing complexity. Only try to deal with the next level if you can completely deal with the previous level.

• Expressions of the form
```  (a * x**b + ...) * y**c + ...
```
That is only expressions with explicit coefficients

• Expressions without coefficients, e.g., `x**b` or `2*x` or `x`

• Expressions with subtraction

• Expressions with arbitrary (constant) exponentiation
```  (x ** 2 + 2 * x + 1) ** 2
```

### Rules with Term Arguments

Rewrite rules can be parameterized with term arguments. In this way you can specify a transformation only for specific terms. For instance, the following rule commutes an addition if the left-argument is the argument `x`:
```  L(|x) : |[ +(x, e) ]| -> |[ +(e, x) ]|
```

Due to a problem in the compiler you should compile with optimization turned off, i.e.,
```  strc -O 0
```

### Useful tests

The following tests can be used in conditions of rules:

```strategies
atomic      = Var(id) + Int(id) + Real(id) + String(id)
commutative = PLUS + MUL
associative = PLUS + MUL
```

The `commutative` and `associative` tests allow you to write more generic transformation rules that apply to all commutative (associative) operators.

Recall: an operator bo is associative if
```   bo(e1, bo(e2, e3)) = bo(bo(e1, e2), e3)
```
and commutative if
```   bo(e1, e2) = bo(e2, e1)
```

### Is it a factor?

The following test determines whether an expression is `x` or a power of `x`.

```  is-factor(|x) = ?|[ x ]| + ?|[ **(x, i) ]|
```

### Factor of

Disect an expression of the general form *(e, **(x, i)) into the coefficient `e` and the exponent `i`.

```  factor-of(|x) : |[ *(e, **(x, i)) ]| -> (|[ e ]|, |[ i ]|)
factor-of(|x) : |[ *(e, x) ]|        -> (|[ e ]|, |[ 1 ]|)
factor-of(|x) : |[ **(x, i) ]|       -> (|[ 1 ]|, |[ i ]|)
factor-of(|x) : |[ x ]|              -> (|[ 1 ]|, |[ 1 ]|)
```

### Exponent of

The following strategy produces the exponent in `x` of an expression:

```  exponent-of(|x) = factor-of(|x); Snd; ?Int(<id>) <+ !"0"
```

Then you can test whether the exponent of expressions `e2` is greater than the exponent of expression `e1` as follows:
```  <gtS>(<exponent-of(|x)> e2, <exponent-of(|x)> e1)
```

Topic revision: r4 - 27 Nov 2007, UnknownUser
PT Course

Lab

Contact

Center for ST

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UUCS? Send feedback