DJ: A Programmers Guide

Therapon Skotiniotis
skotthe@ccs.neu.edu

Introduction

This paper is an attempt to provide a more detailed documentation of DJ's implementation. As such, the following are assumed :

Knowledge of the Java Language [3]
Knowledge of, and experience with, the DJ Library[8] and Adaptive programming[2] in general
Familiarity with UML diagrams and UML[4] notation.

Looking at the code for DJ, and DJ's interaction with the APLibrary[1] package, I hope to provide a new source of information for programmers (or even curious users) that would like to find out about the internals of DJ. At the same time, identifying which classes/code segments, are responsible for which operations/parts of the algorithm that are used by DJ could help to explore alternative approaches in providing a tool for Adaptive Programming (AP). Alternative approaches, or enhancements, can refer both to performance issues of DJ as well as design issues.

With ''performance'' here I refer to the actual execution time of an AP program, written using DJ. People have pointed out that, due to DJ's dependence on Java's Reflection, DJ programs tend to be slow compared to a corresponding DemeterJ program. With ''design issues'', I refer to the possibility to use either a more loosely coupled implementation (if possible) through the deployment of an appropriate Design Pattern. Also, with current AOP technologies, there is also the possibility of making the implementation of DJ more aspectual. As such the implementation will become more robust as well as provide greater functionality than it already has (i.e. considering Java packages as nodes to a traversal graph instead of simply classes, to perform traversals).

The next section introduces the classes, and their central operations, that comprise the DJ package. Section 3 then moves to the related APLibrary classes that interact with DJ. Section 4 looks at the interactions between DJ and the APLibrary at the package level. Finally in Section 5, a discussion on possible enhancements for both increase in performance as well as ideas for extensions of the DJ package.

DJ

The package is made up of 14 Java files. [UML Diagram]

Java File	Description
ClassGraph	Reflectively builds the class graph
Strategy	Parses and creates the strategy Object
Collection	Interface used internally by DJ
StrategyParseException	Exception for Strategy Parsing
FetchException	Thrown by `fetch()` (non-unique paths to an object)
TraversalGraph	The subpaths according to a strategy over a classgraph
IncompatibleClassGraphsException	Class Graph incompatibility
TraversalGraphException	Thrown by empty or error in Traversal Graph
Main	Wrap users main to get loaded classes
TraversalSourceException	Error related to the source node of a traversal
ObjectGraph	Graph of objects confronting to a Class Graph
Visitor	Reflectively calls `before(), after()` methods
ObjectGraphSlice	subgraph of ObjectGraph, defines the strategy graph
VisitorMethodExceptioni	Thrown by Visitor

Narrowing it down to the bear essentials, I'll exclude all the Exception related classes, as these are used to create (and throw) sensible exceptions for error reporting. Also, Main.java, is used as a wrapper class. In essence by extending Java's ClassLoader and wrapping our code around the users main() method, we are able to keep track of all the classes that are to be loaded by the user's program.

`ClassGraph`

The [UML Diagram]ClassGraph, as the name implies, is the object that holds the class graph of the application. The graph actually contains all the classes that your program is using as well as any other classes from the java libraries that are being used. Notice, only the used java library classes is present, not the whole library. By default, classes that are added are the classes found in your current path . as well as the classes that you are using from packages. ¹

The constructors come in many flavors to facilitate the creation of ClassGraphs from whole packages and TraversalGraphs. You are also free to add to your ClassGraph non-static fields as well as non-static non-void non-argument methods via boolean parameters that can be given to the constructor methods.

Both for package addition and class addition, information about the class in question its fields and methods are extracted via reflection. Iterating through the package/current directory we look at all the .class files and reflectively obtain information about that class. The process proceeds as follows :

Reflect on the class that you just found and obtain the class name
Once you have the class name check it against the already seen classes (stored in a HashMap)
Then if the user wants to add non-static fields and non-static non-void non-argument methods, those are added to reflecting on the classes methods and fields variables.
If this class is a subclass, then we have to propagate the inheritance chain and add all superclasses as alternation/inheritance pair.
If the class implements interfaces then the interfaces chain is also propagated and added as alternation/inheritance pairs.

In order to do so the class is actually loaded by the Java Runtime Environment (JVM) and inspected. This step contradicts the JVM policy of ''load on demand'', as a result, after a call to ClassGraph we are forcing the JVM to (a) load all the classes in the path/package (b) reflect on each class (and possible superclasses and interfaces) in order to get class names, methods and members. The above 2 steps (usually) cause a great deal of processing for the JVM resulting in slow execution times and sluggish program behavior.

