Final examination
COM 1204						Karl Lieberherr
Spring 1994
============================================================================


Question 1: 20 UNKNOWNs, 7 points per correct short-cut path
==============================================================================

Consider the following 5 class dictionaries cd1, ... ,cd5 and the
4 propagation patterns f1, ... ,f4.


cd1:

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = K Z.
K = L.
L = <z2> Z.
Z = .
--------------------------------------------------
cd2:

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = D <z1> Z.
D = <z2> Z <k> K.
K = ["l" <l> L].
L = <a> A.
Z = .
--------------------------------------------------
cd3:

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = <d1> D <z1> Z.
D = <k1> K <u1> U.
U = ["a" <a1> A].
K = <z2> Z ["l" <l> L].
L = <u2> U.
Z = .
--------------------------------------------------
cd4:

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = <d1> D <z1> Z.
D = <k1> K.
K = L.
L = Z.
Z = .
V1 : D | U1 *common* <v2> V2.
V2 : U2 | Z.
U1 = "u1".
U2 = "u2".
--------------------------------------------------
cd5:

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = D.
D : K | Z.
K = ["l" L].
L = Z.
Z = .
--------------------------------------------------

The 4 propagation patterns are:

*operation* void f1()
  *traverse*
    *from* Ex *to* Z
  *wrapper* Z
    *prefix*
      (@ cout << this << endl; @)
  *wrapper* A
    *suffix*
      (@ cout << "f1 after traversing A ------------------" << endl; @)

*operation* void f2()
  *traverse*
    *from* Ex *via* K *to* Z
  *wrapper* Z
    *prefix*
      (@ cout << this << endl; @)
  *wrapper* A
    *suffix*
      (@ cout << "f2 after traversing A ------------------" << endl; @)

*operation* void f3()
  *traverse*
    *from* Ex 
      *bypassing* -> K,l,L 
    *to* Z
  *wrapper* Z
    *prefix*
      (@ cout << this << endl; @)
  *wrapper* A
    *suffix*
      (@ cout << "f3 after traversing A ------------------" << endl; @)

*operation* void f4()
  *traverse*
    *from* Ex 
      *through* -> K,l,L 
    *to* Z
  *wrapper* Z
    *prefix*
      (@ cout << this << endl; @)
  *wrapper* A
    *suffix*
      (@ cout << "f4 after traversing A ------------------" << endl; @)

For which combinations of class dictionary and propagation pattern
is there information loss (= inconsistency)
between the propagation directive in the pp and the class dictionary?


	cd1	cd2	cd3	cd4	cd5
-----|-------|-------|-------|-------|------
f1    
-----|-------|-------|-------|-------|------
f2
-----|-------|-------|-------|-------|------
f3
-----|-------|-------|-------|-------|------
f4
-----|-------|-------|-------|-------|------

Mark the squares for which there IS information loss. For example,
between the propagation directive in f1 and cd1 there is no information
loss. Therefore f1/cd1 is not marked.
If there is information loss, give a short-cut path, e.g.
A,D,K,Z means that the short-cut path goes from A to D to K to Z.

Put your answer for propagation directive in fi and class
dictionary cdj into UNKNOWNij.
For example UNKNOWN13 contains nothing if there is no information loss
for f1 and cd3 and otherwise, UNKNOWN13 contains a short-cut path.

Question 2: 1 UNKNOWN, 20 points
===============================================================

Consider the following two class dictionaries:

cd1/abstract

A = K.
K = O.
O = Z.
Z = .


cd2/abstract
A = B <z1> Z.
B = K <z2> Z.
K = L.
L = O.
O = S <z3> Z.
S = <z4> Z.
Z = .


Propagation graph for cd1/abstract:

*source* { A } 
*target* { Z } 
      A = < k > K . 
      K = < o > O . 
      O = < z > Z . 
      Z = . 

Propagation graph for cd2/abstract:

*source* { A } 
*target* { Z } 
      A = < b > B . 
      B = < k > K . 
      K = < l > L . 
      L = < o > O . 
      O = < s > S < z3 > Z . 
      S = < z4 > Z . 
      Z = . 

Find a propagation directive  which computes the two propagation graphs
for the two class dictionaries above.

