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 = Z. Z = . -------------------------------------------------- cd2: Ex = PCList(A). PCList(S) ~ "(" S { "," S } ")". A = D Z. D = Z K. K = ["l" L]. L = A. Z = . -------------------------------------------------- cd3: Ex = PCList(A). PCList(S) ~ "(" S { "," S } ")". A = D Z. D = K U. U = ["a" A]. K = Z ["l" L]. L = U. Z = . -------------------------------------------------- cd4: Ex = PCList(A). PCList(S) ~ "(" S { "," S } ")". A = D Z. D = K. K = L. L = Z. Z = . V1 : D | U1 *common* 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 Z. B = K Z. K = L. L = O. O = S Z. S = 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 PCommaList(UNKNOWN3) UNKNOWN4 PCommaList(UNKNOWN5). J = UNKNOWN6 UNKNOWN7 UNKNOWN8. M = M1. M1 = "(MERGE" E UNKNOWN9 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 . void Ex::f4( ) { // outgoing calls UNKNOWN2 } // A = 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 ] . void K::f4( ) // outgoing calls UNKNOWN4 } // L = 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 // 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()