Previous Up Next

Chapter 7  Strategies

Strategies provides a way to control how a transformation rule is applied. In Tom, users can define elementary strategies (corresponding to a set of rewriting rules) and combine them using the MuTraveler library. An elementary strategy corresponds to a list of MatchStatement (one associated to each sort) and is defined using the construction %strategy. The MuTraveler library, inspired by ELAN, Stratego, and JJTraveler, allows to easily define various kinds of traversal strategies.

Note: strategies are only supported in Java.


7.1  Elementary strategy

7.1.1  Elementary strategies from MuTraveler

The two elementary strategies are the identity and the failure. There are defined in MuTraveler library. These two strategies have no effect on the term. The identity strategy written `Identity() returns the term unchanged. The failure strategy written `Fail() throws a jjtraveler.VisitFailure exception.

7.1.2  Elementary strategies defined by users

Users can define elementary strategies by using the %strategy construction. Here is the %strategy grammar:

StrategyConstruct ::= `%strategy' StrategyName `(' [StrategyArguments] `)'
    `extends' [``'] ExtendsTerm `{' StrategyVisitList `}'
StrategyArguments ::= SubjectName `:' AlgebraicType ( `,' SubjectName `:' AlgebraicType )*
StrategyVisitList ::= ( StrategyVisit )*
StrategyVisit ::= `visit' AlgebraicType `{' ( PatternAction )* `}'


This strategy has a name, followed with mandatory parenthesis. Inside these parenthesis, we have optional parameters.

The strategy has an extendsTerm which defines the behavior of the default strategy that will be applied. In most cases, two default behaviours are used: The body of the strategy is a list of visited sorts. Each StrategyVisit contains a list of PatternAction that will be applied to the corresponding sort. In other words, a StrategyVisit is translated into a MatchStatement.

For strategies, all AlgebraicType must have a TomForwardType. For a given strategy, all visited sorts must have the same TomForwardType. This TomForwardType represents a Java class. This class must implement the interface VisitableVisitor. By default this mechanism is done automatically by Gom 6.2. If you are defining a new sort using %typeterm, you have to define visitor_fwd 5.3.1:

%typeterm Term {
  implement { strategy.term.types.Term }
  visitor_fwd { strategy.term.termVisitableFwd }
  equals(t1,t2) { t1.equals(t2) }
}


For instance, here is an elementary strategy RewriteSystem that can be instantiated as follows: 
  MuStrategy rule = `RewriteSystem();

  %strategy RewriteSystem() extends `Identity() {
    visit Term {
      a() -> { return `b(); }
      b() -> { return `c(); }
    }
  }


Trick
A strategy can receive data as arguments. They must correspond to an algebraic type. To use a strategy as argument, use the type Strategy. To use a Java type, such as HashSet for example, it is sufficient to define an elementary mapping. This can be done as follows: 
%include { util/types/HashSet.tom }

%strategy RewriteSystem(hs:HashSet) extends `Identity() {
  visit Term {
    a() -> { hs.add(`a()); }
    b() -> { return `c(); }
  }
}
The RewriteSystem strategy can be instantiated as follows: 
HashSet hashset = new HashSet();
MuStrategy rule =`RewriteSystem(hashset);
Strategies defined by `%strategy' are local to the file defining them. If you want to export your strategy to another package, you have to create a public function exporting an instance of the strategy built with ``'.


Note: you cannot use %strategy inside a function.


7.2  Basic strategy operators

The following operators are the key-component that can be used to define more complex strategies. In this framework, the application of a strategy to a term can fail. In Java, the failure is implemented by an exception (jjtraveler.VisitFailure).

(Identity)[t] ⇒ t
(Fail)[t] ⇒ failure
(Sequence(s1,s2))[t] ⇒ failure if (s1)[t] fails
    (s2)[t'] if (s1)[t] ⇒t'
(Choice(s1,s2))[t] ⇒ t' if (s1)[t] ⇒t'
    (s2)[t] if (s1)[t] fails
(All(s))[f(t1,...,tn)] ⇒ f(t1',...,tn') if (s)[t1] ⇒t1', ..., (s)[tn] ⇒tn'
    failure if there exists i such that (s)[ti] fails
(All(s))[cst] ⇒ c
(One(s))[f(t1,...,tn)] ⇒ f(t1,...,ti',...,tn) if (s)[ti] ⇒ti'
    failure (s)[t1] fails, ..., (s)[tn] fails
(One(s))[cst] ⇒ failure


For example, we can define myFirstStrat = `All(RewriteSystem) where Rewritesystem is defined as the elementary strategy:

  %strategy RewriteSystem() extends `Fail() {
    visit Term {
      a() -> { return `b(); }
    }
  }


