We call *strategy* an elementary transformation. Suppose that you want to
transform the object a() into the object b(). You can of course
use all the functionalities provided by Tom and Java. But in that case,
you will certainly end in mixing the *transformation* (the piece of code
that really replaces a() by b()) with the *control* (the
Java part that is executed in order to perform the transformation).

The notion of strategy is a clear separation between *control* and *transformation*.
In our case, we will define a strategy named Trans1 that only describes
the transformation we have in mind:

import main.example.types.*; import tom.library.sl.*; public class Main { %gom { module Example abstract syntax Term = a() | b() | f(x:Term) } %include { sl.tom } public final static void main(String[] args) { try { Term t1 = `a(); Term t2 = (Term) `Trans1().visit(t1); System.out.println("t2 = " + t2); } catch(VisitFailure e) { System.out.println("the strategy failed"); } } %strategy Trans1() extends Fail() { visit Term { a() -> { return `b(); } } } }

There exists three kinds of elementary strategy: Fail, which always
fails, Identity, which always succeeds, and transformation rules of the
form *l* → *r*.

Therefore, if we consider the elementary strategy a ⇒b (which
replaces a by b), we have the following results:

(a -> b)[a] = b (a -> b)[b] = failure (a -> b)[f(a)] = failure (Identity)[a] = a (Identity)[b] = b (Identity)[f(a)] = f(a) (Fail)[a] = failure

The sequential operator, Sequence(S1,S2), applies the strategy S1, and then the strategy S2. It fails if either S1 fails, or S2 fails.

(Sequence(a -> b, b -> c))[a] = c (Sequence(a -> b, c -> d))[a] = failure (Sequence(b -> c, a -> b))[a] = failure

The choice operator, Choice(S1,S2), applies the strategy S1. If the application S1 fails, it applies the strategy S2. Therefore, Choice(S1,S2) fails if both S1 and S2 fail.

(Choice(a -> b, b -> c))[a] = b (Choice(b -> c, a -> b))[a] = b (Choice(b -> c, c -> d))[a] = failure (Choice(b -> c, Identity))[a] = a

The strategy Not(S), applies the strategy and fails when S succeeds. Otherwise, it succeeds and corresponds to the Identity.

(Not(a -> b))[a] = failure (Not(b -> c))[a] = a

By combining basic combinators, more complex strategies can be defined. To make the definitions generic, parameters can be used. For example, we can define the two following strategies:

- Try(S) = Choice(S, Identity), which tries to apply S, but never fails
- Repeat(S) = Try(Sequence(S, Repeat(S))), which applies recursively S until it fails, and then returns the last unfailing result

(Try(b -> c))[a] = a (Repeat(a -> b))[a] = b (Repeat(Choice(b -> c, a -> b)))[a] = c (Repeat(b -> c))[a] = a

We consider two kinds of traversal strategy (All(S) and One(S)). The first one applies S to all subterms, whereas the second one applies S to only one subterm.

The application of the strategy All(S) to a term t applies S on each immediate subterm of t. The strategy All(S) fails if S fails on at least one immediate subterm.

(All(a -> b))[f(a)] = f(b) (All(a -> b))[g(a,a)] = g(b,b) (All(a -> b))[g(a,b)] = failure (All(a -> b))[a] = a (All(Try(a -> b)))[g(a,c)] = g(b,c)

The application of the strategy One(S) to a term t tries to apply S on an immediate subterm of t. The strategy One(S) succeeds if there is a subterm such that S can be applied. The subterms are tried from left to right.

(One(a -> b))[f(a)] = f(b) (One(a -> b))[g(a,a)] = g(b,a) (One(a -> b))[g(b,a)] = g(b,b) (One(a -> b))[a] = failure

By combining the previously mentioned constructs, it becomes possible to define well know strategies:

BottomUp(S) = Sequence(All(BottomUp(S)), S) TopDown(S) = Sequence(S, All(TopDown(S))) OnceBottomUp(S) = Choice(One(OnceBottomUp(S)), S) OnceTopDown(S) = Choice(S, One(OnceTopDown(S))) Innermost(S) = Repeat(OnceBottomUp(S)) Outermost(S) = Repeat(OnceTopDown(S))

Let us consider again a Pico language whose syntax is a bit simpler than the one seen in section 4.5.

import pico2.term.types.*; import java.util.*; import jjtraveler.VisitFailure; import jjtraveler.reflective.VisitableVisitor; class Pico2 { %include { mutraveler.tom } %gom { module Term imports int String abstract syntax Bool = True() | False() | Neg(b:Bool) | Or(b1:Bool, b2:Bool) | And(b1:Bool, b2:Bool) | Eq(e1:Expr, e2:Expr) Expr = Var(name:String) | Cst(val:int) | Let(name:String, e:Expr, body:Expr) | Seq( Expr* ) | If(cond:Bool, e1:Expr, e2:Expr) | Print(e:Expr) | Plus(e1:Expr, e2:Expr) } ... }

As an exercise, we want to write an optimization function that replaces an instruction of the form If(Neg(b),i1,i2) by a simpler one: If(b,i2,i1). A possible implementation is:

public static Expr opti(Expr expr) { %match(expr) { If(Neg(b),i1,i2) -> { return `opti(If(b,i2,i1)); } x -> { return `x; } } throw new RuntimeException("strange term: " + expr); } public final static void main(String[] args) { Expr p4 = `Let("i",Cst(0), If(Neg(Eq(Var("i"),Cst(10))), Seq(Print(Var("i")), Let("i",Plus(Var("i"),Cst(1)),Var("i"))), Seq())); System.out.println("p4 = " + p4); System.out.println("opti(p4) = " + opti(p4)); }

When executing this program, we obtain:

p4 = Let("i",Cst(0),If(Neg(Eq(Var("i"),Cst(10))), ConsSeq(Print(Var("i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq)) opti(p4) = Let("i",Cst(0),If(Neg(Eq(Var("i"),Cst(10))), ConsSeq(Print(Var("i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq))

This does not correspond to the expected result, simply because the opti function performs an optimization when the expression starts with an If instruction. To get the expected behavior, we have to add congruence rules that will allow to apply the rule in subterms (one rule for each constructor):

public static Expr opti(Expr expr) { %match(expr) { If(Neg(b),i1,i2) -> { return `opti(If(b,i2,i1)); } // congruence rules Let(n,e1,e2) -> { return `Let(n,opti(e1),opti(e2)); } Seq(head,tail*) -> { return `Seq(opti(head),opti(tail*)); } If(b,i1,i2) -> { return `If(b,opti(i1),opti(i2)); } Print(e) -> { return `Print(e); } Plus(e1,e2) -> { return `Plus(e1,e2); } x -> { return `x; } } throw new RuntimeException("strange term: " + expr); }

Since this is not very convenient, we will show how the use of strategies can simplify this task.

Let us start with a very simple task which consists in printing all the nodes that corresponds to a constant (Cst(_). To do that, we have to define an elementary strategy that is successful when it is applied on a node Cst(_):

%strategy stratPrintCst() extends Fail() { visit Expr { Cst(x) -> { System.out.println("cst: " + `x); } } }

To traverse the program and print all Cst nodes, a TopDown strategy can be applied:

public static void printCst(Expr expr) { try { `TopDown(Try(stratPrintCst())).visit(expr); } catch (VisitFailure e) { System.out.println("strategy failed"); } } public final static void main(String[] args) { ... System.out.println("p4 = " + p4); printCst(p4); }

This results in:

p4 = Let("i",Cst(0),If(Neg(Eq(Var("i"),Cst(10))), ConsSeq(Print(Var("i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq)) cst: 0 cst: 10 cst: 1

As a second exercise, we will try to write another strategy that performs the same task, but we will try to separate the strategy that looks for a constant from the strategy that prints a node. So, let us define these two strategies:

%strategy FindCst() extends Fail() { visit Expr { c@Cst(x) -> { return `c; } } } %strategy PrintTree() extends Identity() { visit Expr { x -> { System.out.println(`x); } } }

Similarly to stratPrintCst, the strategy FindCst extends Fail. The goal of the PrintTree strategy is to print a node of sort Expr. By extending Identity, we specify the default behavior when the strategy is applied on a term of a different sort.

To print the node Cst, we have to look for a Cst and print this node. This can be done by combining, using a Sequence, the two strategies FindCst and PrintTree:

public static void printCst(Expr expr) { try { `TopDown(Try(stratPrintCst())).visit(expr); `TopDown(Try(Sequence(FindCst(),PrintTree()))).visit(expr); } catch (VisitFailure e) { System.out.println("strategy failed"); } }

This results in:

cst: 0 cst: 10 cst: 1 Cst(0) Cst(10) Cst(1)

Here, we will try to rename all the variables from a given program: the name should be modified into _name.

To achieve this task, you can define a primitive strategy that performs the modification, and apply it using a strategy such as TopDown:

%strategy stratRenameVar() extends Fail() { visit Expr { Var(name) -> { return `Var("_"+name); } } } public static void optimize(Expr expr) { try { `Sequence(TopDown(Try(stratRenameVar())),PrintTree()).visit(expr); } catch (VisitFailure e) { System.out.println("strategy failed"); } }

The application of optimize to p4 results in:

Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))), ConsSeq(Print(Var("_i")),ConsSeq(Let("i", Plus(Var("_i"),Cst(1)),Var("_i")),EmptySeq)),EmptySeq))

Suppose now that we want to print the intermediate steps: we do not want to perform all the replacements in one step, but for debugging purpose, we want to print the intermediate term after each application of the renaming rule.

The solution consists in combining the stratRenameVar strategy with the PrintTree strategy.

A first solution consists in applying stratRenameVar using a OnceBottomUp strategy, and immediately apply PrintTree on the resulting term. This could be implemented as follows:

`Repeat(Sequence(OnceBottomUp(stratRenameVar()),PrintTree())).visit(expr);

Unfortunately, this results in:

Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("__i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("___i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("____i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("_____i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("______i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("_______i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("________i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("_________i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("__________i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("___________i"),Cst(10))),... Let("i",Cst(0),If(Neg(Eq(Var("____________i"),Cst(10))),... ...

This is not the expected behavior! Why?

Simply because the renaming rule can be applied several times on a same variable. To fix this problem, we have to apply the renaming rule only if the considered variable has not already be renamed.

To know if a variable has been renamed, you just have to define an elementary strategy, called RenamedVar, that succeeds when the name of the variable starts with an underscore. This can be easily implemented using string matching capabilities:

%strategy RenamedVar() extends Fail() { visit Expr { v@Var(('_',name*)) -> { return `v; } } }

To finish our implementation, it is sufficient to apply stratRenameVar only when RenamedVar fails, i.e., when Not(RenamedVar) succeeds.

`Repeat(Sequence( OnceBottomUp(Sequence(Not(RenamedVar()),stratRenameVar())), PrintTree()) ).visit(expr);

This results in (layouts have been added to improve readability):

Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))), ConsSeq(Print(Var("i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq)) Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))), ConsSeq(Print(Var("_i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq)) Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))), ConsSeq(Print(Var("_i")),ConsSeq(Let("i", Plus(Var("_i"),Cst(1)),Var("i")),EmptySeq)),EmptySeq)) Let("i",Cst(0),If(Neg(Eq(Var("_i"),Cst(10))), ConsSeq(Print(Var("_i")),ConsSeq(Let("i", Plus(Var("_i"),Cst(1)),Var("_i")),EmptySeq)),EmptySeq))

Now that you know how to use strategies, it should be easy to implement the tiny optimizer seen in the beginning of section 6.2.

You just have to define the transformation rule and a strategy that will apply the rule in an innermost way:

%strategy OptIf() extends Fail() { visit Expr { If(Neg(b),i1,i2) -> { return `If(b,i2,i1); } } } public void optimize(Expr expr) { try { `Sequence(Innermost(OptIf()),PrintTree()).visit(expr); } catch (VisitFailure e) { System.out.println("strategy failed"); } }

Applied to the program p4, as expected this results in:

Let("i",Cst(0),If(Eq(Var("i"),Cst(10)),EmptySeq, ConsSeq(Print(Var("i")),ConsSeq(Let("i", Plus(Var("i"),Cst(1)),Var("i")),EmptySeq))))