Midterm CSU 670 Spring 2009 Karl Lieberherr Open book and open notes. No computers and other wireless devices. Question 1: 37 points Question 2: 36 points Question 3: 30 points ----------------------- Total 103 points Question 1: 37 points ============================= Functional Adaptive Programming Structure-shy programming Program Understanding Consider the following program.cd program.beh program.input and output The program is about the paper boy who comes to your apartment and requests payment. We first check whether there is enough money (using methods moneyAvailable) in the apartment and if so, we collect (using method getPayment) the money from the different places in the apartment. The moneyAvailable methods show 5 different ways of accomplishing the check from minimally structure-shy (moneyAvailableLoD0) to not structure-shy (moneyAvailableLoD4 and moneyAvailableLoDV). Find the UNKNOWNs below. UNKNOWN1 is worth 10 points UNKNOWN19 is worth 5 points UNKNOWN20 is worth 5 points Other UNKNOWNs 1 point program.cd ------------------------------------------------------- package gen; import edu.neu.ccs.demeterf.demfgen.lib.*; import edu.neu.ccs.demeterf.*; nogen List(X) : Cons(X) | Empty(X). nogen Cons(X) = X List(X). nogen Empty(X) = . nogen Option(X): Some(X) | None(X). nogen Some(X) = X. nogen None(X) = . Start = List(PaperBoy) EOF. Main = . PaperBoy = "paperboy" Customer int. Apartment = "apartment" Kitchen // Bedroom Bedrooms Bathroom. Kitchen = "kitchen" KitchenCabinet. KitchenCabinet = "kitchencabinet" Money. Bedroom = "bedroom" Mattress. Bedrooms = Bedroom Bedroom. Mattress = "mattress" Money. PlaceWithMoney : Mattress | KitchenCabinet | Wallet. Bathroom = "bathroom". Customer = "customer" Wallet Apartment. Wallet = "wallet" Money. Money = int. program.beh ------------------------------------------------- Main {{ public static void p(String s){ System.out.print(s); } public static void main(String args[]) throws Exception { Start start = Start.parse(System.in); // some sample functionality p(start.display() + "\n"); p(start.print() + "\n"); p(start.toStr() + "\n"); System.out.println(start.equals(start)); p(start.magic().display() + "\n"); } }} Start {{ public Start magic() { return new Traversal(new Bc(){ Money combine(Money a, int v){return new Money(v+10);} Customer combine(Customer c, Wallet w, Apartment a){ Customer modified = c.getPayment(25); Main.p(" customer with money subtracted "); Main.p(modified.display() + "\n"); Main.p(c.moneyAvailableLoD0() + " money available LoD 0 \n"); Main.p(c.moneyAvailableLoD1() + " money available LoD 1 \n"); Main.p(c.moneyAvailableLoD2() + " money available LoD 2 \n"); Main.p(c.moneyAvailableLoD3() + " money available LoD 3 \n"); Main.p(c.moneyAvailableLoD4() + " money available LoD 4 \n"); return new Customer(w,a); } PaperBoy combine(PaperBoy p, Customer c, int i){ Main.p(p.moneyAvailableLoDV() + " money available LoDV \n"); return new PaperBoy(c,i); } }). traverse(this); } }} Customer {{ // create an entirely new apartment! public Customer getPayment(final int m){ // only reach "legal" money objects return new Traversal(new Bc() { int toPay = m; UNKNOWN1 }). traverse(this); } }} Customer {{ public int moneyAvailableLoD0 () { // most structure-shy return new Traversal(new TUCombiner(){ Integer combine(Money a){return a.v;} public Integer combine(){return 0;} public Integer fold(Integer a, Integer b){return UNKNOWN2;} }). traverse(this); } public int moneyAvailableLoD1 () { // most structure-shy return new Traversal(new ID(){ int combine(Money a, int v){return v;} int combine(Object a, int v){return v;} int combine(Object a){return 0;} int combine(Object c, int w, int a){ return UNKNOWN3;} }). traverse(this); } public int moneyAvailableLoD2 () { // less structure-shy but wrong return new Traversal(new ID(){ int combine(Money a, int v){return v;} int combine(Object a, int v){return v;} int combine(Object a){return 0;} int combine(Apartment a, int k, int b){return UNKNOWN4;} int combine(Customer c, int w, int a){ return UNKNOWN5;} }). traverse(this); } public int moneyAvailableLoD3 () { // less structure-shy but correct: 2 part explicit return new Traversal(new ID(){ int combine(Money a, int v){return v;} int combine(Object a, int v){return v;} int combine(Object a){return 0;} int combine(Bedrooms bs, int p, int c){return UNKNOWN6;} int combine(Apartment a, int k, int b){return UNKNOWN7;} int combine(Customer c, int w, int a){ return UNKNOWN8;} }). traverse(this); } public int moneyAvailableLoD4 () { // less structure-shy: 1 and 2 part explicit // this can be generated return new Traversal(new ID(){ int combine(Money a, int v){return v;} // int combine(Object a, int v){return v;} int combine(KitchenCabinet a, int v){return v;} int combine(Bedroom a, int v){return v;} int combine(Mattress a, int v){return v;} int combine(Wallet a, int v){return v;} int combine(Kitchen a, int v){return v;} int combine(Bathroom a){return 0;} // only addition needed for Bedrooms int combine(Bedrooms bs, int p, int c){return UNKNOWN9;} int combine(Apartment a, int k, int b){return UNKNOWN10;} int combine(Customer c, int w, int a){ return UNKNOWN11;} }). traverse(this); } }} // You don't want the paper boy to know about the details // of your apartment. // If you remodel you have to inform the paper boy PaperBoy {{ public int moneyAvailableLoDV () { return customer.wallet.m.v + // customer.apartment.kitchen.kitchenCabinet.m.v + // customer.apartment.bedroom.mattress.m.v ; customer.apartment.kitchen.kitchenCabinet.m.v + customer.apartment.UNKNOWN12.parents.UNKNOWN13.m.v + customer.apartment.bedrooms.children.UNKNOWN14.m.v ; } }} program.input ------------------------------------------------ paperboy customer wallet 9 apartment kitchen kitchencabinet 5 bedroom mattress 8 bedroom mattress 8 bathroom 20 output: -------------------------------------------------------- : Start ( : Cons ( : PaperBoy ( : Customer ( : Wallet ( : Money ( : int "9" ) ) : Apartment ( : Kitchen ( : KitchenCabinet ( : Money ( : int "5" ) ) ) : Bedrooms ( : Bedroom ( : Mattress ( : Money ( : int "8" ) ) ) : Bedroom ( : Mattress ( : Money ( : int "8" ) ) ) ) : Bathroom ( ) ) ) : int "20" ) : Empty ( ) ) ) paperboycustomerwallet9apartmentkitchenkitchencabinet5bedroommattress8bedroommattress8bathroom20 Start(Cons(PaperBoy(Customer(Wallet(Money(9)),Apartment(Kitchen(KitchenCabinet(Money(5))),Bedrooms(Bedroom(Mattress(Money(8))),Bedroom(Mattress(Money(8)))),Bathroom())),20),Empty())) true still to pay 16 still to pay 11 still to pay 3 still to pay 0 customer with money subtracted : Customer ( : Wallet ( : Money ( : int "0" ) ) : Apartment ( : Kitchen ( : KitchenCabinet ( : Money ( : int "0" ) ) ) : Bedrooms ( : Bedroom ( : Mattress ( : Money ( : int "0" ) ) ) : Bedroom ( : Mattress ( : Money ( : int "5" ) ) ) ) : Bathroom ( ) ) ) 30 money available LoD 0 30 money available LoD 1 22 money available LoD 2 30 money available LoD 3 30 money available LoD 4 30 money available LoDV : Start ( : Cons ( : PaperBoy ( : Customer ( : Wallet ( : Money ( : int "UNKNOWN15" ) ) : Apartment ( : Kitchen ( : KitchenCabinet ( : Money ( : int "UNKNOWN16" ) ) ) : Bedrooms ( : Bedroom ( : Mattress ( : Money ( : int "UNKNOWN17" ) ) ) : Bedroom ( : Mattress ( : Money ( : int "UNKNOWN18" ) ) ) ) : Bathroom ( ) ) ) : int "20" ) : Empty ( ) ) ) After you have determined the above UNKNOWNs find this one: UNKNOWN19: The output for moneyAvailableLoD2() is wrong: it is 22 but was expected to be 30. Explain the behavior of the program. UNKNOWN20: Are there any violations of the Law of Demeter in this program? Explain where they are. Question 2: 36 points ================================================ Requirements Analysis Deriving algorithms to implement requirements Use blue book for answers. Determine the break-even prices for the following derivatives. If you cannot determine the exact values, determine sets of derivatives that have the same break-even prices. ((2,0) (2,2)) = (63 238) (119 238) (104,105) (104,106) (104,110) (104,111) It is important to show how you derive the break-even prices. Show the look-ahead polynomials for the relations and how you manipulate them to determine the break-even prices. Question 3: 30 points ====================================================== Class dictionary design As part of the design for the SDG game, we need the capabaility to define simple class dictionaries that define raw materials, predicates to define derivatives and finished products. We have chosen the following cd to define cds. Cd_graph = "sdg" "class" "dictionary" NAdj_list. NAdj_list = Adj Adj_list . Adj = "type" Vertex Neighbors . Neighbors: Product | Sum. Product = "product" "(" Any_vertex_list ")". Sum = "sum" "(" Vertex "|" Vertex ")". Any_vertex : Labeled_vertex | Syntax_vertex. Syntax_vertex = String. Labeled_vertex = ident ":" Vertex. Adj_list: NAdj_list | Empty_Adj_list . Any_vertex_list: Nany_vertex_list | Empty_vl. Nany_vertex_list = Any_vertex Any_vertex_list. Empty_vl = . Empty_Adj_list = . Vertex = ident. Part a: Use this cd to define a cd for describing instances of the knapsack problem. Part b: Use this cd to define a cd for CSP raw materials very similar to the cd that is used in your robot. Part c: Use this cd to define itself (first 4 classes only)