Question 1:
===========

Consider the following program and the input and
output.

Find the UNKNOWNs in program output (you must understand
the program to do this).

Find the UNKNOWNs in program (for ClassName printing).
You basically write a program.

Print list of classes involved in the traversal
in alphabetical order. (Basically the set of classes
that your project would highlight.)

Find UNKNOWNs in the program to change the Exps-object.
You basically write a program.

Find UNKNOWNs in the displayed object 
(1 point per UNKNOWN, 10 UNKNOWNs). (This is easy).

The final task is to improve the class dictionary.
Eliminate the duplication.

Here is the class dictionary Exps:
======================================================

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

Exps = 
  <exps> CommaList(Exp) 
  [*l "equations" <eqs> CommaList(Equation)].
Exp : Simple | Compound | QuantifierCompound.
Simple : Forward | Backward | 
	 Sequential | Later | UpOverDown .
Forward = 
  "->" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Backward = 
  "<-" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Sequential = "seq" <source> ClassName CommaList(ClassName).
Later = 
  "->X<-" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
UpOverDown = 
  "=>X<=" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Exists = "exists" CommaList(ClassName) *l Exp.

Steps: Unlimited | Limited.
// if steps is absent, the default meaning is unlimited
Unlimited = "*".
Limited = <i> Integer.

Compound = Op <args> CommaList(Exp).
Op : Join | Union.
Join = "join".
Union = "union".

QuantifierCompound : Exists.

Equation = *l <left> Exp "=" *l <right> Exp.
ClassName = Ident.
EdgeName = Ident.

CommaList(S) ~ "(" *l + S {"," *l S *s} - *l ")" .

Main = <s> String.


Program input:
========================================

(join (-> A 3 B, -> B 2 C)
,
exists (X) join (-> A X, <- X B) 
// B before A one hill
,
->X<- A * B // B before A, several hills
,
=>X<= A B // up, over and down: class graph: 
	  // special kind of meta graph 
,
seq A (B, C)
,
// reachability formula "from A to B", B concrete
exists (R1) join ( =>X<= A edge e R1, =>X<= R1 B)
)
equations (
-> A B = =>X<= A B // if B is concrete
,
seq A (Q, C) = join( -> A Q, ->X<- Q C)
)

Program:
========================================

Main {
{{
  static ClassGraph cg;
  public static void main(String args[]) throws Exception {
    Exps es = Exps.parse(System.in);
    ClassGraph g = new ClassGraph(true,false);
    cg = new ClassGraph(true, false);
    cg = new ClassGraph(cg,
	    "from Exps bypassing -> *,tail,* to *");
    cg.traverse(es,"from Exps to Simple", new Visitor() {
    // cg.traverse(es,"from Exps to-stop Exp", new Visitor() {
      public void start() 
	{System.out.println("Testing the evaluator");};
      public void before(Exp host){
	host.print();
        System.out.println(" new Exp ===================== ");
	List l = host.eval();
        for(Iterator i = l.iterator(); i.hasNext();) {
          System.out.print(" ClassName ");
          ((ClassName)i.next()).print();
          System.out.println();
	};
      }
      public void before(Equation host){
        System.out.println(" start of Equation-object +++++++++++++ ");
      } ;});
    cg.traverse(es,"from Exps via Sequential to ClassName", 
    new Visitor() {
      public void start() {
	System.out.println("start with ClassName printing");};
      public void before(ClassName host){
	host.print(); System.out.println();
      }
      public void finish() {
	System.out.println("done with ClassName printing");};
    });
    TraversalGraph tg = 
      new TraversalGraph("from Exps via Sequential to ClassName", cg);
    System.out.println("TraversalGraph");
    System.out.println();
    System.out.println(tg);
    cg.traverse(es,"from Exps to {Forward, Backward}", 
    new Visitor() {
      public void before(Forward host){
	if (host.steps == null) host.set_steps(new Unlimited());
      }
      public void before(Backward host){
	if (host.steps == null) host.set_steps(new Unlimited());
      }
    });
    System.out.println(" modified Exps-object ");
    es.print();
    System.out.println();
    System.out.println(" displayed object ");
    es.display();
    System.out.println(" done ");
  }
}}
}

ClassName {
  void print() to * (PrintVisitor);
}

Exp {
  void print() to * (PrintVisitor);
}

Exps {
  void print() to * (PrintVisitor);
  void display() to * (DisplayVisitor);
}

Exp {
{{
  abstract List eval();
}}
}

Simple {
{{
  abstract List eval();
}}
}

Forward {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); return t;
  };
}}
}

Backward {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); t.add(target); return t;
  };
}}
}

Sequential {
{{
  List eval(){ return new ArrayList();};
}}
}

Later {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); t.add(target); return t;
  };
}}
}

UpOverDown {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(target); return t;
  };
}}
}

Exists {
{{
  List eval(){ return new ArrayList();};
}}
}


Op {
{{
  abstract List apply(List t);
}}
}

Union {
{{
  List apply(List args){
    List r = new ArrayList();
    for(Iterator i = args.iterator(); i.hasNext();)
      r.addAll((List)i.next());
      return r;
  }
}}
}

