Assignment Traversals

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. 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: 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:

$ strc -i module.str

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

module cong-traversal
imports Tiger
strategies

  foo = id

cong-traversal-tests.str

module cong-traversal-tests
imports
  cong-traversal
  traversal-tests
  Tiger
  sunit

strategies

  main =
    test-suite(!"Congruence traversal tests",
      foo-test(foo)
    )

traversal-tests.str

module traversal-tests
imports
  Tiger
  sunit

strategies

  foo-test(s) =
    apply-test(!"Identity test", s, !Int("2"), !Int("3"))

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

$ 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

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

stratego> import foo
stratego> main

Tiger Subset

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

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

    Exp -> Uminus(Exp)
    Exp -> Plus(Exp,Exp)
    Exp -> Times(Exp,Exp)

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

4 + (x + 5) * 2 + 3 * y * 5 * z + x

is

2 * x + 15 * y * z + x + 14

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.

module anf
imports
  fixpoint-traversal
  options
  Tiger

strategies

  main = 
    io-wrap(anf)

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

Use stri to run the tool:

echo 'Int("1")' | stri anf.str

or, for a Tiger file in concrete syntax:

parse-tiger -i foo.tig | stri anf.str

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 #stratego at irc.freenode.com.