Data structure traversal with Tom

Strategies provide a nice mecanism for operations that require data structure traversal. This post presents a brief overview of the strategies implementation in Tom.

Strategies

Tom incorporates the concept of strategy which provides a nice way to perform operations that traverse heterogeneous data structures. These operations could be complete/partial tree transformations or queries.

The paper The Essence of Strategic Programming by Ralf Lämmel, Eelco Visser and Joost Visser gives a very nice implementation-independent definition for the concept. From this paper:

The key idea underlying strategic programming is the separation of problem-specific ingredients of traversal functionality (i.e., basic actions) and reusable traversal schemes (i.e., traversal control).

This paragraph mentions two very interesting characteristics of strategic programming: the separation of problem-specific code from traversal code and the use of reusable traversal schemes.

Example

The following example , taken from the Wikipedia entry for the Visitor pattern, shows how strategies are used to print the parts of a data structure.

Given the following definitions:

module Cars
   imports String
   abstract syntax

  Wheel = Wheel(name:String)

  Engine = Engine()

  Body = Body()

  Wheels = Wheels(Wheel*)

  Vehicle = Car(engine:Engine,body:Body,wheels:Wheels)

We can write the following strategy to print all the parts of a Car:

%strategy PrintStrategy() extends Identity(){ 
    visit Wheel {
       Wheel(name) -> { System.out.println("Visiting " + `name+ " wheel"); }
    }        

    visit Engine {
       Engine() -> {System.out.println("Visiting engine");}
    }

    visit Body {
       Body() -> {System.out.println("Visiting body");}
    }

    visit Vehicle {
       Car(_,_,_) -> { System.out.println("Visiting Car"); } 
    }        
}

We can apply this strategy the following way:

public static void main(String[] a) throws Exception {
   Vehicle v = 
       `Car(Engine(),
            Body(),
            Wheels(Wheel("front left"), 
                   Wheel("front right"),
                   Wheel("back left"),
                   Wheel("back right")));
   `TopDown(PrintStrategy()).visit(v);
}

Running this program shows:

Visiting Car
Visiting engine
Visiting body
Visiting front left wheel
Visiting front right wheel
Visiting back left wheel
Visiting back right wheel

As shown in this example, the problem-specific code is located in the definition of PrintStrategy and the traversal code is reused from the existing TopDown strategy.

The ability of switching traversal schemes is very powerful, for example say that we want to print the parts of the data structure starting with the leafs. We can reuse the existing BottomUp strategy the following way:

...
`BottomUp(PrintStrategy()).visit(v);

This program shows:

Visiting engine
Visiting body
Visiting front left wheel
Visiting front right wheel
Visiting back left wheel
Visiting back right wheel
Visiting Car

Just scratch the surface

A very detailed explanation of this feature is provided in the Introduction to strategies and Strategies in practice sections of the Tom manual.

Also there're several incarnations of this concept in other languages and platforms. For more information check the The Essence of Strategic Programming paper.