Here is the midterm for NTU SE737.

Time to solve it: 2 hours. If you take more time, just tell me how
long you worked on it.
(The class in Boston had 90 minutes but only two finished.)

Turn it in before Friday at midnight. Send by email.
Open book and open notes but don't use the Demeter Tools.

If you have made special arrangements
with me, turn it in next week but BEFORE looking at the tape taped
tonight.

Answer form is atthe end.

-- Karl L.
--------------------------------------------------------------------------
Adaptive Object-Oriented Software               Fall 1995
COM 3360/NTU SE737				Karl Lieberherr
---------------------------------------------------------------------------
Midterm Oct. 30, 1995

Question 1:
12 UNKNOWNS, 3 points each	36
Question 2:
26 UNKNOWNS, 3 points each (exepct last one: 20 points) 95
Question 3:
3 UNKNOWNS, 15 points each      45
Question 4:
4 UNKNOWNS, 15 points each      60

				236 total

---------------------------------------------------------------------------
In /course/com1205/hw/project/pde
---------------------------------------------------------------------------
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.

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:
======================================================================
12 UNKNOWNS, 3 points each	36
(directory pde)

Consider the following CD, PP and propagation graphs.
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} .


                         CD-NUMBERED-XREF
   Create a numbered cross reference list for a class dictionary.

-------------------------------------------------------------
 Class Dictionary
-------------------------------------------------------------
     1	Example = <directiveDefs> List(DirectiveDef).
     2	DirectiveDef = <lhs> DirectiveName "=" Directive.
     3	Directive : DirectiveName | StandardDirective | ExtendedDirective.
     4	ExtendedDirective = "(" Directive
     5	  // the following delete vertices or edges from the cd
     6	  // BEFORE the propagation graph is computed.
     7	  // delete all vertices and incident edges in propagation graph of directive
     8	  [ "- vertices" <implicitVertices> Directive ]
     9	  // delete all edges in propagation graph of directive
    10	  [ "- edges" <implicitEdges> Directive ]
    11	  // delete all vertices and incident edges in list
    12	  [ "- enum vertices" <explicitVertices> CommaList(Vertex) ]
    13	  // delete all edges in list
    14	  [ "- enum edges" <explicitEdges> CommaList(Edge) ] ")".
    15	StandardDirective : Simple | Compound.
    16	// from-to
    17	// all conditions need to be satisfied; expressible with intersection
    18	Simple = 
    19	  "[" <source> Vertex "," 
    20	      [ <conds> CommaList(Condition) ] <target> Vertex "]".
    21	Compound : Join | Merge | Intersection | Complement | ToStop.
    22	Join = "(." <args> CommaList(Directive) ")".
    23	Merge = "(+" <args> CommaList(Directive) ")".
    24	Intersection = "(*" <args> CommaList(Directive) ")".
    25	// all paths from source to target which don't satisfy the directive
    26	Complement = "(-" <arg> Directive ")".
    27	// none of the paths is allowed to exit the target
    28	ToStop = "(|" <arg> Directive ")".
    29	Condition : Vertices | Edges *common* Kind.
    30	Kind : Through | Bypassing.
    31	Through = "through".
    32	Bypassing = "bypassing".
    33	Vertices = "vertices" <vertices> CommaList(Vertex).
    34	Edges = "edges" <vertices> CommaList(Edge).
    35	
    36	Vertex = <n> DemIdent.
    37	Edge = "->" <start> Vertex "," <edgeLabel> Label "," <end> Vertex.
    38	Label = <n> DemIdent.
    39	DirectiveName = <n> DemIdent.
    40	
    41	List(S) ~ {S}.
    42	CommaList(S) ~  S {"," S} .

-------------------------------------------------------------
 Cross Reference List
-------------------------------------------------------------
Example 	:1	
DirectiveDef 	:2	1	
Directive 	:3	2	4	8	10	22	23	24	26	28	
ExtendedDirective 	:4	3	
StandardDirective 	:15	3	
Simple 	:18	15	
Compound 	:21	15	
Join 	:22	21	
Merge 	:23	21	
Intersection 	:24	21	
Complement 	:26	21	
ToStop 	:28	21	
Condition 	:29	20	
Kind 	:30	29	
Through 	:31	30	
Bypassing 	:32	30	
Vertices 	:33	29	
Edges 	:34	29	
Vertex 	:36	12	19	20	33	37	37	
Edge 	:37	14	34	
Label 	:38	37	
DirectiveName 	:39	2	3	
List 	:41	1	
CommaList 	:42	12	14	20	22	23	24	33	34	

-------------------------------------------------------------
 Alphabetically Sorted Cross Reference List
-------------------------------------------------------------
Bypassing 	:32	30	
CommaList 	:42	12	14	20	22	23	24	33	34	
Complement 	:26	21	
Compound 	:21	15	
Condition 	:29	20	
Directive 	:3	2	4	8	10	22	23	24	26	28	
DirectiveDef 	:2	1	
DirectiveName 	:39	2	3	
Edge 	:37	14	34	
Edges 	:34	29	
Example 	:1	
ExtendedDirective 	:4	3	
Intersection 	:24	21	
Join 	:22	21	
Kind 	:30	29	
Label 	:38	37	
List 	:41	1	
Merge 	:23	21	
Simple 	:18	15	
StandardDirective 	:15	3	
Through 	:31	30	
ToStop 	:28	21	
Vertex 	:36	12	19	20	33	37	37	
Vertices 	:33	29	

