--------------------------------------------------------------------------
Object-oriented Systems                         Fall 1995
COM 3360/NTU SE737				Karl Lieberherr
---------------------------------------------------------------------------
Midterm

Question 1:
15 UNKNOWNS, 3 points each	45
Question 2:
11 UNKNOWNS, 3 points each	33
Question 3:
30 UNKNOWNS, 2 points each	60
Question 4:
17 UNKNOWNS, 4 points each	68

				206 total

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

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,
e.g., 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
(directory c-oopsla94)

When we develop adaptive software, we work with a CD, PPS,
SENTENCES, INPUT OBJECTS and corresponding OUTPUT OBJECTS. 
During the evolution of adaptive software, behavior preserving transformations
play an important role.

Scenario 1:
We might change the CD to a CD2 so that CD and CD2 have
common sentences, in the sense that the intersection of the languages of the 
two cds is non-empty. We would like to change PPS to PPS2 so that
the output is unchanged on common sentences.

Scenario 2:
We change SENTENCES to SENTENCES2 which implies
to change CD to CD2 so that CD and CD2 have common objects.
We would like to update PPS to PPS2 so that the output is
unchanged on common objects.

In this exam we do an example of scenarios 1 and 2.
Scenario 1 is used in question 3 and scenario 2 in question 4.


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

Consider the following CD, PP and propagation graph.
Find the unknowns.


Example = <directiveDefs> List(DirectiveDef).
DirectiveDef = <lhs> DirectiveName "=" Directive.
Directive : DirectiveName | StandardDirective | ExtendedDirective.
ExtendedDirective = "(" Directive
  // the following delete vertices or edges from the cd
  // BEFORE the propagation graph is computed.
  // delete all vertices and incident edges in propagation graph of directive
  [ "- vertices" <implicitVertices> Directive ]
  // delete all edges in propagation graph of directive
  [ "- edges" <implicitEdges> Directive ]
  // delete all vertices and incident edges in list
  [ "- enum vertices" <explicitVertices> CommaList(Vertex) ]
  // delete all edges in list
  [ "- enum edges" <explicitEdges> CommaList(Edge) ] ")".
StandardDirective : Simple | Compound.
// from-to
// all conditions need to be satisfied; expressible with intersection
Simple = 
  "[" <source> Vertex "," 
      [ <conds> CommaList(Condition) ] <target> Vertex "]".
Compound : Join | Merge | Intersection | Complement | ToStop.
Join = "(." <args> CommaList(Directive) ")".
Merge = "(+" <args> CommaList(Directive) ")".
Intersection = "(*" <args> CommaList(Directive) ")".
// all paths from source to target which don't satisfy the directive
Complement = "(-" <arg> Directive ")".
// none of the paths is allowed to exit the target
ToStop = "(|" <arg> Directive ")".
Condition : Vertices | Edges *common* Kind.
Kind : Through | Bypassing.
Through = "through".
Bypassing = "bypassing".
Vertices = "vertices" <vertices> CommaList(Vertex).
Edges = "edges" <vertices> CommaList(Edge).

Vertex = <n> DemIdent.
Edge = "->" <start> Vertex "," <edgeLabel> Label "," <end> Vertex.
Label = <n> DemIdent.
DirectiveName = <n> DemIdent.

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

================
Propagation patterns:

(@ static Vertex* vdefault =
     new Vertex(new DemIdent("default"));
@)
*operation* void print_sources()
  *traverse*
    *from* Example *to* Directive
  *wrapper* Directive
    (@ cout << this << endl;
       cout << "the source is " << this -> source() << endl; @)

*operation* Vertex* source()
  *init* (@ vdefault; @)
  *traverse*
    *from* Directive
    // to-stop means that there are now outgoing edges
    // in the propagation graph from the to-stop vertices
    *to-stop* {ExtendedDirective, DirectiveName,
      Simple, Join, Merge, Intersection, Complement}
  *wrapper* ExtendedDirective (@ return_val = directive -> source(); @)
  *wrapper* DirectiveName (@ return_val = vdefault; @)
  *wrapper* Simple (@ return_val = source; @)
  *wrapper* Join (@ return_val = args -> car() -> source(); @)
  *wrapper* Merge (@ return_val = args -> car() -> source(); @)
  *wrapper* Intersection (@ return_val = args -> car() -> source(); @)
  *wrapper* Complement (@ return_val = arg -> source(); @)
  *wrapper* ToStop (@ return_val = arg -> source(); @)


