CS 61A Spring 2001 Midterm #1 solutions 1. What will Scheme print? > (butfirst (butlast (se '(this) 'is '(easy)))) (IS) (se '(this) 'is '(easy)) ==> (this is easy) (butlast '(this is easy)) ==> (this is) (butfirst '(this is)) ==> (is) The last step was the hardest; some people said IS rather than (IS). But there's a big difference between a word and a one-word sentence: (first 'is) ==> I (first '(is)) ==> IS Butfirst of a sentence is always a sentence, never a word. > (car ((lambda (lst) (cdr lst)) '((1 2) (3 4)))) (3 4) The easiest way to think about this is to see that (lambda (lst) (cdr lst)) is the same function as CDR, so this expression is really just (car (cdr '((1 2) (3 4)))) (cdr '((1 2) (3 4))) ==> ((3 4)) (car '((3 4))) ==> (3 4) Analagously to the first problem, CDR of a two-element list is a one-element sublist, *not* just the second element. CADR gives the second element. > (let ((rotate (lambda (a b c) (if (number? a) a (b c 2 3))))) (rotate rotate rotate 1)) 1 Substituting ROTATE for A, ROTATE for B, and 1 for C in the body of ROTATE gives (if (number? rotate) rotate (rotate 1 2 3)) ROTATE isn't a number; it's a procedure. So we call ROTATE again, this time with A=1, B=2, C=3: (if (number? 1) 1 (2 3 2 3)) This time, 1 is a number, so we return 1. > (if (equal? '2 2) + -) PROCEDURE Many people found this one tricky, answering either + or - rather than PROCEDURE. In fact (EQUAL? '2 2) returns #T, so Scheme *evaluates* the expression +. But its value isn't +, but is the primitive addition procedure. > (map butfirst '((she loves you) (help!) (penny lane))) ((LOVES YOU) () (LANE)) The common wrong answer here was "error," but there's nothing wrong with this expression, not even a data abstraction violation. The second argument to MAP isn't a sentence, so it isn't a valid argument to BUTFIRST. But MAP doesn't call BUTFIRST with that whole thing as its argument! Rather, MAP calls BUTFIRST three times: (butfirst '(she loves you)) ==> (loves you) (butfirst '(help!)) ==> () (butfirst '(penny lane)) ==> (lane) MAP makes a list of these three results. The second argument to MAP is a *list of sentences*, so each element is a sentence, so it *is* a valid argument to BUTFIRST. Another common wrong answer was ((LOVES YOU) (ELP!) (LANE)). This comes from wanting to treat a one-word sentence as if it were a word. But words and sentences are not the same data type. BUTFIRST of an N-word sentence is always an (N-1)-word sentence, even if N=1. Scoring: 1 point each. 2. Every-nth and data abstraction The key point here is the same as in the last part of question 1: We are dealing with a *list of sentences*, so the list itself should be examined using CAR/CDR/NULL?, but each element of that list is a sentence, so it should be examined using FIRST/BF/EMPTY?. The return value from EVERY-NTH is supposed to be a *sentence*, so we should construct it using SENTENCE: (define (every-nth num list-of-sents) (define (nth num sent) (if (= num 0) (FIRST sent) (nth (- num 1) (BUTFIRST sent)))) (if (NULL? list-of-sents) '() (SENTENCE (nth num (CAR list-of-sents)) (every-nth num (CDR list-of-sents))))) The formal parameters were chosen to be helpful; there wasn't anything tricky about this problem. The abbreviations BF and SE (for BUTFIRST and SENTENCE) were fine too. Scoring: 1 point per blank. 3. Enumerate-buzz and efficiency (a) What value? > (enumerate-buzz 10 20) (10 11 12 13 BUZZ 15 16 BUZZ 18 19 20) The only common error was to forget one of the two BUZZed elements. Scoring: 2 points, minus 1 per wrong/missing/extra element. (b) Order of growth in time: Theta(N). What's N? We're interested in ENUMERATE-BUZZ, not BUZZ, so the best choice for N is the number of elements in the result, (END-START)+1. We're told that all primitive procedures take constant time, so BUZZ takes constant time, since it calls only primitives, with no recursion. [This is actually a slight handwave, since MEMBER? actually takes time proportional to the number of digits in its argument X. But the number of digits in X isn't the N we're interested in; for example, the expression in part (a) calls BUZZ only with two-digit numbers, so MEMBER?'s time *is* constant over this range of numbers.] As for ENUMERATE-BUZZ, it makes N calls to BUZZ, >, CONS, and +, each of which takes constant time, so the N calls make this Theta(N) time. Scoring: 2 points, all or nothing. (c) Use of space: Recursive process. The context of the recursive call in ENUMERATE-BUZZ is (cons (buzz start) (enumerate-buzz ...)) So after enumerate-buzz returns, there is still work to do, namely the CONS call. Therefore this is a recursive process, not an iterative one. Scoring: 2 points, all or nothing. 4. Applicative vs. normal order Let's try it: STk> (load "~cs61a/lectures/1.1/order.scm") okay STk> (def (garply x) (+ (* x x) 1)) garply STk> (normal (garply ((lambda (y) (* y 2)) (* 2 2)))) (garply ((lambda (y) (* y 2)) (* 2 2))) ----> (+ (* ((lambda (y) (* y 2)) (* 2 2)) ((lambda (y) (* y 2)) (* 2 2))) 1) (* ((lambda (y) (* y 2)) (* 2 2)) ((lambda (y) (* y 2)) (* 2 2))) ((lambda (y) (* y 2)) (* 2 2)) (* 2 2) ==> 4 ;; FIRST MULTIPLY ((lambda (y) (* y 2)) 4) ==> 8 ;; SECOND MULTIPLY ((lambda (y) (* y 2)) (* 2 2)) (* 2 2) ==> 4 ;; THIRD MULTIPLY ((lambda (y) (* y 2)) 4) ==> 8 ;; FOURTH MULTIPLY (* 8 8) ==> 64 ;; FIFTH MULTIPLY (+ 64 1) ==> 65 65 STk> (applic (garply ((lambda (y) (* y 2)) (* 2 2)))) (garply ((lambda (y) (* y 2)) (* 2 2))) ((lambda (y) (* y 2)) (* 2 2)) (* 2 2) ==> 4 ;; FIRST MULTIPLY ((lambda (y) (* y 2)) 4) ==> 8 ;; SECOND MULTIPLY (garply 8) ----> (+ (* 8 8) 1) (* 8 8) ==> 64 ;; THIRD MULTIPLY (+ 64 1) ==> 65 65 STk> In normal order, the *expression* ((LAMBDA (Y) (* Y 2)) (* 2 2)) is used as the argument to substitute for X in the body of GARPLY. Since X is used twice in the expression (* X X), the two multiplications shown in that expression are evaluated twice each. Then the final (* X X) adds a fifth multiplication. In applicative order, that argument expression is *evaluated* (using two multiplications), and the value 8 is substituted for X in (* X X), which does a third multiplication. The result, of course, is the same both ways, since this expression is purely functional, so order of evaluation doesn't affect the result. So: (a) 5 for normal, 3 for applicative. (b) 65 for both. Scoring: 2 points each for (a), 1 point each for (b). 5. Twenty-one project. (a) The procedure CONTRARY is supposed to take a strategy as argument, and return a new strategy -- that is to say, a procedure that takes hand and card as arguments: (define (contrary strat) (lambda (customer-hand dealer-card) (not (strat customer-hand dealer-card)))) It's the domains and ranges that are crucial here. CONTRARY must take one argument, not three; it must use LAMBDA to create a procedure of two arguments. And it must call STRAT correctly. If you didn't know about NOT, it was okay to say (if (strat customer-hand dealer-card) #F #T) but you should try to learn the most elegant solutions to these problems. Scoring: 2 points, all or nothing. (b) This question didn't ask you to write a procedure; it asked for an expression you might type at the Scheme prompt, using variables defined elsewhere: ((contrary my-strat) my-hand my-card) The inner parentheses call CONTRARY to produce a new strategy; the outer ones call that new strategy. The most common wrong answer was (contrary (my-strat my-hand my-card)) ;; WRONG!!!! which would give CONTRARY an argument of #t or #f instead of a procedure. Scoring: 2 if correct, 0 otherwise, except that we gave 1 point for a correctly formed expression that used particular values instead of the variables we specified: ((contrary stop-at-17) '(3h 7d 5c) 'as) ;; ONE POINT (c) map over subsets of a hand There are several ways of arriving at a correct solution. One way: (define (suit-map fn hand) (define (get-suit suit) (filter (lambda (card) (equal? (last card) suit)) hand)) (map fn (list (get-suit 'D) (get-suit 'C) (get-suit 'H) (get-suit 'S)))) ...which first filters all the suits and puts them in a list, and them maps the function over that list of sentences. Alternatively, you can avoid the use of MAP by calling FN explicitly for each suit and combining the four results into a list: (define (suit-map fn hand) (define (get-suit suit) (filter (lambda (card) (equal? (last card) suit)) hand)) (list (fn (get-suit 'D)) (fn (get-suit 'C)) (fn (get-suit 'H)) (fn (get-suit 'S)))) Of course either of these can be written replacing the helper procedure GET-SUIT with four explicit calls to FILTER: (define (suit-map fn hand) (list (fn (filter (lambda (card) (equal? (last card) 'D)) hand)) (fn (filter (lambda (card) (equal? (last card) 'C)) hand)) (fn (filter (lambda (card) (equal? (last card) 'H)) hand)) (fn (filter (lambda (card) (equal? (last card) 'S)) hand)))) Finally, instead of four subexpressions, one for each suit, you could use MAP to handle all four cases at once: (define (suit-map fn hand) (map (lambda (suit) (fn (filter (lambda (card) (equal? (last card) suit)) hand))) '(D C H S))) ...which is a little tricky because you have to map over the list of suit names instead of mapping over the hand. (Remember, the result is supposed to be a list of exactly four elements no matter how many cards are in the hand!) And of course you can do it without higher order functions at all by writing GET-SUIT recursively instead: (define (suit-map fn hand) (define (get-suit suit hand) (cond ((empty? hand) '()) ((equal? (last (first hand)) suit) (se (first hand) (get-suit suit (bf hand)))) (else (get-suit suit (bf hand))))) (list (fn (get-suit 'D hand)) (fn (get-suit 'C hand)) (fn (get-suit 'H hand)) (fn (get-suit 'S hand)))) The crucial tasks are: * Extract four subsets from the hand, one per suit. * Apply FN to each subset -- not to each card! * Combine the results into a list -- not into a sentence. Most people managed the first of these, apart from minor errors (such as writing a procedure like get-suit above that makes a sentence of only the suit part of each card: (H H H H) for example). A few people just did the equivalent of (EVERY FN HAND), which got no credit. A few people never invoked FN at all, but the most common way to get in trouble over the second task was to say (map fn (get-suit 'D hand)) ;WRONG!!! which calls FN for each card separately. In combining the results, several people tried calling CONS with four arguments (instead of using LIST as above). Sorry, but CONS constructs exactly one pair, which must have exactly two parts (car and cdr), so CONS requires exactly two arguments. You could make a list of four elements by calling CONS four times: (cons ... (cons ... (cons ... (cons ... '())))) but it's much easier to use LIST as the constructor in this situation. Another way to get in trouble, if you used higher order functions for this task, was to use EVERY instead of MAP in the first solution shown above. This isn't just a data abstraction violation; it gives the wrong answer, flattening the four results into a sentence, so instead of > (suit-map (lambda (x) x) '(3S 4D JS 8C 3D)) ((4D 3D) (8C) () (3S JS)) you'd get the answer (4D 3D 8C 3S JS) ;; wrong! Scoring: The overall guideline was 4 correct 3 trivial errors 2 has the idea 0 other (Note that with rare exceptions we didn't give 1 point.) For the most part, solutions in which the only failed task was combining the four results into a list got 3 points; solutions that called FN for each card got 2; solutions that didn't even separate the suits, or didn't call FN at all, got 0. 6. Mad Libs. The most straightforward solution was to use a helper procedure: (define (mad-libs story) (lambda (nouns adjectives) (define (helper story nouns adjs) (cond ((empty? story) '()) ((equal? (first story) '*NOUN) (se (first nouns) (help (bf story) (bf nouns) adjs))) ((equal? (first story) '*ADJECTIVE) (se (first adjs) (help (bf story) nouns (bf adjs)))) (else (se (first story) (help (bf story) nouns adjs))))) (helper story nouns adjectives))) Having a named helper with all three sentences as its arguments allows walking down the three sentences with simple recursive calls. Without the helper it's a little trickier: (define (mad-libs story) (lambda (nouns adjectives) (cond ((empty? story) '()) ((equal? (first story) '*NOUN) (se (first nouns) ((mad-libs (bf story)) (bf nouns) adjs))) ((equal? (first story) '*ADJECTIVE) (se (first adjs) ((mad-libs (bf story)) nouns (bf adjs)))) (else (se (first story) ((mad-libs (bf story)) nouns adjs)))))) Note the double open parentheses at the points where MAD-LIBS is called recursively. We're trying to build up a sentence with an expression like (se ) but the call to MAD-LIBS doesn't return a sentence (the rest of the story); it returns a procedure, and we have to call that procedure to get the rest of the story. One of the most common mistakes was (se (first ___) (mad-libs (bf story))) ;; wrong! which would try to use a procedure -- the one mad-libs returns -- as part of a sentence! These solutions got at most 4 points. Many people invented unnecessary selectors and constructors for data types that weren't part of the specification, things like FIRST-NOUN and FIRST-ADJECTIVE. You were told that NOUNS and ADJECTIVES are sentences, so there's no reason you shouldn't use the ordinary sentence selectors and constructors for them. Presumably these people were bending over backward because of fear of losing points for data abstraction violations. We didn't take off points for this if the resulting program was readable. Scoring: There were two big ideas here: * DOMAIN AND RANGE: Mad-libs is a procedure that takes one argument, a sentence. It returns a procedure that takes two sentences as arguments, returning a sentence. Mostly this means that the first two lines (define (mad-libs story) (lambda (nouns adjectives) had to be correct. * SENTENCE PROCESSING: The program had to walk down three sentences, going to the next word of STORY for each recursive call but taking the next noun or adjective only sometimes. 8 correct. 7 trivial errors (such as missing or extra quotation marks!) 6 both big ideas understood, but significant errors, or data abstraction violations (CAR or CDR of a sentence), or *really* hideous code. 4 either correct processing but errors about domain and range, or domain and range correct but processing problems (such as taking the butfirst of all three sentences each time). 2 domain and range correct but processing totally incoherent or missing. 0 even worse. Note that we did not assign scores of 5, 3, or 1 except in rare cases when we couldn't decide between two grades.