 # 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): [x|xs] -> [<s> x | <map(s)> xs]

filter(s): []     -> []
filter(s): [x|xs] -> <filter(s)> xs where not (<s> x)
filter(s): [x|xs] -> [<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` and `filter`, explain the differences between both strategies.

### Inverse

The Stratego library defines a strategy `inverse(|e)` with the following implementation:

``````inverse(|a): []     -> a
inverse(|a): [x|xs] -> <inverse(|[x|a])> 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): [x|xs] -> <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 short-circuit operations.

• Define in Stratego a desugaring transformation to eliminate the `And` and `Or` 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 // n-ary function literal ('lambda')
App : E * List(E) -> E      // n-ary function application
``````

The language consists of variables (`Var`), n-ary function literals (`Fun`), and n-ary 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 well-formed 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 a `While` 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 well-formed 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 context-free 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 `re-to-cfg` that transforms a regular expression to a context-free grammar such that `<re-to-cfg> re => cfg` the language defined by the grammar `cfg` is the same as that of the regular expression `re`.