CS 61A Spring 1994 Midterm #1 solutions 1. What will Scheme print? > (+ (* 3 4 0 7) 8) 8 > (lambda (x) (/ x 0)) PROCEDURE [Some people said "error." An error will result if this procedure is *invoked*, but there's nothing erroneous about defining it.] > (butfirst '(help!)) () [The butfirst of a *sentence* containing one word is all but that word, i.e., the empty sentence. (BUTFIRST 'HELP!) without the inner parentheses would be butfirst of a word, and would return ELP!, the most common wrong answer. The second most common wrong answer, although we didn't take off for it, was '() -- that is, the correct answer with a quote in front. If you are reading '() in programs as if it were the name of the empty sentence, then you don't understand quoting.] > ((if 3 * +) 4 5) 20 [Since 3 is true, the value of the inner parenthesized expression is the multiplication function.] > (let ((+ -)) (+ 8 2)) 6 [Names of primitives are just ordinary variables that happen to have a predefined value, but that can be overridden by a local binding. Notice that that isn't true about names of special forms; you can't say (LET ((DEFINE +)) ...) etc.] > (+ 9 3) 12 [The effect of a LET binding is local to the body of the LET. It doesn't change the meaning of + globally.] Scoring: 1/2 point each, rounded down. 2. Which are iterative? (define (butfirst-n num stuff) (if (= num 0) stuff (butfirst-n (- num 1) (bf stuff)))) YES. The result of the recursive invocation is the result of the whole thing. (define (member? thing stuff) (cond ((empty? stuff) #f) ((equal? thing (first stuff)) #t) (else (member? thing (bf stuff))))) YES. Same reasoning. (define (addup nums) (if (empty? nums) 0 (+ (first nums) (addup (bf nums))))) NO. In this case, the result of the recursive invocation is one argument to a + invocation that has to be done to produce the overall result. (Why don't we say, in the first example, "the result of the recursive invocation is one argument to an IF invocation"? Because IF and COND are special forms, and their special evaluation rules mean that by the time the recursive call happens, they've already decided that that will be the overall answer. But + is an ordinary procedure, and its actual argument expressions are evaulated *before* it does its work.) Scoring: One point, all or nothing. 3. Increasing? (define (increasing? nums) (cond ((empty? (bf nums)) #t) ((>= (first nums) (first (bf nums))) #f) (else (increasing? (bf nums))))) There are other possible solutions, but all essentially like this. Scoring: Problems 3-5 are scored on this scale: 5 correct except maybe some right parentheses missing. 3-4 has the idea 1-2 has an idea 0 other In this case, "has the idea" means that it's recursive, and that the first two numbers are compared to determine the partial result, and that there wasn't some awful idiosyncratic problem. A typical 4 would have an error in the base case, or getting the test wrong (allowing equality, for example). A typical 3 would be no base case at all, thinking that BUTFIRST means SECOND, etc. 4. Strategies for the 21 project. I was upset by the number of questions asked about this question during the exam. You should all have understood the domain and range of a strategy procedure from doing the project, and if you didn't understand, the information was right there in the exam: A strategy procedure in the 21 project takes two arguments, the player's hand so far and the dealer's visible card, as in this example: (my-strategy '(3h 4d 10c) '5s) It returns true to indicate that the player wants another card, false otherwise. So everybody who asked "what procedure do I have to call to take another card?" *both* didn't do the project and can't read! (a) A strategy that takes another card if and only if we have fewer than 4. (define (four-cards player-hand dealer-card) (< (count player-hand) 4)) That's it! Many people said (define (four-cards player-hand dealer-card) (if (< (count player-hand) 4) #t #f)) and that's okay, but if you think about it, the extra IF doesn't really make any difference. It says: If < returns true, return true; if < returns false, return false. (b) A procedure that returns a strategy like part (a) but for any number: (define (n-cards num) (lambda (player-hand dealer-card) (< (count player-hand) num))) The crucial point is that n-cards itself is *not* a strategy, but it should *return* a strategy as its value. So it uses lambda to create a procedure that follows the strategy rules: takes two arguments, returns true or false. Scoring: 2 points for (a), 3 for (b), except that if your answer to (b) duplicates a mistake in (a) you don't lose points twice. In (b), a 3-point answer is correct; a 2-point answer has the correct domains and ranges, i.e., it's a function that takes one number as argument and returns a function of two arguments, etc. 5. Brooklyn accent. (define (brooklyn wd) (cond ((<= (count wd) 1) wd) ((equal? (first-two wd) 'oi) (word 'er (brooklyn (bf (bf wd))))) ((equal? (first-two wd) 'er) (word 'oi (brooklyn (bf (bf wd))))) (else (word (first wd) (brooklyn (bf wd)))))) (define (first-two wd) (word (first wd) (first (bf wd)))) Of course you don't have to define first-two as a separate procedure, but you must make some equivalent test. You can't say (equal? (first-two wd) (or 'oi 'er)) ;; wrong!!!!! Scheme isn't English. Ask me or your TA for help if you don't understand this. It turns out that, even though we said "assume the argument word will always contain at least one letter," you have to handle the case of an empty word, because if the last two letters are OI or ER, the recursive call (BROOKLYN (BF (BF WD))) will use an empty word as argument. But we didn't take off for missing that subtle point, because I didn't realize it myself at first! A typical 3-point answer would forget the need to butfirst the word twice in the recursive call for OI and ER cases, or would stop looking after finding one OI or ER. A surprising number of people wanted to use SENTENCE rather than WORD as the combiner; I don't understand why.