Software Development                   Fall 2006
CSU 670




Assignment 5

                                  Due date: Oct. 13, 2006
This assignment is stored in file $SD/hw/5

in file assign.html

THEMES:

READING:

Complete the reading from the previous homework.

Use the following header for your homework submission: 

Course number: 
Name:
Assignment number:
Date:
Team members:
Whenever you have questions about course material, please send e-mail to:

mail csu670-grader@ccs.neu.edu

The CHANGES and BUG files (or the same files in the src directory of the DemeterJ distribution) tell you about the history of the project and the bugs we know. The CHANGES file is currently the most reliable source of documentation for DemeterJ. Some parts of the User Manual are dated. The BUGS file.

PART 1:

PURPOSE: Apply the concepts you learned (e.g., the Visitor pattern) at the Java level, without DemeterJ and DJ.

Instead you need to do this homework using the Eclipse Java Development Tools. In the project you will modify Eclipse and this homework gives you again the chance to use Eclipse on a Java project.

This means that you put all your code into *.java files only. No *.beh or *.cd files to write. The *.beh files mentioned below are only given as a hint. You may ignore them. This hw might make you bored writing all the tedious Java code and to make you appreciate the capabilities of DJ and DemeterJ. The advantage of applying the Visitor pattern manually is that you will better understand what DemeterJ and DJ do in the background.

For this homework part you are encouraged to write a Java program from scratch. You should not use any tools except a Java compiler and interpreter (no DemeterJ nor DJ) and of course, a Eclipse and a machine which can run and compile Java.

Write a program for the class dictionary in: $SD/hw/5/visitor-by-hand/program.cd

The relevant classes are: 

A = "a" <b1> B <c1> C [D] "enda".
B : E | F.
C = .
D = "d" .
E = "e".
F = <g1> G <h1> H <a1> A.
G =.
H = "h".
Write three methods (for class A) in one program for this class dictionary but the three methods are allowed to use only one traversal function traverse(Visitor) attached to all of the above classes.

The three tasks to be done by the three methods are:

Test your functions on three different A-objects using code like: 
in class Main:
 static public void main(String args[]) throws Exception {
   A a = ... // write constructor calls to build an A-object. See:
   // /proj/adaptive/www/sources/DemeterJava/examples/j-c-bypassing/program.beh
   // for an example.

   System.out.println("print:");
   a.g_print(); 
   System.out.println();
   System.out.println("tree structure:");
   a.display();
   System.out.println("count:");
   int result = a.countG();
   System.out.println(result + " done ");  
}

   print() should be implemented by a call traverse(p)
   where p is a PrintVisitor-object.

   display() should be implemented by a call traverse(t)
   where t is a DisplayVisitor-object.
 
   countG() should be implemented by a call traverse(s)
   where s is a CountVisitor-object.
To achieve what you want, you need to introduce an abstract Visitor class. For an example, see the abstract UniversalVisitor class which DemeterJ uses. See file program.xcd in the generated directory (usually called gen).

You need an abstract class: 

Visitor : PrintVisitor | DisplayVisitor | CountVisitor.
For the abstract Visitor class you define empty before and after methods which have a host argument. In the subclasses you override the methods where the behavior needs to be non-empty.

Your traversal functions will call the before and after methods of the visitor. First the before method is called, then the traversal is done and then the after method is called.

Turn in your complete Java-program and the output produced for your three test cases.

PART 2:

PURPOSE: Show you how brittle Java programs are. Structural changes are not easy. Maintenance is tedious.

Repeat PART 1 for the class dictionary in: $SD/hw/5/visitor-by-hand2/program.cd

The relevant classes of the cd are: 

A = "a" X C [D].
X = B.
B : E | F.
C = .
D = "d" .
E = "e".
F = G H.
G =.
H = "h".
Notice that the class dictionary is only slightly different from the one in PART 1.

PART 3:

PURPOSE: Show you how DemeterJ simplifies the job.

