-------------------------------------------------------------------------- Software Design and Development Fall 1994 COM1205 Karl Lieberherr --------------------------------------------------------------------------- Midterm Question 1: 27 UNKNOWNs, 2 points each 54 Question 2: 20 UNKNOWNs, 3 points each (UNKNOWN3 is 12 points) 69 Question 3: 11 UNKNOWNs, 5 points each 55 178 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* At the beginning of a question we give the number of points per unknown. Question 1: ======================================================================= 26 UNKNOWNs, 2 points each Consider the following class dictionary, object graph, corresponding sentence and the first sets of the class dictionary. Find the UNKNOWNS. SchemeProgram = List(Exp). Exp : UNKNOWN1 | LitExp | AppExp | ProcExp | AssignExp | IfExp . UNKNOWN2 = Variable. Variable = UNKNOWN3. LitExp = DemNumber. UNKNOWN4 = "UNKNOWN5" Exp List(Exp) ")". ProcExp = "UNKNOWN6" UNKNOWN7(Variable) List(Exp) ")". AssignExp = "UNKNOWN8" VarExp Exp ")". IfExp = "(if" Exp Exp [ Exp] ")". // parameterized classes Stack(S) ~ "UNKNOWN9" {S} "end". List(S) ~ {S}. PList(S) ~ "UNKNOWN10" {S} ")". Dummy = Stack(PList(Variable)). The object graph in textual representation. : SchemeProgram ( < exps > : Exp_List { : AppExp ( < UNKNOWN11 > : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "UNKNOWN12" ) } < body > : Exp_List { : AppExp ( < UNKNOWN13 > : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "UNKNOWN14" ) , : Variable ( < id > : DemIdent "UNKNOWN15" ) } < body > : Exp_List { : AppExp ( < rator > : VarExp ( < var > : Variable ( < id > : DemIdent "UNKNOWN16" ) ) < rand > : Exp_List { : VarExp ( < var > : Variable ( < id > : DemIdent "UNKNOWN17" ) ) } ) } ) < rand > : Exp_List { : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "b" ) } < body > : Exp_List { : AppExp ( < rator > : VarExp ( < var > : Variable ( < id > : DemIdent "UNKNOWN18" ) ) < rand > : UNKNOWN19 { : VarExp ( < var > : Variable ( < id > : DemIdent "UNKNOWN20" ) ) , : LitExp ( < val > : DemNumber "UNKNOWN21" ) } ) } ) , : LitExp ( < val > : DemNumber "UNKNOWN22" ) } ) } ) < rand > : Exp_List { : LitExp ( < val > : DemNumber "UNKNOWN23" ) } ) } ) The corresponding sentence: ((UNKNOWN24 (a) ((UNKNOWN25 (f a) (f a)) (UNKNOWN26 (b) (plus b 3)) 100)) 10) // First-sets SchemeProgram : firstset = { *epsilon* "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } Exp : firstset = { "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } VarExp : firstset = { *classterminal* DemIdent } Variable : firstset = { *classterminal* DemIdent } LitExp : firstset = { *classterminal* DemNumber } AppExp : firstset = { "(" } ProcExp : firstset = { "(lambda" } AssignExp : firstset = { "(set!" } IfExp : firstset = { "(if" } Dummy : firstset = { "stack" } Exp_List : firstset = { *epsilon* "UNKNOWN27" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } Variable_PList : firstset = { "(" } Variable_PList_Stack : firstset = { "stack" } DemIdent : firstset = { *classterminal* DemIdent } DemNumber : firstset = { *classterminal* DemNumber } Question 2: =================================================================== 20 UNKNOWNs, 3 points each (UNKNOWN3 is 12 points) f-toplas-scheme Consider the class dictionary from question 1, the following propagation patterns, propagation graphs and the C++ code. Find the UNKNOWNS. *operation* void driver() *traverse* *from* SchemeProgram *to-stop* Exp *wrapper* Exp (@ cout << "UNKNOWN1 = " << this << endl << "UNKNOWN2 Variables: " << this -> findFreeVars() << endl; @) *operation* Variable_PList* findFreeVars() *wrapper* Exp *prefix* (@ return_val = this -> findFreeVars(new Variable_PList_Stack()); @) *operation* Variable_PList* findFreeVars (Variable_PList_Stack* boundVars) *init* (@ new Variable_PList(); @) *traverse* // For a given Exp-object find all Variable-objects it contains. // The formal parameters of a procedure can never be free; // Therefore, they need not be visited. *from* Exp *bypassing* -> *,UNKNOWN3,* *to* Variable *wrapper* ProcExp *prefix* // push (@ UNKNOWN4 -> insert(formal); @) *suffix* // pop (@ boundVars -> get(); @) *wrapper* Variable *prefix* (@ if (!boundVars->contains(this)) return_val -> append(this); @) *operation* int contains(Variable* v) *init* (@ 0 @) *traverse* *from* Variable_PList_Stack *to* Variable *wrapper* Variable *prefix* (@ if (this -> g_equal(v)) return_val = 1; @) =========== Propagation graphs: Traversal directive: *from* { SchemeProgram } *to-stop* { Exp } Propagation graph for traversal: *source* { SchemeProgram } *target* { Exp } *paths* SchemeProgram = < exps > Exp_List . Exp : . Exp_List ~ { Exp } . Traversal directive: *from* Exp *bypassing* -> *,formal,* *to* Variable Propagation graph for traversal: *source* { Exp } *target* { Variable } *paths* Exp : UNKNOWN5 | AppExp | ProcExp | AssignExp | IfExp . UNKNOWN6 = < var > Variable . Variable = . UNKNOWN7 = < rator > Exp < rand > Exp_List . ProcExp = < body > Exp_List . AssignExp = < lvalue > UNKNOWN8 < rvalue > Exp . IfExp = < testExp > Exp < trueExp > Exp [ < falseExp > Exp ] . Exp_List ~ { Exp } . Traversal directive: *from* { Variable_PList_Stack } *to* { Variable } Propagation graph for traversal: *source* { Variable_PList_Stack } *target* { Variable } *paths* Variable_PList_Stack ~ { Variable_PList } . Variable_PList ~ { Variable } . Variable = . The C++ program: void SchemeProgram::driver( ) { // outgoing calls UNKNOWN9 } void Exp::driver( ) { // prefix class wrappers cout << "Expression = " << this << endl << "Free Variables: " << this -> findFreeVars() << endl; } void Exp_List::driver( ) { // outgoing calls Exp_list_iterator next_Exp(*this); Exp* each_Exp; UNKNOWN10 ( each_Exp = next_Exp() ) { each_Exp->driver( ); } } Variable_PList* Exp::findFreeVars( ) { Variable_PList* return_val; this->findFreeVars_( return_val ); return return_val; } void Exp::findFreeVars_( Variable_PList* & return_val ) { // prefix class wrappers return_val = this -> findFreeVars(new Variable_PList_Stack()); } Variable_PList* Exp::findFreeVars( Variable_PList_Stack* boundVars ) { Variable_PList* return_val = new Variable_PList(); ; this->findFreeVars_( return_val, boundVars ); return return_val; } void Exp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { UNKNOWN11 } void UNKNOWN12::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_var()->findFreeVars_( return_val, boundVars ); } void Variable::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // prefix class wrappers if (!boundVars->UNKNOWN13(this)) return_val -> append(this); } void UNKNOWN14::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->UNKNOWN15()->findFreeVars_( return_val, boundVars ); this->UNKNOWN16()->findFreeVars_( return_val, boundVars ); } void ProcExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // prefix class wrappers boundVars -> insert(formal); // outgoing calls this->UNKNOWN17()->findFreeVars_( return_val, boundVars ); // suffix class wrappers UNKNOWN18 -> get(); } void AssignExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls UNKNOWN19 this->get_rvalue()->findFreeVars_( return_val, boundVars ); } void IfExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_testExp()->findFreeVars_( return_val, boundVars ); this->get_trueExp()->findFreeVars_( return_val, boundVars ); UNKNOWN20 { this->get_falseExp()->findFreeVars_( return_val, boundVars ); } } etc. etc. etc. etc. etc. Question 3: =================================================================== 11 UNKNOWNs, 5 points each Find the UNKNOWNs below in the programs to be written. Use the class dictionary from question 1. Write a program for printing all IfExp-objects contained in a SchemeProgram-object. *operation* void print_if_statements() *traverse* *from* UNKNOWN1 *wrapper* UNKNOWN2 Write a program which prints for a SchemeProgram-object all Variable-objects which appear in the formal part of some ProcExp-object. *operation* void print_formal_variables() *traverse* *from* UNKNOWN3 *wrapper* UNKNOWN4 Write a program which prints for a SchemeProgram-object all AssignExp-objects contained in some ProcExp-object. *operation* void print_assignments_in_procedure() *traverse* *from* SchemeProgram *to* UNKNOWN5 *wrapper* UNKNOWN6 *prefix* (@ this -> print_assignments_in_procedure2() ; @) *operation* void print_assignments_in_procedure2() *traverse* *from* UNKNOWN7 *to* UNKNOWN8 *wrapper* UNKNOWN9 *prefix* (@ cout << this ; @) Write a program which eliminates the else part (called falseExp-part) from all IfExp-objects contained in a SchemeProgram-object. *operation* void eliminate_else_part() *traverse* *from* UNKNOWN10 *wrapper* UNKNOWN11