Join {
{{
  List apply(List args){
    List r = new ArrayList();
    for(Iterator i = args.iterator(); i.hasNext();)
      r.addAll((List)i.next());
      return r;
  }
}}
}


Compound {
{{
  List eval(){
	List t = new ArrayList();
	for(Enumeration e = args.elements();e.hasMoreElements();)
  	  t.add(((Exp)e.nextElement()).eval());
        return op.apply(t);
  }
}}
}

Program output:
========================================

Reading project file program.prj...
Running the test...
Testing the evaluator
join(
	->A 3 B,
	->B 2 C 
) new Exp ===================== 
 ClassName A
 ClassName B
->A 3 B new Exp ===================== 
 ClassName A
->B 2 C new Exp ===================== 
 ClassName B
exists(
	X
)
join(
	->A X,
	<-X B 
) new Exp ===================== 
join(
	->A X,
	<-X B 
) new Exp ===================== 
 ClassName A
 ClassName X
 ClassName B
->A X new Exp ===================== 
 ClassName A
<-X B new Exp ===================== 
 ClassName X
 ClassName B
->X<-A*B new Exp ===================== 
 ClassName A
 ClassName B
=>X<=A B new Exp ===================== 
 ClassName B
seq A(
	B,
	C 
) new Exp ===================== 
exists(
	R1
)
join(
	=>X<=A edge e R1,
	=>X<=R1 B 
) new Exp ===================== 
join(
	=>X<=A edge e R1,
	=>X<=R1 B 
) new Exp ===================== 
 ClassName R1
 ClassName B
=>X<=A edge e R1 new Exp ===================== 
 ClassName R1
=>X<=R1 B new Exp ===================== 
 ClassName B
 start of Equation-object +++++++++++++ 
->A B new Exp ===================== 
 ClassName A
=>X<=A B new Exp ===================== 
 ClassName B
 start of Equation-object +++++++++++++ 
seq A(
	Q,
	C 
) new Exp ===================== 
join(
	->A Q,
	->X<-Q C 
) new Exp ===================== 
 ClassName A
 ClassName Q
 ClassName C
->A Q new Exp ===================== 
 ClassName A
->X<-Q C new Exp ===================== 
 ClassName Q
 ClassName C
start with ClassName printing
A
B
C
A
Q
C
done with ClassName printing
TraversalGraph

Start set: [Exps: {0}]
Copy 0:
 Nodes:
 Exps
 Exp_CommaList
 Nonempty_Exp_CommaList
 Exp
 Simple
 QuantifierCompound
 Exists
 Compound
 Equation_CommaList
 Nonempty_Equation_CommaList
 Equation
 Edges:
 -> Exps,exps,Exp_CommaList
 -> Exp_CommaList,first,Nonempty_Exp_CommaList
 -> Nonempty_Exp_CommaList,it,Exp
 => Exp,Simple
 => Exp,QuantifierCompound
 => QuantifierCompound,Exists
 -> Exists,exp,Exp
 => Exp,Compound
 -> Compound,args,Exp_CommaList
 -> Nonempty_Exp_CommaList,next,Nonempty_Exp_CommaList
 -> Exps,eqs,Equation_CommaList
 -> Equation_CommaList,first,Nonempty_Equation_CommaList
 -> Nonempty_Equation_CommaList,it,Equation
 -> Equation,left,Exp
 -> Equation,right,Exp
 -> Nonempty_Equation_CommaList,next,Nonempty_Equation_CommaList
 Edges to other copies:
 1: => Simple,Sequential
Copy 1:
 Nodes:
 Exp
 Simple
 ClassName
 Sequential
 ClassName_CommaList
 Nonempty_ClassName_CommaList
 Edges:
 -> Sequential,source,ClassName
 -> Sequential,classname_commalist,ClassName_CommaList
 -> ClassName_CommaList,first,Nonempty_ClassName_CommaList
 -> Nonempty_ClassName_CommaList,it,ClassName
 -> Nonempty_ClassName_CommaList,next,Nonempty_ClassName_CommaList
 Edges to other copies:
Finish set: [ClassName: {1}]
 modified Exps-object 
(
	join(
		->A 3 B,
		->B 2 C 
	),
	exists(
		X
	)
	join(
		->A*X,
		<-X*B 
	),
	->X<-A*B,
	=>X<=A B,
	seq A(
		B,
		C 
	),
	exists(
		R1
	)
	join(
		=>X<=A edge e R1,
		=>X<=R1 B 
	)     
)
equations(
	
	->A*B=
	=>X<=A B,
	
	seq A(
		Q,
		C 
	)=
	join(
		->A*Q,
		->X<-Q C 
	) 
)
 displayed object 
