next_inactive up previous


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 :

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]

Table 1: File names in DJ package
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. 1

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 :

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 NodeSet2 defines a set that holds nodes. Conceptually the ObjectGraphSlice holds the classes that are obtained by following the strategy $s$ while walking the ObjectGraph of a ClassGraph $G$.

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 $s$ and edges hold constraints3 .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.


Table 2: Description of inner classes
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.

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 $s$. 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 $s$ 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 APLib4.

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

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.


Table 3: Interfaces in APLib
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 $s$ as a graph.
  Also a map of the constraints, extracted from the $s$
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 $G$ guided by the constraints of a strategy $S$.

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 $s$ 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 $s$ adding at the same time the constraints (if any) dictated by $s$. 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 )

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)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

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

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


Footnotes

... packages.1
Actually this happens in a more complicated way. See APLib section
... NodeSet2
This is defined as an inner class in APLib.TraversalGraph
... constraints3
See Strategy later on
... APLib4
See the section on APLib

next_inactive up previous
root 2001-12-13