--------------------------------------------------------------------------
Adaptive Object-Oriented Software Development           Fall 2000
COM 3360 at NU and NTU					Karl Lieberherr
---------------------------------------------------------------------------
Midterm

---------------------------------------------------------------------------
Open book and open notes. 

Question 1: 15 UNKNOWNs, 3 points each: 45 points
Question 2: 15 UNKNOWNs, 4 points each: 60 points
Question 3: 18 UNKNOWNs, 4 points each, 72 points.
Question 4: 2 UNKNOWNs, 20 points each, 40 points
Question 5: 2 UNKNOWNs, 20 points each: 40 points

TOTAL:				        257

/proj/adaptive2/course/com1205/f00/hw/5/html/midterm/

To make the grading easier, please put your values for the
unknowns on the enclosed answer sheet.

THE GAME OF REDUNDANCY AND UNKNOWNS
-----------------------------------

Most of the questions in this exam ask you to determine unknowns
of the form UNKNOWN1, UNKNOWN2, ... This makes it easier for you
to answer the questions, since you get extra context information.
Yet you need to master the behavioral objectives of the course to answer
the questions. Guessing an answer is not a successful strategy and
therefore a "game of redundancy" test is more interesting than
a multiple choice test.

The questions have the following pattern: I show you several artifacts
which are related by the theory of object-oriented design and 
programming. Because of the dependencies between the artifacts,
some of the information is redundant and can be recovered from the
context by applying the objectives covered in the course. 
The information which you should discover is marked UNKNOWNx.

If an unknown is not uniquely determined, mark the answer with *CHOICE*.
An unknown may be anything, e.g., a number, an identifier, a character,
two identifiers with a blank between them,
a string etc. If an unknown is the empty string, give NOTHING as answer,
i.e., UNKNOWN = NOTHING. 

Example:

5 + UNKNOWN1 = 8

UNKNOWN1 = 3

---------------

UNKNOWN2 * UNKNOWN3 = 20

UNKNOWN2 = 4 *CHOICE*
UNKNOWN3 = 5 *CHOICE*

At the beginning of a question we give the number of points per unknown.

Question 1:
===========
15 UNKNOWNs, 3 points each: 45 points

Class dictionary design. Designing the static
structure of an OO application.

Write a class dictionary that can represent the following
purchase orders (in XML style):

<xyz:PurchaseOrder>
    <CustomerName> "Henry Ford" </CustomerName>
    <ShipTo>
        <Street> "5th Ave" </Street>
        <City> "New York" </City>
        <State> "NY "</State>
        <Zip> "10010" </Zip>
    </ShipTo>
    <PurchaseLineItems>
        <Order>
            <Product> "Apple" </Product>
            <Price> 2.00 </Price>
        </Order>
        <Order>
            <Product> "Peach" </Product>
            <Price> 1.50 </Price>
        </Order>
    </PurchaseLineItems>
</xyz:PurchaseOrder>

<PurchaseOrder>
    <CustomerName> "Henry Ford" </CustomerName>
    <ShipTo>
        <Street> "5th Ave" </Street>
        <City> "New York" </City>
        <State> "NY "</State>
        <Zip> "10010" </Zip>
    </ShipTo>
    <PurchaseLineItems>
        <Order>
            <Product> "Apple" </Product>
            <Price> 1.50 </Price>
        </Order>
        <Order>
            <Product> "Peach" </Product>
        </Order>
    </PurchaseLineItems>
</PurchaseOrder>



Your task is to write a class dictionary po.cd such that the above
purchase order is a legal sentence of the class dictionary.
In other words,
If you put the cd into po.cd and the input into po.input
and you parse the input in your Main class, DemeterJ will
accept the input without error message.

Find the unknowns in the following class dictionary:

import edu.neu.ccs.demeter.dj.*;
UNKNOWN1 = .

PurchaseOrders = UNKNOWN2.

PurchaseOrder = 
  "<" UNKNOWN3 "PurchaseOrder>"
  CustomerName
  ShipTo
  PurchaseLineItems
  "</" UNKNOWN4 "PurchaseOrder>".

ObjectId = Ident.

CustomerName = UNKNOWN5.
ShipTo = UNKNOWN6.
Street = UNKNOWN7.
City = UNKNOWN8.
State = UNKNOWN9.
Zip = UNKNOWN10.
PurchaseLineItems = UNKNOWN11.
Order =  UNKNOWN12.
Product = UNKNOWN13.
Price = UNKNOWN14.
List(S) ~ UNKNOWN15.


Question 2:
===========
15 UNKNOWNs, 4 points each: 60 points

Writing a simple program for the class dictionary
of question 1. Writing strategies and visitors.
DemeterJ has been used to generate the Java classes.

Write a program that takes as input a list of purchase orders
(from question 1)
and it computes the total price of all the product items
in the purchase order. If an Order-object does not have a price
(price is optional as shown by the input), then a default price
of 1.0 is assumed. The output for the example from
question 1 should be 6.00.

Find the UNKNOWNs below: Some of the UNKNOWNs are out of order.


Main {
{{
  public static void main(String args[]) throws Exception {
    PurchaseOrders m = PurchaseOrders.parse(System.in);
    System.out.println();
    m.print();
    ClassGraph cg = new ClassGraph(true, false);
    TraversalGraph tg = 
      new TraversalGraph(
      "from UNKNOWN14 bypassing ->*,tail,* to UNKNOWN15", cg);
    System.out.println("total cost = " + m.cost(tg));
    System.out.println(cg);
    System.out.println(tg);
    System.out.println();
    
    // also print all state names and Zip codes
    cg.traverse(m, "from PurchaseOrders via {State, Zip} to " +
    " java.lang.String",
    new Visitor(){
      public void before(String h) { System.out.println(h); } } );
  }
}}
}