: Exps  (
	<exps> : Exp_CommaList  {
		<first> : Nonempty_Exp_CommaList  (
			<it> : Compound  (
				<op> : Join  ( )
				<args> : Exp_CommaList  {
					<first> : Nonempty_Exp_CommaList  (
						<it> : Forward  (
							<source> : ClassName  (
								<ident>  : Ident "A" )
							<steps> : Limited  (
								<i>  : Integer "3" )
							<target> : ClassName  (
								<ident>  : Ident "B" ) )
						<next> : Nonempty_Exp_CommaList  (
							<it> : Forward  (
								<source> : ClassName  (
									<ident>  : Ident "B" )
								<steps> : Limited  (
									<i>  : Integer "2" )
								<target> : ClassName  (
									<ident>  : Ident "C" ) ) ) ) } )
			<next> : Nonempty_Exp_CommaList  (
				<it> : Exists  (
					<classname_commalist> : ClassName_CommaList  {
						<first> : Nonempty_ClassName_CommaList  (
							<it> : ClassName  (
								<ident>  : Ident "X" ) ) }
					<exp> : Compound  (
						<op> : Join  ( )
						<args> : Exp_CommaList  {
							<first> : Nonempty_Exp_CommaList  (
								<it> : Forward  (
									<source> : ClassName  (
										<ident>  : Ident "A" )
									<steps> : Unlimited  ( )
									<target> : ClassName  (
										<ident>  : Ident "X" ) )
								<next> : Nonempty_Exp_CommaList  (
									<it> : Backward  (
										<source> : ClassName  (
											<ident>  : Ident "X" )
										<steps> : Unlimited  ( )
										<target> : ClassName  (
											<ident>  : Ident "B" ) ) ) ) } ) )
				<next> : Nonempty_Exp_CommaList  (
					<it> : Later  (
						<source> : ClassName  (
							<ident>  : Ident "A" )
						<steps> : Unlimited  ( )
						<target> : ClassName  (
							<ident>  : Ident "B" ) )
					<next> : Nonempty_Exp_CommaList  (
						<it> : UpOverDown  (
							<source> : ClassName  (
								<ident>  : Ident "A" )
							<target> : ClassName  (
								<ident>  : Ident "B" ) )
						<next> : Nonempty_Exp_CommaList  (
							<it> : Sequential  (
								<source> : ClassName  (
									<ident>  : Ident "A" )
								<classname_commalist> : ClassName_CommaList  {
									<first> : Nonempty_ClassName_CommaList  (
										<it> : ClassName  (
											<ident>  : Ident "B" )
										<next> : Nonempty_ClassName_CommaList  (
											<it> : ClassName  (
												<ident>  : Ident "C" ) ) ) } )
							<next> : Nonempty_Exp_CommaList  (
								<it> : Exists  (
									<classname_commalist> : ClassName_CommaList  {
										<first> : Nonempty_ClassName_CommaList  (
											<it> : ClassName  (
												<ident>  : Ident "R1" ) ) }
									<exp> : Compound  (
										<op> : Join  ( )
										<args> : Exp_CommaList  {
											<first> : Nonempty_Exp_CommaList  (
												<it> : UpOverDown  (
													<source> : ClassName  (
														<ident>  : Ident "A" )
													<edgename> : EdgeName  (
														<ident>  : Ident "e" )
													<target> : ClassName  (
														<ident>  : Ident "R1" ) )
												<next> : Nonempty_Exp_CommaList  (
													<it> : UpOverDown  (
														<source> : ClassName  (
															<ident>  : Ident "R1" )
														<target> : ClassName  (
															<ident>  : Ident "B" ) ) ) ) } ) ) ) ) ) ) ) ) }
	<eqs> : Equation_CommaList  {
		<first> : Nonempty_Equation_CommaList  (
			<it> : Equation  (
				<left> : Forward  (
					<source> : ClassName  (
						<ident>  : Ident "A" )
					<steps> : Unlimited  ( )
					<target> : ClassName  (
						<ident>  : Ident "B" ) )
				<right> : UpOverDown  (
					<source> : ClassName  (
						<ident>  : Ident "A" )
					<target> : ClassName  (
						<ident>  : Ident "B" ) ) )
			<next> : Nonempty_Equation_CommaList  (
				<it> : Equation  (
					<left> : Sequential  (
						<source> : ClassName  (
							<ident>  : Ident "A" )
						<classname_commalist> : ClassName_CommaList  {
							<first> : Nonempty_ClassName_CommaList  (
								<it> : ClassName  (
									<ident>  : Ident "Q" )
								<next> : Nonempty_ClassName_CommaList  (
									<it> : ClassName  (
										<ident>  : Ident "C" ) ) ) } )
					<right> : Compound  (
						<op> : Join  ( )
						<args> : Exp_CommaList  {
							<first> : Nonempty_Exp_CommaList  (
								<it> : Forward  (
									<source> : ClassName  (
										<ident>  : Ident "A" )
									<steps> : Unlimited  ( )
									<target> : ClassName  (
										<ident>  : Ident "Q" ) )
								<next> : Nonempty_Exp_CommaList  (
									<it> : Later  (
										<source> : ClassName  (
											<ident>  : Ident "Q" )
										<target> : ClassName  (
											<ident>  : Ident "C" ) ) ) ) } ) ) ) ) } ) done