Here comes the final since some of you are leaving soon for christmas. We use again the honors system: Do the exam yourself, without Demeter Tools/C++ usage. 2 hours was given to NU students. Send it back as soon as you can. This seems to be much easier than the midterm. Best regards, -- Karl Lieberherr -------------------------------------------------------------------------- Adaptive Object-Oriented Software Fall 1995 COM 3360/NTU SE737 Karl Lieberherr --------------------------------------------------------------------------- Final exam Question 1: 22 UNKNOWNS, 1 point each 22 Question 2: 33 UNKNOWNS, 2 points each 66 Question 3: 2 UNKNOWNS, 6 points each 12 100 points 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* Question 1: ================================================================= 22 UNKNOWNS, 1 point each 22 Consider the following class dictionary and an object and sentence which are both legal with respect to the class dictionary. Find the UNKNOWNS. // An application consists of a list of modules which use // a library. Application = UNKNOWN1 List(UNKNOWN2) UNKNOWN3 List(AdaptiveSoftwareLibrary). // an adaptive software library consists of a list // of adaptive behavioral components (ABCs) and // a list of customizing class dictionaries. AdaptiveSoftwareLibrary = List(ABC_Exp) List(CdExp). // A module is a list of ABCs customized by a class dictionary. Module = "*module*" List(ABC_Exp) CdExp. // A class dictionary may be given explicitly, or by an evolutionary // transformation which extends an existing cd or by a directive // which restricts an existing cd. CdExp : Cd | ExtendedCd | RestrictedCd. Cd = "*cd*". ExtendedCd = "*extended-cd*". RestrictedCd = "*restricted-cd*" Directive CdExp. Directive : SimpleDirective | DirectiveName. SimpleDirective = UNKNOWN4 Vertex "UNKNOWN5" Vertex. ABC_Exp : ABC | ExtendedABC | CompoundABC. ExtendedABC = "*extended-abc*". CompoundABC = List(ABC). // Adaptive Behavioral Component ABC = // customization parameters [ List (CParam)] // provided function ProvidedSignature // named directives ["UNKNOWN6" List(DirectiveDef)] // variables local to ABC; used to "transport" objects ["UNKNOWN7" List(VarDef)] // additional classes and parts needed by ABC ["UNKNOWN8" List(UNKNOWN10)] // calls to other ABCs prefixed by a traversal -> elastic connections ["UNKNOWN11" List(UNKNOWN13)] [ UNKNOWN15 ] [ "*instantiated*" List(ABC_Exp)] [ "*called*" List(ABC_Exp)] . CParam = "*cparam*". DirectiveDef = DirectiveName "=" Directive. DirectiveName = DemIdent. ProvidedSignature = // ABC provided, if return type is not void, can view // it as new edge in extended class graph (derived edge). UNKNOWN16 Type_spec ABC_Name "(" [ CommaList(ParamDecl) ] ")" [ "*init*" Block ] . Type_spec = DemIdent. ParamDecl = Vertex Param_name. Param_name = DemIdent. VarDef = "UNKNOWN17". Extension = "*cd-extension*". Connection = Directive ABC_Name. Traversal = "UNKNOWN18" [ Collaborators] Directive ["*conditions*" List(Condition)] [ "*prelude*" Block] List(Wrapper) [ "postlude*" Block]. Collaborators = UNKNOWN19 // behavioral types List(TypeDef) // represent other ABCs which participate in traversal List(BehObject). TypeDef = "*type*". BehObject = "*behavioral-object*". Wrapper = "UNKNOWN20". Condition : VertexCond | EdgeCond. VertexCond = "*vertex-if*" Block Vertex. EdgeCond = "*edge-if*" Block Edge. Vertex = DemIdent. ABC_Name = DemIdent. Block = DemText. Edge = "*edge*". List(S) ~ "UNKNOWN21" {S} "UNKNOWN22". CommaList(S) ~ S {"," S} . =================================================== object : Application ( < modules > : Module_List { : Module ( < abcs > : ABC_Exp_List { } < customizer > : Cd ( ) ) , : Module ( < abcs > : ABC_Exp_List { : ABC ( < providedsignature > : ProvidedSignature ( < type_spec > : Type_spec ( < n > : DemIdent "A" ) < name > : ABC_Name ( < n > : DemIdent "f" ) ) < directives > : DirectiveDef_List { : DirectiveDef ( < directivename > : DirectiveName ( < n > : DemIdent "X" ) < directive > : SimpleDirective ( < from > : Vertex ( < n > : DemIdent "Q" ) < to > : Vertex ( < n > : DemIdent "R" ) ) ) , : DirectiveDef ( < directivename > : DirectiveName ( < n > : DemIdent "Y" ) < directive > : SimpleDirective ( < from > : Vertex ( < n > : DemIdent "S" ) < to > : Vertex ( < n > : DemIdent "T" ) ) ) } < var > : VarDef_List { : VarDef ( ) , : VarDef ( ) } < cd_extensions > : Extension_List { : Extension ( ) } < connections > : Connection_List { : Connection ( < directive > : DirectiveName ( < n > : DemIdent "X" ) < abc_name > : ABC_Name ( < n > : DemIdent "f" ) ) , : Connection ( < directive > : DirectiveName ( < n > : DemIdent "Y" ) < abc_name > : ABC_Name ( < n > : DemIdent "g" ) ) } < traversal > : Traversal ( < collaborators > : Collaborators ( < typ > : TypeDef_List { } < behavioralObjects > : BehObject_List { } ) < directive > : SimpleDirective ( < from > : Vertex ( < n > : DemIdent "A" ) < to > : Vertex ( < n > : DemIdent "B" ) ) < wrappers > : Wrapper_List { : Wrapper ( ) } ) ) } < customizer > : Cd ( ) ) } < using > : AdaptiveSoftwareLibrary_List { } ) ================================================== sentence *application* ( *module* () *cd* *module* ( *operation* A f() *directives* (X = *from* Q *to* R Y = *from* S *to* T) *var* (*var* *var*) *cd-extensions* (*cd-extension*) *connections* (X f Y g) *traverse* *collaborators* () () *from* A *to* B (*wrapper*) ) *cd*) *using* () Question 2: ================================================================= 33 UNKNOWNS, 2 points each 66 Consider the following class dictionary, propagation patterns and the call in main.C. Find the UNKNOWNS so that the program matches the documentation and the example below. The purpose of the program is to translate from one graph representation to another. Both graph representations are given in the class dictionary. For example, the graph representation Class Dictionary Graph Vertex List ConstVertex Basket name_pos "{183 50}" vertex_pos "{200 66}" AltVertex Fruit name_pos "{183 133}" vertex_pos "{200 150}" ConstVertex Apple name_pos "{133 183}" vertex_pos "{150 200}" ConstVertex Orange name_pos "{233 183}" vertex_pos "{250 200}" ConstVertex Weight name_pos "{283 133}" vertex_pos "{300 150}" ConstVertex DemNumber name_pos "{333 183}" vertex_pos "{400 150}" Edge List ConstEdge fruit name_pos "{205 108}" from ConstVertex Basket to AltVertex Fruit AltEdge from AltVertex Fruit to ConstVertex Apple AltEdge from AltVertex Fruit Bendpoints "{{500 4} {20 90}}" to ConstVertex Orange ConstEdge weight name_pos "{250 145}" from AltVertex Fruit Bendpoints "{{250 400} {500 500}}" to ConstVertex Weight ConstEdge n name_pos "{350 145}" from ConstVertex Weight to ConstVertex DemNumber is translated into: Basket = < fruit > Fruit . Fruit : Apple | Orange *common* < weight > Weight . Apple = . Orange = . Weight = < n > DemNumber . DemNumber = . by propagation pattern cppCreCDGraph at the end of the pp list below. The following code is from the DemDraw COM1205 undergraduate project. ========================================================== class dictionary Graph = "Class Dictionary Graph" < vertices > Vertex_List < edges > Edge_List // made the following optional so we wouldn't need to change the // demeter-input file, but would create using the cppInit.pp [ "defaultConstVertex" < defaultConstVertex > ConstVertex] [ "defaultAltVertex" < defaultAltVertex > AltVertex] [ "defaultConstEdge" < defaultConstEdge > ConstEdge] [ "defaultAltEdge" < defaultAltEdge > AltEdge] . Edge : AltEdge | ConstEdge *common* "from" < from > Vertex [ "Bendpoints" < middlepoints > Coordinates ] "to" < to > Vertex . Edge_List ~ "Edge" "List" { Edge } . Vertex_List ~ "Vertex" "List" { Vertex } . Vertex : AltVertex | ConstVertex | Term *common* < vertexname > VertexName [ "vertex_pos" < position > Coordinates ] . AltEdge = "AltEdge" . ConstEdge = "ConstEdge" < edgename > EdgeName . ConstVertex = "ConstVertex" . AltVertex = "AltVertex" . Coordinates = DemString. VertexName = < name > DemIdent [ "name_pos" < vn_offset > Coordinates ] . EdgeName = < name > DemIdent "name_pos" < en_offset > Coordinates . Term = "TermVertex" . // New classes for creating a Class Dictionary Graph object Cd_Graph = < adjacencies > Cd_Adj_List . Cd_Adj_List ~ { Cd_Adjacency } . Cd_Adjacency = < source > Cd_Vertex < ns > Cd_Neighbors "." . Cd_Neighbors : Cd_Construct | Cd_Alternat *common* < construct_ns > Cd_LV_List . Cd_Construct = "=" . Cd_Alternat = ":" < alternat_ns > Cd_V_BarList "*common*" . Cd_LV_List ~ { Cd_LVertex } . Cd_V_BarList ~ Cd_Vertex { "|" Cd_Vertex } . Cd_LVertex = "<" < label_name > DemIdent ">" < vertex > Cd_Vertex . Cd_Vertex = < vertex_name > DemIdent . CD-NUMBERED-XREF Create a numbered cross reference list for a class dictionary. ------------------------------------------------------------- Class Dictionary ------------------------------------------------------------- 1 Graph = "Class Dictionary Graph" 2 < vertices > Vertex_List 3 < edges > Edge_List 4 5 // made the following optional so we wouldn't need to change the 6 // demeter-input file, but would create using the cppInit.pp 7 8 [ "defaultConstVertex" < defaultConstVertex > ConstVertex] 9 [ "defaultAltVertex" < defaultAltVertex > AltVertex] 10 [ "defaultConstEdge" < defaultConstEdge > ConstEdge] 11 [ "defaultAltEdge" < defaultAltEdge > AltEdge] . 12 13 Edge : AltEdge 14 | ConstEdge 15 *common* 16 "from" < from > Vertex 17 [ "Bendpoints" < middlepoints > Coordinates ] 18 "to" < to > Vertex . 19 20 Edge_List ~ "Edge" "List" { Edge } . 21 22 Vertex_List ~ "Vertex" "List" { Vertex } . 23 24 Vertex : AltVertex 25 | ConstVertex 26 | Term 27 *common* 28 < vertexname > VertexName 29 [ "vertex_pos" < position > Coordinates ] . 30 31 AltEdge = "AltEdge" . 32 33 ConstEdge = "ConstEdge" 34 < edgename > EdgeName . 35 36 ConstVertex = "ConstVertex" . 37 38 AltVertex = "AltVertex" . 39 40 Coordinates = DemString. 41 42 VertexName = < name > DemIdent 43 [ "name_pos" < vn_offset > Coordinates ] . 44 45 EdgeName = < name > DemIdent 46 "name_pos" < en_offset > Coordinates . 47 48 Term = "TermVertex" . 49 50 51 // New classes for creating a Class Dictionary Graph object 52 53 Cd_Graph = < adjacencies > Cd_Adj_List . 54 55 Cd_Adj_List ~ { Cd_Adjacency } . 56 57 Cd_Adjacency = < source > Cd_Vertex < ns > Cd_Neighbors "." . 58 59 Cd_Neighbors : Cd_Construct | Cd_Alternat 60 *common* < construct_ns > Cd_LV_List . 61 62 Cd_Construct = "=" . 63 64 Cd_Alternat = ":" < alternat_ns > Cd_V_BarList "*common*" . 65 66 Cd_LV_List ~ { Cd_LVertex } . 67 68 Cd_V_BarList ~ Cd_Vertex { "|" Cd_Vertex } . 69 70 Cd_LVertex = "<" < label_name > DemIdent ">" < vertex > Cd_Vertex . 71 72 Cd_Vertex = < vertex_name > DemIdent . ------------------------------------------------------------- Alphabetically Sorted Cross Reference List ------------------------------------------------------------- AltEdge :31 11 13 AltVertex :38 9 24 Cd_Adj_List :55 53 Cd_Adjacency :57 55 Cd_Alternat :64 59 Cd_Construct :62 59 Cd_Graph :53 Cd_LV_List :66 60 Cd_LVertex :70 66 Cd_Neighbors :59 57 Cd_V_BarList :68 64 Cd_Vertex :72 57 68 68 70 ConstEdge :33 10 14 ConstVertex :36 8 25 Coordinates :40 17 29 43 46 Edge :13 20 EdgeName :45 34 Edge_List :20 3 Graph :1 Term :48 26 Vertex :24 16 18 22 VertexName :42 28 Vertex_List :22 2 ===================================================== propagation patterns // This pp will return a DemIdent* that points to the DemIdent that holds the // name of the ConstEdge object on which the function is called. *operation* DemIdent* GetCEName() *traverse* UNKNOWN1 *wrapper* UNKNOWN2 (@ return_val = this->get_name(); @) // This pp will return a DemIdent* that points to the DemIdent that holds the // name of the Vertex object on which the function is called. *operation* DemIdent* GetVName() *traverse* UNKNOWN3 *wrapper* UNKNOWN4 (@ return_val = this->get_name(); @) // Find the Cd_V_BarList-object of Adjacency with source SrcVert // and add DesVert to Cd_V_BarList-object. // If the source SrcVert is a // construction vertex, the command has no effect. *operation* void cdgAddANeighbor(DemIdent* SrcVert, DemIdent* DesVert) *traverse* UNKNOWN5 *carry* *in* Cd_Vertex* S_Chk_Vert = (@ this -> get_source() @) *along* *from* Cd_Adjacency *to* UNKNOWN6 *wrapper* Cd_V_BarList (@ if (SrcVert->UNKNOWN7(S_Chk_Vert->get_vertex_name())) { this->UNKNOWN8(new Cd_Vertex((DemIdent*)DesVert->g_copy())); } @) // Find the Cd_LV_List-object of Adjacency with source SrcVert // and add DesVert to Cd_LV_List-object. // For instance, if the source is an alternation vertex, the // destination vertex should be added to the "common" list. *operation* void cdgAddCNeighbor(DemIdent* SrcVert, DemIdent* Name, DemIdent* DesVert) *traverse* UNKNOWN9 *carry* *in* Cd_Vertex* S_Chk_Vert = (@ this -> get_source() @) *along* UNKNOWN10 *wrapper* Cd_LV_List (@ if (SrcVert->UNKNOWN11(S_Chk_Vert->get_vertex_name())) { Cd_LVertex* new_LVertex = new Cd_LVertex(); new_LVertex->set_vertex(new Cd_Vertex((DemIdent*)DesVert->g_copy())); new_LVertex->set_label_name((DemIdent*)Name->g_copy()); this->UNKNOWN12(new_LVertex); } @) // Create a new adjacency with a source vertex of the given name // and an empty neighbor list of type Cd_Alternat. Add it to // the current Cd_Adj_List. *operation* void cdgAddSourceAVertex(DemIdent* name) *traverse* UNKNOWN13 *wrapper* Cd_Adj_List (@ Cd_Adjacency* NewAdj = new Cd_Adjacency(); Cd_Vertex* NewVertex = new Cd_Vertex(name); Cd_Alternat *NewAlternat = new Cd_Alternat(new Cd_V_BarList()); NewAlternat->set_construct_ns(new Cd_LV_List()); NewAdj->set_source(UNKNOWN14); NewAdj->set_ns(UNKNOWN15); this->append(NewAdj); @) // Create a new adjacency with a source vertex of the given name // and an empty neighbor list of type Cd_Construct. Add it to // the current Cd_Adj_List. *operation* void cdgAddSourceCVertex(DemIdent* name) *traverse* UNKNOWN16 *wrapper* UNKNOWN17 (@ Cd_Adjacency* NewAdj = new Cd_Adjacency(); Cd_Vertex* NewVertex = new Cd_Vertex(name); Cd_Construct *NewConstruct = new Cd_Construct(); NewConstruct->set_construct_ns(new Cd_LV_List()); NewAdj->set_source(UNKNOWN18); NewAdj->set_ns(UNKNOWN19); cout << "Before the append" << endl; this->append(UNKNOWN20); @) // Iterate through the edge list, adding each as a neighbor to the list of // adjacencies in the CDG object. The actual function call used depends on // the edge type. Just pass the vertex name and leave it up to the CDG // object to implement the addition. // This must be done after to cppAddSourceVertices. *operation* void cppAddNeighbors(Cd_Graph* cdg) *traverse* *from* UNKNOWN21 *through* -> *,UNKNOWN22,* *to* { UNKNOWN23, AltEdge } *wrapper* UNKNOWN24 (@ cdg->cdgAddCNeighbor(this->get_from()->GetVName(), this->GetCEName(), this->get_to()->GetVName()); @) *wrapper* AltEdge (@ cdg->cdgAddANeighbor(this->get_from()->GetVName(), this->get_to()->GetVName()); @) // Iterate through the vertex list, adding each as a source vertex // to the list of adjacencies in the CDG object. The actual function call // used depends on the vertex type. Just pass the vertex name and leave it // up to the CDG object to implement the addition. // This must be done prior to cppAddNeighbors. *operation* void cppAddSourceVertices(Cd_Graph* cdg) *traverse* *from* UNKNOWN25 *through* -> *,UNKNOWN26,* *to* { UNKNOWN27, UNKNOWN28 } *wrapper* UNKNOWN29 (@ cdg->cdgAddSourceCVertex(this->GetVName()); @) *wrapper* UNKNOWN30 (@ cdg->cdgAddSourceAVertex(this->GetVName()); @) // Add all vertices as source vertices to the CDG object. // Add all edges as neighbors to the CDG object. *operation* UNKNOWN31* cppCreCDGraph() *init* (@ new UNKNOWN32(new UNKNOWN33()) @) *wrapper* Graph (@ cout << "Before cppAddSourceVertices" << endl; this->cppAddSourceVertices(return_val); cout << "After/Before cppAddNeighbors" << endl; this->cppAddNeighbors(return_val); cout << "Final After Add Neighbors" << endl; @) ===================================================== call in main.C cout << " the cd " << iGraph -> cppCreCDGraph() << endl; Question 3: ================================================================= 2 UNKNOWNS, 6 points each 12 Consider the following class dictionary: A = B C D. B : R | S | T | U | V | W | X *common* G. C : R | T | V | X *common* H. D : S | U | W *common* I. R = . S = . T = . U = . V = . W = . X = . G = . H = . I = . Does it have the tree-property? Answer in UNKNOWN1 (YES or NO) Is it object-equivalent to a single inheritance class dictionary? If so, replace one class definition to make the class dictionary single inheritance or give answer "NO" in UNKNOWN2. ===================================================== ===================================================== Optional Question (when you are done with 1 to 3) Write a brief critique of the program in question 2 (part of DemDraw) produced by my undergraduate students. Is it structure shy? Does it contain unnecessary redundancies? Put your discussion after your answers to question 3. ===================================================== ===================================================== HAPPY HOLIDAYS -------------------------------------------------------------------------- Object-oriented Systems Fall 1995 COM 3360/NTU SE737 --------------------------------------------------------------------------- --------------------------------------------------------------------------- Final 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 = UNKNOWN13 = UNKNOWN14 = UNKNOWN15 = UNKNOWN16 = UNKNOWN17 = UNKNOWN18 = UNKNOWN19 = UNKNOWN20 = UNKNOWN21 = UNKNOWN22 = 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 = UNKNOWN27 = UNKNOWN28 = UNKNOWN29 = UNKNOWN30 = UNKNOWN31 = UNKNOWN32 = UNKNOWN33 = Question 3: ================================================== UNKNOWN1 = UNKNOWN2 =