Assignment In Control Of Rewriting

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)