When applying this strategy to different subjects, we obtain:
(myFirstStrat)[f(a(),a())] ⇒ f(b(),b())
(myFirstStrat)[f(a(),b())] ⇒ failure
(myFirstStrat)[b()] ⇒ b()


Sometimes, it is interesting to get the position where the strategy is applied. Positions in a term are represented as sequences of integers. The interface MuStrategy each strategy do implement provides a method getPosition() to collect the current position in the term visited by the strategy. This information is also available through the getPosition(Visitablevisitor v) static method from the MuTraveler class. To use this method or the following strategies which depend on it, you must call the static method MuTraveler.init on your strategy.

try {
  VisitableVisitor s = MuTraveler.init(`OnceBottomUp(rule));
  s.visit(subject));
} catch(VisitFailure e) {
  System.out.prinltn("Failure at position" + MuTraveler.getPosition(s));
}


The library gives several basic strategies using the position:

(Omega(i,s))[f(t1,...,tn)] ⇒ f(t1,...,ti',...,tn) if (s)[ti] ⇒ti'
    failure if (s)[ti] fails
(MuTraveler.getReplace(i,t))[f(t1,...,tn)] ⇒ f(t1,...,t,...,tn)
(MuTraveler.getSubterm(i,t))[f(t1,...,tn)] ⇒ ti


Note: the static method MuTraveler.getReplace(i,t) corresponds to the strategy Omega(i,s) where s is a strategy reduced to one rule x → t.


Note: the static method MuTraveler.getPosition(i,t) returns a strategy that is not type preserving.

7.3  Strategy library

In order to define recursive strategies, we introduce the μ abstractor. This allows to give a name to the current strategy, which can be referenced later.

Try(s) = Choice(s,Identity)
Repeat(s) = μ x.Choice(Sequence(s,x),Identity())
OnceBottomUp(s) = μ x.Choice(One(x),s))
BottomUp(s) = μ x.Sequence(All(x),s))
TopDown(s) = μ x.Sequence(s,All(x)))
Innermost(s) = μ x.Sequence(All(x),Try(Sequence(s,x))))


The Try strategy never fails: it tries to apply the strategy s. If it succeeds, the result is returned. Otherwise,the Identity strategy is applied, and the subject is not modified.

The Repeat strategy applies the strategy s as many times as possible, until a failure occurs. The last unfailing result is returned.

The strategy OnceBottomUp tries to apply the strategy s once, starting from the leftmost-innermost leaves. BottomUp looks like OnceBottomUp but is not similar: s is applied to all nodes, starting from the leaves. Note that the application of s should not fail, otherwise the whole strategy also fails.

The strategy Innermost tries to apply s as many times as possible, starting from the leaves. This construct is useful to compute normal forms.

For example, we define myFirstInnerMost = InnerMost(s) where s is defined as the elementary strategy:

  %strategy RewriteSystem() extends `Fail() {
    visit Term {
      a()        -> { return `b(); }
      b()        -> { return `c(); }
      g(c(),c()) -> { return `c(); }
    }
  }
The application of this strategy to different subject terms gives:
(myFirstInnerMost)[g(a(),b())] ⇒ c()
(myFirstInnerMost)[f(g(g(a,b),g(a,a)))] ⇒ f(c(),c())
(myFirstInnerMost)[g(d(),d())] ⇒ g(d(),d())


We can notice that Innermost strategy never fails. If we try myFirstBottomUp = BottomUp(s) with the same subjects, we obtain always failure because if s fails on a node, the whole strategy fails.

7.4  Strategies with identity considered as failure

In order to get more efficient strategies (in particular when performing leftmost-innermost normalization), we consider variants where the notion of failure corresponds to the identity. This means that when a term cannot can be transformed by a strategy (into a different term), this is considered as a failure.
(SequenceId(s1,s2))[t] ⇒ (s2)[t'] if (s1)[t] ⇒t' with t≠t'
    t otherwise
(ChoiceId(s1,s2))[t] ⇒ t' if (s1)[t] ⇒t' with t≠t'
    (s2)[t] otherwise
(OneId(s))[f(t1,...,tn)] ⇒ f(t1,...,ti',...,tn) if (s)[ti] ⇒ti' with ti≠ti'
    f(t1,...,tn) otherwise
(OneId(s))[cst] ⇒ cst
     
TryId(s) = s
RepeatId(s) = μ x.SequenceId(s,x))
OnceBottomUpId(s) = μ x.ChoiceId(OneId(x),s))
OnceTopDownId(s) = μ x.ChoiceId(s,OneId(x)))
InnermostId(s) = μ x.Sequence(All(x),SequenceId(s,x)))
OutermostId(s) = μ x.Sequence(SequenceId(s,x),All(x)))


We can define a strategy trying to apply a simple rewrite system to the root of a term, replacing a() by b(), b() by c(), and g(c(),c()) by a(), and otherwise returning the identity: 
import jjtraveler.reflective.VisitableVisitor;
import tom.library.strategy.mutraveler.*;
import jjtraveler.Visitable;
import jjtraveler.VisitFailure;


We also need to import the corresponding mapping: 
  %include { mustrategy.tom }


Then we define an elementary strategy:

  %strategy RewriteSystem() extends `Fail() {
    visit Term {
      a()        -> { return `b(); }
      b()        -> { return `c(); }
      g(c(),c()) -> { return `c(); }
    }
  }


Then, it becomes quite easy to define various strategies on top of this elementary strategy: 
Term subject = `f(g(g(a,b),g(a,a)));
VisitableVisitor rule = `RewriteSystem();
try {
  System.out.println("subject       = " + subject);
  System.out.println("onceBottomUp  = " +
      MuTraveler.init(`OnceBottomUp(rule)).visit(subject));
  System.out.println("innermost   = " +
      MuTraveler.init(`Choice(BottomUp(rule),Innermost(rule))).visit(subject));
} catch (VisitFailure e) {
  System.out.println("reduction failed on: " + subject);
}


7.5  Strategies generated by Gom

See section 6.4.

7.6  Matching and visiting a strategy

Strategies can be considered as algebraic terms. For instance, the BottomUp(v) strategy corresponds to the algebraic term mu(MuVar("x"),Sequence(v,All(MuVar("x")))).

Those strategy terms can then be traversed and transformed by mean of strategies. As strategies are considered as algebraic terms, it is possible to use pattern matching on the elementary strategies of the strategy language.

The following function uses pattern matching on a strategy expression, to identify a TopDown strategy and transform it to BottomUp. 
public MuStrategy topDown2BottomUp(MuStrategy s) {
  %match(s) {
    Mu(x,Sequence(v,All(x))) -> {
      return `Mu(x,Sequence(All(x),v));
    }
  }
  return s;
}


Strategy expressions being visitable terms, we can also use the `%strategy' construction to define strategy transformations, for example, removing unnecessary Identity() strategies.

%strategy RemId extends Identity() {
  visit Strategy {
    Sequence(Identity(),x) -> { return `x; }
    Sequence(x,Identity()) -> { return `x; }
  }
}


7.7  Implementing elementary strategies in Java

The simplest way to use strategies is to use them with data-structures generated by Gom, as this data structure implementation provides the interfaces and classes needed to use `%strategy'.

However, it is not impossible (nor difficult) to use `%strategy' with another term implementation. The requirements for using `%strategy' on the data structure are: We detail here on a simple example of hand written data structure how to adapt the data structure to be able to use `%strategy'. Given a Java class Person we can define an algebraic mapping for this class: 
 %typeterm TomPerson {
   implement { Person }
   equals(t1,t2) { t1.equals(t2) }
   visitor_fwd { PersonVisitor }
 }
For this example, we consider a data-structure those Gom equivalent could be 
Term = A()
     | B()
     | G(arg:Slot)
     | F(arg1:Term, arg2:Term)
Slot = Name(name:String)


7.7.1  Simple implementation of the data structure

We first present a very straightforward implementation of this data structure. It will serve as a basis and will be extended to provide support for strategies.

We first define abstract classes for the two sorts of this definition, Term and Slot, and classes for those operators extending those sort classes. 
public abstract class Term { }
public abstract class Slot { }

/* A and B are similar up to a renaming */
public class A extends Term {
  public String toString() {
    return "A()";
  }
  public boolean equals(Object o) {
    if(o instanceof A) {
      return true;
    }
    return false;
  }
}

/* G is similar to F, but has only one child */
public class F extends Term {
  public Term a;
  public Term b;
  public F(Term arg0, Term arg1) {
    a = arg0;
    b = arg1;
  }
  public String toString() {
    return "F("+a.toString()+", "+b.toString()+")";
  }
  public boolean equals(Object o) {
    if(o instanceof F) {
      F f = (F) o;
      return a.equals(f.a) && b.equals(f.b);
    }
    return false;
  }
}

public class Name extends Slot {
  public String name;
  public Name(String s) {
    this.name = s;
  }
  public String toString() {
    return "Name("+name+")";
  }
  public boolean equals(Object o) {
    if(o instanceof Name) {
      Name n = (Name) o;
      return name.equals(n.name);
    }
    return false;
  }
}


We only took care in this implementation to get a correct behavior for the equals method. Then, the Tom mapping is simply 
%include { string.tom }
%typeterm Term {
  implement { Term }
  equals(t1,t2) {t1.equals(t2)}
}
%typeterm Slot {
  implement { Slot }
  equals(t1,t2) {t1.equals(t2)}
}
%op Term A() {
  is_fsym(t) { (t!= null) && (t instanceof A) }
  make() { new A() }
}
%op Term F(arg1:Term, arg2:Term) {
  is_fsym(t) { (t!= null) && (t instanceof F) }
  get_slot(arg1,t) { ((F) t).a }
  get_slot(arg2,t) { ((F) t).b }
  make(t0, t1) { new F(t0, t1) }
}
...
%op Slot Name(name:String) {
  is_fsym(t) { (t!= null) && (t instanceof Name) }
  get_slot(name,t) { ((Name) t).name }
  make(t0) { new Name(t0) }
}


7.7.2  Extending to support strategies

We first need to make sure all classes representing operators do implement the jjtraveler.Visitable interface. We also need those classes to provide a accept method taking as argument the class that will serve as visitor_fwd. We decide here to call this class BasicStrategy, and its code and behavior will be detailed later.

public abstract class Term implements jjtraveler.Visitable {
  public Term accept(BasicStrategy v) throws jjtraveler.VisitFailure {
    return v.visit_Term(this);
  }
}

public abstract class Slot implements jjtraveler.Visitable {
  public Slot accept(BasicStrategy v) throws jjtraveler.VisitFailure {
    return v.visit_Slot(this);
  }
}


Once the abstract classes for sorts declare they implements jjtraveler.Visitable, we have to adapt the classes for the operators to actually implement it. This interface is composed of three methods: As all subterms have to implement the jjtraveler.Visitable interface, we do not provide access to subterms of builtin sorts like String od int, but discard them. Thus those children will not be traversed by the strategies.

For constants like the class A, we get: 
public class A extends Term {
  public int getChildCount() { return 0; }
  public jjtraveler.Visitable getChildAt(int index) {
    throw new IndexOutOfBoundsException();
  }
  public jjtraveler.Visitable setChildAt(int index, jjtraveler.Visitable v) {
    throw new IndexOutOfBoundsException();
  }
  public String toString() {
    return "A()";
  }
  public boolean equals(Object o) {
    if(o instanceof A) {
      return true;
    }
    return false;
  }
}


Then for F, which has two subterms, we implement setters and getters for children: 
public class F extends Term {
  public Term a;
  public Term b;
  public F(Term arg0, Term arg1) {
    a = arg0;
    b= arg1;
  }
  public int getChildCount() { return 2; }
  public jjtraveler.Visitable getChildAt(int index) {
    if(index == 0) {
      return a;
    } else if(index == 1) {
      return b;
    }
    throw new IndexOutOfBoundsException();
  }
  public jjtraveler.Visitable setChildAt(int index, jjtraveler.Visitable v) {
    if(index == 0) {
      return new F((Term)v,b);
    } else if(index == 1) {
      return new F(a,(Term)v);
    }
    throw new IndexOutOfBoundsException();
  }
  public String toString() {
    return "F("+a.toString()+", "+b.toString()+")";
  }
  public boolean equals(Object o) {
    if(o instanceof F) {
      F f = (F) o;
      return a.equals(f.a) && b.equals(f.b);
    }
    return false;
  }
}


The case of Name is special, since it has only one child, which is of sort String, and thus do not implement jjtraveler.Visitable

public class Name extends Slot {
  public String name;
  public Name(String s) {
    this.name = s;
  }
  /* Do not visit the "String" child, as we can't make it Visitable */
  public int getChildCount() { return 0; }
  public jjtraveler.Visitable getChildAt(int index) {
    throw new IndexOutOfBoundsException();
  }
  public jjtraveler.Visitable setChildAt(int index, jjtraveler.Visitable v) {
    throw new IndexOutOfBoundsException();
  }
  public String toString() {
    return "Name("+name+")";
  }
  public boolean equals(Object o) {
    if(o instanceof Name) {
      Name n = (Name) o;
      return name.equals(n.name);
    }
    return false;
  }
}


Then, the BasicStrategy has to be implemented. This class implements an interface from the JJTraveler library: jjtraveler.reflective.VisitableVisitor. It also has an arguments which itself is a strategy, and its visit method either call the accept method of both Term and Slot sorts (which in turn will call the type preserving visit methods BasicStrategy declares), or delegate the visit call to its argument.

public class BasicStrategy implements jjtraveler.reflective.VisitableVisitor {
  protected jjtraveler.Visitor any;

  public BasicStrategy(jjtraveler.Visitor v) {
    this.any = v;
  }

  public jjtraveler.Visitable visit(jjtraveler.Visitable v)
                                   throws jjtraveler.VisitFailure {
    if (v instanceof Term) {
      return ((Term) v).accept(this);
    } else if (v instanceof Slot) {
      return ((Slot) v).accept(this);
    } else {
      return any.visit(v);
    }
  }

  public Term visit_Term(Term arg) throws jjtraveler.VisitFailure {
    return (Term) any.visit(arg);
  }

  public Slot visit_Slot(Slot arg) throws jjtraveler.VisitFailure {
    return (Slot) any.visit(arg);
  }

  /* jjtraveler.Visitable interface */
  public int getChildCount() { return 1; }
  public jjtraveler.Visitable getChildAt(int index) {
    if(index == 0) {
      return (jjtraveler.Visitable) any;
    }
    throw new IndexOutOfBoundsException();
  }
  public jjtraveler.Visitable setChildAt(int index, jjtraveler.Visitable v) {
    if(index == 0) {
      any = ((jjtraveler.Visitor) v);
      return this;
    }
    throw new IndexOutOfBoundsException();
  }
}


Once this is set up, we still have to modify the Tom mapping to add a visitor_fwd, pointing to the BasicStrategy class.

%typeterm Term {
  implement { Term }
  visitor_fwd { BasicStrategy }
  equals(t1,t2) { t1.equals(t2) }
}
%typeterm Slot {
  implement { Slot }
  visitor_fwd { BasicStrategy }
  equals(t1,t2) { t1.equals(t2) }
}


Those changes make possible the use of `%strategy' with any term implementation. While the core Tom functionalities can work without any modification of the user data structure, the use of `%strategy' requires some changes to the data structure to be used. However, those changes are relatively easy to implement, and the jjtraveler.Visitable interface is reasonable for tree-like structures.

Previous Up Next