Assignment Traversals

Pt04
%TOC%

The purpose of this assignment is to understand how traversal
strategies work. The assignment consists of two parts. In the first
part, you will implement some small exercises using congruences and
generic traversals. In the second part, you will define a format
checker and implementation of a transformation to a normal form.

---++ More Stratego

---+++ Using the Stratego Library

From now, you are allowed to use the Stratego Library. The library
contains many useful strategies for io, list processing, traversals,
and so
on. [[http://catamaran.labs.cs.uu.nl/dist/stratego/stratego-lib-docs-9033/docs/][API and source documentation]] of the Stratego Library is available
online.

---+++ Stratego Unit

In this exercise, you will define test suites in the Stratego Unit
(=sunit=) unit testing framework. The Stratego/XT manual explains how
to use =sunit= to define test suites:
[[http://catamaran.labs.cs.uu.nl/dist/stratego/strategoxt-manual-unstable-latest/manual/stratego-unit-testing.html][Unit Testing with SUnit]].

---+++ Stratego Compiler and Interpreter

You have already used the Stratego Shell extensively during the
previous assignment. The Stratego Shell is an interface to the
Stratego Interpreter. In this assignment, you will use an alternative
front-end, =stri=, which allows you to execute modules with a certain
entry point (=main= by default). Invocation of =stri= will be
explained later. You can still use the Stratego Shell to experiment
with the language and your solutions.

Stratego modules can also be compiled using the Stratego Compiler:

<verbatim>
$ strc -i module.str
</verbatim>

The resulting program will be _much_ faster than the interpreter, but
the compilation itself takes some time. However, for larger examples
in the =innermost= assignment, this additional compilation time is
well spent.

---++ (A) Small Traversals

---+++ File Instructions

   * Define your solutions in a Stratego module =cong-traversal.str=.

   * Define a test suite in the Stratego module
     =traversal-tests.str=. Parameterize all test cases with the
     actual implementation of the strategy. This is important to make
     your test suite reusable for the generic traversal exercise.

   * Apply your test suite to the =cong-traversal= strategies in the
     Stratego module =cong-traversal-tests.str=.

For your convenience, we provide skeletons for the various files:

cong-traversal.str
<verbatim>
module cong-traversal
imports Tiger
strategies

  foo = id
</verbatim>

cong-traversal-tests.str
<verbatim>
module cong-traversal-tests
imports
  cong-traversal
  traversal-tests
  Tiger
  sunit

strategies

  main =
    test-suite(!"Congruence traversal tests",
      foo-test(foo)
    )
</verbatim>

traversal-tests.str
<verbatim>
module traversal-tests
imports
  Tiger
  sunit

strategies

  foo-test(s) =
    apply-test(!"Identity test", s, !Int("2"), !Int("3"))
</verbatim>

You can now run the test suite using =stri. =stri= executes the =main=
strategy of a specified Stratego module. 

<verbatim>
$ stri cong-traversal-tests.str
test suite: Congruence traversal tests
Identify test
  result not equal : Int("2")
  expected         : Int("3")
successes: 0
failures: 1
stri: rewriting failed
</verbatim>

Running a Stratego module =foo.str= with =stri= is equivalent to
entering the following commands in the Stratego Shell:

<verbatim>
stratego> import foo
stratego> main
</verbatim>

---+++ Tiger Subset

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

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

    Exp -> Uminus(Exp)
    Exp -> Plus(Exp,Exp)
    Exp -> Times(Exp,Exp)
</verbatim>

---+++ (A.1) Congruence Exercises

For each item in the list below you should write:

   * a strategy definition in =cong-traversal.str= 
   * a few parameterized tests in =traversal-tests.str=
   * applications of these tests in =cong-traversal-tests.str=

You are not allowed to use generic traversals. All traversing code
must be implemented using congruences. The tests should demonstrate
the working of the strategy and of course you can use them to test
your solution by running the test suite.

Tip: it is useful to define reusable primitives for traversing the
Tiger subset (i.e. =one-Tiger=, =some-Tiger=, =all-Tiger=, etc).

   1. Replace all =Var("x")= by =Int("3")=.

   1. Replace all =Var("x")= by =Int(x)=, where =x= is a given integer
      (i.e. parameterize the strategy of the previous exercise).

   1. Replace all multiplications by 2 (i.e. =e*2= or =2*e=) by an
      addition (i.e. =e+e=).

   1. Replace all outermost additions by multiplications (yes, this
      entirely meaningless). An outermost term is the first term from
      the root. For example, in =B(A(A(1)))= the outermost =A= is
      =A(A(1))=.

   1. Replace all innermost additions by multiplications. An innermost
      term is the first term from the leaves. In the previous example,
      the innermost =A= is =A(1)=.

---+++ (A.2) Generic Traversal Exercises

Now, create the modules =generic-traversal.str= and
=generic-traversal-tests.str=. Repeat the previous exercise, this time
using generic traversals. The traversals should be as generic as
allowed by the description: your solutions should support the full
Tiger language. Invoke all the tests you developed in the previous
exercise and add some more tests for the full Tiger language to the
=generic-traversal-tests.str= module.

---++ (B) Additive Normal Form

---+++ (B.1) Format Checking

A format checker is a `transformation' which checks the format of a
term. For instance, the =TAS-Format= component of the Tiger compiler
checks if a term is a well-formed Tiger abstract syntax tree. Format
checkers can be defined nicely using congruence operators. See the
[[https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/tiger-front/tas/TAS-Format.str][source]]
of the =TAS-Format= component.

Define a format checker that checks if a Tiger expression is in
_additive normal form_ (ANF). This means that the expression only
consists of additions of multiplications. Also, the only place where a
constant integer is allowed, is at the first point of the
multiplication and as the last addition. In other words, an expression
in ANF has the form =a * x + b * y + ... + c=, where =a=, =b=, and =c=
are integer constants and =x= and =y= are variables. Multiple
variables are allowed in a single multiplication and the same
variable is allowed to occur in more then one multiplication.

For example, the ANF of 
<verbatim>
4 + (x + 5) * 2 + 3 * y * 5 * z + x
</verbatim>

is

<verbatim>
2 * x + 15 * y * z + x + 14
</verbatim>

Define a format checker strategy in a Stratego module =anf-format.str=
that checks that an expression is in ANF form. The strategy should
fail if an expression is not in ANF.

---+++ (B.2) Innermost Normalization

In this part of the assignment you will implement the transformation
that achieves the ANF. Use the ANF format checker to test more complex
examples and test smaller examples by explicitly mentioning the
expected outcome.

Extend the following skeleton of a Stratego Module with rewrite rules
that achieve the transformation of an expression in our Tiger subset
mentioned before to ANF. You are not allowed to do any traversal
related stuff in the rewrite rules. The skeleton defines a =main=
strategy that handles input and output.

<verbatim>
module anf
imports
  fixpoint-traversal
  options
  Tiger

strategies

  main = 
    io-wrap(anf)

  anf =
    innermost(fail /* Invoke your rules here */ )
</verbatim>

Use =stri= to run the tool:

<verbatim>
echo 'Int("1")' | stri anf.str
</verbatim>

or, for a Tiger file in concrete syntax:

<verbatim>
parse-tiger -i foo.tig | stri anf.str
</verbatim>

Of course, you implement a test suite for your =anf= transformation
(for example in module called =anf-tests.str=).

---++ Submission

Pack your Stratego modules in a =.tar.gz= or =.zip= file and send your
solution by email to =martin@cs.uu.nl= at least 15 minutes before the
lecture of Tuesday, i.e. 8:45. The same day, you will get a short
notification that I've received your solution. If you don't get this
reply, then please contact me.

---+++ Questions

After the lab session you can still send questions to =pt@cs.uu.nl= or
join [[irc://irc.freenode.com/#stratego][#stratego]] at
=irc.freenode.com=.