CS 61A Summer 2002 Midterm 2 solutions Question 1: Tree Recursion (6 Points) Here is a solution that does not require a helper: (define (count-nodes node) (if (leaf? node) (make-node 1 '()) (let ((kids (map count-nodes (children node)))) (make-node (accumulate + 1 (map datum kids)) kids)))) The tricky part was not forgetting to map DATUM before accumulating. Mapping COUNT-NODES returns a list of trees. We need to add the datums of every tree in the list to create the datum of the new tree, hence (map datum kids). This solution is even cooler less the explicit base case: (define (count-nodes node) (let ((kids (map count-nodes (children node)))) (make-node (accumulate + 1 (map datum kids)) kids))) Yes, it's that short! The base case is built into the MAP function: when (children node) returns an empty list--indicating a leaf--MAP just returns that empty list. The more common correct solution uses a helper to perform the actual node counting (an explicit base case is again optional): (define (count-nodes node) (make-node (number-of-nodes node) (map count-nodes (children node)))) (define (number-of-nodes node) (accumulate + 1 (map number-of-nodes (children node)))) The grading went something along the lines of: o One point was docked for an incorrect base case. o Two points were docked for major errors: Data Abstraction Violations, forgetting to map MAP, forgetting to MAP altogether, other domain-range mismatch errors. o Four points were docked if the existing tree was modified, instead of a new one created. The most common errors were forgetting to map DATUM and calling (count-nodes (children node)). COUNT-NODES takes a tree, not a list of trees! Other errors included adding 1 to the return value of MAP (a list) and returning 1 in the base case instead (make-node 1 '()). Question 2: Data Directed Programming (10 Points) (define *decryption-procs* (list decrypt-0 decrypt-1 ... decrypt-9)) (define (decrypt message) (if (not (number? (first message))) message (decrypt ((list-ref *decryption-procs* (first message)) (bf message))))) Grading: o A solution that that used tables (i.e. PUT and GET) got at most 7.5 points. Even if you were using a table, we still expected you to create it by showing a few calls to PUT. o Three points for getting the algorithm correct: using the (first message) as a key, recursing on a decrypted message, etc. o Four points for locating the decryption procedure via DDP, as opposed to a big fat cond (explicit dispatch). o Three points for creating the search structure: a list of procedures was the answer we were looking for, though other structures--like a tree of decryption procedures--also would work. o We deducted two points if instead of listing the procedures with the LIST function, you did something like: '(decrypt-0 decrypt-1 ... decrypt-9). Using quotation creates a list of words--not of procedures! o We deducted one point if the search structure was internal to the DECRYPT function. This limits its usefulness, since no other procedure can operate on it and causes the data structure to be recreated each time DECRYPT is called. Question 3: OOP Environments (12 Points) Part I (4 Points) (define-class (basic-frame enclosing-environment) (instance-vars (global #f)) (method (make-global) (set! global #t))) Two points were awarded for having some mechanism that allows a frame to extend another frame. The simplest way to do this was to pass the frame being extended --the enclosing environment--as an instantiation argument. Another way to accomplish this is to create a SET-PARENT method in the Basic Frame class. Two more points were awarded for designating a global frame in some way. We did this by creating an instance var to serve as a flag--if it's true, then this frame is the global frame. Other approaches included passing #f or the empty list as the enclosing environment. The grading was pretty lenient here. If you did not have an explicit method for testing if a frame is the global frame in the Basic Frame class, but you tested for it in some way in Part II you received full credit for Part I. We also checked Part III to make sure that it was consistent with your frame extension mechanism. Part II (6 Points) (define-class (var-frame enclosing-environment) (parent (basic-frame enclosing-environment)) (instance-vars (bindings (make-table))) (method (define var val) (put bindings var val)) (method (set! var val) (let ((found (get bindings var))) (if found (put bindings var val) (if (not (ask self 'global)) (ask enclosing-environment 'set! var val) (error "Unbound variable: " var))))) (method (lookup var) (let ((value (get bindings var))) (if value value (if (not (ask self 'global)) (ask enclosing-environment 'lookup var) (error "Unbound variable: " var)))))) The grading went more or less as follows: o One point was awarded for using a storage structure of some sort-- preferably a table--to hold the frame's variables. Some people implemented their own tables. This, of course, was not what the question was asking. Solutions that had a faulty table implementation but used it correctly received full credit. o One point was awarded for having the Var Frame class correctly inherit from the Basic Frame class. Incorrect use of the parent clause generally cost half a point. This was one of the few cases where we were specifically looking for correct OOP syntax. In the other parts of this question, we were pretty generous with closing parentheses. o One point was awarded for a method that bound a variable to a value in the current frame. This is the DEFINE method above. Remember, the real DEFINE special form adds a binding to the current frame. o The SET! and LOOKUP methods were worth 1.5 points each: 1/2 point for looking in the current frame, plus a full point for searching the enclosing environment when necessary. The rule here is that the most local binding will be changed or looked-up; the enclosing environment should only be searched if the variable is not bound in the current frame. A common error was forgetting to search the enclosing environment. Part III (2 Points) (define global (instantiate var-frame 'dummy)) (ask global 'make-global) (ask global 'define 'y 15) (define e1 (instantiate var-frame global)) (ask e1 'define 'x 11) (define e2 (instantiate var-frame e1)) (ask e1 'define 'x 12) (define e3 (instantiate var-frame global)) (ask e3 'define 'x 5) We graded this problem fuzzily: o If it was mostly correct, you got two points. o If a few errors were present--one point. o Otherwise zero. o Also, we took off points if the answer to Part III was not consistent with Parts I and II. Question 4: Environments Ouch! (12 Points) The environment diagram should have five frames--E1 to E5--plus the global frame (given). There should be three procedure objects on the diagram: 1 Takes in "erwin" and its right buble points to the global frame. 2 The second one takes in "greg" and "ilya" and points to E1. 3 The third one takes in "jeff" and points to E1, also. The only procedure object that has a name (an arrow pointing to it) should be the procedure that takes in "greg" and "ilya", number 2 in the above list. Bindings: E1 (extends G) : erwin --> 3 E2 (extends E1): jeff ---> procedure object #2 E3 (extends E1): greg ---> procedure object #2 ilya ---> 3 E4 (extends E1): greg ---> procedure object #2 ilya ---> 2 E5 (extends E1): greg ---> procedure object #2 ilay ---> 1 The return value is 6, the factorial of 3. This is a solution to the extra problem on Homework 1: achieving recursion without define. The code looks a bit nicer with sugar: (let ((erwin 3)) (let ((jeff (lambda (greg ilya) (if (= ilya 1) 1 (* (greg greg (- ilya 1)) ilya))))) (jeff jeff erwin))) Our factorial procedure is the procedure that takes in greg and ilya. The trick to achieving recursion without naming our procedures is to pass the procedure we want to call recursively as an argument to itself. Hence, greg always points to the same procedure - the factorial procedure. But to get this process started, we still need a name for our factorial procedure because we need to refer to it twice: to call it and to pass it as an argument to itself. We can do this by naming the factorial procedure locally: we've called it jeff. Then, the expression (jeff jeff erwin) gets the "recursion" started. The most common mistake was to point the procedure that takes in greg and ilya to E2 instead of E1. But this procedure is just an argument to the let procedure. Therefore, we must evaluate it first, still in E1. Another common error was not evaluating the whole expression, stating that it returns a procedure. Translated into lets however, it is clear that nowhere does this Scheme expression return a procedure. Grading: o One point for drawing each of the three procedure objects and pointing them to the correct frames. o One point for binding erwin to 3 in E1. o One point for binding jeff to the factorial procedure in E2. o One point for binding greg to the factorial procedure in E3, E4 and E5, as well as for binding ilya to 3 in E3, 2 in E4 and 1 in E5. o Two points for having E1 extend global and E2 extend E1. One of these points comes from having E1 and E2 point to the same frames as the procedures that created them. o Two points for having E3, E4, and E5 all extend E1. One of these points is for pointing each of these to the frame that the procedure that created them (the factorial procedure) points to. o One point for numbering the frames in the order in which they're created. o One point for Part II. No one got the 10 secret extra credit points for numbering their frames Z1 ... Z5.