Homework Assignments Week 1.4
Also on WebLab
Map and Filter
The Stratego library provides two strategies filter
and map
with the following implementation:
map(s): [] > []
map(s): [xxs] > [<s> x  <map(s)> xs]
filter(s): [] > []
filter(s): [xxs] > <filter(s)> xs where not (<s> x)
filter(s): [xxs] > [<s> x  <filter(s)> xs]
Stratego also provides a strategy inc
, which rewrites an integer number to its successor.

What is the result of
<filter(inc)> [1, "two", 3]
? Show each step of computation. 
What is the result of
<map(inc)> [1, "two", 3]
? Show each step of computation. 
Based on the definition of
map
andfilter
, explain the differences between both strategies.
Inverse
The Stratego library defines a strategy inverse(e)
with the following implementation:
inverse(a): [] > a
inverse(a): [xxs] > <inverse([xa])> xs

Explain the semantics of
inverse
in English. 
What is the result of applying
inverse([])
to the term[1,2,3]
. Show each step of computation. 
Based on the definition of
inverse
, explain how an accumulator is used.
Fold
The Stratego library provides a strategy foldr(s1, s2)
with the following implementation:
foldr(s1, s2): [] > <s1>
foldr(s1, s2): [xxs] > <s2> (x, <foldr(s1, s2)> xs)
Evaluate the following Stratego code. Show all intermediate steps and results.
<foldr(!0, add)> [1,2,3] => ... => ... => ...
Boolean Operators
Consider the following algebraic signature representing the abstract syntax of an expression language in Stratego:
signature
constructors
Var : String > E
Int : Int > E
Add : E * E > E
Mul : E * E > E
And : E * E > E
Or : E * E > E
If : E * E * E > E
In this language integers are used to represent Boolean values, with
Int(0)
representing false and all other integers representing true.
The Boolean operators And
and Or
are shortcircuit operations.

Define in Stratego a desugaring transformation to eliminate the
And
andOr
operators. 
Give the term resulting from desugaring the term
And(Var("x"), Or(Int(1), Var("y")))

Define in Stratego a strategy that, given a transformation that maps variables to expressions, applies this transformation to all variables in an expression; use only basic operators.

Define in Stratego a constant folding transformation for desugared expressions.
Function Application
Consider the following algebraic signature representing the abstract syntax of an expression language in Stratego:
signature
constructors
Var : String > E
Fun : List(String) * E > E // nary function literal ('lambda')
App : E * List(E) > E // nary function application
The language consists of variables (Var
), nary function literals (Fun
), and nary function applications (App
). For example, the expression
App(Fun(["x", "y"], Var("x")), [Var("a"), Var("b")])
is the application of a binary function to two argument expressions.

Functions with two or more arguments can be turned into nested functions with just one argument. This is known as currying. Define in Stratego a transformation (rules and strategy) to curry function literals and function applications in the language above. The resulting terms should be wellformed wrt the signature of expressions above. If you use a traversal strategy, provide its definition as well.

Give the term resulting from currying the term
App(Fun(["x", "y"], Var("x")), [Var("a"), Var("b")])

A variable in an expression is free if it is not bound by the parameter of a surrounding function literal. Define in Stratego a strategy
freevars
that produces the free variables of an expression. 
Stratego rules are themselves subject to desugaring to a core language of basic transformation operations. Desugar the following Stratego rule:
rules
Beta : App(Fun([x], e1), [e2]) > <alltd((Var(x) > e2))>e1
For
Consider the following algebraic signature representing the abstract syntax of an expression language in Stratego:
signature
constructors
Var : ID > E // x
Int : Int > E // i
Plus : E * E > E // e + e
Lt : E * E > E // e < e
Assign : ID * E > E // x := e
Seq : E * E > E // e ; e
While : E * E > E // while(e) { e }
For : ID * E * E * E > E // for(i := e to e) { e }
The concrete syntax in comments shows the mapping to the common programming language constructs.
The For(x, e_from, e_to, e_body)
construct is a loop that initializes the loop iteration variable x
to the value of the e_from
expression and then executes e_body
, incrementing x
on each iteration as long as it is smaller than e_to
.
For example, the following program computes the sum of integers from $0$ to $9$:
Seq(
Assign("sum", Int(0)),
For("x", Int(0), Int(10),
Assign("sum", Plus(Var("sum"), Var("x")))
)
)

The
For
loop can be expressed as aWhile
loop. Give the term resulting from desugaring the sum program above. 
Define in Stratego a transformation (rules and strategy) to desugar for loops to while loops in the language above. The resulting terms should be wellformed wrt the signature of expressions above. If you use a traversal strategy, provide its definition as well.

Stratego rules are themselves subject to desugaring to a core language of basic transformation operations. Desugar the following Stratego rule:
rules
Eval : Plus(Int(i), Int(j)) > Int(<plus>(i, j))
RE to CFG
Consider the following signatures defining the abstract syntax of regular expressions and contextfree grammars:
signature
sorts RE
constructors
: String > CC
Wld : RE
Str : STRING > RE
CC : CC > RE
EOL : RE
Seq : RE * RE > RE
Alt : RE * RE > RE
Plus : RE > RE
Star : RE > RE
Opt : RE > RE
signature
constructors
Grammar : List(Prod) > Prod
Prod : Symbol * List(Symbol) > Prod
NT : ID > Symbol
T : STRING > Symbol
L : LCID > Symbol
CC : CC > Symbol
Define a transformation retocfg
that transforms a regular expression to a contextfree grammar such that <retocfg> re => cfg
the language defined by the grammar cfg
is the same as that of the regular expression re
.