Preparation in: /proj/asl/lieber/java/new-java-envs/fall97/ -------------------------------------------------------------------------- Adaptive Object-Oriented Software Development Fall 1997 COM 3360 NTU SE-737 --------------------------------------------------------------------------- Final QUESTION 1: 4 UNKNOWNs, 15 points each 60 QUESTION 2: 7 UNKNOWNs, 10 points each 70 QUESTION 3: 25 points 25 QUESTION 4: 50 points 50 205 points total --------------------------------------------------------------------------- Open book and open notes. Overview: This final consists of 4 questions with subparts. The first question is about class dictionary design and writing a simple adaptive program. The second question is about three layer model architectures as used by the UML and the OMG object model (they actually have four layers but only three layers are widely used). The question is phrased in terms of the three layer model of Demeter/Java and is about explaining the DisplayVisitor generation process and the generated DisplayVisitor. The third question is an essay question related to comparing the current approach to visitors with a new approach to visitors described by the class dictionary of question 2. The fourth question is also an essay question about strategies. Questions 1 and 2 use the UNKNOWN format. Please put your answers on the provided answer form at the end of the exam. 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: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 4 UNKNOWNs, 15 points each PART 1: This question is about class dictionary design. You are given a class dictionary old.cd which defines a simplified form of the strategy notation of Demeter/Java. The problem with this notation is that we have to repeat bypassing information: strategy t1 = {A->B bypassing {A,B,C} B->C bypassing {A,B,C} } Instead we would like to write this in shorter form: strategy t1 = { -> A B -> B C} bypassing {A,B,C} The following strategy t2 = {A->B bypassing {X,A,B,C} B->C bypassing {Y,A,B,C} } we would like to write in a form which factors the common information: strategy t2 = {-> A B bypassing {X} -> B C bypassing {Y}} bypassing {A,B,C} The idea is to view strategies as expressions which are either simple or compound. Expressions can be nested to any level. Curly braces { and } indicate the nesting level. Strategy s3 below has nesting level two. In the new notation, a strategy edge is written in prefix notation "-> A B" instead of the infix notation "A -> B". This change was made for two reasons: 1. To make the new cd LL(1). 2. To be in line with the edge notation for class graph edges where also a prefix notation is used, e.g. "before -> A,b,B". Further examples of strategies in the new notation are: strategy s = {-> A B bypassing {C}}. strategy s2 = {-> A B -> B C} bypassing {A, B, C}. strategy s3 = { {-> A B bypassing X -> B C bypassing Y} bypassing {A, B, C} -> C Y}. strategy s4 = {-> A B bypassing {X,A,B,C} -> B C bypassing {Y,A,B,C} -> C Y}. The old class dictionary old.cd (which is LL(1)) is: StrategyDefinitions = List(StrategyDefinition). StrategyDefinition = "strategy" StrategyName "=" StrategyExpression ".". StrategyExpression : StrategyGraph. StrategyGraph = "{" *l + SList(SGEdge) - *l "}". SGEdge = ClassGlobSpec *s "->" *s ClassGlobSpec [ NegativeConstraint ]. Constraint : NegativeConstraint *common* GlobSpec. NegativeConstraint : Bypassing. Bypassing = "bypassing". GlobSpec : OneGlob | GlobSet. OneGlob = Glob. GlobSet = "{" *s [ Commalist(Glob) *s ] "}". Glob : ClassGlob | EdgeGlob. EdgeGlob : PartGlob . ClassGlob = ClassNameGlob. PartGlob = "->" *s SourceGlob "," *s PartNameGlob "," *s DestGlob. SourceGlob = ClassNameGlob. DestGlob = ClassNameGlob. ClassNameGlob : ClassNameExact | AnyClass. ClassNameExact = ClassName. AnyClass = "*". PartNameGlob : PartNameExact | AnyPart. PartNameExact = PartName. AnyPart = "*". ClassGlobSpec : OneClassGlob | ClassGlobSet. OneClassGlob = ClassGlob. ClassGlobSet = "{" *s Commalist(ClassGlob) *s "}". Main = . // Terminal buffer classes. ClassName = Name. PartName = Name. StrategyName = Name. Name = Ident. // Parameterized class definitions. List(S) ~ {*s S}. NList(S) ~ S {*s S}. SList(S) ~ S { *l S } . Commalist(S) ~ S {"," *s S}. The new class dictionary (which is also LL(1)) is: StrategyDefinitions = List(StrategyDefinition). StrategyDefinition = "strategy" StrategyName "=" StrategyExpression ".". StrategyExpression : UNKNOWN1 . StrategyGraph = UNKNOWN2 . SGEdge = UNKNOWN3 . Constraint : NegativeConstraint *common* GlobSpec. NegativeConstraint : Bypassing. Bypassing = "bypassing". GlobSpec : OneGlob | GlobSet. OneGlob = Glob. GlobSet = "{" *s [ Commalist(Glob) *s ] "}". Glob : ClassGlob | EdgeGlob. EdgeGlob : PartGlob . ClassGlob = ClassNameGlob. PartGlob = "->" *s SourceGlob "," *s PartNameGlob "," *s DestGlob. SourceGlob = ClassNameGlob. DestGlob = ClassNameGlob. ClassNameGlob : ClassNameExact | AnyClass. ClassNameExact = ClassName. AnyClass = "*". PartNameGlob : PartNameExact | AnyPart. PartNameExact = PartName. AnyPart = "*". ClassGlobSpec : OneClassGlob | ClassGlobSet. OneClassGlob = ClassGlob. ClassGlobSet = "{" *s Commalist(ClassGlob) *s "}". Main = . // Terminal buffer classes. ClassName = Name. PartName = Name. StrategyName = Name. Name = Ident. // Parameterized class definitions. List(S) ~ {*s S}. NList(S) ~ S {*s S}. SList(S) ~ S { *l S } . Commalist(S) ~ S {"," *s S}. Find the UNKNOWNs. PART 2: Write a method (for the new class dictionary) which returns a float indicating the average number of StrategyGraph-objects per StrategyDefinition-object in a StrategyDefinitions-object. If your program does not work for some inputs, write a condition which the inputs must satisfy. Express the condition in English or using OCL. Example: The StrategyDefinitions-object contains 3 StrategyDefinition-objects. The first one contains 1 StrategyGraph-object, the second one 2 and the third one 3. The average is 2 StrategyGraph-objects per StrategyDefinition-object. Put your method into UNKNOWN4. Question 2: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 7 UNKNOWNs, 10 points each You are given the following artifacs: program.cd defines a new visitor notation program.input gives an example of the new visitor notation DisplayVisitor.beh generated from program.cd by gendisplayvis.beh gendisplayvis.beh DisplayVisitor generator A summary of demjava.cd only what is important for display visitor generation out the output produced by DisplayVisitor.beh for the object in program.input program.cd ==================================== Visitors = Visitor_List. Visitor = VisitorName [Modification] VisitorBody. Modification = "modifies" VisitorName. VisitorBody = VisitorEntry_CList. VisitorEntry : ModifyStructure | ModifyBehavior | During | Boundary. ModifyStructure : DataMember | Init | Return. Boundary : Start | Finish *common* Strat JavaCode. ModifyBehavior = ClassExp BehaviorOrStructure_CList. BehaviorEntry : WhenVisiting *common* JavaCode. BehaviorOrStructure : BehaviorEntry | ModifyStructure2. ModifyStructure2 = ModifyStructure. // to prevent multiple inheritance WhenVisiting = "when-visiting". During = "during" Strat ModifyBehavior_CList. DataMember = "local" Ident ";". Init = "init" JavaCode. Return = "return" JavaCode. Start = "start". Finish = "finish". ClassExp = Ident. JavaCode = Text. Main = . VisitorName = Ident. Strat = "strategy". Visitor_List ~ {Visitor}. VisitorEntry_CList ~ "{" {VisitorEntry} "}". BehaviorOrStructure_CList ~ "{" {BehaviorOrStructure} "}". ModifyBehavior_CList ~ "{" {ModifyBehavior} "}". program.input ========================================= DFTVisitor // some strategy type // {-> Graph Adjacency // -> Adjacency Vertex // -> Vertex Adjacency} { // visitor entries Adjacency { local mark; init (@ mark = false; @) return (@ mark @) when-visiting (@ if (mark==false) {mark=true;}; @) } } ConnectivityVisitor modifies DFTVisitor { //visitor entries local count; init (@ count = 0;@) return (@ count @) during strategy // {-> Graph Adjacency stop} { Adjacency { when-visiting (@ if (next.return()=false) // check whether unmarked {count+=1; next();}; @) } } } DisplayVisitor.beh ============================================== 1 // This file is automatically generated by Demeter/Java. 2 DisplayVisitor { 3 (@ 4 private java.io.PrintWriter out = new java.io.PrintWriter(System.out, true); 5 java.io.PrintWriter get_out() { return out; } 6 void set_out(java.io.PrintWriter new_out) { out = new_out; } 7 DisplayVisitor(java.io.PrintWriter out) { set_out(out); } 8 DisplayVisitor(java.io.PrintStream out) 9 { set_out(new java.io.PrintWriter(out, true)); } 10 @) 11 before Visitors (@ 12 out.print(": Visitors ("); 13 indent++; 14 @) 15 after Visitors (@ 16 out.print(" )"); 17 indent--; 18 @) 19 before -> Visitors, visitor_list, Visitor_List (@ 20 out.println(); for (int i = 0; i < indent; i++) out.print("\t"); 21 out.print(" "); 22 @) 23 before Visitor (@ 24 out.print(": Visitor ("); 25 indent++; 26 @) 27 after Visitor (@ 28 out.print(" )"); 29 indent--; 30 @) 31 before -> Visitor, visitorname, VisitorName (@ 32 out.println(); for (int i = 0; i < indent; i++) out.print("\t"); 33 out.print(" "); 34 @) 35 before -> Visitor, modification, Modification (@ 36 out.println(); for (int i = 0; i < indent; i++) out.print("\t"); 37 out.print(" "); 38 @) OMITTED 139 before -> DataMember, ident, Ident (@ 140 out.println(); for (int i = 0; i < indent; i++) out.print("\t"); 141 out.print(" "); 142 out.print(" : Ident"); 143 out.print(" \"" + source.get_ident() + "\""); 144 @) 145 before Init (@ 146 out.print(": Init ("); 147 indent++; 148 @) 149 after Init (@ 150 out.print(" )"); 151 indent--; 152 @) 153 before -> Init, javacode, JavaCode (@ 154 out.println(); for (int i = 0; i < indent; i++) out.print("\t"); 155 out.print(" "); 156 @) 157 before Return (@ 158 out.print(": Return ("); 159 indent++; 160 @) CUT gendisplayvis.beh: (the first part is numbered; the second part contains some utility functions which are not numbered. This code is taken from the Demeter/Java source and was written by Doug Orleans and Geoff Hulten.) ====================================== 1 // genuniversal.beh -- generate code for DisplayVisitor. 2 // $Id: gendisplayvis.beh,v 1.8 1997/10/09 11:30:02 dougo Exp $ 3 Program { 4 /** Add a "DisplayVisitor" class to the set of class definitions. 5 Don't call this until after buildClassDefTable()! */ 6 void addDisplayVisitor(String name) (@ 7 addClassDef(ClassDef.parse("*notparsed* *visitor* " + name 8 + " = int.")); 9 @) 10 /** Generate the behavior file for DisplayVisitor. */ 11 void generateDisplayVisitor(String name, File file) = allParts { 12 before Program (@ 13 host.openOutputFile(file); 14 Program.out.println(host.genericOutputVisitorPreamble(name)); 15 @) 16 (@ ClassName classname; @) 17 before ClassDef (@ 18 classname = host.get_classname(); 19 // don't do anything for alternation classes 20 if (host.isAlternationClass()) return; 21 boolean rep = classname.isOrWasRepetitionClass(); 22 String body = 23 " out.print(\": " + classname + " " 24 + (rep ? "{" : "(") + "\");\n" 25 + " indent++;\n"; 26 Program.out.println(classname.makeBefore(body)); 27 body = 28 " out.print(\" " 29 + (rep ? "}" : ")") + "\");\n" 30 + " indent--;\n"; 31 Program.out.println(classname.makeAfter(body)); 32 @) 33 before Part (@ 34 ClassName dest = host.get_classname(); 35 String deststr = dest.toString(); 36 PartName partname = host.get_partname(); 37 String body = 38 " out.println();" 39 + " for (int i = 0; i < indent; i++) out.print(\"\\t\");\n" 40 + " out.print(\"<" + partname + "> \");\n"; 41 if (dest.isBuiltinType()) { 42 if (deststr.equals("char")) { 43 body += " out.print(\" '\"" 44 + " + source.get_" + partname + "() + \"' \");\n"; 45 } else { 46 body += " out.print(\" : " 47 + dest + " \\\"\" + dest + \"\\\"\");\n"; 48 } 49 } else if (dest.isTerminalClass()) { 50 body += " out.print(\" : " + dest + "\");\n"; 51 if (deststr.equals("String")) { 52 body += " out.print(\" \\\"\"" 53 + " + source.get_" + partname + "() + \"\\\" \");\n"; 54 } else if (deststr.equals("Text")) { 55 body += " out.print(\" " + Text.begin + "\"" 56 + " + source.get_" + partname + "() + " 57 + Text.quoted_end + " + \" \");\n"; 58 } else if (deststr.equals("Character")) { 59 body += " out.print(\" '\"" 60 + " + source.get_" + partname + "() + \"' \");\n"; 61 } else { 62 body += " out.print(\" \\\"\" + source.get_" + partname + "() + \"\\\"\");\n"; 63 } 64 } 65 Program.out.println(host.makeBefore(classname, body)); 66 @) 67 after Program (@ 68 Program.out.println("}"); 69 host.closeOutputFile(); 70 @) 71 } 72 } ClassNameAccessor { before ClassSpec (@ @) before ClassName (@ @) } ClassDef { traversal toClassName(ClassNameAccessor v) { bypassing { ClassParts, ClassMethods, -> *,parameters,* } to ClassName; } } { Subclass, Superclass, Part, RepeatedPart } { traversal toClassName(ClassNameAccessor v) { bypassing { -> *,actual_parameters,* } to ClassName; } } { ClassDef, Subclass, Superclass, Part, RepeatedPart } { ClassName get_classname() = toClassName { before ClassName (@ return_val = host; @) } } { ClassDef, Part, RepeatedPart } { void set_classname(ClassName classname) = toClassName { before ClassSpec (@ host.set_classname(classname); @) } } Part { (@ boolean isTerminal() { ClassDef def = Program.prog.findClassDef(get_classname()); return def == null || def.isInterface(); } String makeWrapper(ClassName source, String body) { return new PartGlob(source, get_partname(), get_classname()) + " " + Text.begin + body + Text.end; } String makeBefore(ClassName source, String body) { return " before " + makeWrapper(source, "\n" + body + " "); } String makeAfter(ClassName source, String body) { return " after " + makeWrapper(source, "\n" + body + " "); } @) } ClassName { (@ String makeWrapper(String body) { return this + " " + Text.begin + body + Text.end; } String makeBefore(String body) { return " before " + makeWrapper("\n" + body + " "); } String makeAfter(String body) { return " after " + makeWrapper("\n" + body + " "); } @) } ClassName { (@ private static String builtinTypes[] = { "boolean", "char", "byte", "short", "int", "long", "float", "double" }; private static String terminalClasses[] = { // from java.lang.*: "Boolean", "Character", "Integer", "Long", "Float", "Double", "Number", "String", "StringBuffer", // from demeter.*: "Ident", "Text" }; boolean isBuiltinType() { String s = toString(); for (int i = 0; i < builtinTypes.length; i++) { if (builtinTypes[i].equals(s)) return true; } return false; } boolean isTerminalClass() { String s = toString(); for (int i = 0; i < terminalClasses.length; i++) { if (terminalClasses[i].equals(s)) return true; } return false; } boolean isKnownTerminal() { return isBuiltinType() || isTerminalClass(); } @) } PartGlob { public String toString() (@ return "-> " + source + ", " + name + ", " + dest; @) } { Program, ClassDef } { traversal allParts(PartVisitor v) { to { Part, RepeatedPart }; } } A summary of demjava.cd: ========================================================= ========================================================= Instead of giving you the class dictionary for Demeter/Java (which has several hundred lines) I summarize the information it must contain for the purpose of generating the DisplayVisitor: generateDisplayVisitor: {-> Program ClassDef -> ClassDef Part} get_classname: {-> {ClassDef,Part} ClassName} get_partname: {-> Part PartName} This means that there must be classes Program ClassDef Part ClassName PartName which are connected as follows: There must be a path from Program via ClassDef to Part. From ClassDef and Part there must be a path to ClassName. From Part there must be a path to PartName. out: ======================================================= 1 CLASSPATH=./gen:$CLASSPATH java Main < program.input 2 done 3 : Visitors ( 4 : Visitor_List { 5 : Nonempty_Visitor_List ( 6 : Visitor ( 7 : VisitorName ( 8 : Ident "DFTVisitor" ) 9 : VisitorBody ( CUT Here come the unknowns: Example: line 3 in out: : Visitors ( is printed by lines UNKNOWN100 in DisplayVisitor.beh and those lines in DisplayVisitor.beh are printed by lines UNKNOWN200 in gendisplayvis.beh UNKNOWN100 = 12 UNKNOWN200 = 26 The following part of line 4 in out: is printed by lines UNKNOWN1 in DisplayVisitor.beh. Line 24 of DisplayVisitor.beh: out.print(": Visitor ("); is printed by line UNKNOWN2 in gendisplayvis.beh. Line 28 of DisplayVisitor.beh: out.print(" )"); is printed by line UNKNOWN3 in gendisplayvis.beh. Line 31 of DisplayVisitor.beh: before -> Visitor, visitorname, VisitorName (@ is printed by line UNKNOWN4 in gendisplayvis.beh. Line 142 of DisplayVisitor.beh: out.print(" : Ident"); is printed by line UNKNOWN5 in gendisplayvis.beh. We want to modify the program as follows: Instead of printing all the part names, as in: : Visitors ( : Visitor_List { : Nonempty_Visitor_List ( : Visitor ( : VisitorName ( : Ident "DFTVisitor" ) we want a simplified form of display which looks like: : Visitors ( : Visitor_List { : Nonempty_Visitor_List ( : Visitor ( : VisitorName ( : Ident "DFTVisitor" ) Give in UNKNOWN6 the line number(s) of gendisplayvis.beh which need to be changed, and indicate how to change them. Note the the indentation should be kept as shown in the above example. =========== The following is a utility function in Demeter/Java: // you can attach the same code to several classes { ClassDef, Subclass, Superclass, Part, RepeatedPart } { ClassName get_classname() bypassing { ClassParts, ClassMethods, -> *,parameters,* } to ClassName // the following is an inlined visitor { before ClassName (@ return_val = host; @) } } Explain the purpose of this code in UNKNOWN7. Question 3: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 25 points Consider the class dictionary for visitors from question 2. Describe an interesting feature difference between the visitor notation defined by the new visitor class dictionary and the visitor notation used by Demeter/Java and motivate why the new feature is useful. (About half a page.) Question 4: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 50 points Part 1: Define the concept of strategy refinement. A strategy s2 is a refinement of strategy s1 if ... The intuition is that the refined strategy is at least as restrictive as the original one. Some examples of refinements: {A->B B->C} is a refinement of {A->C} {A->B bypassing {C} is a refinement of {A->B} {A->B} is a refinement of {A->B} Part 2: Describe at a high level how you would implement a strategy refinement checker. At most 1/2 page. HAPPY HOLIDAYS! -------------------------------------------------------------------------- Adaptive Object-Oriented Software Development Fall 1997 COM 3360 NTU SE 737F --------------------------------------------------------------------------- Final - Answer Form YOUR NAME: Question 1: ================================================== UNKNOWN1 = UNKNOWN2 = UNKNOWN3 = UNKNOWN4 = -- Question 2: ================================================== UNKNOWN1 = UNKNOWN2 = UNKNOWN3 = UNKNOWN4 = UNKNOWN5 = UNKNOWN6 = UNKNOWN7 = Question 3: ================================================== Question 4: ==================================================