CS 61A Spring 1994 Midterm 2 solutions 1. Box & pointer diagrams > (list '(2 3) '(4 5)) ((2 3) (4 5)) +---+---+ +---+---+ | | | | | /| ---------> | | | --------------------------->| | | / | | | | | | | |/ | +-|-+---+ +-|-+---+ | | | | V V +---+---+ +---+---+ +---+---+ +---+---+ | | | | | /| | | | | | /| | | | ----->| | | / | | | | ----->| | | / | | | | | | | |/ | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | | | | | | | | | V V V V 2 3 4 5 The LIST constructor makes a list whose elements are its arguments. In this case, that means a list of two elements, whose spine is the two pairs on the top row of the diagram. > cons (list 2 3) 4) ((2 3) . 4) +---+---+ | | | ---------> | | | --------> 4 | | | | +-|-+---+ | | | | | V +---+---+ +---+---+ | | | | | /| | | | ----->| | | / | | | | | | | |/ | +-|-+---+ +-|-+---+ | | | | V V 2 3 CONS always constructs exactly one pair -- in this case, the one on the top row of the diagram. Because the second argument to CONS isn't a list, the return value isn't a list either, so there's a dot in its printed representation. > (cddadr '((a b c d e) (f g h i j) (l m n o p) (q r s t u))) (H I J) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | | | ----->| | | ----->| | | / | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ | | | | | | V V V H I J (cdr '((a b c d e) (f g h i j) (l m n o p) (q r s t u))) ===> ((f g h i j) (l m n o p) (q r s t u))) (car '((f g h i j) (l m n o p) (q r s t u))) ===> (f g h i j) (cdr '(f g h i j)) ===> (g h i j) (cdr '(g h i j)) ===> (h i j) > (cons (cdr '(a)) (cdr '(b))) (()) +---+---+ | /| /| ---------> | / | / | |/ |/ | +---+---+ This seems to have been the hardest for most people. The printed form can't be (() . ()), because Scheme *never* prints a dot if the next thing would be a left parenthesis. If in your diagram you drew an arrow pointing to () we accepted it, but if your arrow pointed to '() we didn't, since that means you don't understand what the quote means. There is only one pair in this diagram! Scoring: One point each. 2. Binary search trees. Although the ADT doesn't include empty trees, the program is easier to write if you allow for the possibility of getting an empty list as argument instead of a tree, because that's what happens when you try to recur for the children of a leaf node. On that assumption, here's one way to write it: (define (all-smaller? tree num) (or (null? tree) (and (< (entry tree) num) (all-smaller? (left-branch tree) num) (all-smaller? (right-branch tree) num)))) (define (bst? tree) (or (null? tree) (and (all-smaller? (left-branch tree) (entry tree)) (all-larger? (right-branch tree) (entry tree)) (bst? (left-branch tree)) (bst? (right-branch tree))))) Most people wrote equivalent programs using COND, which is fine, but I find this style cleaner when writing predicates. A BINARY TREE is just a tree in which each node has at most two children. A BINARY SEARCH TREE is a binary tree with the ordering constraints as described in the text. The text doesn't make that entirely clear, because their only use of binary trees is to represent the SET ADT, for which a BST is needed. Therefore, we didn't take off points if in part (a) you assumed the ordering relationship and therefore only checked the right branch of the tree, as long as you did the tree recursion properly in (b). Scoring: This and the remaining problems are graded on the scale 5 correct 3-4 has the idea 1-2 has an idea 0 other Having the idea, in this problem, means doing a tree recursion. The most common form of not having the idea was to think, in part (b), that the ordering must be checked only with respect to the root node, so you left out the recursive calls to BST?. We took off one point if you violated the binary tree ADT, using CAR and CDR instead of ENTRY, LEFT-BRANCH, and RIGHT-BRANCH. (If you thought that those three things are names of trees, rather than of procedures, you didn't have the idea.) A too-common error was to say things like (< (left-branch tree) (entry tree)) as if the left branch were a number! It's not; it's a tree. 3. Song ADT. (define (who-sang song) (define (helper songs) (cond ((null? songs) #f) ((equal? song (title (car songs))) (artist (car songs))) (else (helper (cdr songs))))) (helper great-songs)) The crucial point here was to respect the data abstraction; just finding your way through the list shouldn't be a challenge at this point in the course. So in order to "have the idea" you must say (title (car songs)) and not (caar songs) Some people made up an ADT for list-of-songs. That's perfectly okay, but not required by the problem. But it's *not* okay if you used TITLE to mean CAR when referring to the list of songs! Some people compromised and made up a different ADT in which they had selectors like (define title-of-first-song caar) We weren't quite as unhappy about this as we were if you just ignored data abstraction altogether, but this, too, violates the song ADT. In your list-of-songs type, you shouldn't make assumptions about the representation of an individual song. I was surprised at how many people were nervous about the idea of a global variable. You seemed to think this is a new idea, but in fact every time you invoke CAR or + or SQUARE or WHO-SANG you are using a global variable! A variable is a connection between a name and a value, even if the value is a procedure. Several people tried to solve the problem with FILTER. This is a great idea, except that almost nobody quite got it to work, because they all left out the invocation of CAR shown in capitals here: (define (who-sang song) (let ((songs (filter (lambda (great) (equal? (title great) song)) great-songs))) (if (null? songs) #f (artist (CAR songs))))) The point is that FILTER returns a *list* of things that match the condition. Even if there is only one such thing, FILTER will return a list of length one. So you have to extract the song from that one-long list of songs. Many people used EQ? instead of EQUAL?. We didn't take off for that, because it's not something we've made a fuss about, but it wouldn't work. For now, the rule is that EQ? can be used only to compare atoms, not lists. In a week or two we'll learn what EQ? means for lists, when we talk about mutation. We didn't take off points from the people who expressed incorrect opinions regarding the quality of Led Zeppelin. 4. Combine DDP and M-P. This was the hardest problem for most people, probably because you don't really understand the essential ideas (as opposed to the specific A&S implementation) of DDP and M-P. The answer we wanted was this; the change to operate-2 is shown in capitals: (define (operate-2 op arg1 arg2) (let ((t1 (type arg1))) (let ((proc (DISPATCH t1 op))) (proc (contents arg1) (contents arg2))))) (define (dispatch method-table message) (if (equal? (caar method-table) message) (cdar method-table) (dispatch (cdr method-table) message))) I've shown DISPATCH as a recursive procedure with no base case. What makes that okay is that we said you could leave out the error checks, and for method-table to run out without finding the correct message would be an error. But it's fine if you want to use a COND and check also for (null? method-table). Some people didn't change operate-2 at all, but instead wrote a new procedure GET equivalent to what I've called DISPATCH here; that was okay. There are other possible solutions but it's very hard to do it without a helper procedure to look through the type. Having the idea means extracting the type from an argument and searching through it to find the message. If you built into your program the assumption that all numbers are complex, you got zero points -- that defeats the whole point of the enterprise! One point off for violating the typed-data ADT (using CAR instead of TYPE, for example). We were unsympathetic to people who merely copied the solution to a similar but different problem in one of the sample midterms. Instead of trying to list all the various ways people got this wrong, let me try to explain the point about DDP and M-P. A lot of people thought that if message-passing is involved, then the program has to look like (define (operate-2 op arg1 arg2) (lambda (message) ...)) but that's a superficial understanding. Here's the point: MESSAGE-PASSING means that the knowledge of methods is located in the data themselves, and that those methods are accessed by sending the data messages, which are names for the methods. DATA-DIRECTED PROGRAMMING means that the knowledge of which method goes with what operation and type takes the form of a table, understandable by a general-purpose procedure like operate-2, rather than the form of a COND that checks all the possibilities explicitly. So the idea is that each datum carries around a manifest type consisting of a table that associates methods with messages for that type. Since the table includes the messages, it's possible for different types to accept different messages; this is quite different from that sample midterm problem, in which the four specific operations addition, subtraction, multiplication, and division are built into the mechanism.