PurchaseOrders {
{{
  double cost(TraversalGraph what) {
    Double result = (Double) what.UNKNOWN1(UNKNOWN2, UNKNOWN3 {
      double total;
      public void UNKNOWN4() { total = 0.0;}
      public void before (UNKNOWN5 o) {
	UNKNOWN6 p = o.UNKNOWN7(); 
	if (p != UNKNOWN9) {
	  total = total + p.UNKNOWN10();  
	  } else UNKNOWN11 ;
      }
      public Object UNKNOWN12() { return new Double(UNKNOWN13);}
    });
    return result.doubleValue();
  } 
}}
}


Question 3:
===========
18 UNKNOWNs, 4 points each, 72 points.

Executing a traversal-visitor style program.
Understanding strategies and visitors.

Consider the following class dictionary,
behavior file and input and output.
Find the UNKNOWNS:
The classes have been generated by DemeterJ.
Remember that the -> *,tail,* edges are not
bypassed in the traversal strategies below.

// class dictionary

import edu.neu.ccs.demeter.dj.*;
Input = List(A) EOF.
List(S) ~ "(" S {"," S} ")".
Main = <s> String.
A = ["x" X] ["r" R].
B = ["b" B] D.
R = S.
S = ["t" T] C.
C = D.
X = B.
T = R.
D = .

// behavior file

Main {
  public static void main(String args[]) throws Exception {{
    Input m = Input.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    TraversalGraph tg = new TraversalGraph(
    "{Input -> B B -> D Input -> C C -> D}", cg);
    // System.out.println(cg);
    // System.out.println(tg);
    cg.traverse(m,"{Input->T T->D}", new Visitor() {
      public void before(A h){System.out.println(" new A-Object ");}
      public void before(R h){System.out.println(" before R ");}
      public void before(S h){System.out.println(" before S ");}
      public void before(C h){System.out.println(" before C ");}
      public void before(T h){System.out.println(" before T ");}  });
    System.out.println("bypassing");
    cg.traverse(m,"from Input bypassing T to T", new Visitor() {
      public void before(A h){System.out.println(" new A-Object ");}
      public void before(R h){System.out.println(" before R ");}
      public void before(S h){System.out.println(" before S ");}
      public void before(C h){System.out.println(" before C ");}
      public void before(T h){System.out.println(" before T ");}  });
    System.out.println("to-stop");
    cg.traverse(m,"from Input to-stop T ", new Visitor() {
      public void before(A h){System.out.println(" new A-Object ");}
      public void before(R h){System.out.println(" before R ");}
      public void before(S h){System.out.println(" before S ");}
      public void before(C h){System.out.println(" before C ");}
      public void before(T h){System.out.println(" before T ");}  });
  }}
}

// input

(
r,
r t,
x b,
)

// output

DemeterJ version 0.8.2
Copyright (c) 2000 Northeastern University
Reading project file ps.prj...
Running the test...
 new A-Object 
 before UNKNOWN1 
 before UNKNOWN2 
 new A-Object 
 before UNKNOWN3 
 before UNKNOWN4 
 before UNKNOWN5 
 before UNKNOWN6 
 before UNKNOWN7 
 before UNKNOWN8 
 new A-Object 
 new A-Object 
bypassing
 new A-Object 
 before UNKNOWN9 
 before UNKNOWN10 
 new A-Object 
 before UNKNOWN11 
 before UNKNOWN12 
 before UNKNOWN13 
 new A-Object 
 new A-Object 
to-stop
 new A-Object 
 before UNKNOWN14 
 before UNKNOWN15 
 new A-Object 
 before UNKNOWN16 
 before UNKNOWN17 
 before UNKNOWN18 
 new A-Object 
 new A-Object 



Question 4:
===========
2 UNKNOWNs, 20 points each, 40 points

Consider the class dictionary of question 3
and the strategy in the following class:

Main {
{{
  public static void main(String args[]) throws Exception {
    ClassGraph cg = new ClassGraph(true, false);
    TraversalGraph tg = new TraversalGraph(
    "{A -> B B -> D A -> C C -> D}", cg);
    System.out.println(cg);
    System.out.println(tg);
  }
}}
}

Write a regular expression for the path set defined by the strategy
in the class graph. The source is A and the target is D.
Put your answer into UNKNOWN1.

New subquestion:

Express the regular expression you found in the first part
and express it as a class dictionary that defines the same language
as your regular expression. Put your answer into UNKNOWN2.



Question 5:
===========
2 UNKNOWN, 20 points: 40 points

Understanding traversal strategies. LL(1) conditions.

Consider the following behavior file. There is something
wrong with the strategy which causes DJ to throw an exception.
Explain in UNKNOWN1 what kind of exception it is.
The class graph is the same as in the previous question.

Note: {A->T T->D} = from A through T to D

// behavior file

Main {
{{
  public static void main(String args[]) throws Exception {
    Input m = Input.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    cg.traverse(m,"{A->T T->D}", new Visitor() {
      public void before(A h){System.out.println(" new A-Object ");}
      public void before(R h){System.out.println(" before R ");}
      public void before(S h){System.out.println(" before S ");}
      public void before(C h){System.out.println(" before C ");}
      public void before(T h){System.out.println(" before T ");}  });
  }
}}
}


New subquestion:

Consider the class dictionary from question 3. Consider:
List(S) ~ "(" S {"," S} ")".

Explain why

List(S) ~ "(" {S} ")".

would create a LL(1) violation. Answer in UNKNOWN2.