WebHome
Education Page
Description
Schedule
Slides
Assignments

Center
Master Program
Assignment Generic Traversal Strategies

Pt03
This assignment consists of two parts. The first part consists of exercises for
understanding traversal strategies. The second is a transformation on Tiger programs
using strategies.

%TOC%

---------++ Understanding Traversal Strategies

The purpose of this assignment is to understand how traversal strategies work. 
You should write modules strat-test.str and traversal-test.str 
The modules should define a number of tests using the Stratego:StrategoUnit test framework.
For each item in the lists below you should write a strategy definition and a few tests that demonstrate the working of the strategy.

The exercises should produce transformations on terms over the following signature:
<verbatim>
signature
  sorts Term
  constructors
    A : Term
    B : Term
    F : Term * Term -> Term
    G : Term * Term -> Term
    H : Term * Term -> Term
    I : Int -> Term
</verbatim>
However, your solutions should be as general as possible.

----+++ Composing Strategies

Create module =strat-test.str= and write strategies for the following exercises.
Note that all traversals should be implemented using congruence operators.

   1 Increment all integers in a term with 1
   1 Increment all integers in a term with a constant
   1 Replace all occurrences of G by H
   1 Replace all outermost occurrences of G by H
   1 Replace all innermost occurrences of G by H

----+++ Generic Traversal

Create module =traversal-test.str= with strategies defining traversals according to the following descriptions. 
Note however, that traversals should be as generic as allowed by the description. For instance, it should be possible to add or delete constructors if these are not directly mentioned in the description.

   1 Increment all integers in a term with 1
   1 Increment all integers in a term with a constant
   1 Replace all occurrences of G by H
   1 Replace all outermost occurrences of G by H
   1 Replace all innermost occurrences of G by H

----+++ Type Unifying Strategies

Further extend module =traversal-test.str= with strategies for the following type-unifying transformations.

   1 Count the number of occurrences of G and A nodes
   1 Compute the sum of all numbers in a tree
   1 Collect all I subterms.
   1 Collect all I subterms, but not those that are direct or indirect subterms of an H term.
   1 Collect all F subterms.
   1 Collect all outermost F subterms.
   1 Collect all F subterms, but not those that are _not_ direct or indirect subterms of an H term.