Traversal directive:

*from* { Example } *to* { Directive } 

Propagation graph for traversal:

      Example = < directiveDefs > DirectiveDef_List . 
      DirectiveDef = < directive > Directive . 
      Directive : 
               StandardDirective | 
               ExtendedDirective *common* . 
      ExtendedDirective = 
               < directive > Directive 
               [ < implicitVertices > Directive ] 
               [ < implicitEdges > Directive ] . 
      StandardDirective : Compound *common* . 
      Compound : 
               Join | 
               Merge | 
               Intersection | 
               Complement | 
               ToStop *common* . 
      Join = < args > Directive_CommaList . 
      Merge = < args > Directive_CommaList . 
      Intersection = < args > Directive_CommaList . 
      Complement = < arg > Directive . 
      ToStop = < arg > Directive . 
      DirectiveDef_List ~ { DirectiveDef } . 
      Directive_CommaList ~ Directive { Directive } . 


/////////////////////////////////////////////////////////////////
//    There are 27 classes in total
//    There are 13 classes in the propagation graph
//     There are 14 classes not in the propagation graph
//     They are 
//     Simple 
//     Condition 
//     Kind 
//     Through 
//     Bypassing 
//     Vertices 
//     Edges 
//     Vertex 
//     Edge 
//     Label 
//     DirectiveName 
//     Vertex_CommaList 
//     Edge_CommaList 
//     Condition_CommaList 

Traversal directive:

*from* { Directive } 
*to-stop* { ExtendedDirective , DirectiveName , Simple , 
	    Join , Merge , Intersection , Complement } 

Propagation graph for traversal:

      Directive : 
               DirectiveName | 
               StandardDirective | 
               ExtendedDirective *common* . 
      ExtendedDirective = . 
      StandardDirective : 
               Simple | 
               Compound *common* . 
      Simple = . 
      Compound : 
               Join | 
               Merge | 
               Intersection | 
               Complement | 
               ToStop *common* . 
      Join = . 
      Merge = . 
      Intersection = . 
      Complement = . 
      ToStop = < arg > Directive . 
      DirectiveName = . 


/////////////////////////////////////////////////////////////////
//    There are 27 classes in total
//    There are 11 classes in the propagation graph
//     There are 16 classes not in the propagation graph
//     They are 
//     Example 
//     DirectiveDef 
//     Condition 
//     Kind 
//     Through 
//     Bypassing 
//     Vertices 
//     Edges 
//     Vertex 
//     Edge 
//     Label 
//     DirectiveDef_List 
//     Vertex_CommaList 
//     Edge_CommaList 
//     Condition_CommaList 
//     Directive_CommaList 
/////////////////////////////////////////////////////////////
Question 2:
===========

Consider the CD from question 1 and the following PPS:


(@ static Vertex* vdefault =
     new Vertex(new DemIdent("default"));
@)
*operation* void print_sources()
  *traverse*
    *from* Example *to* Directive
  *wrapper* Directive
    (@ cout << this << endl;
       cout << "the source is " << this -> source() << endl; @)

*operation* Vertex* source()
  *init* (@ vdefault; @)
  *traverse*
    *from* Directive
    *to-stop* {ExtendedDirective, DirectiveName,
      Simple, Join, Merge, Intersection, Complement}
  *wrapper* ExtendedDirective (@ return_val = directive -> source(); @)
  *wrapper* DirectiveName (@ return_val = vdefault; @)
  *wrapper* Simple (@ return_val = source; @)
  *wrapper* Join (@ return_val = args -> car() -> source(); @)
  *wrapper* Merge (@ return_val = args -> car() -> source(); @)
  *wrapper* Intersection (@ return_val = args -> car() -> source(); @)
  *wrapper* Complement (@ return_val = arg -> source(); @)
  *wrapper* ToStop (@ return_val = arg -> source(); @)