The propagation directive is: *from* UNKNOWN1

Question 3: 17 UNKNOWNs, 4 points each
=======================================================

Read first the entire question.

Consider the following sentence

{
FROM {A,B} TO {C,D},
(MERGE
  FROM {A} TO {B},
  FROM {A} TO {C}),
(MERGE
  (JOIN
    FROM {A} TO {B},
    FROM {B} TO {C}),
  (JOIN
    FROM {A} TO {X},
    FROM {X} TO {C}))
}

and the following class dictionary:

Ex = PCommaList(E).
E : UNKNOWN1 | J | M.
S = UNKNOWN2 <sources> PCommaList(UNKNOWN3)
    UNKNOWN4 <targets> PCommaList(UNKNOWN5).
J = UNKNOWN6 <arg1> UNKNOWN7 <arg2> UNKNOWN8.
M = <m1> M1.
M1 = "(MERGE" <arg1> E UNKNOWN9 <arg2> E ")".
Vertex = DemIdent.

PCommaList(S) ~ UNKNOWN10 S {UNKNOWN11 S} UNKNOWN12.

The sentence is legal with respect to the class dictionary.
Find the UNKNOWNS.

The following propagation pattern finds all MERGE expressions and 
for each such merge expression it finds all containing FROM-TO
expressions which are not contained in a nested MERGE expression.
Find the UNKNOWNs in the program output.


*operation* void FROMinsideMERGE()
  *traverse*
    *from* Ex
    *to* M1
  *wrapper* M1
    *prefix*
      (@ this -> find_FROM(); @)

*operation* void find_FROM()
  *traverse*
    *from* M1
      *bypassing* -> *,m1,*
    *to* S
    // begin transportation pattern
    *carry* *in* M1* merge = (@ this @)
    *along* 
      *from* M1
      *to* S
    *wrapper* S
      *prefix*
	(@ cout << "basic " << this << endl
		<< "contained in " << merge << endl; @)
    // end transportation pattern

Program output:


: Ex ( 
   < e_pcommalist > : E_PCommaList { 
      : S ( 
         < sources > : Vertex_PCommaList { 
            : Vertex ( 
               < demident > : DemIdent "A" ) , 
            : Vertex ( 
               < demident > : DemIdent "B" ) } 
         < targets > : Vertex_PCommaList { 
            : Vertex ( 
               < demident > : DemIdent "C" ) , 
            : Vertex ( 
               < demident > : DemIdent "D" ) } ) , 
      : M ( 
         < m1 > : M1 ( 
            < arg1 > : S ( 
               < sources > : Vertex_PCommaList { 
                  : Vertex ( 
                     < demident > : DemIdent "A" ) } 
               < targets > : Vertex_PCommaList { 
                  : Vertex ( 
                     < demident > : DemIdent "B" ) } ) 
            < arg2 > : S ( 
               < sources > : Vertex_PCommaList { 
                  : Vertex ( 
                     < demident > : DemIdent "A" ) } 
               < targets > : Vertex_PCommaList { 
                  : Vertex ( 
                     < demident > : DemIdent "C" ) } ) ) ) , 
      : M ( 
         < m1 > : M1 ( 
            < arg1 > : M ( 
               < m1 > : M1 ( 
                  < arg1 > : S ( 
                     < sources > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "A" ) } 
                     < targets > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "B" ) } ) 
                  < arg2 > : S ( 
                     < sources > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "B" ) } 
                     < targets > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "C" ) } ) ) ) 
            < arg2 > : M ( 
               < m1 > : M1 ( 
                  < arg1 > : S ( 
                     < sources > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "A" ) } 
                     < targets > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "X" ) } ) 
                  < arg2 > : S ( 
                     < sources > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "X" ) } 
                     < targets > : Vertex_PCommaList { 
                        : Vertex ( 
                           < demident > : DemIdent "C" ) } ) ) ) ) ) } ) 

