Chapter 12  Strategies

To exercise some control over the application of the rules, rewriting based languages provide abstract ways by using reflexivity and the meta-level for Maude, or the notion of rewriting strategies as in Tom. Strategies such as bottom-up, top-down or leftmost-innermost are higher-order features that describe how rewrite rules should be applied (At each step, the strategy chooses which rule is applied and in which position inside the term).

In Tom, we have developed a flexible and expressive strategy language inspired by ELAN, Stratego, and JJTraveler where high-level strategies are defined by combining low-level primitives. For example, the top-down strategy is recursively defined by Sequence(s,All(TopDown(s))). Users can define elementary strategies (corresponding to a set of rewriting rules) and control them using various combinators proposed in the sl library. This rich strategy language allows to easily define various kinds of term traversals.

In this chapter, first, we briefly present the sl library functioning. After that, we describe in detail every elementary strategies and strategy combinators. Then, we explain how the sl library can be used in combination with Gom structures.

12.1  Overview

The package tom.library.sl is mainly composed by an interface Strategy and a class for each strategy combinator.

12.1.1  Strategy interface

Every strategy (elementary strategies or combinators) implements the Strategy interface. To apply a strategy on a term (generally called the subject), this interface offers two methods:

• Visitable visitLight(Visitable) visits the subject any in a light way (without environment)
• Visitable visit(Visitable) visits the subject any by providing the environment

A strategy can visit any Visitable object. Any term constructed using a Tom mapping or a Gom signature is Visitable. The first method visitLight is the most efficient because it does not manage any environment. Most of time, it is sufficient.The second method depends on an environment (see Section 12.1.2). The visit(Visitable) method behaves like visitLight but updates at each step an environment.

When applying on a term, a strategy returns a Visitable corresponding to the result. In case of failures, these two methods throw a VisitFailure exception.

12.1.2  Environment

An environment is composed of the current position and the current subterm where the strategy is applied. This object corresponds to the class Environment of the package tom.library.sl and can be associated to a strategy using setEnvironment(Environment) and accessed using getEnvitonment(). A position in a term is a sequence of integers that represents the path from the root of the term to the current subterm where the strategy is applied.

The method getPosition() in the Environment class returns a Position object that represents the current position. Due to the method getSubject(), users can also get the current subterm where the strategy is applied.

To retrieve all this information from a strategy, the visit method is necessary.

12.2  Elementary strategy

12.2.1  Elementary strategies from sl

An elementary strategy corresponds to a minimal transformation. It could be Identity (does nothing), Fail (always fails), or a set of rewrite rules (performs an elementary rewrite step only at the root position). In our system, strategies are type-preserving and have a default behavior (introduced by the keyword extends)

The first two elementary strategies are the identity and the failure. There are defined by two corresponding classes in sl library: Identity and Fail. These two strategies have no effect on the term. The identity strategy returns the term unchanged. The failure strategy throws a VisitFailure exception.

12.2.2  Elementary strategies defined by users

Users can define elementary strategies by using the %strategy construction. This corresponds to a list of MatchStatement (one associated to each sort) and can be schematically seen as a set of rewriting rules.

Here is the %strategy grammar:

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 failure: Fail()
• the identity: Identity()

Note that this default behaviour is executed if no rule can be applied or if there is no Java return statement executed in the applied rules.

The body of the strategy is a list of visited sorts. Each StrategyVisit contains a list of VisitAction that will be applied to the corresponding sort. A VisitAction is either a PatternAction or simply a Term (equivalent to the VisitAction { return Term;}). In other words, a StrategyVisit is translated into a MatchStatement.

