Day 5-old

On the first day of the second part, you will learn the concepts of Stratego step by step in a little tutorial about refactorings.

A Simple Rewrite Rule and Strategy

Open trans/refactoring.str in your MiniJava project and add the following content:

strategies

    tutorial = try(truth)

rules

    truth: Add(IntValue("21"), IntValue("21")) -> IntValue("42")

You have just defined a very simple rewrite rule truth. On its left-hand side, it matches an expression that adds the two integer constants 21 and 21. On its right-hand side, it instantiates a new expression, namely an integer constant 42.

The strategy tutorial tries to apply the rewrite rule. That is, if the rewrite rule can be applied to an input term, its output term becomes the result of the strategy. Otherwise, the input term becomes the output term.

Integration into the Editor

In order to test the strategy, you need to integrate it into your MiniJava editor. For this, define the following rewrite rule in trans/refactoring.str:

rules

    constant-folding-refactoring:
        (_, selected, position, ast, path, project-path) -> ([(source, result)], [], [], [])
    where
        source := selected ;
        <tutorial> selected => result

and define a refactoring in editor/MiniJava-Builders.esv:

refactoring Exp: "Tutorial (selection)" = constant-folding-refactoring (source)

You can now test the strategy and the rewrite rule. Select different expressions, choose Tutorial in the Refactoring menu and observe the different results.

Variables in Stratego

Define another rewrite rule in refactoring.str and adapt the definition of the strategy tutorial:

strategies

    tutorial = try(zero)

rules

    zero: Add(x, IntValue("0")) -> x

The new rewrite rule zero includes a variable x. When matching the rule's left-hand side, this variable is bound to a term. When instantiating the rule's right-hand side, the variable is replaced by the term it is bound to. Having said this, try to understand what the rewrite rule does.

Multiple Rewrite Rules of the Same Name

Add another rewrite rule with the same name:

strategies

    tutorial = try(zero)

rules

    zero: Add(x, IntValue("0")) -> x
    zero: Add(IntValue("0"), x) -> x

Whenever you try to apply zero, Stratego tries to apply one of the rules with this name. If more than one rules can be applied, there is no ordering of rules. One of the rules is chosen non-deterministicly.

Conditional Rewriting

Add the following rewrite rule and adapt the definition of tutorial:

strategies

    tutorial = try(zero + calc)

rules
    zero: Add(x, IntValue("0")) -> x
    zero: Add(IntValue("0"), x) -> x
 
    calc: Add(IntValue(x), IntValue(y)) -> IntValue(z)
        where <addS> (x, y) => z

The new rewrite rule calc matches an expression that adds two integer constants. The values of these constants are bound to variables x and y. The rule instantiates a new expression, namely an integer constant of value z. This variable is bound in a condition, expressed in the where clause of the rewrite rule. The condition reads as follows: Applying addS to a tuple of x and y should yield z.

More formally, <s> t applies the strategy s to a term t and s => t matches the result of s with t. In our example, addS is applied to the tuple and the result is matched with z, which binds z to this result. During the instantiation of the right-hand side pattern of the rewrite rule, this binding is used to replace z by its bound value.

The new definition of the tutorial strategy tries to apply either zero or calc. The choice between both is non-deterministic.

Exercises: Rewriting

1. You added a rewrite rule constant-folding-refactoring before. Try to understand what it does.
2. Define rewrite rules named two which replace multiplications by 2 with additions, e.g. 2*e by e+e.
3. Include these rules into the tutorial strategy.
4. Make the choices in the tutorial strategy deterministic.
5. Think about different ways to make the choice between the two rules for zero deterministic.
6. Extend the refactoring to support constant folding in multiplications.
7. Define a transformation replacing a method call by its first argument.
8. Define a similar transformation removing the first argument of a method call.
9. Define another similar transformation which replaces a method call by its last argument. Define helper rules rewriting a list to its last element. These rules need to be recursive.
10. Find instead a strategy in the Stratego library which does this for you.

Exercises: Traversals

Until now, all the rewriting happens at the top node of an AST. Stratego provides several generic strategies for traversing a tree and rewriting inner nodes of this tree. Define new refactorings by using the following strategies and try to find out what they are doing and how they differ. Which one gives the best result?

1. try(topdown(zero + two + calc))
2. topdown(try(zero + two + calc))
3. try(bottomup(zero + two + calc))
4. bottomup(try(zero + two + calc))
5. try(alltd(zero + two + calc))
6. alltd(try(zero + two + calc))
7. try(innermost(zero + two + calc))
8. innermost(zero + two + calc)

Is tutorial = innermost(try(zero + two + calc)) a good idea? What will happen if you call it? Why will it happen?

At the end of this day, you should clean up your code and provide only three refactorings:

1. A local refactoring, which folds constants in a selected expression, but not in its subexpressions.
2. A local refactoring, which simplifies a selected expression as much as possible.
3. A global refactoring, which simplifies all expressions in a program as much as possible.