>> void Ex::FROMinsideMERGE()
 >> void E_PCommaList::FROMinsideMERGE()
  >> void E::FROMinsideMERGE()
   >>  at S , ***  PREMATURELY TERMINATED *** 
   <<  at S , ***  PREMATURELY TERMINATED *** 
  << void E::FROMinsideMERGE()
  >> void M::FROMinsideMERGE()
   >> void M1::FROMinsideMERGE()
    >> void M1::find_FROM()
     >> void S::find_FROM(M1*  merge)
UNKNOWN13
contained in (MERGE FROM { A } TO { B } , FROM { A } TO { C } ) 
     << void S::find_FROM(M1*  merge)
     >> void S::find_FROM(M1*  merge)
UNKNOWN14
contained in (MERGE FROM { A } TO { B } , FROM { A } TO { C } ) 
     << void S::find_FROM(M1*  merge)
    << void M1::find_FROM()
    >> void E::FROMinsideMERGE()
     >>  at S , ***  PREMATURELY TERMINATED *** 
     <<  at S , ***  PREMATURELY TERMINATED *** 
    << void E::FROMinsideMERGE()
    >> void E::FROMinsideMERGE()
     >>  at S , ***  PREMATURELY TERMINATED *** 
     <<  at S , ***  PREMATURELY TERMINATED *** 
    << void E::FROMinsideMERGE()
   << void M1::FROMinsideMERGE()
  << void M::FROMinsideMERGE()
  >> void M::FROMinsideMERGE()
   >> void M1::FROMinsideMERGE()
    >> void M1::find_FROM()
     >> void E::find_FROM(M1*  merge)
      >>  at M , ***  PREMATURELY TERMINATED *** 
      <<  at M , ***  PREMATURELY TERMINATED *** 
     << void E::find_FROM(M1*  merge)
     >> void E::find_FROM(M1*  merge)
      >>  at M , ***  PREMATURELY TERMINATED *** 
      <<  at M , ***  PREMATURELY TERMINATED *** 
     << void E::find_FROM(M1*  merge)
    << void M1::find_FROM()
    >> void M::FROMinsideMERGE()
     >> void M1::FROMinsideMERGE()
      >> void M1::find_FROM()
       >> void S::find_FROM(M1*  merge)
UNKNOWN15
contained in (MERGE FROM { A } TO { B } , FROM { B } TO { C } ) 
       << void S::find_FROM(M1*  merge)
       >> void S::find_FROM(M1*  merge)
basic FROM { B } TO { C } 
contained in (MERGE FROM { A } TO { B } , FROM { B } TO { C } ) 
       << void S::find_FROM(M1*  merge)
      << void M1::find_FROM()
      >> void E::FROMinsideMERGE()
       >>  at S , ***  PREMATURELY TERMINATED *** 
       <<  at S , ***  PREMATURELY TERMINATED *** 
      << void E::FROMinsideMERGE()
      >> void E::FROMinsideMERGE()
       >>  at S , ***  PREMATURELY TERMINATED *** 
       <<  at S , ***  PREMATURELY TERMINATED *** 
      << void E::FROMinsideMERGE()
     << void M1::FROMinsideMERGE()
    << void M::FROMinsideMERGE()
    >> void M::FROMinsideMERGE()
     >> void M1::FROMinsideMERGE()
      >> void M1::find_FROM()
       >> void S::find_FROM(M1*  merge)
UNKNOWN16
contained in (MERGE FROM { A } TO { X } , FROM { X } TO { C } ) 
       << void S::find_FROM(M1*  merge)
       >> void S::find_FROM(M1*  merge)
UNKNOWN17
contained in (MERGE FROM { A } TO { X } , FROM { X } TO { C } ) 
       << void S::find_FROM(M1*  merge)
      << void M1::find_FROM()
      >> void E::FROMinsideMERGE()
       >>  at S , ***  PREMATURELY TERMINATED *** 
       <<  at S , ***  PREMATURELY TERMINATED *** 
      << void E::FROMinsideMERGE()
      >> void E::FROMinsideMERGE()
       >>  at S , ***  PREMATURELY TERMINATED *** 
       <<  at S , ***  PREMATURELY TERMINATED *** 
      << void E::FROMinsideMERGE()
     << void M1::FROMinsideMERGE()
    << void M::FROMinsideMERGE()
   << void M1::FROMinsideMERGE()
  << void M::FROMinsideMERGE()
 << void E_PCommaList::FROMinsideMERGE()
