Artan Simeqi
Ping Li


Project: Partial Evaluation of DJ programs.

The idea for partial evaluation of DJ programs was suggested by Prof. Lieberherr.
If we have statements like: 
S s = new TraversalGraph(" to S", cg).fetch(this);
the DJ library builds a traversal graph and then using java.lang.reflect package.
The traversal is quite slow.
If the strategy that is given as an argument to the constructor is supposed to be
fixed (i.e. not to change at runtime), and also the class graph is not supposed to
change, we can make a static evaluation (as opposed to runtime evaluation) of the 
traversal and the classes we have to traverse in order to execute the visitor. In the
simple case of the fetch we propose to create a tool that given a Java program like
this:

import java.io.*;
import edu.neu.ccs.demeter.dj.*;

class A {
    private B b;
    public A(B bin) {
	b=bin;
    }
}

class B {
    private D d;
    private C c;
    public B(C cin, D din) {
	c=cin;
	d=din;
    }
}

class C {}

class D {
    private X x;
    public D(X xin) {
	x=xin;
    }
}

class X {
    private String name;
    public X (String s) {
	name=s;
    }
    public void printName() {
	System.out.println(name);
    }
}


public class Demo {
    public static void main(String[] argv) {
	A a=new A(new B(new C(), new D(new X("DJC"))));
	ClassGraph cg=new ClassGraph(true, false);
	X x= (X) new TraversalGraph("{A -> X}", cg).fetch(a);
	x.printName();
    }
}




will parse it and output a Java program like this:


import java.io.*;
import edu.neu.ccs.demeter.dj.*;

class A {
    private B b;
    public A(B bin) {
	b=bin;
    }
    public X get_X() {
	return b.get_X();
    }
}

class B {
    private D d;
    private C c;
    public B(C cin, D din) {
	c=cin;
	d=din;
    }
    public X get_X() {
	return d.get_X();
    }
}

class C {}

class D {
    private X x;
    public D(X xin) {
	x=xin;
    }
    public X get_X() {
	return x;
    }
}

class X {
    private String name;
    public X (String s) {
	name=s;
    }
    public void printName() {
	System.out.println(name);
    }
}


public class Demo {
    public static void main(String[] argv) {
	A a=new A(new B(new C(), new D(new X("DJC"))));
	ClassGraph cg=new ClassGraph(true, false);
	//X x= (X)new TraversalGraph("from A to X", cg).fetch(a);
	X x=a.get_X();
	x.printName();
    }
}

There are 2 reasons to do this.
The first reason is that the resulting program is going to be much faster.
Another reason is that the debugging of the second program is much easier.
We can inspect by hand which way the traversal goes, so we could discover
i.e surprise paths, or other possible bugs.
To do this we propose to a write a tool which we are going to call PartialEvaluator (PE).
After we write our DJ program and compile it, we run PartialEvaluator.
PE reads the Java files and identifies the Expression to expand. In our case that 
expression is 

(X)new TraversalGraph("from A to X", cg).fetch(a);

Then using DJ, we build the class graph (since it is created by inspecting 
the .class files in the directory). Then using the strategy from the above
expression and the AP library, we build a traversal graph which we think will
be the same one that the DJ program will create at runtime. We use this traversal
graph to identify the classes that will be traversed by DJ and insert in all of
the the appropriate code to retrieve the desired object. The last thing will
be to replace the expression with something like a.get_X();. Note that a is the
argument of fetch, so it should be easily identified.

We preview that several steps are needed to achieve this result:

1. Obtain or produce a .cd file for Java. We got one written by  Binoy Samuel, as
a class project in 1997. The first thing we did with that was to update it for the
changes in DemeterJ. Then we decorated it with the needed symbols so that the
PrintVisitor will print something readable. Then we wrote some code that can insert
a method in some given class (identified by its name). 
We have completed this step.

2. Write code to identify the expression. This turned out to be much harder than
we thought. We needed a thorough study of the .cd file (which is 13 pages in print), 
and in the same time some use of the DisplayVisitor. The analysis tells us
that something very complicated is going on. For a simple file like this:

public class Demo {
    public void test() {
	X x= new TraversalGraph("{A -> X}", cg).fetch(a);
    }
}

the DisplayVisitor prints 184 rows, which means that 184 objects are created.
Although it seems that the organization of the objects is correct, it looks
also a little strange. We do not have the BNF in which this .cd was based,
but a BNF from the book "The Java Language Specification, second edition",
seems to diverge in some points from our .cd .
We are evaluating the possibility to change the .cd in an appropriate way
but this is not an easy task, and we still are not sure if this needs to be 
done. In the other side we could go with the current .cd since now we have
a full understanding of it.
We think that we need to create a production of the type
TraversalGraphFetch at some point in our .cd. The other method would be to use
a CopyVisitor, or a specialized visitor to find such an expression. We think
the first method would be more useful, since because the structure of the found
expression is still very complex, some traversals will be needed to get
it's arguments, and the class TraversalGraphFetch will be a nice starting
point for them. Also once we are done with the expression object we can delete
it, and we are not aware of an easy way to implement a DeleteVisitor (cannot
say delete this; I guess).

3. Find the classes traversed by the traversal. For this we are going to study
the code used in class ObjectGraphSlice by Doug Orleans. Particularly we are
going to study how he implements Algorithm 2 from the paper on Strategies.
We do not expect to follow very strictly his implementation since he does
it at runtime, but we think it will be useful.
Once the nodes and the edges of the traversal are identified we insert the 
code on the classes as described in step 1.


4. Do the same thing, but now not for fetch(), but for gather(). This is
more challenging, but also more useful to understand how this could be
done for general visitors. We do not expect to do anything for the
method traverse().

Other steps that we are sure we are not going to implement:

5. Do same thing for different combinations of Strategy or TraversalGraph.

i.e.

Strategy S= new Strategy(" to X");
X x = (X) new TraversalGraph(S,cg).fetch(a);

or:

TraversalGraph tg=new TraversalGraph("to X", cg);
X x= (X) tg.fetch(a);

We expect this to be very challenging since now the concept of scope 
enters, so we will need to provide some kind of interpreter with it's 
own Environment. Maybe it needs to deal with only a subset of the
language, but still should be quite difficult.