CS 61A Fall, 2009 Final exam solutions 1. List mutation vs. variable binding > (define x '(1)) > (define y '(2)) > (define z '(3)) > (set! y z) > (set! x y) > (set! z '(4)) > x SET! doesn't mutate any pairs; it just changes the binding of a variable. So, the first SET! changes Y to (3); the next changes X to (3); and the third changes Z to (4). This last one has no effect on X and Y; they remember their /value/, not whatever expression gave rise to the value. Answer: (3) > (define mylist (list 2 4 6 8)) > (define (magic! ls) (set-car! (cdr ls) 100) (set! ls (cons 1 ls)) (set-car! (cdr ls) 4)) > (magic! mylist) okay > mylist This time we /do/ mutate pairs. When we call MAGIC!, the variable LS is initially bound to the value of MYLIST, namely (2 4 6 8). The first SET-CAR! changes the car of (4 6 8) (which is (CDR LS)) to 100, so LS is now (2 100 6 8) and so is MYLIST, which is bound to the same pair. The SET! gives LS the value (1 2 100 6 8), /without/ changing MYSLIST. (CDR LS) is (2 100 6 8), so SET-CAR!ing that makes LS (1 4 100 6 8). But that first element isn't part of MYLIST. So we get Answer: (4 100 6 8) Scoring: 2 points each, all or nothing. 2. Dynamic vs. lexical scope > (define y 6) > (define z 3) > (define (foo x) (set! y (+ x y z)) y) > (define (bar z) (foo 10)) > (bar (foo 7)) The environment diagram is almost the same regardless of scope rule, so let's start by drawing it: The bindings Y=6 and Z=3 are added to the global frame G. The third DEFINE has an implicit lambda, which makes the procedure P1: params (x), body (set! ...) y, env G and adds the binding FOO=P1 to G. The fourth DEFINE similarly makes P2: params (z), body (foo 10), env G and adds the binding BAR=P2 to G. So far, everything has happened in the global environment, because we haven't called any procedures. Now we have to start being careful about scope. To evaluate (bar (foo y)) we first evaluate the subexpressions (with current environment G). The value of BAR is P2. (FOO 7) is a procedure call, which we evaluate in the same way: FOO (in G) is P1; 7 is self-evaluating. Now we call P1 with argument 7. To do that, we make a frame in which the formal parameter [X] is bound to the actual argument value [7]. Which frame does it extend? In lexical scope, it extends the environment in which it was created, namely G. In dynamic scope, it extends the current environment, which is also G. So, for this procedure call it doesn't matter which rule we're following. E1: X=7, extends G Now, with E1 as current environment, we evaluate the body of P1, which has two expressions. The first is (SET! Y (+ X Y Z)). We start by evaluating the procedure call (+ X Y Z). We find these bindings: + = addition primitive, in G X = 7, in E1 Y = 6, in G Z = 3, in G So the result of the addition primitive is 7+6+3 = 16. Now we do the SET!, which modifies the binding of Y, in G, to 16. G: Y=16, Z=3, FOO=P1, BAR=P2 The second expression in the body of P1 is Y. We find the global binding Y=16, so (FOO 7) returns the value 16. Now we can call (BAR 16). The current environment is again G. BAR is P2. We make a frame with the binding Z=16. As before, this frame has to extend G regardless of scope rule: E2: Z=16, extends G With E2 as current environment, we evaluate the body of P2, which is (FOO 10). So we make a frame with the binding X=10. What environment should it extend? The current environment is E2, but procedure P2 was created in G. So this is where we have a choice: E3-lex: X=10, extends G E3-dyn: X=10, extends E2 This choice will affect the result, because the two environments have conflicting bindings for Z, which is not bound in E3 itself. With E3 as current environment, we evaluate the body of P1. First we have to evaluate (+ X Y Z), so we look for bindings for the subexpressions: + = addition primitive, in G X = 10, in E3 Y = 16, in G lexical: Z = 3, in G dynamic: Z = 16, in E2 So the value of (+ X Y Z) is 10+16+3 = 29 in lexical scope, or 10+16+16 = 42 in dynamic scope. We change the (global) binding of Y to either 29 or 42, and return that new value. So we have: Answer: Lexical = 29, Dynamic = 42. For the diagram, draw it as above, using E3-dyn. Scoring: 1 point each for the two answers; 1 point total if you get them backwards. No points for arithmetic errors etc. 2 points for the diagram. 1 point for lexical provided that you got the two answers backwards, otherwise 0. 0 points for binding parameters to argument expressions instead of to argument values. OK if your procedures have no right bubble (because it's unnecessary in dynamic scope). 3. Order of growth. (a) In the worst case, you try all the other keys before you find the correct key, for a total of N trials, so this is Theta(N). (b) After you open the outer box (worst case N trials), you know that /another/ key opens the inner box, so in the worst case you make N-1 trials, for a total worst case of 2N-1, which is still Theta(N). (c) For the safe deposit box, you can't first find the left-lock key and then find the right-lock key, because you won't know you have the correct left-lock key until you are simultaneously trying the correct right-lock key. So you have to try every pairing of keys, which means N possibilities for the left key /times/ (not plus) N-1 possibilities for the right key. So in the worst case you make N(N-1) = N^2 - N trials, which is Theta(N^2). [Some of the TAs thought that it would be N(N-1)/2, which is the number of combinations of N things taken 2 at a time. But we need permutations, not combinations, because it matters which is the left key and which is the right key. If you don't know about permutations and combinations, ignore this paragraph, because N(N-1)/2 would still be Theta(N^2).] Scoring: 2 points each, all or nothing. It's ok if you gave an exact formula such as 2N-1 for part (b), as long as your formula has the correct order of growth. We graded this one leniently, as if the entire formula had a Theta() around it. 4. Applicative vs. normal order. "Applicative order guarantees that arguments to a procedure are evaluated before the procedure body." This is TRUE -- it's the definition of applicative order. (The alternative is normal order, in which unevaluated actual argument expressions are given to the procedure.) "Normal order guarantees that arguments to a procedure are evaluated from left to right." This is FALSE. Normal order delays argument evaluation until the values are needed by a primitive called inside the procedure body, but it could turn out, for example, that the leftmost argument is /never/ evaluated, as in the procedure (lambda (x y) (* y y)). Scoring: 2 points each, all or nothing. 5. Miscellaneous short answer. A list is a /PAIR/ whose /CDR/ is /A LIST/, or the empty list. This is the official definition of "list." We also gave some credit to solutions of the form "a list is a sequence of pairs whose final CDR is null", though not as correct (a vector whose elements are pairs would also match this definition). A list is more efficient than a vector when... a) Removing items from the front of the sequence. YES. Changing the size of a vector requires copying the entire vector (other than the element you're removing). But removing the first element of a list is just CDR, which is constant time. b) Replacing values at the front of the sequence. NO. Both SET-CAR! and VECTOR-SET! are constant time operations. (Replacing a value somewhere other than the front of the sequence takes longer for a list, because you have to call CDR repeatedly to find the element you want to change.) c) Printing out every element. NO. This is Theta(N) time both for vectors and for lists. Since you want to print every element, there's no way to jump directly into the middle, which would give vectors the advantage. d) Never; vectors are always more efficient. NO -- Operations that change the length of the sequence are more efficient for lists because there is no recopying. A client-server connection's three-way handshake ensures... a) The network is reliable. NO. It does ensure that (some part of) the network is working right now, but there's no guarantee that it will keep working until we're finished with this application. b) Both sides can send and receive messages. YES. It has to be a three-way handshake because after the first two messages have been sent and received, the originating host (typically the client) knows that it can both send and receive to/from the other host (typically the server), but the second host knows only that it can receive from the first; it doesn't know that the first host got its answer until it receives the third message. c) The connection will be terminated when the client quits. NO. This one is completely irrelevant! d) None of the above. NO, because (b) was correct. The argument to a continuation is... a) The previous expression evaluated by the interpreter. b) The expression to evaluate next. NO. A continuation is a procedure, and arguments to procedures are always values, not expressions! /The continuation itself/ represents the expression to evaluate next, but it isn't the same thing as the expression. c) The value computed by a procedure call. YES. The continuation uses this value to continue (that's why it's called a "continuation") the computation. Note, this says "computed by" rather than "returned by" because in continuation passing style, no procedure ever actually returns; it just tail-calls the next continuation. d) An environment. NO. Environments are not first class in Scheme. Scoring: 2 points each, all or nothing. 6. Concurrency. > (define s (make-serializer)) > ((s (lambda () (parallel-execute (lambda () (set! z (- x y))) (lambda () (set! y (+ y x))) (lambda () (set! x 10)) )))) NO. This serializes the PARALLEL-EXECUTE itself, but does not protect the threads within the PARALLEL-EXECUTE from each other. > (define s (make-serializer)) > (parallel-execute (lambda () (set! z (- x y))) (s (lambda () (set! y (+ y x)))) (s (lambda () (set! x 10))) ) NO. This one is really hard to think about without listing all the cases. It seems as if it could be safe, since the unprotected thread is the only one that modifies Z, and because it looks at X and Y once each, it can't have the sort of error in which (* X X) gets two different values of X when another thread modifies X in the middle. First of all, what are the possible correct results? "Correct" means "could happen given some sequential ordering of the threads." With three threads (let's call them A, B, and C), there are six possible orderings. Suppose the initial values are X=100, Y=200, Z=400. ABC: Z = 100-200 = -100. Y = 200+100 = 300. X = 10. ACB: Z = 100-200 = -100. X = 10. Y = 200+10 = 210. BAC: Y = 100+200 = 300. Z = 100-300 = -200. X = 10. BCA: Y = 100+200 = 300. X = 10. Z = 10-300 = -290. CAB: X = 10. Z = 10-200 = -190. Y = 200+10 = 210. CBA: X = 10. Y = 200+10 = 210. Z = 10-210 = -200. Now, what can go wrong because A isn't serialized? It has to be that something else interrupts A. Let's look at this sequence of events: A loads X=100 into a register. C sets X to 10. (It runs to completion.) B sets Y to 200+10=210. (It also runs to completion.) A continues, loading Y=210 into a register, then setting Z to 100-210=-110. (Note, even though X=10 at this point, thread A had already loaded X=100 into its local register.) The problem is subtle. X=100 is a possible legal value. Y=210 is a possible legal value. It's just not legally possible for /both/ of those to be true /at the same time/, and that's why Z gets an impossible value. > (define ser-x (make-serializer)) > (define ser-y (make-serializer)) > (parallel-execute (ser-x (ser-y (lambda () (set! z (- x y))))) (ser-y (ser-x (lambda () (set! y (+ y x))))) (ser-x (lambda () (set! x 10))) ) NO. The first two threads can deadlock, because they acquire the two serializers in the opposite order from each other. > (define s (make-serializer)) > (parallel-execute (s (lambda () (set! z (- x y)))) (s (lambda () (set! y (+ y x)))) (s (lambda () (set! x 10))) ) YES. This is inefficient; since all threads are protected with the same serializer, it doesn't allow any parallelism at all. But it's safe. Scoring: One point each, all or nothing. 7. MapReduce. This is a little like the wordcount example, in that we turn the lines of the input stream into key-value pairs in which the key is a word from the text of a file. In the case of wordcount, we just want to add up how many times the word is used, so all the values in the key-value pairs we generate are 1. But this time we want to remember which file this word appears in, so the value will be the filename. The other complexity is that we only care about certain words, and if the word isn't one of those, we don't generate a key-value pair for it. (define (search keywords) (define (search-mapper line-pair) (map (lambda (wd) (make-kv-pair wd (kv-key line-pair))) (filter (lambda (wd) (member wd keywords)) (kv-value line-pair) ))) (mapreduce search-mapper cons '() input-stream)) The nice thing about MapReduce is that it will handle the "sorted by keyword" aspect for us. The problem deliberately didn't specify the exact format of the output, so a solution using CONS-STREAM as the reducer would also be accepted. By the way, although the problem says not to worry about the same word appearing more than once in the same file, if we wanted to eliminate duplicates, the reducer is where we'd do it. Scoring: 2 points for making (word . filename) kv-pairs 2 points for filtering out non-keywords 1 point for returning a /list/ of kv-pairs in mapper 1 point for reducing correctly We accepted solutions that used a STREAM-FILTER to do the filtering, though this isn't the best use of MapReduce. Solutions that used multiple calls to MapReduce, one for each keyword, got a maximum of 5 points, since the output wasn't sorted by keyword as specified in the problem. Some solutions had two-expression IFs to do their filtering, but (if #f '()) has a result of OKAY!. These solutions got a maximum of 5 points if there was a simple value that could be put in for the third expression (such as the empty list) that would make it work, and 4 points if more post-processing would be needed. 8. Data Directed Programming (a) You're told that each procedure takes the old position as argument and returns the new position. So this is all you have to do: (put 'robot 'forward (lambda (pos) (+ pos 1))) (put 'robot 'back (lambda (pos) (- pos 1))) (put 'robot 'home (lambda (pos) 0)) Since the PUT that's provided for you is two-dimensional, I used the word ROBOT as a sort of type tag. But we didn't take off for using a one-dimensional table with just the operation name as key, or for using a LOOKUP/INSERT! table. It's also okay to define the procedures before putting them in the table: (define (forward pos) (+ pos 1)) (put 'robot 'forward forward) But in this case it's important that the key is the quoted operation name and the value stored in the table is the (not quoted) procedure! (b) We have to use GET to translate an operation name into a method: (define (final-position init cmds) (if (null? cmds) init (final-position ((get 'robot (car cmds)) init) (cdr cmds)))) Scoring: 3 points for each part: 3 correct 2 non-conceptual error (e.g. HOME is the wrong function) 1 sets a global position variable (could be either or both parts) 1 (a) puts a non-function in the table 1 (b) list of procedures instead of command names 0 doesn't use GET/PUT 9. Streams As usual for interleave problems, it's helpful to draw a zigzag diagram: 5 ___ ___ ___ ___ ___ ___ ___ ___ ___ In the dashes on the first line we're going to put elements of my-stream as we learn them, and in the dashes on the second row we'll put 2 times the elements of my-stream. We already know one element: 5 _5_ ___ ___ ___ ___ _10 ___ ___ ___ Now we know the second and third elements: 5 _5_ _5_ _10 ___ ___ _10 _10 _20 ___ And now we know the first seven elements, which is much more than we need: 5 _5_ _5_ _10 _5_ _10 _10 _10 _20 _10 So the first eight elements are 5 5 10 5 10 10 20 5. Scoring: The first three elements are worth 1 point total (all must be right), the next three are worth 1 point total, and the last two are worth 1 point each. Solutions that got the output of INTERLEAVE backwards only lost 1 point total. The same penalty was assigned to people who displayed the stream starting from the second element, or who squared instead of multiplying by 2. 10. Query sustem (a) prefix The examples gave you a big hint about the base case, which is that the empty list is a prefix of any list: (assert! (rule (prefix () ?any))) If the first list isn't empty, then its first element must be the first element of the second list too. And then the same relation must hold for the cdrs of the two lists: (assert! (rule (prefix (?first . ?small) (?first . ?big)) (prefix ?small ?big))) The use of ?FIRST twice in the rule's conclusion is what requires the first elements to agree, and the body of the rule is the recursive query about the two CDRs. Many people weren't comfortable with reusing variables and tried this, which also works: (assert! (rule (prefix (?car-a . ?cdr-a) (?car-b . ?cdr-b)) (and (same ?car-a ?car-b) (prefix ?cdr-a ?cdr-b)))) The trouble came when some people noticed that (prefix ?x ?x) was a valid rule and tried to use PREFIX as SAME. The problem with that is that it doesn't work properly for deep lists: (()) is a prefix of ((1)) that way. We took off a point for this. There is also a solution that uses APPEND-TO-FORM, the relation for appending from the book: (assert! (rule (prefix ?pre ?full) (append-to-form ?pre ?something ?full))) (b) sublist The big hint is that you use PREFIX to help you define SUBLIST! In fact, that gives you the base case for this relation: (assert! (rule (sublist ?a ?b) (prefix ?a ?b))) If the first list isn't a prefix of the second list, then it has to be a sublist of the cdr of the second list: (assert! (rule (sublist ?sub (?first . ?rest)) (sublist ?sub ?rest))) The two rules can be combined into one using OR, but you have to be careful. If you just say (assert! (rule (sublist ?sub (?first . ?rest)) ; almost right (or (prefix ?sub (?first . ?rest)) (sublist ?sub ?rest)))) this rule works only if the second list is non-empty, since its conclusion requires that list to have a car and a cdr. So you need to add one special case: (assert! (sublist () ())) So you still have two assertions, and this version is, I think, harder to read. So I'd be inclined not to use OR in this problem. We weren't strict about this, though, since this time it only eliminates that single case. (If you got this wrong in PREFIX, it meant that one list wasn't a prefix of itself. But for SUBLIST, this case ends up being handled by PREFIX.) Many people slipped up by using PREFIX for the "recursive" call instead of SUBLIST; this fails to check the rest of the list. Others tried to make sure the first elements /didn't/ match; this resulted in (1 2 3) not being a sublist of (1 1 2 3). The last common mistake was trying to merge the PREFIX rules in as SUBLIST rules. This would work for sub-/sequences/, but fell down for SUBLIST: (1 3 5) would then be a sublist of (1 2 3 4 5). As with PREFIX, there is also a direct solution using APPEND-TO-FORM: (assert! (rule (sublist ?sub ?full) (and (append-to-form ?something ?sub ?prefix) (append-to-form ?prefix ?something-else ?full)))) Scoring: 4 points each half 4 correct 3 correct except for empty lists 2 misses significant cases but gets something right 1 severe logic errors 0 not logic programs (composition of functions, or just incoherent) Answers with spurious parentheses around the arguments to a relation got a maximum of 3 points. 11. Tree programming If DEPTH is zero, then there is just one tree in the answer. But the answer still has to be a /forest/ with that one tree in it. If DEPTH is greater than zero, then we have to combine the results of applying LEVEL to all this tree's children, with DEPTH reduced by 1. What does "combine" mean? Each result is a /forest/, i.e., a list of trees. We want the overall result to be a forest, too, not a list of forests. So we have to APPEND the results we get. (define (level depth Tree) (if (= depth 0) (list Tree) ; a forest with one Tree in it. (apply append ; or use REDUCE instead of APPLY (map (lambda (child) (level (- depth 1) child)) (children Tree))))) That's it! Of course you can write a FOREST-LEVEL instead of calling MAP, but it's not necessary. Scoring: 8 correct. 7 trivial error, or base case wrong. 6 tries to flatten but does it wrong. 4 returns list of forests. 4 returns list of data. 4 works on binary trees. 3 serious domain errors, e.g., (level (- depth 1) (children tree)). 3 works on deep lists (correctly). 1 some kind of functional tree recursion. 0 even worse. 12. Metacircular evaluator. This is a special form, so it's the job of EVAL, not APPLY. We'll add a COND clause to MC-EVAL, like this: (define (mc-eval exp env) (cond ... ((while? exp) (eval-while exp env)) ...)) (define (while? exp) (tagged-list? 'while exp)) (define while-test cadr) ; selectors for while expression (define while-actions cddr) Now we have to do what WHILE is supposed to do: Evaluate the test expression. If it's false, we're done. Otherwise, evaluate the actions, and then do the same thing again. (define (eval-while exp env) (if (true? (mc-eval (while-test exp) env)) (begin (eval-sequence (while-actions exp) env) (eval-while exp env)) 'okay)) That's all! Luckily we had EVAL-SEQUENCE available to evaluate all the actions in one step. Scoring: 2 points for detecting and parsing WHILE expressions 3 points for the logic of testing and acting 3 points for recursive evaluation of subexpressions