-------------------------------------------------------------------------- Software Design and Development Fall 2000 COM 1205 Prof. Karl Lieberherr --------------------------------------------------------------------------- Final QUESTION 1: 4 UNKNOWNs: 8 points each: 32 points QUESTION 2: 4 UNKNOWNs, 10 points each: 40 points QUESTION 3: 5 UNKNOWNs, 8 points each: 40 points QUESTION 4: 22 UNKNOWNs, 5 points each: 110 points QUESTION 5: 4 UNKNOWNs, 10 points each, 40 points QUESTION 6: 40 points 302 points total --------------------------------------------------------------------------- To make the grading easier, please sort the unknowns in increasing order. THE GAME OF REDUNDANCY AND UNKNOWNS ----------------------------------- Some 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 software 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: ============================================== 4 UNKNOWNs: 8 points each: 32 points Consider the following cd: Main = String. Grammar ~ {Statement}. Statement = NonTerminal "=" Expression ".". Expression ~ Term {"|" Term}. Term ~ Factor {Factor}. Factor : NonTerminal | Terminal | Compound | Bracketed | Curlyed. Compound = "(" Expression ")". Bracketed = "[" Expression "]". Curlyed = "{" Expression "}". NonTerminal = Ident. Terminal = String. Unfortunately, this cd is not self-describing, but almost. When you put the above cd in file g.cd and also into file g.input and you use the following g.beh file: Main { {{ public static void main(String args[]) throws Exception { Grammar g = Grammar.parse(System.in); System.out.println(" done "); } }} } you will get syntax error messages when you run the program. Your task is to find a small change to g.input that makes it a legal input. The two changes are of the following form: Replace all occurrences of UNKNOWN1 by UNKNOWN2. Replace all occurrences of UNKNOWN3 by UNKNOWN4. Find the UNKNOWNs. Question 2: ============================================== 4 UNKNOWNs, 10 points each: 40 points Consider the cd of question 1 together with the following behavior file, input and output: Find the UNKNOWNs. class dictionary: the same as in question 1 ============================= behavior file: ============================= Main { {{ public static void main(String args[]) throws Exception { Grammar g = Grammar.parse(System.in); ClassGraph cg1 = new ClassGraph(true,false); System.out.println(" Number of errors " + g.isDefinedExactlyOnce(cg1)); System.out.println(" done "); } }} } // Collaboration // role System played by Grammar // role UsedElementHolder played by Expression // role Element played by NonTerminal Grammar{ {{ // where we want to go String si = "from NonTerminal to edu.neu.ccs.demeter.Ident"; String getDef = "from Grammar bypassing Expression to NonTerminal"; String getUsed = "from Grammar through Expression to NonTerminal"; int errors = 0; int isDefinedExactlyOnce(ClassGraph cg){ checkDefined(cg, getDefinedThings(cg)); return errors; } HashSet getDefinedThings(final ClassGraph cg){ return (HashSet)cg.traverse(this, getDef, new Visitor(){ HashSet rv = new HashSet(); void before(NonTerminal v){ Ident i = (Ident) cg.fetch(v,si); if (rv.contains(i)) { errors++; System.out.println("The element "+ i + " is defined more than once.");} else rv.add(i); } public Object getReturnValue(){ return rv; } }); } void checkDefined(final ClassGraph cg, final HashSet definedSet){ cg.traverse(this, getUsed, new Visitor(){ void before(NonTerminal v){ Ident i = (Ident) cg.fetch(v,si); if(!definedSet.contains(i)) { System.out.println("The element "+ i + " is undefined."); errors++; } } }); } }} } input: ============================= Main = String. Grammar = Statement. Grammar = Statement. Statement = NonTerminal "=" Expression ".". Expression = Term. NonTerminal = Ident. Terminal = String. Term = Factor . Factor = NonTerminal . Compound = "(" Expression ")". Bracketed = "[" Expression "]". Curlyed = "{" Expression "}". output: ============================= UNKNOWN1 UNKNOWN2 UNKNOWN3 UNKNOWN4 Number of errors 4 done Note: Each UNKNOWN is a one-line error message. Question 3: ================================================= 5 UNKNOWNs, 8 points each: 40 points This question is about class dictionary design. Find a smallest class dictionary so that the behavior file of question 2 produces for the given input the given output. behavior file: see question 2 ======================= input: ======================= (a b c b) ( (a b c) (x y) ) output: ======================= The element b is defined more than once. The element x is undefined. The element y is undefined. Number of errors 3 done Find the UNKNOWNs in the following class dictionary: ======================= import edu.neu.ccs.demeter.dj.*; import java.util.*; Main = String. Grammar = UNKNOWN1 UNKNOWN2. UNKNOWN3 = UNKNOWN4. UNKNOWN5 = Ident. List(S) ~ "(" {S} ")". Question 4: ==================================================== 22 UNKNOWNs, 5 points each: 110 points Consider the cd of question 1 and the following behavior file, and input and output. Find the UNKNOWNs. This program is about finding unique parts. It has been used to check the unique parts rule for class dictionaries using the class dictionary of class dictionaries in your project. Here it is applied to a different class structure that defines grammars. class dictionary: see question 1 ---------------------------------- behavior file: ---------------------------------- Main { {{ public static void main(String args[]) throws Exception { Grammar g = Grammar.parse(System.in); ClassGraph cg1 = new ClassGraph(true,false); g.checkUnique(cg1); System.out.println(" done "); } }} } //checks for unique parts. // // Collaboration // role System played by Grammar // out void checkUnique(final ClassGraph cg) // in Strategy getAllUnitsToBeChecked // role UnitToBeChecked played by Statement // in Strategy checkAllParts // role NotDuplicated played by NonTerminal Grammar{ {{ Strategy getAllUnitsToBeChecked = new Strategy("from UNKNOWN1 to UNKNOWN2"); void checkUnique(final ClassGraph cg){ UNKNOWN3.traverse(this, UNKNOWN4, UNKNOWN5 UNKNOWN6(){ void before(UNKNOWN7 a){ a.UNKNOWN8(cg); } }); } }} } Statement{ {{ Strategy checkAllParts = new Strategy( "from UNKNOWN9 through UNKNOWN10 to UNKNOWN11"); void checkDuplicateParts(ClassGraph cg){ UNKNOWN12.traverse(this, UNKNOWN13, UNKNOWN14 UNKNOWN15(){ UNKNOWN16 hParts = new UNKNOWN17(); void UNKNOWN18(UNKNOWN19 l){ if(!UNKNOWN20.add(l.get_ident())){ System.out.println("UNKNOWN21 "+ l.get_ident() + " UNKNOWN22."); } } }); } }} } input: ---------------------------------- A = [B] C {B} . Q = ( [R] {R} (R) ). B = D G G X (D | E |E). X = (X X). output: ---------------------------------- Element B is not unique. Element R is not unique. Element R is not unique. Element G is not unique. Element D is not unique. Element E is not unique. Element X is not unique. done Question 5 ===================================================== 4 UNKNOWNs, 10 points each, 40 points This question is similar to question 3. Use the behavior file from question 4 (four) and find a smallest class dictionary with which the above program will work. Your class dictionary should accept inputs like: ( Y (A B C D) Z (A B C A) W (B B C A) ) and the program above will produce the following output: Element A is not unique. Element B is not unique. done Find the UNKNOWNs below: Grammar = UNKNOWN1. Statement = NonTerminal UNKNOWN2. Expression = UNKNOWN3. NonTerminal = Ident. List(S) ~ UNKKNOWN4. Question 6 =================================================== 40 points Explain Adaptive Programming in less than half a page to a C++ programmer. Response by Jeanne Travers: Adaptive Programming is based on the idea of writing code in such a way that objects used in that code can be modified and the code will need to change only slightly if at all. Adaptive Programming is done in such a way that in the case where an object needs to call upon an object deeply embedded in it, the programmer will not need to write code to dig down the object one level at a time. He can make a call that assumes very little about the structure of the object, and therefore, if the structure of the object is then changed, the code will not be broken. Response by Brendan Coffey: Adaptive Programming addresses many of the problems inherent in object-oriented programming while retaining its intuitiveness and flexibility. The usual C++ style "digging" through objects is alleviated by describing strategies which are abstractions of the entire application class graph. AP also allows the containment and inheritance structure of the application to be much more flexible, since strategies describe subsets of the class graph in a way that requires little knowledge of its underlying structure. Response by Earl Kinney: Adaptive object-oriented programming allows programs to be written in a way that makes them less brittle in the face of class interrelationship changes. Where as in tue OOP you have to make widespread changes when changing class relationships, AOOP provides a level of abstraction above OOP, away from details like navigation paths.