CS 61A Fall 1994 Final exam solutions 1. Higher-order functions. (define (multicompose funs) (lambda (x) (if (null? funs) x ((car funs) ((multicompose (cdr funs)) x))))) Two crucial points to note: The return value in the base case is *not* the empty list; the parentheses in the last line are very important! Many other arrangements of the same idea are possible. If those parentheses seem frightening, some of them can be avoided by using a helper function: (define (multicompose funs) (define (helper funs x) (if (null? funs) x ((car funs) (helper (cdr funs) x)))) (lambda (x) (helper funs x))) An even more elegant solution uses the COMPOSE function that you've seen before: (define (compose f g) (lambda (x) (f (g x)))) (define (multicompose funs) (if (null? funs) (lambda (x) x) (compose (car funs) (multicompose (cdr funs))))) Typical errors: 4 points Use LAST, BUTLAST (a data abstraction violation because the argument is a list of procedures, not a sentence which is a list of words). Bad base case (most often (lambda (x) '())). 3 points Apply the functions in reverse order. Try to avoid the reverse-order bug by reversing the list, but fail. Forget to invoke the result of the recursive call. No base case at all. 2 points Apply each function separately to x instead of composing them. Call multicompose with two arguments (as if it were helper). Name/value confusion, such as thinking LIST is in the argument list, in the examples, or calling EVAL on an element of the argument list. 1 point Don't return a function (for example, return a list of functions). 0 points Use SET!. (The question did say, in boldface, "no mutation!") 2. Abstract data type (a) Add two prices, respecting the abstraction. (define (+price a b) (let ((pence (+ (cents a) (cents b)))) (if (< pence 100) (make-price (+ (dollars a) (dollars b)) pence) (make-price (+ (dollars a) (dollars b) 1) (- pence 100))))) Scoring: 3 points if correct; 2 points for not noticing if the number of cents is >= 100; 1 point for (+ a b); 0 if even worse. Note that, since a price is represented internally as a number of cents, the procedures listed as 2-point and 1-point solutions would work correctly. But, as we'll see in part (b), they would stop working if the representation is changed. (b) Change to list representation (define make-price list) (define dollars car) (define cents cadr) Scoring: 2 points if correct; 1 point for a change to some other consistent representation that wasn't what we asked for (example: cons, car, cdr); 0 points for an inconsistent representation or anything requiring a change to +price. 3. Telephone calls (a) Connect method for telephone-company class. (method (connect caller num) (let ((callee-entry (assoc num phones))) (if (not callee-entry) 'NOT-IN-SERVICE (let ((callee (cdr callee-entry))) (if (ask callee 'busy?) 'BUSY (sequence (ask callee 'ring) (set! connections (cons (cons caller callee) connections)) 'CONNECTED)))))) We didn't take off, although strictly speaking it's a data abstraction violation, if you used find-other instead of assoc. Find-other is for lists of symmetrical bindings (who's connected to whom) rather than for association lists with key-value bindings (phone number to object). (b) (method (call other-num) (let ((result (ask company 'connect self other-num))) (if (equal? result 'CONNECTED) (set! busy? #t)) result)) Scoring: 5 correct 3-4 mutual ASKing okay (call method asks phone company to connect; connect method asks phone to ring). 2 more confused than that, but still more or less OOPy 0-1 not OOPy. A typical 4-point solution is one that doesn't take the cdr of the binding returned by assoc (or by find-other). A typical 2-point solution is one that asks numbers to do things (as opposed to asking phone objects). A typical 1-point solution *prints* BUSY, or whatever, in the connect method, instead of returning a value to the caller. (We didn't take off if the call method prints something, because the problem didn't precisely specify its result. We wouldn't have taken off if the connect method prints BUSY and also returns it, but I don't think there were any of those.) Similarly, invoking ERROR from the connect method in these cases gets 1 point. 4. Stream of randoms. (a) What's wrong with Ben's program? Ben will get a stream containing the same number repeatedly, e.g., 4, 4, 4, 4, 4, ... forever. The reason is that cons-stream evaluates its first argument; only the second argument is delayed (promised). So when Ben evaluates the expression (cons-stream (random 10) randoms), the subexpression (random 10) is evaluated BEFORE a stream is constructed. The head of the stream will be whatever number random returned. The reason has nothing to do with memoization! Memoization is part of the answer to a different question: In the corrected program (see part b), Ben will always get the same STREAM OF random numbers. For example, if Ben asks Scheme to evaluate (head (tail (tail (tail randoms)))) then he'll always get the same answer, because of memoization. But that answer will be different from the answer to (head (tail randoms)) Scoring: 2 if correct, 1 if memoization cited, 0 for "Ben will get an error message" or other such misunderstandings. (b) Fix it. (define (make-randoms) (cons-stream (random 10) (make-randoms))) (define randoms (make-randoms)) or (define tens (cons-stream 10 tens)) (define randoms (map random tens)) or (define randoms (map (lambda (x) (random 10)) integers) [Notice that that last one ignores x in the body of the lambda!] The key point is that the invocation of cons-stream must be inside a procedure, so that it can be invoked once for each element of the stream. Scoring: 3 if correct; 2 if (make-randoms) defined but never invoked; 1 for a well-motivated but wrong solution such as (define randoms (cons-stream (random 10) (map random randoms))) which will make a stream in which each element is smaller than the previous one until a zero is reached, at which point an error results; 0 for completely unstreamish attempts. Another typical 1-point solution was to rewrite delay/force to be non-memoizing. 5. Logic program. (rule (odd-length (?a))) (rule (odd-length (?x ?y . ?b)) (odd-length ?b)) or (even-length ()) (rule (odd-length (?a . ?b)) (even-length ?b)) (rule (even-length (?a . ?b)) (odd-length ?b)) or (rule (odd-length (?a))) (rule (odd-length (?a . ?b)) (not (odd-length ?b))) [As we were grading the exams, we were surprised that this last solution worked, because it uses a NOT that isn't buried inside an AND. But it's okay because all of the variables used in the NOT (in this case, just ?b) are bound in the conclusion of the rule, so NOT can filter out candidates based on those bindings.] Scoring: 5 correct 4 correct except for base case 3 good idea, bad syntax 2 not-so-good idea (e.g., everything turns out to be of odd length) 1 Lispy (e.g., (rule (odd-length ?a) (odd (length ?a)))) 0 even worse Speaking of syntax, note that (odd-length (?a)) means that some list containing one element is of odd length, whereas (odd-length ?a) means that the variable ?a represents a list whose length is odd. 6. Invent packages. (a) EXPORT is a special form, so it must be a change to EVAL. (Its arguments would already have been evaluated before we would get to APPLY.) (b) Symbols are looked up in the environment by EVAL also. (c) To invent a new special form, we add a clause to the big COND inside EVAL itself, then write new procedures such as EVAL-EXPORT. (d) If you understand the PKG:NAME notation as still being a symbol, then the most logical place to recognize this notation is LOOKUP-VARIABLE-VALUE. But it's also possible to do this within EVAL itself, if you think of the new notation as something separate from symbols. (e) Here's the implementation of EXPORT: Add the clause ((export? exp) (eval-export exp env)) to the cond in EVAL that checks for each special form. Then write (define (export? exp) (and (list? exp) (eq? (car exp) 'export))) (define (eval-export exp env) (map (lambda (sym) (binding-in-env sym env)) (cdr exp))) or (define (eval-export exp env) (make-frame (cdr exp) (list-of-values (cdr exp) env))) [Note: Actually the first of these (using binding-in-env) is better, for an obscure reason one of the TAs pointed out. If the exported frame is a list of the very same binding pairs as the ones in the environment in which EXPORT was used, then the bindings can be mutated. For example, suppose we say (define my-pkg (let () (define x 3) (define (foo n) (+ n x)) (export foo x))) Then we expect FOO to add 3 to its argument: > (my-pkg:foo 5) 8 But what happens if we do this? > (set! my-pkg:x 7) > (my-pkg:foo 5) The version of export that uses binding-in-env will give the answer 12, whereas the version of export that uses list-of-values (or eval, or lookup-variable-value, etc.) will still give the answer 8, because the binding of x within the frame of the empty LET and the binding of x within the exported frame are two separate bindings. But we didn't expect you to think of that!] The implementation of PKG:NAME symbol lookup was a bit more complicated. Many students implemented this in a way that allowed the use of these symbols only as the operator of an application. This means not only that symbols naming non-procedures couldn't be exported (such as the X in the example above), but even a symbol naming a procedure can't be used in all contexts. For example, your solutions allowed (sort-package:sort '(5 3 8 2 47)) but not ((car (list sort-package:sort sort-package:merge)) '(5 3 8 2 47)) The correct solution has nothing to do with procedure application, but rather with variable lookup: (define (lookup-variable-value var env) (LET ((LEFT (BEFORE-COLON VAR)) (RIGHT (AFTER-COLON VAR))) (IF LEFT (LET ((FRAME (LOOKUP-VARIABLE-VALUE LEFT ENV))) (LET ((B (BINDING-IN-FRAME RIGHT FRAME))) (IF (FOUND-BINDING? B) (BINDING-VALUE B) (ERROR "UNEXPORTED VARIABLE" VAR)))) (let ((b (binding-in-env var env))) (if (found-binding? b) (binding-value b) (error "Unbound variable" var)))))) The lines in UPPER CASE are new. Another solution would be to add a clause to the COND in EVAL, *before* the one about variables, like this: ((package-variable? exp) (lookup-package-value exp env)) and then write (define (package-variable? exp) (and (variable? exp) (before-colon exp))) (define (lookup-package-value var env) (let ((frame (lookup-variable-value (before-colon var) env))) (let ((b (binding-in-frame (after-colon var) frame))) (if (found-binding? b) (binding-value b) (error "unexported variable" var))))) Scoring: 5 correct 4 the right idea, some good code, some errors 3 the right idea, lousy code, OR semi-right idea implemented well (such as operator-position-only) 2 some idea or other, mostly implemented 1 a stab at an idea 0 off the wall (such as building in the specific example of SORT-PACKAGE)