Now the restriction of using DemeterJ is lifted. You can now take advantage of the brain power which CCS students and faculty have put into DemeterJ. We hope you will be pleased by how the task is now simplified so that you can do it easily yourself in 30 minutes.

Do PART 1 and PART 2 using DemeterJ. Copy the directories:

$SD/hw/5/visitor-by-hand/* and $SD/hw/5/visitor-by-hand2/*

and modify the program.cd and program.beh and program.input files if needed.

To regenerate:

demeterj test

Note that sometimes it is necessary to use "demeterj clean" before "demeterj test".

Please hand in only a short description of the modifications, if any, you did to program.cd and program.beh. What is the number of lines you wrote in your Java program? What is the number of lines in the program.beh and program.cd files? Turn in the two numbers and the ratio of "pure Java" divided by "DemeterJ". Turn in only the files that you changed.

PART 4:

PURPOSE: Experience the behavior of the Java Compiler Compiler JavaCC. The JavaCC input is in gen/*.jj. Study error messages of JavaCC and map them back to the class dictionary level. Learn to debug class diagrams by verifying that desired objects can be represented by the classes in the class diagram.

To be good at object-oriented software development, you need to have several skills, including:

In this part you focus on defining the structure and syntax of your objects, i.e., on how to write class dictionaries. Using a different terminology, we say that you learn to master the data binding aspect.

We first start with simple class dictionaries. Therefore, first do the work described in 17.5.1 and 17.5.2 and 17.5.3 (except 17.5.3.3) on pages 551 and 552 of the AP-book. Use DemeterJ to test your sentences. This will give you an opportunity to learn about the Java Compiler Compiler. Type "javacc" to find out about all the options JavaCC offers. Also visit the JavaCC website. Use

demeterj test

to test your class dictionary and its inputs. It is possible that for some bugs in your class dictionary, the Java Compiler Compiler or Java compiler will complain and not DemeterJ. Turn in your class dictionaries and your sentences and for each class dictionary a statement (comment) which says: My class dictionary was accepted by DemeterJ and the Java Compiler Compiler without warning or error.

See http://www.ccs.neu.edu/research/demeter/DemeterJava/ on how to use DemeterJ.

When writing your class dictionaries, follow the Terminal-Buffer rule described on page 393 of the AP book.

Also follow the following Repetition-Buffer rule: A repetition class should be used as the only part class of a construction class. Example: 

Body                    = "{" [Initialize] PathDirective Wrappers "}".
Wrappers                = [ < wrappers> Wrapper_SList ] .       
Wrapper_SList 		~ Wrapper {  Wrapper } .
Here Wrappers is the buffer class for the wrapper list. The reason for buffering repetition classes is that their names might change later. If we need to pass around wrappers, it is better to pass around Wrappers-objects than Wrapper_SList-object since Wrapper_SList might be renamed to Wrapper_CVector later.

Now after you have gained experience in designing small class dictionaries, we go for a larger one. This class dictionary is about what you learn in the AP-book: propagation patterns.

Adaptive object-oriented programming has three key ingredients: class dictionaries, traversals and visitors. But sometimes, those ingredients require us to write long programs and therefore, we look for abbreviations, also called syntactic sugar. Propagation patterns are such a mechanism to make it easier to program with traversals and visitors.

Consider the task of computing the total of all salaries paid by a company. We need to define a method called sum_salaries for class Company. To implement the method we need to define a visitor class called SummingVisitor. We also need to define a traversal method "allSalaries". The body of method sum_salaries will instantiate the Visitor and call the method allSalaries with the SummingVisitor-object as argument. For a related example, see http://www.ccs.neu.edu/research/demeter/sources/DemeterJava/examples/j-c-holding/ in file holding.beh.

This all can be said with a propagation pattern: 

Company {
  traversal-pp int sum_salaries() {
    initialize (@ 0 @)  // initialize return_val to 0
    to Salary		// traversal
    before Salary (@ return_val = return_val + host.get(v).intValue(): @)
  }
}
Propagation patterns are implemented in DemeterJ (as adaptive methods) and the purpose of this part is to design a part of a class dictionary for a slightly different language than DemeterJ.

Extend the class dictionary below so that it can handle the following input: 

Company {
  traversal-pp int sum_salaries() {
    initialize (@ 0 @)  // initialize return_val to 0
    to Salary		// traversal
    before Salary (@ return_val = return_val + host.get(v).intValue(): @)
  }
}

Shape {
  traversal-pp Integer gp1x(){
    bypassing {-> *,p2,*, -> *,y,*} to Integer
    before Integer (@ return_val = this; @) 
  }
}

ClassGraph {
  traversal-pp void constrClassNames() {
      through :cdef ClassDef  to Construct
      // the class definition is made available in variable cdef
      before Construct
        (@ System.out.println(cdef.getClassName()); @)
  }
}

X {
  traversal-pp int f(float f, int i, A a) {
    initialize (@ 0 @)
    bypassing {X,Y, -> *,r,R} 
    through {:x X, :y Y, -> *,r,:rv R} 
     // the wrappers below may refer to x,y and rv
     to Z
    before {R,S} (@ ... @)
    after {U,V} (@ ... @)
  }
}
The class dictionary: 
// -- class dictionary for DemeterJ with propagation patterns

//////////////////////
// Behavior (methods).
//////////////////////
// man g_print (Demeter/C++) explains the pretty printing commands
// *l *s + -

ProgramBehavior		= [ <behavior> DList(ClassBehavior) ] .

ClassBehavior		= ClassName ClassMethods.

ClassMethods		= "{" *l + [ <methods> SList(Method) ] - "}" .

Method			: Traversal | TraversalPP| Behavior.
Behavior		: Wrapper | Verbatim.


// Class graph traversal specifications.
Traversal		= "traversal" TraversalName TraversalArgs "{" *l
			+ PathDirective ";" - *l
			"}".
TraversalPP		= "traversal-pp" 
			  <returnType> UNKNOWN1
			  UNKNOWN2
			  UNKNOWN3
			  UNKNOWN4.
Args			= "(" [ <l> Commalist(UNKNOWN5) ] ")".
Arg			= <typ> JavaTypeName  <arg> Variable. 
Body			= "{" [UNKNOWN6] UNKNOWN7 UNKNOWN8 "}".
Initialize		= "initialize" UNKNOWN9.

Wrappers		= *l + [ <wrappers> SList(UNKNOWN10) ] -  .

TraversalArgs		= "(" [ <visitors> Commalist(Visitor) ] ")" .

Visitor			= ClassName VisitorName.

PathDirective		= [ BypassingDirective ]
			  [ ThroughDirective ]
			  TargetDirective.

BypassingDirective	= "bypassing" <glob> GlobSpec.
ThroughDirective	= "through" <glob> GlobSpec.

TargetDirective		: To | ToStop *common* <targets> ClassGlobSpec.
To			= "to".
ToStop			= "to-stop".

GlobSpec		: OneGlob | GlobSet.
OneGlob			= Glob.
GlobSet			= "{" [ <globs> Commalist(Glob) ] "}".

Glob			: ClassGlob | EdgeGlob.
EdgeGlob		: PartGlob | SubclassGlob | SuperclassGlob.

ClassGlob		= <dest> ClassNameGlob.
PartGlob		= "->" <source> ClassNameGlob ","
			       <edge> PartNameGlob "," <dest> ClassNameGlob.
SubclassGlob		= "=>" <source> ClassNameGlob "," <dest> ClassNameGlob.
SuperclassGlob		= ":>" <source> ClassNameGlob "," <dest> ClassNameGlob.

ClassNameGlob		: ClassNameExact | AnyClass.
ClassNameExact		= [UNKNOWN11 Variable] ClassName.
AnyClass		= "*".

PartNameGlob		: PartNameExact | AnyPart.
PartNameExact		= PartName.
AnyPart			= "*".

ClassGlobSpec		: OneClassGlob | ClassGlobSet.
OneClassGlob		= ClassGlob.
ClassGlobSet		= "{" <classglobs> Commalist(ClassGlob) "}".


// Before and after wrappers.
Wrapper			: Before | After *common* <hosts> HostSpec JavaCode.

Before			= "before".
After			= "after".

HostSpec		: ClassGlobSpec.


// Verbatim java code.
Verbatim		= JavaCode.


// Terminal buffer classes.
DirName			= <name> Ident.
ClassName		= <name> Ident.
PartName		= <name> Ident.
TraversalName		= <name> Ident.
VisitorName		= <name> Ident.
MethodName		= <name> Ident.
JavaCode		= <code> Text.

JavaTypeName		= <name> Ident.
Variable		= <name> Ident.

// Parameterized class definitions.
List(S) ~ {S}.
SList(S) ~ S { *l S } *l .
DList(S) ~ S { *l *l S } *l .
Commalist(S) ~ S {"," S}.
Barlist(S) ~ S { *l "|" S}.

Main = .
For this part turn in the UNKNOWNs along with the class dictionaries as mentioned earlier.

Discussion

Notice that it is not too hard to translate a propagation pattern back into traversal/visitor style. All the wrappers become the methods in a new visitor class called V. V is defined by: 
V = <return_val> WhatEverType.
If the propagation pattern has arguments, we need an additional visitor class called ArgV which has as many parts as the propagation pattern has arguments. The initalization code is used to initialize return_val.

For example, the propagation pattern: 

Company {
  traversal-pp int sum_salaries() {
    initialize (@ 0 @)  // initialize return_val to 0
    to Salary		// traversal
    before Salary (@ return_val = return_val + host.get(v).intValue(); @)
  }
}
is translated into 
Company {
  (@
    int sum_salaries() {
      SummingVisitor sv = new SummingVisitor( 0 );
      this.allSalaries(sv);
      return sv.get_return_val();
  @)
  traversal allSalaries(SummingVisitor sv) {
    to Salary; }
}
 
SummingVisitor {
  before Salary (@ return_val = return_val + host.get(v).intValue(); @)
}
As this example shows, propagation patterns are an abbreviated form for certain kinds of adaptive programs. But propagation patterns don't take advantage of the full power of visitors: They use only very simple visitors.

Finally you need to write a small program for the above class dictionary. Write a program, using the DJ library that counts how many ClassNameGlob-objects are in a source position. In other words, count how many has-a edges of the form -> *,source,ClassNameGlob are traversed in a given ProgramBehavior object. Test your program on an input and turn in your program, your test input and your output.

PART 5:

Implement a recursive backtrack algorithm for finding
a maximal interpretation (satisfying the maximum weight)
for the standard satisfiability problem. Use
the OR relations (OR1, OR2 and OR3).

I suggest a simple algorithm of the form:

P(f) :
f is a conjunctive normal form with weights on the clauses.
  if f has at least one unassigned variable x {
    P(f[x=1])
    P(f(x=0])
  }
This algorithm would explore the entire search tree of size 2**n
where n is the number of variables in f.

For efficiency reasons, we use the following variant of
the above algorithm that will explore a smaller search space.

I = random interpretation; // currently best interpretation
current_min_weight_unsat = weight of unsatisfied clauses by I;

Precise(f) returns interpretation I 
if f has at least one unassigned variable x {
 consider f reduced for x = 1;
 if weight_unsat(f) < current_min_weight_unsat then 
   Precise(f[x=1]);
   update current_min_weight_unsat and I

 consider f reduced for x = 0; 
 if weight_unsat(f) < current_min_weight_unsat then 
   Precise(f[x=0]);
   update current_min_weight_unsat and I
}

You are welcome to add improvements to this algorithm
but this is not needed. 

Does this algorithm work for any CSP problem captured in
/home/lieber/.www/courses/csu670/f06/hw/2/csp ?

PART 6:

Read the survey paper:
The Quest for Efficient Satisfiability Solvers
http://www.princeton.edu/~chaff/publication/cade_cav_2002.pdf
by L. Zhang and S. Malik, Invited Paper, 
Proceedings of 8th International Conference on Computer Aided Deduction (CADE 2002) 
and also in Proceedings of 14th Conference on Computer Aided Verification (CAV2002), 
Copenhagen, Denmark, July 2002 

The goal of the project is to implement a fast SAT solver in the time that you have available.

Study the following SAT solvers, one in Java and the other in C++.

http://www.sat4j.org/

http://www.sat4j.org/doc/

zchaff from Princeton University (you can also get chaff directly from Princeton)
https://www.ccs.neu.edu/course/csg260/ssl/zchaff/

Let's start with a very modest improvement: Find 2 violations of the Law of Demeter
in the two implementations.
Turn in the violations with an explanation.

Compare with:
http://www.ccs.neu.edu/home/lieber/courses/csu670/f06/coupling-blog/690.aspx.htm

Do you agree with the statement:
Low Coupling Can Cause Unnecessary Complexity?
Turn in your opinion.
==================

Ad-hoc polymorphism

By John Sung

I'll explain the concept of polymorphism in relation to method calls
and how the visitor pattern works. 

If you had these class definitions:

class A { 
  void foo() { System.out.println("A"); }
}

class B extends A {
  void foo() { System.out.println("B"); }
  void bar(A a) { a.foo(); }
}

And if you had these statements in some other place:

A a = new A();
B b = new B();

a.foo();
b.foo();
b.bar(b);

The output of the program would be this:
A
B
B

There are a couple of things going on here in the statement
b.bar(b);. Basically, the compiler attempts to match
bar with the type B, but it doesn't find it. However
it does find a parameter with type A. Since, there's a
is-a relationship between A and B, you can interchange
b with type A. This is what we call implicit casting. 

Now, in the method bar(), we only have a reference to
an object of type A and we call foo() on that object.
The compiler does some tricks to resolve the method
call to the one defined in B instead of the one
defined in A. The compiler does this because the
object is really of type B and not of type A. B just
acts similar to A, i.e. it has the same methods defined.


This pattern occurs twice at the same time during a
traversal. First, in the actual traversal method and
the second time for the visitor inheritance tree. 

Let's say we have this class graph:

A =  B.
B :  C |  D *common*  F.
C = .
D = .
F = .

An object graph looks like this:

A -> B <:- C 
      \
       -> F
 
Assume that there is a traverse(Visitor v) method defined
for all classes. When A calls b.traverse(v), the
actual method that's being called is the one defined
in C and not in B. It's because of the example given
above. But since the object F is defined in B and not
in C so that whole tree is not traversed.

So, you need to use a little feature called super in
Java. You use super.traverse(v).
This just allows you
to call the method defined in the super class.
So, if you put this in C's traverse method, it'll call
B's traverse method and B's traverse method will call
F's traverse method. 

Now, the second time this pattern occurs is when you
have the before and after methods for the visitors.
You have this inheritance relationship:

Visitor : PrintingVisitor

And each of these has before and after methods for all
the classes defined in the previous class dictionary. 

C.traverse() {
v.before(this) ;
}

In this call in C, the before method that gets called
to v, an instance of Visitor, the actual method that
gets called is the one in PrintingVisitor, because
PrintingVisitor over-rides the before(C c) method
defined in Visitor. 

This particular relationship allows you to have only 1
traverse method defined for all classes and have 3
visitor classes for print(), display(), and countG().
Remember that traversal + visitor = work done. The
traversal can be reused in this particular case. 

so, for part one, you should only have traverse method
defined for all classes and only 1 method for print(),
display() and countG() defined in A to start the
traversal. i.e. instantiate the correct visitor and
call a.traverse(v). 

So, if you are defining print(), display(), and
countG() on all of the classes, you're not doing this
assignment correctly. As, some of you have noticed
that if you do this, most of the code are very
similar, infact, they are the same. Only difference is
the fact that you're using different visitors. So, you
use inheritance to factor out these commonalities and
only have one traverse() method instead of 3 methods
all over the class graph.