Assignment Composing Strategies

Goal

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

• /projects/stratego/ssl/spec

Also you can browse the online documentation at

• http://catamaran.labs.cs.uu.nl/docs/ssl/current/index_code.html

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

Testing

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.

Iteration

The following module defining various iteration strategies is part of the Stratego Standard Library:

  -------------------------------------------
  module iteration   
  imports conditional   
  strategies
    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 iteration-test.str which defines tests for each of these strategies. 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 this difference.

List Operations

The following are strategies implementing list operations:

• filter
• zip
• fetch
• qsort
• map
• partition
• conc
• concat

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 single module list-transformations.str.

Congruence

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

• http://www.stratego-language.org/tiger-front/tas/TAS-Format.str

for the soure of the TAS-Format component.

Define a format checker SEF-Format 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 liftargs component. You should get warnings in the places where your transformation does not lift non-atomic arguments.

Submit

Submit the following files

• iteration-test.str
• list-transformations.str
• SEF-Format.str
• Makefile
• any files needed in your tests