\documentstyle{article}


\newlength{\growupdown}
\newlength{\growleftright}

\settoheight{\growupdown}{-1 in}
\settowidth{\growleftright}{-1 in}


% Reduce margins by 1/4 inch.
\addtolength{\voffset}{-1.0\growupdown}
\addtolength{\textheight}{2.0\growupdown}
\addtolength{\hoffset}{-1.0\growleftright}
\addtolength{\textwidth}{2.0\growleftright}

\newcommand{\ct}[1]{[{\em #1}]} % will make \cite when ready


\title{First-Class Traversal Strategies}

\author{Johan}

\begin{document}
\maketitle

\begin{abstract}

{\em no! a strategy is not an iterator. a strategy has no nextObject() call.}

The vistor pattern is profitably implemented by parametrising it over an iterator that traverses the application's object graph. 
We present a technique for constructing such iterators at runtime that requires no a-priori knowledge about the application's class graph.
Our technique allows extremely dynamic applications to be written in a mostly static language, such as java.

\end{abstract}

\section{Introduction}

In our experience, a large part of the computation of an OO program is in the seemingly trival task of fetching objects from distant parts of the  object graph.
Keeping the structural assumptions encoded in the fetching code in sync with the class graph of the application as it evolves has been identified as a major contributor to high program-maintenance costs \ct{karl again}.



One way to solve this and related problems is to use {\em succint traversal strategies} to generate the fetching code based on a specification of the class graph. 
Unfortunately, this approach suffers from needing an a-priori description of the class graph.


\section{Three approaches}

We present three approaches to implementing traversals as first class objects.\
They can be organised in a matrix:

\begin{tabular}{p{1.3in}||l|l}
   & Class Graph      & Class Graph\\
   & Known at Compile time   & Discovered at Run time \\
\hline \hline
Strategy Expanded at Compile Time     & {\em unimplemented} & {\em unknown}\\ 
\hline
Strategy Expanded at Run Time         & TAO                 & DJ\\ 
\end{tabular}

The entries in the table are the name of the corresponding implemenation. 

We have restricted the overview to implementations that generate first-class traversal objects. 

\begin{itemize}
\item The upper left box is marked unimplemented as our implementation for that quadrant \ct{Demeter} does not generate separate traversal objects, but rather inserts code into the user's application. However, we expect that an implementation would have roughly the same runtime speed as our current code-inserting implementation. 

\item The upper right box is unknown. We do now know of any situation in which the strategy could be expanded at compile time against a class graph that will only become known at run time, but this is likely just a shortcoming of our imagination. 

\item TAO was implemented with an emphasis towards efficiency. 
      At compile time, it inserts a specialied interpreter into each class of the application. 
      In addition, the traversal specification is translated into a form optimised for fast interpretation. 
      Both of these approaches of course only work if the class graph is known at compile time. 


\item DJ deduces the class graph at run time, as part of its initialisation.
      This allows DJ to be provided as a run time library only.
      However, as it not specialied for any application, it suffers a performance penalty.
\end{itemize}

\section{Why}

Some of the uses of traversals as objects 

1) strategy objects: we can parametrise our behavior by the traversal objects. This for example lets us have generic fetch functions.

2) dynamic behavior modification: by constructing the traversal specifications dynamically, we are able to easily have unforseen behavior variations. 

3) given traversals as first class values, we can further have fun by defining logical operations on them. Intersection, union, difference would all be fun to have. Esp. intersection. 


\section{What's new}

TAO is interesting as it is a traversal interpreter that is partially evaluated by the class graph.
An interesting question is: if we have both DJ and TAO use the same intermediate representation, how much faster is TAO -- ie how much do we gain from the partial evaluation?

As for DJ, what is new? 
We need to look into evolution of long-running processes. 
Basically, if we have a program that can never go down, how can we evolve it? 
If we are able to find a way to punt the java part, then we can say that DJ is a great match for the adaptive part as all we have to do is recompute the cg on each modification.

\section{Implementation}

In this section, we discuss implentenation. There are really only two interesting issues. 1) how does DJ discover the class graph and 2) how does TAO partially evaluate the class graph.

\section{Performance}

The fun comes when we try a number of adaptive programs with demjava, TAO, and DJ. 
It'd be cool if we were able to modify demjava to organise traversals into their own classes. 
That would put all of the participants on an equal footing.
I had a partial, nonworking, version of this a few months ago. 

So we test performance on a few programs. 
Demjava, for example, and perhaps a few others. Suggestions? 

\section{Analysis}

I expect to say: DJ uses reflection, so it is the most dynamic, but look at the performace penalty. 
Ouch!

\end{document}