*operation* void print_targets()
  *traverse*
    *from* Example *to* Directive
  *wrapper* Directive
    (@ cout << this << endl;
       cout << "the target is " << this -> target() << endl; @)

*operation* Vertex* target()
  *init* (@ vdefault @)
  *traverse*
    *from* Directive
    *to-stop* {ExtendedDirective, DirectiveName,
      Simple, Join, Merge, Intersection, Complement}
  *wrapper* ExtendedDirective (@ return_val = directive -> target(); @)
  *wrapper* DirectiveName (@ return_val = vdefault; @)
  *wrapper* Simple (@ return_val = target; @)
  *wrapper* Join (@ return_val = args -> lastexp() -> target(); @)
  *wrapper* Merge (@ return_val = args -> lastexp() -> target(); @)
  *wrapper* Intersection (@ return_val = args -> lastexp() -> target(); @)
  *wrapper* Complement (@ return_val = arg -> target(); @)
  *wrapper* ToStop (@ return_val = arg -> target(); @)

*operation* void print_well_formed()
  *traverse*
    *from* Example *to* Directive
  *wrapper* Directive
    (@ cout << this << endl;
       cout << "the directive is well-formed " << 
	 this -> well_formed() << endl; @)

*operation* int well_formed()
  *init* (@ 0 @)
  *traverse*
    *from* Directive
    *to-stop* {ExtendedDirective, DirectiveName,
      Simple, Join, Merge, Intersection, Complement}
  *wrapper* ExtendedDirective (@ return_val = directive -> well_formed(); @)
  *wrapper* DirectiveName (@ return_val =  1; @)
  *wrapper* Simple (@ return_val = 1; @)
  *wrapper* Join (@ return_val = this -> check(); @)
  *wrapper* Merge (@ return_val = this -> check(); @)
  *wrapper* Intersection (@ return_val = this -> check(); @)
  *wrapper* Complement (@ return_val = arg -> well_formed(); @)
  *wrapper* ToStop (@ return_val = arg -> well_formed(); @)

*operation* int check()
  *init* (@ 0 @)
  *wrapper* Join (@ @)
  *wrapper* Merge (@ @)
  *wrapper* Intersection (@ @)

The PPS are called with:

iExample -> print_sources();
iExample -> print_targets();
iExample -> print_well_formed();

for the sentence which is as C++ object in iExample:


D0 = (. [A,B], [X,Y])
D81 = (| [A,B])
D9 = [A, vertices A,B bypassing, edges -> A,b,B through Z]
D91 = [A, vertices A,B through, edges -> A,b,B bypassing Z]

Find the UNKNOWNs in the following output:

(. [ A , B ] , [ X , Y ] ) 
the source is A 
[ A , B ] 
the source is A 
[ X , Y ] 
the source is X 
(| [ A , B ] ) 
the source is A 
[ A , B ] 
the source is A 
[ A , vertices A , B bypassing , edges -> A , b , B through Z ] 
the source is A 
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the source is A 
(. [ A , B ] , [ X , Y ] ) 
the target is Y 
[ A , B ] 
the target is B 
[ X , Y ] 
the target is Y 
(| [ A , B ] ) 
the target is B 
[ A , B ] 
the target is B 
[ A , vertices A , B bypassing , edges -> A , b , B through Z ] 
the target is Z 
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the target is Z 
(. [ A , B ] , [ X , Y ] ) 
the directive is well-formed 0
[ A , B ] 
the directive is well-formed 1
[ X , Y ] 
the directive is well-formed 1
(| [ A , B ] ) 
the directive is well-formed 1
[ A , B ] 
the directive is well-formed 1
[ A , vertices A , B bypassing , edges -> A , b , B through Z ] 
the directive is well-formed 1
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the directive is well-formed 1

Question 3:
===========

Your programming team asks you to allow from now on multiple sources
and targets in your propagation directives. The old
sentences which use just one source and one target should still
get the same behavior.

Therefore, you change your CD to CD2 as follows:

<   "[" <source> Vertex "," 
<       [ <conds> CommaList(Condition) ] <target> Vertex "]".
---
>   "[" <source> List(Vertex) "," 
>       [ <conds> CommaList(Condition) ] 
>       <target> List(Vertex) "]".