================
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 no 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 : UNKNOWN1
      ExtendedDirective = UNKNOWN2
      StandardDirective : UNKNOWN3
      Compound : UNKNOWN4
      Join = < args > Directive_CommaList . 
      Merge = < args > Directive_CommaList . 
      UNKNOWN5 = < 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 : 
               UNKNOWN6 | 
               StandardDirective | 
               ExtendedDirective . 
      ExtendedDirective = . 
      StandardDirective : UNKNOWN7
      Simple = . 
      Compound : 
               Join | 
               Merge | 
               Intersection | 
               Complement | 
               ToStop *common* . 
      Join = UNKNOWN8. 
      Merge = UNKNOWN9. 
      Intersection = UNKNOWN10. 
      Complement = UNKNOWN11. 
      ToStop = UNKNOWN12. 
      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:
======================================================================
26 UNKNOWNS, 3 points each (exepct last one: 20 points) 95

Consider the CD from question 1 and the following PPS:
(print_sources() is as in question 1)

(@ 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();

Find the UNKNOWNs below:

For the INPUT sentence (e.g., in demeter-input)
which is as C++ object in iExample
(produced by g_parse):

D0 = UNKNOWN1
D81 = (UNKNOWN2 [A,B])
D9 = [A, vertices A,B bypassing, edges -> A,b,B through Z]
D91 = UNKNOWN3

the following output is produced:

(. [ A , B ] , [ X , Y ] ) 
the source is UNKNOWN4 
[ A , B ] 
the source is UNKNOWN5 
[ X , Y ] 
the source is UNKNOWN6 
(| [ A , B ] ) 
the source is UNKNOWN7 
[ A , B ] 
the source is UNKNOWN8
UNKNOWN9
the source is UNKNOWN10 
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the source is UNKNOWN11 
(. [ A , B ] , [ X , Y ] ) 
the target is UNKNOWN12 
[ A , B ] 
the target is UNKNOWN13 
[ X , Y ] 
the target is UNKNOWN14 
(| [ A , B ] ) 
the target is UNKNOWN15 
[ A , B ] 
the target is UNKNOWN16 
[ A , vertices A , B bypassing , edges -> A , b , B through Z ] 
the target is UNKNOWN17 
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the target is UNKNOWN18 
(. [ A , B ] , [ X , Y ] ) 
the directive is well-formed UNKNOWN19
[ A , B ] 
the directive is well-formed UNKNOWN20
[ X , Y ] 
the directive is well-formed UNKNOWN21
(| [ A , B ] ) 
the directive is well-formed UNKNOWN22
[ A , B ] 
the directive is well-formed UNKNOWN23
[ A , vertices A , B bypassing , edges -> A , b , B through Z ] 
the directive is well-formed UNKNOWN24
[ A , vertices A , B through , edges -> A , b , B bypassing Z ] 
the directive is well-formed UNKNOWN25

Implement function check for the Join class.
Check that the immediate subdirectives of the join are well-formed
and check that the target of subdirective i is the same as the source
of subdirective i+1.

Put your answer into UNKNOWN26.


Question 3:
======================================================================
3 UNKNOWNS, 15 points each  	45
(directory pde/cd2)

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 but the program should also work reasonably
for multiple sources and targets.

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? 

There are three changes needed to the propagation patterns.
They are:

UNKNOWN1

UNKNOWN2

UNKNOWN3


Question 4:
=====================================================================
4 UNKNOWNS, 15 points each	60

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)
(remember that an UNKNOWN can be anything and might go over several
lines.)


< 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 : UNKNOWN1
> 

(UNKNOWN1 consists of more than one class definition.)

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

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

UNKNOWN4

===============

--------------------------------------------------------------------------
Object-oriented Systems                         Fall 1995
COM 3360/NTU SE737
---------------------------------------------------------------------------
Oct. 30, 1995

---------------------------------------------------------------------------
Midterm					YOUR NAME:
					YOUR NAME:
					YOUR NAME:
---------------------------------------------------------------------------
Open book and open notes. 

PLEASE GIVE YOUR ANSWERS ON THIS FORM

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

UNKNOWN1 = 


UNKNOWN2 =


UNKNOWN3 =


UNKNOWN4 =


UNKNOWN5 =


UNKNOWN6 =


UNKNOWN7 =


UNKNOWN8 =


UNKNOWN9 =


UNKNOWN10 =


UNKNOWN11 =


UNKNOWN12 =



Question 2: 
==================================================



UNKNOWN1 = 

UNKNOWN2 =

UNKNOWN3 =

UNKNOWN4 =

UNKNOWN5 =

UNKNOWN6 =

UNKNOWN7 =

UNKNOWN8 =

UNKNOWN9 =

UNKNOWN10 =

UNKNOWN11 =

UNKNOWN12 =

UNKNOWN13 =

UNKNOWN14 =

UNKNOWN15 =

UNKNOWN16 =

UNKNOWN17 =

UNKNOWN18 =

UNKNOWN19 =

UNKNOWN20 =

UNKNOWN21 =

UNKNOWN22 =

UNKNOWN23 =

UNKNOWN24 =

UNKNOWN25 =

UNKNOWN26 =














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

UNKNOWN1 = 









UNKNOWN2 =









UNKNOWN3 =



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

UNKNOWN1 = 








UNKNOWN2 =









UNKNOWN3 =