Out: November 5, 2007
Due: November 13, 2007
For the programming parts turn in your programs with test cases. It is again recommended that you ssh to a CCIS Solaris machine to use all tools: DemeterF, DemeterJ, and DJ.
This homework prepares you for writing interpreters and compilers more effectively. By more effectively, I mean that you need to write less code than with the "follow the grammar" approach because the code is specified by a higher level description. A grammar can be used in two ways to define behavior (besides a parser, printer or editor): a traverser or a transformer.
A traverser navigates through an object and an aspect (a visitor) executes additional interesting code during the traversal. So far we used the traverser approach both with DemeterJ and DJ.
A transformer navigates through an object creating a transformed object. An aspect executes additional interesting code during the transformation: specialized additional transformation (the identity is the default, apply methods), collapsing or reconstructing information from subtraversals and sending it up the tree (combine methods), and sending down additional information (update methods).
The core of the transformer are the combine methods. An example of a transformer is a Boolean transformer that takes Boolean inputs from the leaves of the tree-object and that combines them into one Boolean. Such a transformer may be written very generically. Assume that the object is made up of objects with either one or two parts. The Leaf-objects have two parts, put we consider those parts terminal (that is why we declare Node as a built-in class). Then the entire transformer, which ands together the Booleans from the leaves, can be written in the following short way, even if the class graph contains hundreds of classes:
In main() method:
edu.neu.ccs.demeterf.util.Util.addBuiltIn(Node.class);
// in a class WfCheck that extends IDb
Boolean combine(Object o, Boolean fn, Boolean sn) {
return fn && sn ; }
Boolean combine(Object o, Boolean fn) {
return fn; }
Boolean combine(Leaf lf, Node source, Node target) { lf.g(); }
// do traversal as follows
new edu.neu.ccs.demeterf.Traversal(new WfCheck()).
traverse(this);
// the full path is needed because of the conflict with the
// Traversal class in the DJ package (only if DJ is imported).
The first combine method combines information for objects
with two subtrees by anding the results of the two subtraversals.
The second combine method combines information for objects
with one subtree by passing the Boolean up the tree.
The third combine method gathers a Boolean from leaf objects
and passes it up the tree.
Note the structure-shy nature of such a transformer. Also note that the transformers at this point are not controlled by a traversal strategy in a similar way as a traversal is controlled by a traversal strategy. At the moment, the transformers are controlled by a strategy "from Host to *" but in the future fine-grained control using strategies will be allowed.
In this homework we focus on using a transformation approach developed by Bryan Chadwick. He implemented a tool called DemeterF. In DemeterF, the "aspects" for the transformer are described by 3 function objects. If you run into problems with DemeterF, please email Bryan at: chadwick@ccs.neu.edu as well as Jesse and me. In this homework, we only use 2: the transformer function object (apply methods of IDf) and the builder function object (combine methods of IDb).
To install and use DemeterF, follow: How to use DemeterF.
Study the paper provided here: Paper about DemeterF.
Study the documentation and examples provided on Bryan's DemeterF page: DemeterF home page. AND Compiler example. First read the paper and then read the examples.
PART 1: 5 points
==================================
Purpose: Structure-shy transformation: combining a tree into a Boolean.
Evolution of a structre-shy program.
The program to modify is
here.
The program shows 4 solutions to the first midterm question
(well-formed checker).
(Parallel, independent program implementations using different
technologies are used for systems that must be very reliable.)
In this part we learn to evolve 4 functions:
The first function "boolean well_formed()"
is written in the good old "follow the grammar" approach.
The other functions use the elevation approach in
3 different versions.
The second function "boolean DemeterJwf() to Simple (WfVisitor)"
uses the generator-based traversal approach of DemeterJ.
The third function "Boolean DJwff(ClassGraph cg)" uses
the dynamic traversal approach of DJ.
The fourth function "Boolean DemeterFwff()" uses the transformer
based functional approach of DemeterF.
Now we expand the data types. First we
add a construct called complement, using the "not" operator.
An example is
(not (join -> L X -> X Q)) where we want to express what
we called "bypassing". We want all paths from L to Q that
don't go through X.
So a Complement-object consists of one PathSpec-object.
The definition of well-formed for Complement is:
a Complement is well-formed if the contained PathSpec
is well-formed.
Extend your class dictionary and update the four functions
so that they implement the well-formed concept correctly.
Which of the four functions requires the most maintenance?
Part 2: 5 points
====================================
Purpose: Structure-shy transformation: combining a tree into a Boolean.
Evolution of a structre-shy program.
Extend now the language in addition with Intersection.
Use the following class dictionary:
here
which supports an input like:
(intersect (join -> A K -> K Q)
(join -> A L (not (join -> L X -> X Q))))
The definition of well-formedness for intersections is the same
as for merge (see the program or the midterm).
Now update the four functions that compute the well-formed predicate.
PART 3: 5 points
====================================
Purpose: Structure-shy transformation:
translating a tree into a modified tree.
Now we switch entirely to DemeterF and we use DemeterF
for a transformation task:
A PathSpec with not, join, merge and intersection
is translated into a new PathSpec
where we have the original object modified
in such a way that each join or merge expression is surrounded by a not.
We call this transformation NOT_JOIN_MERGE.
Examples:
BEFORE TRANSLATION
(intersect
(join
->A K
->K Q
)
(join
->A L
(not
(join
->L X
->X Q
)
)
)
)
AFTER TRANSLATION
(intersect
(not
(join
->A K
->K Q
)
)
(not
(join
->A L
(not
(not
(join
->L X
->X Q
)
)
)
)
)
)
BEFORE TRANSLATION
(merge
(join
->A B
->B C
)
(join
->A Q
->Q C
)
)
AFTER TRANSLATION
(not
(merge
(not
(join
->A B
->B C
)
)
(not
(join
->A Q
->Q C
)
)
)
)
Hint:
In the behavior file use:
ComplementMerge { {{
PathSpec apply(UNKNOWN m) {
return new UNKNOWN(m);
}
PathSpec apply(UNKNOWN j) {
return new UNKNOWN(j);
}
}} }
// replace the UNKNOWNs.
PathSpec new_host =
new Traversal(new ComplementMerge()).
traverse(host);
In the class dictionary use:
ComplementMerge = extends IDf.
and import the DemeterF library.
Implement the same transformation also in Scheme,
using a version of the data structure from the midterm.
PART 4: 5 points
=============================================
Purpose: Reasoning about structure-shy programs.
Prove or disprove the following theorem:
NOT_JOIN_MERGE preserves well-formedness, i.e.,
For all path specifications ps:
well-formed(ps) implies well-formed(NOT_JOIN_MERGE(ps)).
Turn in your proof or a counter-example.
Test the theorem experimentally: Run your well-formed checkers
on both ps and NOT_JOIN_MERGE(ps). If the theorem holds,
you should always get the same result unless there is
a bug in one of your well-formed checkers.
PART 5: 5 points
=============================================
Purpose: Structure-shy transformation: combining a tree into a pair of int.
Illustrate that DemeterF works with any Java program.
Consider the capacity checking program
Capacity Checking with DemeterF.
Compile it with: javac ContainerCheck.java
Run it with: java edu.neu.ccs.demeterf.examples.ContainerCheck
The program checks recursively defined containers for capacity violations.
A subcontainer violates the capacity constraint if its total weight is
larger than its container capacity.
The core of the checker is the following pair combiner.
A pair consists of a total weight and the total number of violations.
// Checker, Type-unifying to Pair(int,int)
class Check extends IDb{
public Pair combine(E e, Integer i){ return Pair.make(e.weight,0); }
public Pair combine(C c, Integer ca, Pair wv)
{ return wv.add(0, (wv.w > c.cap)?1:0); }
public Pair combine(IEmpty l){ return Pair.make(0,0); }
public Pair combine(ICons l, Pair f, Pair r){ return f.add(r.w, r.v); }
}
The leaves of the object tree are the EmptyI-objects where we inject (0,0).
For an element (E) we increase the weight of the pair.
For a Container (C) we increase the number
of violations by one if there is one.
The generic way to combine two pairs is to add their components.
public Pair combine(Object l, Pair f, Pair r){ return f.add(r.w, r.v); }
is more structure-shy than:
public Pair combine(ICons l, Pair f, Pair r){ return f.add(r.w, r.v); }
Modify the given program as follows:
Also introduce a weight for each container that adds to the total weight
of the container. Update the capacity checker.
PART 6: 5 points
=============================================
Purpose: Reflection.
Compare advantages and disadvantages of DemeterF compared
to DemeterJ and DJ.
=====================================
A general reminder about DemeterJ: instead of
Join { {{ Node source(){ return get_first().source();} }} }
Merge { {{ Node source(){ return get_first().source();} }} }
you may use:
{Join, Merge} { {{ Node source(){ return get_first().source();} }} }
Last modified: November 2007