What are the required changes to the PPS in question 2 so that the output
stays the same as in question 2? 

< (@ static Vertex* vdefault =
<      new Vertex(new DemIdent("default"));
---
> (@ static Vertex_List* vdefault = 
>      new Vertex_List(new Vertex(new DemIdent("default")));

< *operation* Vertex* source()
---
> *operation* Vertex_List* source()

< *operation* Vertex* target()
---
> *operation* Vertex_List* target()

Question 4:
==========

You are asked to modify the syntax of your sentences so that 
the sentence

D0 = (. [A,B], [X,Y])
D1 = ([A,B] - vertices [X,Y])
D11 = ([A,B] - enum vertices X,Y)
D12 = ([A,B] - edges [X,Y])
D13 = ([A,B] - enum edges -> A,b,B , -> C,c,C)
D2 = [A,B]
D3 = (+ D1, D2)
D4 = (. D1, D2)
D5 = (* D1, D2)
D6 = (- D1)
D7 = (. ([A,B] - vertices [X,Y]), [B,D])
D8 = (| D8)
D81 = (| [A,B])
D9 = [A, vertices A,B bypassing, edges -> A,b,B through Z]
D91 = [A, vertices A,B through, edges -> A,b,B bypassing Z]

will appear as

D0 = (join [A,B], [X,Y])
D1 = ([A,B] - vertices [X,Y])
D11 = ([A,B] - enum vertices X,Y)
D12 = ([A,B] - edges [X,Y])
D13 = ([A,B] - enum edges -> A,b,B , -> C,c,C)
D2 = [A,B]
D3 = (merge D1, D2)
D4 = (join D1, D2)
D5 = (intersect D1, D2)
D6 = (- D1)
D7 = (join ([A,B] - vertices [X,Y]), [B,D])
D8 = (| D8)
D81 = (| [A,B])
D9 = [A, bypassing vertices (A,B) , through edges ( -> A,b,B) Z]
D91 = [A, through vertices (A,B) , bypassing edges ( -> A,b,B) Z]

The differences are (as produced by diff): 

< D0 = (. [A,B], [X,Y])
---
> D0 = (join [A,B], [X,Y])

< D3 = (+ D1, D2)
< D4 = (. D1, D2)
< D5 = (* D1, D2)
---
> D3 = (merge D1, D2)
> D4 = (join D1, D2)
> D5 = (intersect D1, D2)

< D7 = (. ([A,B] - vertices [X,Y]), [B,D])
---
> D7 = (join ([A,B] - vertices [X,Y]), [B,D])

< D9 = [A, vertices A,B bypassing, edges -> A,b,B through Z]
< D91 = [A, vertices A,B through, edges -> A,b,B bypassing Z]
---
> D9 = [A, bypassing vertices (A,B) , through edges ( -> A,b,B) Z]
> D91 = [A, through vertices (A,B) , bypassing edges ( -> A,b,B) Z]

How would you change the class dictionary?
The differences as given by diff should be (find the UNKNOWNS)


< Join = "(." <args> CommaList(Directive) ")".
< Merge = "(+" <args> CommaList(Directive) ")".
< Intersection = "(*" <args> CommaList(Directive) ")".
---
> 
> Join = "(join" <args> CommaList(Directive) ")".  
> Merge = "(merge" <args> CommaList(Directive) ")".
> Intersection = "(intersect" <args> CommaList(Directive) ")".  
> 

< Condition : Vertices | Edges *common* Kind.
< Kind : Through | Bypassing.
---
> 
> Condition : Through | Bypassing *common* GraphElements. 
> GraphElements : Vertices | Edges. 
> 

< Vertices = "vertices" <vertices> CommaList(Vertex).
< Edges = "edges" <vertices> CommaList(Edge).
---
> Vertices = "vertices" "(" <vertices> CommaList(Vertex) ")" .
> Edges = "edges" "(" <vertices> CommaList(Edge) ")".

How would you change the propagation patterns from question 2 
so that the output on objects which are common to both cds
are the same?

NOTHING