\documentclass{article}

\newcommand{\prog}[1]{\mbox{\sf #1}}

\title{TAO\\ Traversals As Objects}

\begin{document}

\section{Introduction}

The idea of TAO is to make traversals a dynamic entity of the program, rather than a compile time concept. 
In Demeter as it was, traversals and strategies are translated statically into methods at compile time.
Thus, any dynamic control of the traversal must be performed manually- {\bf during the traversal}. 
Since the goal of traversals is to separate the concerns of navigation and computation, it is clearly undesirable to have to have dynamic modifications to the traversal be made at compute time. 

Furthermore, some computations might wish to be parametrised over the traversal. 
In the current scheme, this is almost impossible to express. 

TAO solves both of these problems. 

\section{What TAO does}

TAO allows the programmer to dynamically create Traversal Objects at runtime, and then invoke them on Visitors. 
Since objects are first class values this allows behavior to be parametrised both by navigation (TAO) and computation (Visitor). 

An example of using TAO might be:

\begin{tabbing}
\prog{void} \= \prog{something(Visitor v, Foo f) \{} \\
  \> \prog{Traversal t = Traversal.fromString({\tt "from Foo to Bar bypassing {A,B};"});} \\
  \> \prog{t.traverse(f,v);} \\
\prog{\}}
\end{tabbing}

\section{How TAO does}

TAO works, like almost all the code that I write, by priming the classes statically to partake in dynamic relationships, and then using a number of runtime classes to help implement the relationships. 

Basically, the idea is that \prog{Traversal.fromString(...)} creates a Traversal Object that represents the desired traversal. 
Static information (the .cd file) is used to do the right thing when creating a traversal object. 
This is one place where reflection might (or maybe not) be useful. 
I'll discuss this at the end. 

This traversal object can be used to traverse an object \prog{f}: \prog{t.traverse(f,v)}.
Statically inserted code in the program interprets the traversal object, which is optimised for easy decoding (basically, it is the mother of all cyclic objects- I'm quite proud of the design). 
The object is a set of arrays that reference each other circularly.

Currently, the dynamic aspect of the system is that we can pass TAOs like any other objects, and we can construct the string from which they are instantiated dynamically. 
In the future, it would be cool to be able to perform logical operations like intersection, merge, and difference  on existing TAOs.

\section{Optimisations}

One obvious optimisation is to scan for static strings used to create traversals.
When we see \prog{Traversal.fromString("}{\em some traversal}\prog{")}, that can be replaced by an instantiation of an inner class that subclasses Traversal, and whose traverse method calls a static traversal that does {\em some traversal}.
This should allow TAO to replace all static traversals with no speed hit. 

\section{Using Reflection}

Instead of using static information from the .cd file to create a Traversal from a string, we could use reflection to rederive the .cd file afresh every time. 
The benefit of this would be that we would be able to update the class graph dynamically. 
To not have too much of a performance penalty, we would need to cache the derived class graph and have the static initialiser of each class flush that class when loaded. 

The downside is that the every time the cache is flushed, the next traversal will result in ALL classes being loaded. 
If we garbage collect classes (and hence reload, and hence flush the cache), this could become a burden, as we might end up recomputing the class graph very often. Some kind of class versioning scheme will be needed. 

So, in summarium; using reflection can help, but not without a lot of external support- so much so that I think it easier to just {\bf tell} the system what the class graph is, rather than having it figure it out by itself. 

\section{Details (god) Details}

As god is in the details (but you got it the first time, right?) here follows a brief but thorough example. We will ignore alternation classes for now, since they are the hardest.

First of all, the example: 

\begin{tabbing}
Example \= = Tree.\\
Tree \> ="("  $<$l$>$  Label [ $<$left$>$  LTree] "." [ $<$right$>$  RTree] ")". \\
Label \> =  $<$v$>$  Integer. \\
\\
LTree \> = Tree.\\
RTree \> = Tree.\\
\\
Visitor \> : SummingVisitor. \\
SummingVisitor =  $<$total$>$  Integer.\\
Main \> = . \\
\end{tabbing}

\subsection{Dynamic}

We perform the following traversal:

\prog{Traversal t = Traversal.fromString("from Example to LTree then to Label;");}

Notice that the syntax is different from Demjava. Sorry. 
The above goes from Example to Label via LTree.  

This would construct the following object (using a hashtable to get the circularity right):

\begin{tabbing}
\prog{rtree = null;}\\
\prog{ltree = new Object[2]; ltree[0] = ``ltree''; ltree[1] = tree;}\\
\prog{label = new Object[1]; label[0] = ``label''}\\
\prog{tree  = new Object[4]; tree[0] = ``tree''; tree[1] = label; tree[2] = ltree; tree[3] = rtree;} \\
\\
\prog{example = new Object[2]; example[0] = ``example''; example[1] = tree; }\\
\end{tabbing}

That circular object is then used to traverse the user objects.

\subsection{Static}

Several things are generated by TAO:

\begin{itemize}
\item Several runtime classes. 
Many of these could be put into a jar, but I didn't think of this when I wrote TAO. 
Graph and Traversal need to be generated. 

\begin{itemize}
\item Graph takes care of calculating the subgraph for each leg of the traversal. Graph needs to be generated as it has a representation of the .cd file in it. 
\item Traversal needs to be generated as it references Graph\footnote{and thus needs Graph in order to be compiled.}. It parses the string that is passed to it and creates a cyclic traversal object that is interpreted by the code inserted into each class of the application. 
\end{itemize}

\item Each class is primed with code to interpret the Traversal object. Getting the order of visits to match that of the compiled case took a bit of work, but it can be done by using ALOT of methods. 
\item Each Alternation class ``Foo : Bar $|$ Baz'' requires special attention. 
To controll which subclasses are included in the traversal, we would create the array

\prog{foo = new Object[3]; foo[0] = ``foo''; foo[1] = bar; foo[2] = null;}

if, for example, we wished to only traverse through Bar.  
\end{itemize}

As mentioned before, the traversal is represented by a cyclic object consisting arrays.
Each array has the name of the class it represents in index 0 (for debugging, mainly) and the parts following that. 
Each slot for a part holds either a null if the part is not to be traversed, or an array for the class of the part if it is. 

The idea is to keep the Traversal Object in lockstep with the object being traversed. 
Thus, given a Tree object (this), and a Tree Traversal object (trav), the traversal method goes like this:

\begin{tabbing}
\prog{void} \= \prog{prototrav\_Tree(Object[] trav, Visitor[] visitors) \{}\\
\> \prog{this.runbeforevisitors(visitors);} \\
\> \prog{if (}\= \prog{(this.get\_l()!=null) \&\&}\\
\>            \> \prog{(trav[1]!=null)) this.get\_l().prototrav((Object[]) trav[1],visitors);}\\
\> \prog{if (}\= \prog{(this.get\_left()!=null) \&\&}\\
\>            \> \prog{(trav[2]!=null)) this.get\_left().prototrav((Object[]) trav[2],visitors);}\\
\> \prog{if (}\= \prog{(this.get\_right()!=null) \&\&}\\
\>            \> \prog{(trav[3]!=null)) this.get\_right().prototrav((Object[]) trav[3],visitors);}\\
\> \prog{this.runaftervisitors(visitors);} \\
\prog{\} }
\end{tabbing}

For clarity, we've omitted around methods, which are supported, and edge wrappers,  which are not.
Also, we really only need to check for \prog{this.get\_l()!=null} if \prog{l} is an optional part.


To traverse alternation classes, we use an array that indicates which subclasses, rather than parts, are to be traversed. 

A user class ``A : B $|$ C.'' would thus be traversed:

\begin{tabbing}
\prog{void} \= \prog{prototrav\_A(Object[] trav, Visitor[] visitors) \{}\\
\> \prog{if (}\= \prog{(this instanceof B) \&\&}\\
\>            \> \prog{(trav[1]!=null)) this.prototrav\_B((Object[]) trav[1],visitors);}\\
\> \prog{if (}\= \prog{(this instanceof C) \&\&}\\
\>            \> \prog{(trav[2]!=null)) this.prototrav\_C((Object[]) trav[2],visitors);}\\
\prog{\}}
\end{tabbing}

\end{document}