Wednesday, April 9, 2008

Pattern matching on Java objects with Tom

This post presents a quick overview of the mechanism that Tom provides to enable pattern matching on plain Java objects.

Mappings

Tom performs pattern matching on special data structures defined using Gom. However there's a mechanism that allows the mapping parts of an object to data structure that could be used to perform pattern matching.

In section 8.1 Hand-written mappings, a nice explanation of this mechanism . Also there's a very interesting video available from Tom's site where Tom is used to manipulate Java Persistence API objects.

Mappings for java.io.File

For this example we will create mappings for the java.io.File class . The first step is to create the sort definition for the File class.


%typeterm FileSystemElement {
implement { java.io.File }
is_sort(t) { t instanceof java.io.File }
equals(t1,t2) { t1.equals(t2) }
}


Inside of Tom constructs the sort that represents files will be called FileSystemElement. Basic operations must be provided in order to specify: the class that is being mapped (implement), a predicate to determine if is a valid element (is_sort) and an equals criteria (equals).

Now we need to create a operator or constructor that represents files. Here's the definition for that element.


%op FileSystemElement File(name:String, parent:FileSystemElement) {
is_fsym(t) { (t instanceof java.io.File) &&
((java.io.File)t).isFile() }
get_slot(name, t) { t.getName() }
get_slot(parent, t) { t.getParentFile() }
make(name,parent) { new java.io.File(parent,name) }
}


This %op definition says that we're defining a File which belongs to the FileSystemElement sort. In particular we're going to use this definition to represent java.io.File instances that refer to a file, the is_fsym definition verifies this. Now we define two slots one for the name of the file and another to the java.io.File definition of the parent. Finally a make allows us to use the backquote(`) syntax to create instances of File.

A use of this definition is the following:


File f = new File("/tmp/test.txt");

%match(f) {
File(name,parent) -> {
System.out.println("File name "+`name);
System.out.println("Parent "+`parent+" "+`parent.getClass());
}
}


By running this program we get:


File name test.txt
Parent /tmp class java.io.File


Notice that by calling getClass on parent we get java.io.File.

Mapping for directories

Using handwritten mappings allows you to expose only the parts of an object that are interesting for a certain problem. This powerful notion is present in other languages like Scala with the use of Extractors or F# with Active Patterns and originally from Views in Haskell.

For example now we're going to create a definition that represents directories which is another mapping from java.io.File.


%op FileSystemElement Directory(name:String,
parent:FileSystemElement,
children:Children )
{
is_fsym(t) { (t instanceof java.io.File) &&
((java.io.File)t).isDirectory() }
get_slot(name, t) { t.getName() }
get_slot(parent, t) { t.getParentFile() }
get_slot(children, t) { createFromArray(t.listFiles()) }
make(name,parent, children) { new java.io.File(parent,name) }
}


Notice that the is_fsym definition checks identifies a java.io.File instance that refers to a directory. Also notices that for this definition we're exposing the child files and directories.

In order to expose a sequence of elements we need to create a separate mapping. For example the above example mentions the Children sort which is defined as:


%typeterm Children {
implement { java.util.ArrayList<java.io.File> }
is_sort(t) { t instanceof java.util.ArrayList }
equals(t1,t2) { t1.equals(t2) }
}

%oparray Children Children(FileSystemElement*) {
is_fsym(t) { t instanceof ArrayList }
get_element(l,n) { l.get(n) }
get_size(l) { l.size() }
make_empty(n) { new ArrayList<java.io.File>(n) }
make_append(e,l) { addToFileArrayList(e,l) }
}


Notice that the %oparray definition contains special mapping for array-like collections. In section 8.1.4 Using list-matching there's more information about this element and about the %oplist element which allows the mapping of list-like collections.

The addToFileArrayList is a static method that creates an ArrayList from the result of calling java.io.File.listFiles().

Example: listing a directory

With the definitions available above we can write a small program that lists a directory:


File homeDirectory = new File("/home/ldfallas");

%match(homeDirectory) {
Directory(_,_,Children(_*,f,_*)) -> {
%match(f) {
File(name,_) -> { System.out.println("File: "+`name); }
Directory(name,_,_) -> { System.out.println("Directory: "+`name); }
}
}
}


As explained in a previous post, since Children(_*,f,_*) has no restriction on f then the body of the case will be executed for all possible child file of the specified directory.


Example: Files with same name


The following example tries to find two files stored in two separate directories in the same level.


...
%match(homeDirectory) {
Directory(_,_,Children(_*,Directory(dir1,_,Children(_*,File(name,_),_*)),
_*,Directory(dir2,_,Children(_*,File(name,_),_*)),
_*)) -> {

System.out.println("File name "+`name);
System.out.println(`dir1);
System.out.println(`dir2);
}
}


Notice that this little example will show all the pairs of files with the same name stored in two different directories at the same level.

Friday, April 4, 2008

Technorati claim post

Technorati Profile

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.