| title | permalink |
|---|---|
Documentation:Strategies |
/Documentation: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 . 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 , 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 strategy and strategy combinator. Then, we explain how the sl library can be used in combination with structures.
The package tom.library.sl is mainly composed by an interface Strategy and a class for each strategy combinator.
Every strategy (elementary strategy or combinator) implements the Strategy interface. To apply a strategy on a term (generally called the subject), this interface offers two methods:
Visitable visitLight(Visitable any)visits the subjectanyin a light way (without environment)Visitable visit(Visitable any)visits the subjectanyand manages the environment
A strategy can visit any Visitable object. Any term constructed using a mapping or a 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. The visit(Visitable) method behaves like visitLight but updates at each step an environment.
When applied on a term, a strategy returns a Visitable corresponding to the result. In case of failures, these two methods throw a VisitFailure exception.
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 getEnvironment(). 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. The method getSubject() allows users to get the current subterm where the strategy is applied.
To retrieve all this information from a strategy, the visit method is necessary.
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.
import tom.library.sl.*; // imports the runtime strategy library
public class SimplestStrategies {
// includes description of strategy operators for tom (Identity here)
%include { sl.tom }
%gom { // signature
module Term
imports int
abstract syntax
Term = a()
| b()
| c()
| f(x:Term)
| g(x:Term,y:Term)
}
public static void main(String[] args) throws VisitFailure {
System.out.println(`Identity().visit(`a()));
System.out.println(`Fail().visit(`a()));
}
}
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:
The keyword defines the behavior of the default strategy that will be applied. In most cases, two default behaviors are used:
- the failure:
Fail() - the identity:
Identity()
Note that this default behavior 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(); }
}
}
public static void main(String[] args) throws VisitFailure {
Strategy rule = `RewriteSystem();
System.out.println(rule.visit(`c()));
}
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.
%strategy RewriteSystem() extends Fail() {
visit Term {
a() -> { return `b(); }
}
}
When applying this strategy to different subjects, we obtain:
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.
Strategy s;
try {
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:
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 strategy applies the strategy as many times as possible, until a failure occurs. The last unfailing result is returned.
The strategy tries to apply the strategy once, starting from the leftmost-innermost leaves. looks like but is not similar: is applied to all nodes, starting from the leaves. Note that the application of should not fail, otherwise the whole strategy also fails.
The strategy tries to apply as many times as possible, starting from the leaves. This construct is useful to compute normal forms.
For example, we define = where 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:
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 be transformed by a strategy (into a different term), this is considered as a failure.
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);
}
As mentioned in Section Congruence strategies, automatically generates congruence and construction strategies for each constructor of the signature.
Strategies can be considered as algebraic terms. For instance, the TopDown(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 into BottomUp.
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 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; }
}
}
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 . 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 with any term implementation.
We detail here on a simple example of hand written data structure and how to use 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)
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) }
}
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 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());
}