CS 61A Spring 1995 Midterm 3 solutions 1. Box & pointer diagrams In the diagrams below, the arrows drawn with dots (......>) are replaced by mutation with the ones drawn in bangs (!!!!!!>). You didn't have to show the old ones to get credit. > (let ((x (list 1 2 3 4))) (set-cdr! x (caddr x)) x) (1 . 3) [Note the dot!!] +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| ---------> | | | +....>| | | ----->| | | ----->| | | / | | | | ! | | | | | | | | | | | |/ | +-|-+-!-+ +-|-+---+ +-|-+---+ +-|-+---+ | ! | | | | ! | | | V ! V V V ! 1 ! 2 3 4 ! ^ ! ! !!!!!!!!!!!!!!!!!!!!! [You didn't have to show the disconnected pairs to get credit; a single pair whose car is 1 and whose cdr is 3 was enough.] > (let ((x (list 1 2 3 4))) (set-car! (cdr x) (cddr x)) x) (1 (3 4) 3 4) !!!!!!!!!!!!! ! V +---+---+ +-!-+---+ +---+---+ +---+---+ | | | | ! | | | | | | | /| ---------> | | | ----->| ! | ----->| | | ----->| | | / | | | | | | . | | | | | | | | |/ | +-|-+---+ +-.-+---+ +-|-+---+ +-|-+---+ | . | | | . | | V V V V 1 2 3 4 [Notice that there are only four pairs in this diagram. It would be an error to draw two extra pairs whose cars are 3 and 4. Make sure you understand this point!] > (let ((x (list 1 (list 2 3) 4))) (set-car! (cadr x) (car x)) x) (1 (1 3) 4) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | | | ----->| | | ----->| | | / | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ | | | | | V | | | | 4 | | | | V | | 1 | ^ V ! +---+---+ +---+---+ ! | | | | | /| !!!!!!!!!!!!+ | ----->| | | / | | . | | | | |/ | +-.-+---+ +-|-+---+ . | V V 2 3 [Note that the new arrow points to the 1, not to the pair above it. It's okay if you wrote another 1 near the 2 instead of drawing an arrow across to the left. (It's *not* okay to duplicate pairs, because that obscures the fact that modifying the one pair would change two parts of the printed representation. But numbers aren't mutable, so it doesn't really matter whether there's one one or two ones.)] Scoring: One point each. Both the printed form and the diagram had to be right. 2. OOP passwords (define-class (password-protect obj pwd) (default-method (if (eq? message pwd) obj (error "Password incorrect")))) That's it! You have to use default-method because you don't know ahead of time what the password will be, so your method must check explicitly. Scoring examples: 4 correct. 3 uses default-method but syntax not quite right: (default-method (lambda (message) (if ...))). 3 Tries for a variable message: (method pwd ...). 2 (parent obj). 2 Really bad syntax. 1 Uses default-method but has the counter example built in. 1 A bare glimmer of an idea. 0 Even worse. By the way, there's no need for, e.g., (ask self obj). You can just use the symbol obj to refer to an object's local variable. 3. Deep-map! Here is the most elegant solution: (define (deep-map! fn lst) (cond ((null? lst) '()) ((atom? lst) (fn lst)) (else (set-car! lst (deep-map! fn (car lst))) (set-cdr! lst (deep-map! fn (cdr lst))) lst))) This solution depends on the fact that a value is returned for each invocation. Also, it works for improper lists, even though we didn't require that -- if you think about it the right way, handling the more general case makes the problem easier, not harder. Most people invented a solution that doesn't depend on the return value: (define (deep-map! fn lst) (cond ((null? lst) 'ok) ((atom? (car lst)) (set-car! lst (fn (car lst)))) (else (deep-map! fn (car lst)))) (cond ((null? lst) 'ok) ((atom? (cdr lst)) (set-cdr! lst (fn (cdr lst)))) (else (deep-map! fn (cdr lst)))) lst) The only trouble with that solution is that most people who tried it forgot to check for an empty argument in *both* CONDs. There were also solutions with lots of checks for special cases, e.g., checking for a list in which each element is an atom, or handling the second element of a list explicitly, etc. It's possible to get such a solution to work, but really you should try to develop a stronger aesthetic sense about trusting the recursion to handle the second element and so on. Nothing in the problem suggests the use of the Tree abstract data type; there should not have been any calls to DATUM or CHILDREN in your solution. Don't be confused about the use of the word "tree" in the phrase "tree recursion," which just means any situation in which there are two or more recursive calls carried out from the same invocation of a procedure. The tree ADT would only be relevant if the examples used make-node, etc. Scoring examples: 4 Correct. 3 Correct except for base case(s). 2 Sequential (map!) instead of tree recursive. 1 (set! lst ...) 1 (set-car! some-non-pair ...) 0 (set! (car lst) ...) 0 Uses CONS 4. Stream of ones and zeros. Okay, this was a hard problem, we admit. But many people did pretty well with it. The beautiful solution we were hoping for is this: (define oz (cons-stream '() (interleave (map (lambda (set) (cons 0 set)) oz) (map (lambda (set) (cons 1 set)) oz)))) A few other ideas turned up that were clever but not easily workable. Each of these ideas can be made to work, but with *much* more agony than the solution above. ------ One idea was this, using the SUBSETS procedure from the course reader: (define one-zero (cons-stream 1 (cons-stream 0 one-zero))) (define oz (subsets one-zero)) ;; wrong! The main problem with this is that the SUBSETS in the reader works only for a finite stream. You can see this in two ways. From an algorithm point of view, the problem is that the procedure must compute (subsets (tail strm)) before it can produce even one element of its own result, so there is an infinite recursion. From a mathematical point of view, *any* procedure that claims to produce a stream of all the subsets of an infinite stream must be incorrect, because the number of subsets of an infinite set is uncountable, and a stream has to be at most countably infinite. A second problem is that, since the stream one-zero contains duplicates, its subsets will contain duplicates also. To fix the first problem, what we can do is write a procedure that makes a stream of the *finite* subsets of an infinite stream. (There are only countably many of those, and it's all we need for this purpose.) (define (n-subsets n set) (cond ((= n 0) (stream '())) ((empty-stream? set) the-empty-stream) (else (interleave-delayed (map (lambda (subset) (cons (head set) subset)) (n-subsets (- n 1) (tail set))) (delay (n-subsets n (tail set))))))) (define (finite-subsets set) (define (helper n) (interleave-delayed (n-subsets n set) (delay (helper (1+ n))))) (helper 0)) Note that, unlike our original solution to the oz problem, this program won't work unless we use interleave-delayed. To solve the second difficulty, we can write a remove-duplicates procedure for infinite streams. (This is left as an exercise for the reader!) ------ Another clever attempt at a solution is this: (define oz (map convert-to-binary integers)) ;; wrong! where convert-to-binary is a procedure that returns a list containing ones and zeros to represent its argument as a binary numeral, e.g., > (convert-to-binary 14) (1 1 1 0) > (convert-to-binary 20) (1 0 1 0 0) (We haven't actually written convert-to-binary; it's left as an exercise.) The trouble with this approach is that it doesn't include the elements of the desired result that have zeros at the left, and it doesn't include the empty list. One solution would be to compute all of the lists OF A GIVEN LENGTH using a procedure convert-to-n-digit-binary and applying that only to the integers between 0 and (2^n)-1, then string those together somewhat like the n-subsets in the previous solution. Some students did this. Another clever fix is to take the binary numerals and their complements, i.e., the strings of bits with each 0 replaced by a 1 and vice versa: (define binaries (map convert-to-binary integers)) (define oz (cons-stream '() (interleave binaries (map complement binaries)))) Alternatively, take all the binary numerals starting with 1 and remove the leftmost 1, so instead of (1) (1 0) (1 1) (1 0 0) (1 0 1) ... we have () (0) (1) (0 0) (0 1) ... This is an especially short solution: (define oz (map (lambda (n) (cdr (convert-to-binary n))) integers)) One student actually got the generate-one-at-a-time approach to work: (define (next-element lst) (cond ((null? lst) '(0)) ((= (car lst) 0) (cons 1 (cdr lst))) (else (cons 0 (next-element (cdr lst)))))) (define (make-oz element) (cons-stream element (make-oz (next-element element)))) (define oz (make-oz '())) We all had to read this over several times before we believed it! (And the student made it harder by giving what I've called next-element the name add-one, which it doesn't do, and which wouldn't give the right answer if it did!) But it's quite impressive. ------ Solutions using the PERMUTATIONS procedure from the text have the same problem as the SUBSETS approach: That procedure works only for finite streams. But we could take permutations of finite streams and join them together for the overall solution. Another problem with using PERMUTATIONS is that _as written_ > (ss (permutations (stream 0 0 0 0 0))) ((0) (0) (0) (0) (0)) because the recursive call: (permutations (remove x S)) will filter out all zeros. So instead of remove we need remove-first. Here is a solution from Trey, once we fix that. Suppose we have one-streams --> (() (1) (1 1) (1 1 1) (1 1 1 1) ... ) zero-streams --> (() (0) (0 0) (0 0 0) (0 0 0 0) ... ) Line them up like this to make a 2-D table: () (1) (1 1) (1 1 1) ... ------------------------------------------------------------- () | () | (1) | (1 1) | (1 1 1) | (0) | (0) | (1 0) | (1 1 0) | (1 1 1 0) | (0 0) | (0 0) | (1 0 0) | (1 1 0 0) | (1 1 1 0 0) | (0 0 0) | (0 0 0) | (1 0 0 0) | (1 1 0 0 0) | (1 1 1 0 0 0) | (0 0 0 0) | (0 0 0 0) | (1 0 0 0 0) | (1 1 0 0 0 0) | (1 1 1 0 0 0 0) | . . . . . . The entries in the table are gotten by appending each of the indices. i.e. at (1 1) and (0 0 0) there is (1 1 0 0 0) By constructing this table, you can find a list made of any number of zeros and ones. So, if you find the permutations of each of the entries in this table, you will get OZ. (define oz (remove-duplicates (map stream->list (flatmap permutations (cross-product zero-streams one-streams))))) (define (cross-product s1 s2) (interleave-delayed (map (lambda (x) (append-streams (head s2) x)) s1) (delay (cross-product s1 (tail s2))))) Cross-product computes the table entries from the two streams. > (ss (cross-product zero-streams one-streams)) (() (1) (0) (1 1) (0 0) (1 0) (0 0 0) (1 1 1) (0 0 0 0) (1 0 0) ...) Since permutations returns a stream of streams, and we want lists, I map stream->list to change all the inner streams to lists, then remove any duplicates. > (ss oz 10) (() (1) (0) (1 1) (0 0) (1 0) (0 0 0) (0 1) (1 1 1) (0 0 0 0) ...) The ordering is a little odd because of the interleaves. ------ Scoring: 4 correct 3 almost correct, or flawed but clever idea like (map binary integers) 2 (subsets one-zero-stream) or similar 1 not nearly correct but shows understanding of the exponential complexity of the problem *or* of the difficulties of handling infinite streams 0 worse NOTE: Far too many people used SET! or SET-CAR! in this problem. Streams are a functional programming technique! They're in chapter 3 because (1) they are the functional alternative to OOP for time-varying data; (2) their *implementation* uses mutation (for memoization only). In particular, if you compute the next element of the stream by mutating the previous element, then you've changed the value of that previous element, too! This is why mutation is problematic. Group problem: ____________________ G: | |<---------+ | | | OO | p: value foo: 6 | b: (lambda (arg) ...) | | maximizer ----------+-------> OO-----------------------------+ | p: arg | ____________________| b: (if (> arg value)...) value | ^ | | | | | | | _________|____________ | E1: | | |<-------------------------------------+ value: 6 | ______________________| ^ | | | _________|____________ E2: | | arg: 6 | ______________________| Scoring examples: 4 OK. 3 OK except missing the anonymous LET procedure. 2 foo is a procedure. 1 Two frames with VALUE bindings. 0 Maximizer procedure created in global frame.