<< void Ex::FROMinsideMERGE()

Question 4: 11 UNKNOWNs, 3 points each
========================================================================

Consider the class dictionary cd5 (from question 1)
and the following propagation pattern
and the C++ code. Find the UNKNOWNs.

In UNKNOWN1 give a one-sentence explanation why this program will not
work correctly.

cd5 (from question 1)

Ex = PCList(A).
PCList(S) ~ "(" S { "," S } ")".
A = D.
D : K | Z.
K = ["l" L].
L = Z.
Z = .


*operation* void f4()
  *traverse*
    *from* Ex 
      *through* -> K,l,L 
    *to* Z
  *wrapper* Z
    *prefix*
      (@ cout << this << endl; @)
  *wrapper* A
    *suffix*
      (@ cout << "f4 after traversing A ------------------" << endl; @)


The C++ memberfunctions:


//  Ex  = <a_pclist > A_PCList .
void Ex::f4(  )
{
  // outgoing calls
  UNKNOWN2
}

//  A  = <d > D .
void A::f4(  )
{
  // outgoing calls
  UNKNOWN3
  // suffix class wrappers
 cout << "f4 after traversing A ------------------" << endl; 
}

//  D  : K   |
//    Z 
//           *common* .
void D::f4(  )
{
}

//  K  =  [ <l > L  ] .
void K::f4(  )
  // outgoing calls
  UNKNOWN4
}

//  L  = <z > Z .
void L::f4(  )
{
  // outgoing calls
  this->get_z()->f4(  );
}

//  Z  = .
void Z::f4(  )
{
  // prefix class wrappers
 cout << this << endl; 
}

//  A_PCList  ~ A  { A  }. .
void A_PCList::f4(  )
{
  // outgoing calls
  UNKNOWN5	next_A(*this);
  A*		each_A;

  UNKNOWN6
}


class Ex : public Construction {
private:
  UNKNOWN0 (this is out of order)
  static const char* type;
public:
  Ex( A_PCList* = NULL );
  ~Ex();
  A_PCList* get_a_pclist() const { return( UNKNOWN7 ); }
  void set_a_pclist( A_PCList* new_a_pclist ) { a_pclist = UNKNOWN8; }
  A_PCList* rset_a_pclist( A_PCList* );

  const char*        get_type() const { return( type ); }
  static const char* get_formal_type() { return type; }
  void       set_data_member( int, Universal* );
  Universal* get_data_member( int ) const;
  int        number_of_parts() const;
  int        number_of_imm_parts() const;

  void       DEM_abstract() { }
  void       pp( ostream& = cout ) const;
#include "Ex.h"
};

class A : public Construction {
private:
  UNKNOWN9
  static const char* type;
public:
  A( D* = NULL );
  ~A();
  D* get_d() const { return( d ); }
  void set_d( D* new_d ) { d = new_d; }
  D* rset_d( D* );

  const char*        get_type() const { return( type ); }
  static const char* get_formal_type() { return type; }
  void       set_data_member( int, Universal* );
  Universal* get_data_member( int ) const;
  int        number_of_parts() const;
  int        number_of_imm_parts() const;

  void       DEM_abstract() { }
  void       pp( ostream& = cout ) const;
#include "A.h"
};

class D :  public Construction {
private:
  UNKNOWN10
  static const char* type;
public:
  D();
  virtual ~D();
  const char*        get_type() const { return( type ); }
  static const char* get_formal_type() { return type; }
  virtual void       set_data_member( int, Universal* );
  virtual Universal* get_data_member( int ) const;
  virtual int        number_of_parts() const;
  virtual int        number_of_imm_parts() const;

  virtual void       DEM_abstract() = 0;
  virtual void       pp( ostream& = cout ) const;
#include "D.h"
};

class K UNKNOWN11 {
private:
  L* l;
  static const char* type;
public:
  K( L* = NULL );
  ~K();
  L* get_l() const { return( l ); }
  void set_l( L* new_l ) { l = new_l; }
  L* rset_l( L* );

