CS 61A Spring 2001 Midterm 2 solutions 1. Box and pointer. > c (() lets (go) bears) --->/*--->XX----->XX---->X/ | | | V V V lets X/ bears | V go The pair marked as /* is the one created by the CONS. Its *CAR* is slashed because it's null (the empty list is an element of the main list). The most common mistake was to represent the empty list with an extra pair: --->XX--->XX----->XX---->X/ | | | | | V V V | lets X/ bears | | | V | go | V // <---- This is wrong! A pair with both car and cdr slashed represents (()), a one-element list containing the empty list. We accepted an arrow pointing to () [but not to '() -- there aren't any quotes in values, only in expressions you type] and we accepted an arrow pointing to a *single* slashed square. But a slash right in the pair, as shown above, is the correct notation. > a (lets (go) bears) --->XX----->XX---->X/ | | | V V V lets X/ bears | V go Appending an empty list to something doesn't change its value. (APPEND combines the *elements* of its arguments, and the empty list has no elements to contribute to the result.) > l (() (lets (go) bears)) --->/X--->X/ | V XX----->XX---->X/ | | | V V V lets X/ bears | V go LIST always creates a list with as many elements as it has arguments -- two, in this example. The first element is the empty list; the second is that other list we keep seeing in this question! > (cdr c) (lets (go) bears) > (cdr a) ((go) bears) > (cdr l) ((lets (go) bears)) In each case the way to think about the problem is to look at the first pair in the box and pointer diagram and take the cdr of that pair. Scoring: One point per printed representation, one point per box and pointer diagram. No part credit! Exception: consistently putting quotation marks in the results loses at most 3 points. Another exception: If the printed form in the first set of answers is wrong, but the corresponding box and pointer diagram agrees with that wrong answer, and so does the printed form of the cdr, the score is one point (instead of zero) for those three answers. 2. OOP lists. The point of this question was that an object-oriented solution has to be consistently object-oriented. That means that everything is an object, and also that there shouldn't be type-dispatching code within a method; if you have something like (if (type-1? arg) (do-type-1-algorithm arg) (do-type-2-algorithm arg)) anywhere, then type-1 and type-2 should usually be separate classes instead, perhaps inheriting from a common parent (although not in this case). (a) What does Louis's implementation do? > (ask my-list 'length) 1 > (ask other-list 'length) ERROR -- attempt to apply non-procedure (). Louis's implementation works for non-empty lists, but his empty list isn't an object, so you can't send it messages. This is the design error that Dan Ingalls described when he complained about languages that aren't 100% object-oriented. The common wrong answers for this part were 1 and 0, which is what a correct LENGTH implementation would do, and 1 and 1, presumably because people read Louis's base case as if it said (if (null? self) ...). Scoring: One point for each of the two answers, all or nothing. (You didn't have to give an exact error message; "error" is enough.) (b) How to fix it? A list is, by definition, either the empty list or a pair whose cdr is a list. That means there are two distinct kinds of things we need to implement lists: pairs and empty lists. In an OOP implementation, each of those should be a class. (define-class (pair the-car the-cdr) (method (length) (+ 1 (ask the-cdr 'length)))) (define-class (empty-list) (method (length) 0)) (define (new-cons a b) (instantiate pair a b)) ; This doesn't change (define (new-cdr p) (ask p 'the-cdr)) ; This doesn't change (define new-nil (instantiate empty-list)); NEW! (define my-list (new-cons 3 new-nil)) ; CHANGED! (define other-list (new-cdr my-list)) ; This doesn't change Now we get the correct length both for pairs and for empty lists: > (ask my-list 'length) 1 > (ask other-list 'length) 0 The most common wrong answer was to represent the empty list using a pair with special values in the car and in the cdr. But pairs are allowed to have any values, so it's a mistake to rule out some particular value. So, for example, many people used (NULL? THE-CAR) as a special test, but lists are allowed to have empty lists as elements! The list (() LETS (GO) BEARS), which is the answer to the first part of question 1, starts with a pair whose car is null. If the test is (AND (NULL? THE-CAR) (NULL? THE-CDR)), you're ruling out an empty list as the *last* element of a list. One clever solution had (define-class (pair the-car the-cdr) (method (length) (+ 1 (ask the-cdr 'length))) (initialize (if (null? the-cdr) (set! the-cdr new-nil)))) in addition to defining an empty-list class and a new-nil instance, as above, so that Louis could still say (new-cons 3 '()) and end up with a correct OOP list. In a correct solution, every instance of the PAIR class must represent an actual pair, not some encoding of the empty list. In a two-point solution, the empty list is represented as an object of some sort. Perhaps it would help some students' understanding to display a solution that uses a single LIST class in a way that's correct but not really using the OOP style: (define-class (list type maybe-car maybe-cdr) (method (null?) (equal? type 'null)) (method (car) (if (equal? type 'pair) maybe-car (error "CAR of empty list"))) (method (cdr) (if (equal? type 'pair) maybe-cdr (error "CDR of empty list"))) (method (length) (if (equal? type 'null) 0 (+ 1 (ask maybe-cdr 'length))))) (define (new-cons a b) (instantiate list 'pair a b)) (define new-nil (instantiate list 'null 'unused 'unused)) In this solution every list is an object, and the empty list is correctly distinguished from a pair. But each method has to check which type of list this is, and that suggests that these should really be two different classes. Scoring: 4 correct 3 some detail wrong but two classes each minding its own business 2 two classes, and/or makes the cdr an object 1 cdr isn't an object 0 incoherent 3. OOP locks (a) vanilla locks (define-class (LOCK MY-PIN) (INSTANCE-VARS (OPEN? #F)) (method (open pin) (cond ((NOT (EQUAL? PIN MY-PIN)) '(sorry wrong pin)) (OPEN? '(lock is open already!)) (else (SET! OPEN? #T) '(lock opens)))) (method (close) (cond ((NOT OPEN?) '(lock is closed already!)) (else (SET! OPEN? #F) '(lock closes))))) Some variants on this are still correct. For example, values other than #T and #F can be used to represent whether the lock is open or closed, although the solution is easiest and most elegant this way. But the solution must use an instance variable of some kind for that purpose. Scoring: 3 correct 2 trivial mistake 1 not keeping track of openness, other serious mistake 0 incoherent (b) smart locks There are two general ways to solve this problem. In both cases, it's important to use an ordinary lock as the parent! (That's part of what's MEANT by "proper object-oriented programming style" -- using inheritance to avoid rewriting code.) Also, in both solutions the smart-lock OPEN method has to know whether the pin is correct so that it can keep track of the number of incorrect attempts. In one solution, the smart-lock OPEN method compares the user's pin with the lock's pin itself: (define-class (smart-lock my-pin) (parent (lock my-pin)) (instance-vars (errors 0)) (method (open pin) (cond ((>= errors 3) '(lock shut down)) ((not (equal? pin my-pin)) (set! errors (+ errors 1)) (usual 'open pin)) (else (usual 'open pin))))) In the other solution, the smart-lock OPEN method calls the ordinary lock OPEN method, checking the value returned to find out whether the pin was correct: (define-class (smart-lock my-pin) (parent (lock my-pin)) (instance-vars (errors 0)) (method (open pin) (if (>= errors 3) '(lock shut down) (let ((result (usual 'open pin))) (if (equal? result '(sorry wrong pin)) (set! errors (+ errors 1))) result)))) Neither of these is really perfect. The first approach duplicates in smart-lock the pin-testing that ordinary locks already do. This isn't so important when the testing is just a comparison of two numbers, but suppose we later change how PINs are represented or tested; we'd then have to make similar changes in two class definitions. The second approach avoids that problem by letting the usual lock OPEN method do the pin-testing. But it relies on the text of the error message to find out the result of the test; if we translate the error messages to another language, the smart-lock class might mysteriously stop working. The best solution, although not allowed by the structure of the problem, would be to redesign the ordinary lock class so that it has an additional CORRECT-PIN? method that takes a trial pin and returns #T or #F to indicate whether it's the correct pin. (define-class (lock my-pin) (instance-vars (open? #f)) (METHOD (CORRECT-PIN? PIN) ;;; added (EQUAL? PIN MY-PIN)) ;;; added (method (open pin) (cond ((not (ASK SELF 'CORRECT-PIN? PIN)) ;;; changed '(sorry wrong pin)) (open? '(lock is open already!)) (else (set! open? #t) '(lock opens)))) (method (close) (cond ((not open?) '(lock is closed already!)) (else (set! open? #f) '(lock closes))))) (define-class (smart-lock my-pin) (parent (lock my-pin)) (instance-vars (errors 0)) (method (open pin) (cond ((>= errors 3) '(lock shut down)) ((not (ASK SELF 'CORRECT-PIN? PIN)) ;; changed (set! errors (+ errors 1)) (usual 'open pin)) (else (usual 'open pin))))) Note that we can use ASK SELF rather than USUAL because there's no explicit CORRECT-PIN? method in the smart-lock class, so we get the parent's method by inheritance. Using ASK SELF is better because it allows for the possibility that we might later decide to give the smart-lock class its own testing method (perhaps using USUAL to include the standard test). Scoring: 3 correct 2 trivial mistake 1 not keeping track of errors, other serious mistake 0 no inheritance, incoherent 4. Filling binary trees (a) make-filler The solution we expected was: (define (make-filler levels) (if (= levels 0) '() (make-tree 0 (make-filler (- levels 1)) (make-filler (- levels 1))))) As it turns out, there is also a correct iterative solution: (define (make-filler levels) (define (helper levels tree) (if (= levels 0) tree (helper (- levels 1) (make-tree 0 tree tree)))) (helper levels '())) This works by using the very same tree as both left and right child of each non-leaf node. (The other solution uses two separate trees that have the same shape and the same data.) A common mistake was to misread the question and think that (make-filler 1) should return the number 0, rather than a one-node tree with 0 as its entry. We gave these solutions 3 points if nothing else was wrong, although you should bear in mind that an error in the base case affects every other result also; all of the leaves of the tree will be ill-formed. Another common mistake, here and in part (b), was to think that a binary tree means a pair with the left branch as its car and the right branch as its cdr. This isn't just a benign data abstraction violation that looks ugly but works! It produces nodes that have branches but no actual data. Scoring: 4 correct 3 trivial mistake 2 tree recursive (or correctly iterative) but not binary trees 0 even worse (b) fill-help There are two general categories of solution, depending on whether the procedure is willing to accept the empty list as its TREE argument. If so, that's the base case: (define (fill-help tree dep) (if (null? tree) (make-filler (+ depth 1)) (make-tree (entry tree) (fill-help (left-branch tree) (- dep 1)) (fill-help (right-branch tree) (- dep 1))))) If not, then the procedure must check each branch separately for emptiness: (define (fill-help tree dep) (make-tree (entry tree) (if (null? (left-branch tree)) (make-filler dep) (fill-help (left-branch tree) (- dep 1))) (if (null? (right-branch tree)) (make-filler dep) (fill-help (right-branch tree) (- dep 1))))) A variant version of the above, instead of separate IF expressions for each branch, uses a four-way COND for all the possible cases of existing or non-existing branches: (define (fill-help tree dep) (cond ((and (null? (left-branch tree)) (null? (right-branch tree))) (make-tree (entry tree) (make-filler dep) (make-filler dep))) ((and (null? (left-branch tree)) (not (null? (right-branch tree)))) (make-tree (entry tree) (make-filler dep) (fill-help (right-branch tree) (- dep 1)))) ((and (not (null? (left-branch tree))) (null? (right-branch tree))) (make-tree (entry tree) (fill-help (left-branch tree) (- dep 1)) (make-filler dep))) (else (make-tree (entry tree) (fill-help (left-branch tree) (- dep 1)) (fill-help (right-branch tree) (- dep 1)))) But people who wrote it that way often made mistakes, leaving out some cases or getting the branches backward in the calls to make-tree. A common mistake was to use (= DEP 0) as the base case. DEP reaches zero at the very bottom of the tree (nodes J, K, L in the example), but the program also has to work for higher leaf nodes (such as E in the example). Scoring: 6 correct 5 trivial mistake [for example, DEP instead of (+ DEP 1)] 4 has the idea: tree recursive, makes binary trees (even if DAVs), works for one-child nodes, *and* adds zeros at the bottom 2 has an idea: tree recursive 0 worse 5. Adventure game. The solution we wanted was this: (define (act room request) (if (= (length request) 1) ; or (null? (cdr request)) ((get room (car request))) ((get (cadr request) (car request))) )) The crucial point is that there are two sets of parentheses around each of the invocations of GET. First GET is invoked, and it returns a procedure, which is in turn invoked. The examples of data-directed programming in the text don't have quite this form because they do error checking. They're more like this: (let ((proc (get ... ...))) (if proc (proc ...) (error ...))) But the idea is the same; we must invoke the procedure that we find in the table. Scoring: We divided the 8 points for this question into three parts. 1. Invocation. 3 points if the procedure returned by GET is invoked correctly; 2 points if it's invoked with arguments; no points if not invoked at all. 2. Use of GET. 3 points if correct. 2 points or less if room is used as an argument no matter what. 1 point or less if elements of the data are built in, e.g., calls to VISIT. No points if the arguments to GET are quoted: (get '(cadr request) '(car request)) ; WRONG! This comes from magic thinking: "You always have to quote the arguments when you use get." Pfui! Quoting means the same thing in this context that it means in any other context. 3. List processing of the request. 2 points if correct. 1 point or less for things like CDR instead of CADR, or forgetting the CAR for a one-word request. 1 point or less if a call to read-line is included within the definition. ----------------------------------- If you don't like your grade, first check these solutions. If we graded your paper according to the standards shown here, and you think the standards were wrong, too bad -- we're not going to grade you differently from everyone else. If you think your paper was not graded according to these standards, bring it to Brian, Dan, or your TA. We will regrade the entire exam carefully; we may find errors that we missed the first time around. :-) If you believe our solutions are incorrect, we'll be happy to discuss it, but you're probably wrong!