ClassGraph also provides the facility to add classes from within your program using addClass. Classes that are introduced at runtime via network or by the user need to be incorporated into the current ClassGraph in order to be used for traversals and by adaptive methods in your code.

Finally, a ClassGraph allows you to traverse the classgraph starting from an object, according to some strategy and applying some behavior along the way that is specified by a visitor. The calls to traverse vary in signature in order to facilitate different needs. You also have fetch, gather, asList that help you obtain target object(s) from a ClassGraph. All of these operation are, internally handled by calling ObjectGraph.slice() with the correct parameters.

`ObjectGraph`

[UML Diagram]ObjectGraph has as members a ClassGraph and a ''root'' object. An ObjectGraph consists of object that confronts to a ClassGraph but also has a unique object that we have distinguished as the ''root'' of the ObjectGraph. Operations on a an ObjectGraph are a superset of the traverse operations that one finds in the ClassGraph, albeit now we no longer need to give the starting object as in ClassGraph's case we already have it. Excluding then the setter and getter methods for root and ClassGraph members we are left with yet again all the variations of traverse, gather, asList, fetch .

The important method to look at here is slice that calls ObjectGraphSlice along with a Strategy s. This is the method that all other methods in this object, actually call in order to obtain any result. The actual traversal on the ObjectGraph is performed by the ObjectGraphSlice.

`ObjectGraphSlice`

[UML Diagram]ObjectGraphSlice has as its members a TraversalGraph, an ObjectGraph, a ''root'' object and a NodeSet. The NodeSet² defines a set that holds nodes. Conceptually the ObjectGraphSlice holds the classes that are obtained by following the strategy

while walking the ObjectGraph of a ClassGraph

ObjectGraphSlice is created by giving it an ObjectGraph and a TraversalGraph (or any combination of parameters from which we can extract an ObjectGraph and a TraversalGraph ), thus its constructors can get as parameters an Object and a TraversalGraph , an ObjectGraph and a Strategy or an ObjectGraph and a String.

The major functionality of this class is to traverse the ObjectGraphSlice denoted by the ObjectGraph and TraversalGraph and apply the visitors that have been passed by the user program. In doing this, a Strategy Graph is created that holds all nodes that are mentioned in the Strategy and edges hold constraints³ .Visitors are placed in a visitor array (even when you pass a single visitor for a traversal ObjectGraphSlice created a visitors vector with 1 visitor). Walking through the array in a loop we pick up each visitor and first call its start() method. This initializes, if coded by the user, any state that we want our visitor to have. Then we use a Visitor Traverser, an inner class of ObjectGraphSlice to actually perform the traversal and store the result. As soon as this is completed we loop through the array of visitors and call their corresponding finish() method . Then the traversal return the saved value from the call to VisitorTraverser. The gory details of the actual traversal are found inside the inner classes of ObjectGraphSlice.

Inner Class	Description
Traverser	Abstract Class that holds most of the
	on how to traverse objects, superclasses, edges,
	arrays, collections
Fetcher	Specific behavior to perform `fetch()`
Gatherer	Specific behavior to perform `gather()`
ConcurrentTraverser	Implements a stop and continue iterator
APCollection	A collection implementation to hold target object for
	`asList`
APCollectionIterator	Thread co-routine iterator to use with asList

Thus, a call to fetch() is actually a call to an instance of Fetcher() a call to gather() is in tern a call to an instance of Gatherer and a call to asList is a call to APCollection which in turn uses APCollectionIterator which then used ConcurrentTraverser. All of these inner classes are specializations of the Traverser inner class that has the default behavior of a traversal abstracted.

`Traverser`

The Traverser [UML Diagram] takes care of all the possibilities (i.e. kinds of nodes) that it will come across. We start of with the root node and a set of nodes NodeSet that denote the nodes and edges in the strategy graph. A sketch of the algorithm follows. Look at the node and identify if it is a class or an Array or an Edge or a primitive type. For each node that you reach you can call before and after. These 2 methods get overwritten accordingly by the subclasses of Traverser.