  const char*        get_type() const { return( type ); }
  static const char* get_formal_type() { return type; }
  void       set_data_member( int, Universal* );
  Universal* get_data_member( int ) const;
  int        number_of_parts() const;
  int        number_of_imm_parts() const;

  void       DEM_abstract() { }
  void       pp( ostream& = cout ) const;
#include "K.h"
};

// rest deleted


Question 5: 14 UNKNOWNs, 3 points each
=========================================================================

Consider the C++ member functions below.
What is the corresponding class dictionary. 
Put it into UNKNOWN0.

The member functions come from the following propagation pattern which contains
two transportation patterns. Find the unknowns.

Propagation pattern
-----------------------------------------------

*operation* void f()
*traverse* 
  *from* A *to* {B,C}

  ////// transportation pattern 1
  *carry* *out* B* UNKNOWN1
    *along*
      *from* A *to* B
    *at* B UNKNOWN2 = (@ this @)
  *carry* *UNKNOWN3* C* c1
    *along*
      *from* A *to* UNKNOWN4
    *at* C UNKNOWN5 = (@ UNKNOWN6 @)
  *wrapper* A
    *suffix*
      (@ cout << b1 << c1 << this << endl; @)
  ////// end transportation pattern 1

  ////// transportation pattern 2
  *carry* *in*  A* UNKNOWN7 = (@ this @)
    *along*
      *from* A *to* UNKNOWN8
  *wrapper* UNKNOWN9
    *prefix*
      (@ cout << "a " << a1 << this << endl; @)
  ////// end transportation pattern 2

  *wrapper* -> *,*,*
    *prefix*
      (@ cout << "traversing construction edge" << endl; @)

C++ member functions
-----------------------------------------------

//  A  = "a" 
//    <b > B 
//    <c > C .
void A::f(  )
{
  DEM_TRACE("A","void A::f()");
  // variables for carrying in and out
  B*  b1 ;
  C*  c1 ;
  A*  a1 =  this ;

  // assignments for carrying in

  // prefix class wrappers

  // outgoing calls
  // construction edge prefix wrappers
 cout << "traversing construction edge" << endl; 
  this->get_b()->f( b1 ,  a1  );
  // construction edge suffix wrappers
  // construction edge prefix wrappers
 cout << "traversing construction edge" << endl; 
  this->get_c()->f( c1 ,  a1  );
  // construction edge suffix wrappers

  // suffix class wrappers
 cout << b1 << c1 << this << endl; 

  // assignments for carrying out
}

//  B  = "b" .
void B::f( B* &  b1,A*  a1 )
{
  DEM_TRACE("B","void B::f(B* &  b1,A*  a1)");
  // variables for carrying in and out

  // assignments for carrying in

  // prefix class wrappers
 cout << "a " << a1 << this << endl; 

  // outgoing calls

  // suffix class wrappers

  // assignments for carrying out
  b1 =  this ;
}

//  C  = "c" .
void C::f( C* &  c1,A*  a1 )
{
  DEM_TRACE("C","void C::f(C* &  c1,A*  a1)");
  // variables for carrying in and out

  // assignments for carrying in

  // prefix class wrappers
 cout << "a " << a1 << this << endl; 

  // outgoing calls

  // suffix class wrappers

  // assignments for carrying out
  c1 =  this ;
}

Parsing in object in: demeter-input. 

Drawing the parsed object:
A HAS 2 PARTS(
    B HAS 0 PART()
    C HAS 0 PART())
End of drawing.

Copying the object.

Displaying the copied object as a tree:
: A ( 
   < b > : UNKNOWN10 ( ) 
   < c > : UNKNOWN11 ( ) ) 
End of display.

Comparing the two objects:
copied and original object are equal

Pretty printing the parsed object:
a b c 

End of printing.

Selftest of generic parser/printer:
g_parse and g_parse( g_print( g_parse ) ) are equal.
Selftest passed.

>> void A::f()
traversing construction edge
 >> void B::f(B* &  b1,A*  a1)
UNKNOWN12
 << void B::f(B* &  b1,A*  a1)
traversing construction edge
 >> void C::f(C* &  c1,A*  a1)
UNKNOWN13
 << void C::f(C* &  c1,A*  a1)
UNKNOWN14
<< void A::f()