Assignment Composing Strategies
The goal of this assignment is to learn to understand and use the basic strategy combinators.
Rather than constructing a complete transformation you should construct several small strategies.
You are free (encouraged) to use operators from the Stratego library.
The sources of the Stratego Standard Library can be found in
Also you can browse the online documentation at
Finding the right definition is a bit of an art. Here are some methods
- Look in the module index for a module with a name that suggests a relation with your application
- Guess a plausible name and
grep in the sources
- Just browse the library sources
Tests must be implemented using Stratego Unit
, which is a unit-testing framework for Stratego. The Stratego Unit page explains how to create sunit modules and how to write tests.
The following module defining various iteration strategies is part of the Stratego Standard Library:
repeat(s, c) = rec x(s; x <+ c)
repeat(s) = rec x(try(s; x))
repeat1(s, c) = rec x(s; (x <+ c))
repeat1(s) = repeat1(s, id)
repeat-until(s, c) = rec x(s; (c <+ x))
while(c, s) = rec x(try(c; s; x))
do-while(s, c) = rec x(s; try(c; x))
while-not(c, s) = rec x(c <+ s; x)
for(i, c, s) = i; while-not(c, s)
Write a module
which defines tests for each of
The tests should (1) define a sample strategy that is defined in
terms of these operators using some custom made rules, and (2) apply
it to sample terms.
The tests should be such that the difference
between the various
iteration operators is illustrated. Include comments that explains
The following are strategies implementing list operations:
Find out the definitions of these strategies in the library and
use them to implement the following transformations on lists.
- Sort a list of integers in descending order
- Sort a list of strings in ascending order
- Find the first Let binding in a list of Tiger expressions and replace it with its body
- Replace all Let binding in a list of Tiger expressions and replace them with their bodies
- Reduce a list of expressions to only those expressions that are variables or constants
- Split a list of expressions into a pair of a list of atomic expressions and a list of non-atomic expressions
- Concatenate two lists
- Concatenate a list of lists into one list
- For each element in a list of expressions generate a new name using
new, then combine the list of names with the list of expressions to form a sequence of assignments assigning the expression to a variable using the new name.
Include definitions for these transformations with tests in a
A format checker is a `transformation' which checks the format of
a term. For instance, the
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.
for the soure of the
Define a format checker
that checks that expressions are side-effect free, and issues a warning (using debug) if that is not the case.
According to this format statement constructors (assignments, loops, etc)
should not occur nested in expressions. Function calls should only occur
as the top-level expression of an assignment.
Use this component to check the output of the
You should get warnings in the places where your transformation does
not lift non-atomic arguments.
Submit the following files
- any files needed in your tests