CS 61A Spring 1995 Midterm #1 solutions 1. What will Scheme print? > (first (butfirst '(yesterday))) ERROR ['(yesterday) is a sentence of length 1. Its butfirst is therefore an empty sentence. First of an empty sentence is an error.] > ((lambda (x) x) (lambda (x) x)) PROCEDURE [The expression ((lambda (x) x) --ANYTHING--) is the same as just typing the anything; the procedure just returns its argument. So in this case, the entire expression is the same as if we'd just typed (lambda (x) x) -- that is, the second one -- and the value of that expression is a procedure.] > ((lambda (w) (sentence (word 'h w) (word 'th w))) 'ere) (HERE THERE) [Substitute 'ere for w in the body, and you get the expression (sentence (word 'h 'ere) (word 'th 'ere)).] > (+ (* 3 5 0 7) (- 8 2)) 6 [I think everybody got this one!] > (and (> 2 3) (/ 5 0)) #F [AND is a special form. It evaluates its arguments from left to right, and as soon as any argument is false, it stops. So the second argument expression is never evaluated.] > (let ((me 'you) (you 'me)) (sentence 'you 'love me)) (YOU LOVE YOU) [The quoted words 'you and 'love evaluate to YOU and LOVE regardless of any variable bindings. The unquoted word ME is a variable reference, for which its value, YOU, is substituted.] Scoring: 1/2 point each, rounded down, except that you only lost 1/2 point once for leaving out the parentheses in the two sentences, and you only lost 1/2 point once for quoting the two sentences. [Please be sure you understand that it's wrong to quote them! Scheme does NOT print '(HERE THERE) for the third example, etc.] 2. List the calls to ALL-VOWELS? in this: (define (all-vowels? wd) (cond ((empty? wd) #t) ((vowel? (first wd)) (all-vowels? (bf wd))) (else #f))) (define (keep-all-vowels sent) (cond ((empty? sent) '()) ((all-vowels? (first sent)) (se (first sent) (keep-all-vowels (bf sent)))) (else (keep-all-vowels (bf sent))))) > (keep-all-vowels '(eva ai xxx a)) (ALL-VOWELS? 'EVA) (ALL-VOWELS? 'VA) (ALL-VOWELS? 'AI) (ALL-VOWELS? 'I) (ALL-VOWELS? "") (ALL-VOWELS? 'XXX) (ALL-VOWELS? 'A) (ALL-VOWELS? "") for a total of eight calls. The key point is that once a consonant is seen, there are no more recursive calls for that word. Scoring: 3 correct 2 missing the base-case calls, or one extra call 1 two or more wrong, or keep going after consonants 0 no recursive calls, or a call per individual letter We didn't take off if you said '() instead of "" because that distinction wasn't the point of this problem, but you should know that the empty word and the empty sentence are two different things! 3. make-false-ok Several solutions are possible. The most straightforward is (define (make-false-ok oper) (lambda (x y) (if (or (equal? x #f) (equal? y #f)) #f (oper x y)))) Brandy's more elegant solution, taking advantage of the fact that AND is a special form: (define (make-false-ok oper) (lambda (x y) (and x y (oper x y)))) There are intermediately elegant ones like (if (and x y) (oper x y) #f). We didn't take off for tests involving NUMBER? or BOOLEAN? even though a strict reading of the problem tells you that the only special case value for the arguments is #F. Scoring: 5 correct. 4 uses = instead of EQUAL? to test non-numbers. uses + as a formal parameter. (This can work, but is really ugly.) incorrect test condition, e.g., (or x y). 3 doesn't do (oper x y) but does get (lambda (oper) (lambda (x y) ...)) and isn't bizarre. [There were only a few special cases about this.] 2 returns a function, but not an appropriate one, e.g., not one with two args. 1 creates a function with lambda, but then invokes it instead of returning it. 0 no lambda at all. has the specific example built in, e.g., (> x 30) or something. 4. Modify count-coins into a predicate (define (change-possible? amount coin-sent) (cond ((= amount 0) #T ) ---- ((or (< amount 0) (empty? coin-sent)) #F ) ---- (else ( OR (change-possible? (- amount (first coin-sent)) ---- coin-sent) (change-possible? amount (bf coin-sent)))))) Scoring: 3 correct 2 a correct procedure not following the framework, e.g., (if (not ...) ...) instead of (or ...) 1 gets the wrong answer, but at least a Boolean answer, e.g., base cases backwards 0 doesn't even always return a Boolean 5. Two-twice? The most straightforward solution: (define (two-twice? wd) (cond ((< (count wd) 3) #f) ((substring? (word (first wd) (second wd)) (bf wd)) #t) (else (two-twice? (bf wd))))) (define (substring? two wd) (cond ((< (count wd) 2) #f) ((equal? two (word (first wd) (second wd))) #t) (else (substring? two (bf wd))))) Another equally good solution: (define (two-twice? wd) (define (helper twos) (cond ((empty? twos) #f) ((member? (first twos) (bf twos)) #t) (else (helper (bf twos))))) (helper (make-twos wd))) (define (make-twos wd) (if (< (count wd) 2) '() (sentence (word (first wd) (second wd)) (make-twos (bf wd))))) Yet another, not-so-obvious one: (define (two-twice? wd) (cond ((< (count wd) 3) #f) ((and (equal? (first wd) (last (butlast wd))) (equal? (second wd) (last wd))) #t) (else (or (two-twice? (butfirst wd)) (two-twice? (butlast wd)))))) Some people misunderstood what the problem was asking, because of not thinking hard enough about the examples shown. For example, if your program includes (member? (first wd) (bf wd)) then you are answering the question "are there two letters, each of which appears twice in the word?" instead of the question "is there a pair of consecutive letters that appears twice in the word?" On the other hand, if your program includes (member? (word (first wd) (second wd)) (bf wd)) then what you don't understand is how the MEMBER? procedure works! Only a single letter can be a member of a word. Scoring: 5 correct. 4 error in base case. (bf (bf wd)) in recursion. 3 uses (MEMBER? (FIRST WD) (SECOND WD) (BF WD)) or equivalent. 2 compares single letters. compares only adjacent letters or pairs. 1 not a predicate, or really off the wall. 0 even more off the wall than that. has specific example words (e.g., banana) built in. --------------- If you think your paper was misgraded, bring it to Mike Clancy, who will regrade the entire test.