For instance, here is an elementary strategy RewriteSystem that can be instantiated as follows:

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

  Strategy rule = `RewriteSystem();

%include { util/types/HashSet.tom }

%strategy RewriteSystem(hs:HashSet) extends Identity() {
  visit Term {
    a() -> { hs.add(`a()); }
    b() -> { return `c(); }
  }
}

HashSet hashset = new HashSet();
Strategy rule =`RewriteSystem(hashset);

12.3  Basic strategy combinators

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 (VisitFailure) of the package library.sl.

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:

Sometimes, it is interesting to get the environment where the strategy is applied. The interface Strategy each strategy do implement provides a method getEnvironment() to get the current environment of the strategy. In particular, it is interesting when you want to collect the current position where the strategy is applied. In this case, you can call getEnvironment().getPosition().

This information is also available through the getEnvironment() method from the AbstractStrategy class. To use this method or the following strategies which depend on it, you must call the visit method on your strategy instead of visitLight. That is the difference between visitLight and visit. Only the visit method maintain an environment.

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

The library gives several basic strategies using the position:

12.4  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.

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:

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.

12.5  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.

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 tom.library.sl.*;

We also need to import the corresponding mapping:

  %include { sl.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)));
Strategy rule = `RewriteSystem();
try {
  System.out.println("subject       = " + subject);
  System.out.println("onceBottomUp  = " +
      `OnceBottomUp(rule).visitLight(subject));
  System.out.println("innermost   = " +
      `Choice(BottomUp(rule),Innermost(rule)).visitLight(subject));
} catch (VisitFailure e) {
  System.out.println("reduction failed on: " + subject);
}

12.6  Congruence strategies (generated by Gom)

As mentioned section 11.5, Gom automatically generates congruence and construction strategies for each constructor of the signature.

12.7  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.

public Strategy topDown2BottomUp(Strategy 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; }
  }
}

12.8  Applying a strategy on a user defined data-structures (*)

The simplest way to use strategies is to apply them on data-structures generated by Gom, as this data structure implementation provides the interfaces and classes needed to use ‘%strategy’. In particular, all the data structure classes implement the tom.library.sl.Visitable interface used as argument of visit methods in the tom.library.sl.Strategy interface. However, it is also possible to use ‘%strategy’ with any term implementation.

We detail here on a simple example of hand written data structure and how to use ‘%strategy’ statements and the Tom strategy library.

Given a Java class Person we can define an algebraic mapping for this class:

 %typeterm TomPerson {
   implement { Person }
   equals(t1,t2) { t1.equals(t2) }
 }

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)

12.8.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) }
}

12.8.2  Visiting data-structures by introspection

If the classes representing operators do not implement the tom.library.sl.Visitable interface, there is no special code modification for supporting strategies. Users have just to activate the Tom option –gi.

We can use the tom.library.sl.Introspector interface to apply strategies on such terms:

public Object setChildren(Object o, Object[] children);
public Object[] getChildren(Object o);
public Object setChildAt( Object o, int i, Object child);
public Object getChildAt(Object o, int i);
public int getChildCount(Object o);

In the tom.library.sl.Strategy interface, there exist corresponding methods to visit objects that do not implement the tom.library.sl.Visitable interface:

public Object visit(Object any, Introspector i) throws VisitFailure;
public Object visitLight(Object any, Introspector i) throws VisitFailure;
public Object visit(Environment envt, Introspector i) throws VisitFailure;

In the implementation of these methods, the introspector behaves like a proxy to render any object visitable. When activating the Tom option –gi, the compiler generates in each Tom class an inner class named LocalIntrospector that implements the tom.library.sl.Introspector interface. This class uses informations from the mappings to know how visiting the corresponding classes.

For example, we can define the following ‘%strategy’ statement:

%strategy Rename(oldname:String,newname:String) extends Identity() {
  visit Slot {
    Name(n) -> {
      if(n.equals(oldname)) {
        return `Name(newname);
      }
    }
  }
}

Then by using the generated class LocalIntrospector, it is possible to use the strategy Rename with any strategy combinators:

public static void main(String[] args) {
  Term t = `F(F(G("x"),G("y")),G("x"));
  `TopDown(Rename("x","z")).visit(t, new LocalIntrospector());
}