If it is a class then you should check for superclasses and interfaces that it may extend and/or implement. We create a list of all superclasses and interfaces that we iterate through first calling after on each one. Once we have exhausted the whole list of iterators then call before on the original node that we encountered and then in reverse order iterate through your ancestors again and call after.
If you reached a primitive, then we wrap the primitive around a class (this doesn't matter in terms of types since a primitive cannot be any other value) and call before and then after
If you reached an Array then iterate through each of the elements of the array by calling traverseNode on each array member.
Else we have an edge. In the case of an edge we then need to obtain all outgoing edges from the same node and pass them as a set edgeSet. Having the set of outgoing edges we then iterate through them and call traverseEdge. traverseEdge obtains the type of edge (alteration, construction etc.) as well as the targets that it can lead to if we take the edge. All of these information is found in the NodeSet that we carried around from the StrategyGraph. With edges now we have to be careful about Collections as they may cause loops (due to multiple inheritance paths) so we keep track of which ones we have already traversed. Also we need to keep track of the last traversed edge, if it was an inheritance edge then we cannot cross an alternation edge. This will violate the semantics of Object Traversals. All of the above points for edges create calls to traverseCollection, traverseCollectionElement, traverseConstructionEdge ...

`VisitorTraverser`

The VisitorTraverser [UML Diagram] holds an array of visitors that get called iteratively for both before and after methods of the VisitorTraverser. Within the before method we call the corresponding visitors before method and within the after method we call the corresponding visitor's after method. Here we have to also define getReturnValue to call the first visitor's (i.e. visitor[0]) getReturnValue.

`Fetcher`

For the fetch [UML Diagram] method we simply check for multiple paths to our target and if so then raise an error. Thus collections arrays immediately raise an error for now. Else we walk down the edges as before until we get to target and return that object.

`Gatherer`

The Gatherer, [UML Diagram] since we return all targets as a java list we simply walk down according to the strategy and collect target object is a list which we return back to the user.

`ConcurrectTraverser`

Using Point [UML Diagram] as an inner class to store the object at which your iterator was last at, this class mimics ''suspend/resume'' iterator that remembers where it left of last time. This class works hand in hand with the APCollectionIterator which has the daemon thread that creates worker threads of ConcurrentTraverser. The worker threads work to collect the targets which will make up the result for asList call. The difference between the asList and gather is that any modifications made to the result of asList are reflected on the underlying ClassGraph while with gather this is not the case. This created the need for an iterator that would iterate through the set of nodes but without making copies simply group a traversals targets together and return a structure (list) that refers to these targeted objects. In cases of backtracking or even pre-emption the iterator should be able to remember the up to that point valid classes and continue from where it left off last. This dictated the implementation of the ConcurrentTraverser.

`APCollection`

[UML Diagram]Is a local implementation of Java's AbstractSequentialList that creates a collection-view of the ObjectClass reachable by the strategy . As such, the implementation details mimic gather but instead return a part of the ObjectGraphSlice encapsulated in list.

`APCollectionIterator`

Implements an iterator for APCollection following the idea of co-operating a worker thread of ConcurrenstTraverser. Creating a daemon thread that waits upon the worker thread you. The worker thread can stop and resume without lose of state or history and gathers all targets of Strategy which are then returned as a list to the asList method called by the user program.

ObjectGraphSlice also defines methods to obtain the class names of the target objects, obtain by the Strategy object , getters and setters for obtaining and setting the targets of edges.

`Strategy`

The DJ Strategy class inherits from APLib's Strategy class which is responsible for parsing strategy expressions (Strings) and generated the StrategyGraph within APLib⁴.

`TraversalGraph`

The TraversalGraph [UML Diagram] is a set of subpaths of the ClassGraph that are determined by a Strategy. The actual computation of the TravesalGraph is performed by the corresponding class in the APLib. TraversalGraph also provides the traverse, gather, fetch,asList methods by the corresponding calls to the slice method of the DJ package.

`Visitor`

An abstract class [UML Diagram] that defines the methods

start() Called at a traversal for each visitor
finish() Calls at the end of a traversal on each visitor
getReturnValue() Called on the first visitor in the array (visitors[0]) and this is the value returned by the traversal.
before(Object obj, Class cl Reflectively calls the concrete visitors before method
after(Object obj, Class cl)Reflectively calls the concrete visitors after method

All user defined visitors should provide the necessary method implementations from the list above. This will enable the addition of behavior to the traversal when objects are encountered. The objects of interest are given as parameters to the before and after methods. By deploying reflection DJ's visitors are loosely coupled to the classes the operate on, unlike the typical visitors as found in the ''Patterns Book'' [6].

APLibrary

The APLibrary (APLib) [UML Diagram] itself is made up of 2 sub-packages cd, sg, full Java implementations of TraversalGraph, OrderPreservingHashMap and OrderPreservingHashSet, Exceptions for error reporting and interface declarations for each of the APLib components that get manipulated by applications that use the APLibrary. APLib, at the package level, implements the algorithm for creating a ClassGraph from a textual representation to a Java object. A StrategyGraph as a Java Object from a java.String and a TraversalGraph from a ClassGraph and a Strategy to be applied on that ClassGraph.

StrategyGraph and ClassGraph are generated by the cd and sg sub-packages respectively. The implementation of both of these packages is based on DemeterJ. Both of the sub-packages are examined in later later sections. The details of the algorithm used to expand, flatten and generate FTraversalGraph can be found in [7].

The APLib, although used by DJ and partly DemeterJ itself, can also be used as a stand alone library in other applications that need to handle Traversals on Object structures using Strategies. In order to do so, your application should use the interfaces found at the top level of the APLib or inherit from the corresponding classes of APLib directly (i.e. ClassGraph, TraversalGraph etc). The interfaces serve as abstractions of the building blocks for traversal operations.

Java Files	Description
ClassGraphI	A directed graph of Nodes with all edges (as EdgeI objects)
	Each node contains all construction edges.
EdgeI	Methods provided by an edge object inside a `ClassGraph`
	(e.g. `getLabel(), getSource(), getTarget()` etc)
StrategyGraphI	Holds target, source nodes of a strategy as a graph.
	Also a map of the constraints, extracted from the
ConstraintMapI	Allows to check the strategy constraint for a given edge
NameMapI	A mapping of symbolic names within a strategy to
	nodes and edges in the `ClassGraph`
StrategyI	Encapsulates the a strategy (as a graph) a set of
	sources and targets a `NameMap` from names
	to nodes and edges as well as a `ConstraintMap` that
	maps strategy constraints to edges

Considering the sub-packages of APLib as black-boxes (cd, sg), which will each provide you with the a ClassGraph and a StrategyGraph respectively, then using the above interfaces we can manipulate the 2 above given structures to generate a TraversalGraph. The TraversalGraph object will consist of all subpaths inside a classgraph guided by the constraints of a strategy .

`TraversalGraph`

[UML Diagram]

The `cd` Sub-Package

The cd [UML Diagram] package is used to traverse through a textual version of a UML class graph (DemeterJ 's .cd file) and create the Java object representation of the input class graph.

`ClassGraph`

[UML Diagram]Looking at the code, the input text file that holds the representation is first parsed and then normalized(). The normalization step performs the following tasks using DemeterJ traversals.

buildClassDefTable(): Builds a table of class definitions that are encountered in the input
expandParamDefs(): Expands all parametrized class definitions from the ''.cd'' file and returns back a ClassGraph object.
convertRepetition(): This is called on the ClassGraph object which tales care of all repetition classes, making it easier to traverse them without looping indefinetly around them.
fillInPartNames(): Each elements that gets added is of type Part, for practical reasons type names are lowercased and replaced in the ClassGraph object
setInheritanceLinks(): For each alteration edge, replace it with an inheritance link
setBackLinks(): Sets up a table of all tail call back links and two way associations

The resulting ClassGraph object is the returned after all of the above steps are completed. Additional methods ClassGraph are used to add inheritance edges, Part elements and other adding operations that need to be performed by the traversals as defined in the .beh.

The `sg` Sub-Package

The sg [UML Diagram] package holds the role for parsing and generating the StrategyGraph. Like the cd package, sg is implemented using DemeterJ. Crudely describing its functionality, 3 important classes are found in sg. Strategy, Strategy Expression, StrategyGraph, the first being a concrete class that holds the second as a member. StrategyExpression is an abstract class that gets extended by StrategyGraph. The flow of responsibilities starts with Strategy which parses in the strategy that is represented as a java.String. Iterating through the process, Strategy parses in a definition of a strategy

and normalizes it. Normalization here refers to the traversals that are being performed to gather information about the strategy (nodes, restrictions via, through etc.). Then having gathered all this information StrategyGraph walks through creating a graph of all the mentioned nodes and edges in the strategy

adding at the same time the constraints (if any) dictated by

. This generates the StrategyGraph that supervises traversals on the object graph in an AP program.

`StrategyGraph`

[UML Diagram]

DJ and the APLibrary

Looking at the two packages and the way they function together, we see that DJ uses APLib as the backbone for creating an applications classgraph, strategy graph and traversal graph. By the term ''backbone'' here I refer to the fact that, although DJ builds the classgraph by deploying reflection, this is only done in the place of parsing in a static, textual, specification as APLib does by default. Thus we can look at DJ as a more specialized version of DemeterJ, albeit with less features implemented with the current version of DJ than DemeterJ.

In essence, the APLib can take as input textual representations of both a class graph specification and a strategy representation. The results, are a ClassGraph, StrategyGraph as the main components, along with well defined interfaces for obtaining information so that one could create the TraversalGraph (an implementation of which is also available by the APLib).

DJ, performs some more work for us, so as to allow complete and seamless integration with Java. By using Java's reflection package, DJ collects information that are then passed to the APLib in the place of the textual (and static) class graph specification that is used by default in the APLib. Strategies are simply java.String objects and thus DJ has to simply pass then along to the APLib, no other processing needs to be done. APLib will come back with the necessary java object encapsulation of ClassGraph,StrategyGraph. DJ then picks up again in order to add the extra feature of the DJ Visitor and traversal operations. DJ, again exploiting Java's reflection package, uses within ObjectGraphSlice the well formed abstractions that are provided by APLib to process the traversals that the AP program specifies calling the necessary behavior found in the user defined visitor classes.

Conclusion

Some ideas to improve/extend the current implementation of the DJ package, while at the same time, keep DJ as a java package that is easily integrated into any typical Java compiler and Java Virtual Machine (JVM) could be (and these are open to discussion )

An alternative approach to the co-operating thread implementation for the asList implementation. Threads, and as an entailment locking and synchonization in the JVM, degrade the efficiency of your Java applications[5]. A non threaded approach might be faster, at the price of more complicated code inside DJ.
Currently DJ cannot look inside Java jar files, which is common format for most libraries for Java
An attempt to cache traversals in memory (or even write the object as a byte stream file) that could be read/accessed if traversal in an AP application tend to use the same section of the ObjectGraph.
A nice feature to the programmer would be to compose strategies or traversals by taking the union or intersection. This might bring about a performance cost.

Another idea that Doug sketched out, is to use the idea of Aspectual Collaborations in order to define the abstractions that are used by DJ to manipulate the structures returned by the APLibrary. That is the interfaces that DJ uses to refer,for example , to an edge object using the EdgeI. This interfaces are hard coded in APLib. By using Aspectual Collaborations(AC) we could be able to define abstractions to capture not just edges but possible packages. If that can be done with the current AC technology then we could define whole packages as source or targets. Thus extend AP programming to inter package collaborations. Something like this could be of use to people that extend and analyze large APIs.

Other ideas would change either the way by which DJ integrates into the Java Compiler or the JVM. For example, altering the reflection mechanism for java so that information concerning a .class file could be obtained without loading it in the JVM (i.e. directly from the file on the file system). Although this seems more of an extension to the Java Language and Runtime Environment rather than DJ.

Another idea is to have a DJ compiler that simply calls a preprocessor on all the java files and collects information related to the class graph of the application. Collecting class names, methods and such and then passing these pieces of information to DJ. In this way we can use reflection to gather the information only when new classes are created and introduced to the current application. This approach however will have to also manage Java Library classes in some way (either hard code the standard libraries or still use reflection for the standard library classes).

Bibliography

1: The APLibrary.
http://www.ccs.neu.edu/research/demeter/AP-Library/.
2: The Demeter Group.
http://www.ccs.neu.edu/research/demeter.
3: The Java Language.
http://java.sun.com.
4: The OMG Web Page.
http://www.omg.org.
5: Jeff Bogda and Urs Hölzle.
Removing unnecessary synchronization in Java.
ACM SIGPLAN Notices, 34(10):35-46, 1999.
6: R. Gamma E. Helm R. Johnson and Vlissides J.
Design Patterns; Elements of Reusable Object-Oriented Software.
Addison-Wesley Longman, Inc., 1995.
7: Karl J. Lieberherr and Boaz Patt-Shamir.
Traversals of Object Structures: Specification and Efficient Implementation.
Technical Report NU-CCS-97-15, College of Computer Science, Northeastern University, Boston, MA, July 1997.
8: Doug Orleans and Karl Lieberherr.
DJ: Dynamic Adaptive Programming in Java.
Technical Report NU-CCS-2001-02, College of Computer Science, Northeastern University, Boston, MA, March 2001.

About this document ...

DJ: A Programmers Guide

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.42)

The command line arguments were:
latex2html -split 0 writeup.tex

The translation was initiated by root on 2001-12-13

Footnotes

... packages.¹: Actually this happens in a more complicated way. See APLib section
... NodeSet ²: This is defined as an inner class in APLib.TraversalGraph
... constraints ³: See Strategy later on
... APLib ⁴: See the section on APLib

root 2001-12-13