CS61a Spring 2004 Final Review Solutions 1. MCE *** ERROR: Unbound variable: if Remember what 'if' is in the MCE. It's a variable, so it will do a variable lookup, but will there be a variable 'if' in the MCE environment? Nope it isn't! 2. ANALYZING EVALUATOR Which of the following interactions will execute faster, slower, or the same in the analyzing evaluator than in the original MCE? i) > (define (gauss-recur n) (if (= n 1) 1 (+ n (gauss-recur (- n 1))))) > (gauss-recur 1000) GAUSS-RECUR is a recursive procedure for computing the sum of all the integers from 1 to n, making n procedure calls in the process. Since it gets called 1000 times in this interaction, its body must be evaluated 1000 times. This is *faster* in the analyzing evaluator, because the work of determining the meaning of the expressions in the body is done only once. In the original metacircular evaluator, much work is involved in determining the kind of expression being evaluated. EVAL has to ask whether the expression is a number or a variable or a list starting with QUOTE or a list starting with SET!, etc. In the case of GAUSS-RECUR, EVAL has to do this not only for the IF, but also for two of the subexpressions and *their* subexpressions, and so on. When the evaluator finally gets to the point where it makes the recursive call, it starts over with the body of GAUSS-RECUR, as if it has never seen it before. The analyzing evaluator still has to do all of this work, but it does it once, when GAUSS-RECUR is defined, instead of every time GAUSS-RECUR is called. It figures out ahead of time that the body contains an IF and that the predicate expression wants to call a procedure named `=', among other things. It packages its discoveries into a fast underlying Scheme procedure that takes an environment and produces the result of the expression in that environment. When a recursive call is made, the same underlying Scheme procedure is reused, and the slow process of dissecting the original code is not repeated. ii) > (define (gauss n) (/ (* (+ n 1) n) 2)) > (gauss 1000) GAUSS, given a positive integer, computes the same result as GAUSS- RECUR through the use of a mathematical trick. Contrary to what some people thought, this program is *not* faster in the analyzing evaluator. As explained above, the analyzing evaluator saves time by avoiding repeated work, specifically the work of analyzing a given expression more than once. But there is no repeated work here; GAUSS is called only once! If we called GAUSS more than once, then we could save some time. So is this interaction slower if we analyze the expressions, or is its running time unchanged? The answer we expected was SAME, which is almost true. It turns out that the analyzing evaluator has a trivial amount of overhead for making those fast underlying Scheme procedures, potentially making it slightly slower. We accepted either SLOWER or SAME for this question. 3. EVALUATORS For each evaluator, will the following expression return a value or cause an error? (let ((a 3) (b a)) (+ a 4)) Error, in the MCE, analyzing, and dynamically scoped evaluators. Value in the lazy evaluator. The problem with this expression is that the variable A is used to assign a value to B, but it is only bound in the body of the LET. This can be seen easily if we de-sugar the LET into: ( (lambda (a b) (+ a 4)) 3 a ) In regular Scheme (the MCE), we evaluate the subexpressions before we call the procedure, and we get an error because A is unbound. Clearly nothing changes if we evaluate the expression in the analyzing evaluator, because the analyzing evaluator is exactly the same as the vanilla MCE above the line, albeit a little faster. An evaluator with dynamic scope doesn't help, since the only difference between dynamic scope and lexical scope is realized when new frames are made. (In lexical scope, the new frame extends the procedure's environment; in dynamic scope, it extends the current environment.) But the error occurs before we even make a new frame, since the first step in the evaluation is to evaluate the subexpressions. The lazy evaluator doesn't have any problems with this expression because the arguments to the procedure, 3 and A, are delayed. The value of B is never needed, so it is never computed. (let ((a 3) (b a)) (+ a b)) This produces an error in all of the evaluators listed. Why does this fail in lazy, whereas the earlier LET worked? Consider the situation when we have just called the procedure corresponding to the LET. A is bound to a thunk that, when forced, evaluates the expression `3' in the global environment. B is bound to a thunk that evaluates the expression `A' in the global environment. We evaluate (+ A B), and both thunks are forced because + is a primitive. But notice that forcing B causes the expression `A' to be evaluated in the *global* environment, where A isn't bound. Note that each thunk carries with it both an expression and an environment in which the expression was supposed to be evaluated. This allows the lazy evaluator to follow the same scoping rules as an applicative order evaluator. 4. MCE Lem E. Tweakit makes the following change to MC-EVAL: ((application? exp) (mc-apply (mc-eval (operator exp) env) (list (eval-sequence (operands exp) env)))) This clause in MC-EVAL is responsible for evaluating the subexpressions in a combination and then calling MC-APPLY. Lem has replaced LIST-OF-VALUES, which takes a list of expressions and produces a list of expression values, with a call to EVAL-SEQUENCE. EVAL-SEQUENCE is ordinarily used only to evaluate the bodies of procedures and BEGINs; it evaluates each expression in sequence, then returns the value of the *last* one. Lem takes that single result and puts it in a list of one element. This approach works fine if the procedure is being called with only one argument, but for procedures of multiple arguments, all but the last argument value will be lost. The problem asked you to decide which expressions produced errors or incorrect results in the modified evaluator. (square 1) The result is correct, but for an accidental reason. Clearly the call to SQUARE works fine, since there is only one argument. But in the call to *, the second argument is ignored. However, this doesn't pose a problem, because the value of (* 1 1) is the same as the value of (* 1). (square 2) This one produces an incorrect result. (* 2 2) does not produce the same value as (* 2). (+ 3 4) This is incorrect, too. The modified evaluator tries to evaluate (+ 4), which gives 4, not 7. (lambda (x y) y) This works fine. LAMBDA is a special form that creates procedures. The APPLICATION? clause in MC-EVAL is only used for ordinary procedures, not special forms, so the arguments to the LAMBDA aren't mangled. ((lambda (x y) y) 6 7) This produces an error. The argument 6 is dropped by Lem's evaluator, which then attempts to call a procedure of two arguments with only one argument: ((lambda (x y) y) 7). ((lambda (x) (+ x 5)) 9) The result of this expression is incorrect in Lem's evaluator. The call to the LAMBDA-created procedure works fine, since there is only one argument, but the first argument to + is dropped. The result is 5, even though we expect it to be 9. 5. AMB EVALUATOR > (* 2 (if (amb #t #f #t) (amb 3 4) 5)) a) What are the values we get before the evaluator responds with ``No more values''? [different forms of the exam have different numbers] We get 6, 8, 10, 6, and 8, in that order. The first time around, (AMB #T #F #T) returns #T. This causes the consequent clause of the IF, namely (AMB 3 4) to be selected. (AMB 3 4) returns 3, so the value of the whole IF expression is 3. We multiply by 2 to get the first answer. Typing TRY-AGAIN at the prompt causes the most recent AMB to fail; (AMB 3 4) now gives us 4 and we try the multiplication again and get 8. If you still don't like that answer and you say TRY-AGAIN once more, the (AMB 3 4) has no more values to offer you, so it fails. This causes the evaluator to realize that the choice the IF predicate made wasn't acceptable. It propogates the failure back to the predicate in hopes that the predicate will have better ideas. Indeed, (AMB #T #F #T) decides to try its second argument, #F. This time, the alternative clause of the IF, namely 5, is chosen; we get the answer 10. If we ask the evaluator to try again once more, the alternative fails. There are no more values for `5' other than 5 itself. The evaluator turns to the predicate one more time for another try, and sure enough, (AMB #T #F #T) tries its third argument. Thus, the next two answers are 6 and 8. After those, (AMB #T #F #T) has exhausted all three of its guesses, so the entire expression fails. b) When ambeval is called to evaluate (AMB 3 4), it is given a success continuation. The success continuation takes as arguments a value and a failure continuation, and the first thing it does is multiply the value by 2. In any Scheme interpreter, the value of the value of an IF expression is the value of the consequent or the value of the alternative. If we evaluate the consequent, (AMB 3 4), then the value of that expression is the value of the whole IF. The evaluator is waiting for the value from the IF so it can use it as the second argument to *. (Said another way, there is a *continuation* waiting for the value of the IF.) Therefore, the the first thing the evaluator does when that value is available is multiply it by 2. Note that you don't have to go into the details of the code for ambeval to understand this problem. There isn't even a need to worry about failure continuations. You only need to think about what is *supposed* to happen next in the evaluation process. 6. CONCURRENCY (define x 5) (define y 8) (define s (make-serializer)) (define t (make-serializer)) a) (parallel-execute (s (lambda () (set! x (+ x 1)))) (t (lambda () (set! x (+ x 2))))) Is deadlock possible? NO! What are the possible results? 6, 7, 8 b) (parallel-execute (s (t (lambda () (set! y (+ x 1))))) (t (s (lambda () (set! x (* y 2)))))) Is deadlock possible? YES What are the possible results? x = 12 16 y = 6 17 7. QUERY EVALUATOR (define (subseq l1 l2) (cond ((null? l1) #t) ((null? l2) #f) ((equal? (car l1) (car l2) (subseq (cdr l1) (cdr l2)))) ((not (equal? (car 11) (car l2))) (subseq l1 (cdr l2))))) (assert! (rule (same ?x ?x))) (assert! (rule (subseq () ?l2 ?l2))) (assert! (rule (subseq (?carl1 . ?cdrl1) (?carl1 . ?cdrl2) (?carl1 . ?cdrl2)) (subseq ?cdrl1 ?cdrl2 ?cdrl2))) (assert! (rule (subseq (?carl1 . ?cdrl1) (?carl2 . ?cdrl2) (?carl2 . ?cdrl2)) (and (subseq (?carl1 . ?cdrl1) ?cdrl2 ?cdrl2) (not (same ?carl1 ?carl2))))) 8. QUERY EVALUATOR (assert! (rule (the fib of () is (a)))) (assert! (rule (the fib of (a) is (a)))) (assert! (rule (the fib of (a a . ?rest) is ?result) (and (the fib of (a . ?rest) is ?temp1) (the fib of ?rest is ?temp2) (append ? 9. AMB EVALUATOR (let ((a (amb 1 2 3)) (b (amb 4 5 6))) (display "hello") (require (= b (* a 2))) a) How many times will hello be printed? What is the return value? Hello will be printed 9 times the return values are: 2 and then 3 10. MUTATION Here is a transcript of a Scheme session. Fill in the blanks > a (1 2 (3 4 5) 6) > b (1 2 3 4 5) >c (1 2 (3 4 5) 6) > (eq? (cddr b) (caddr a)) #T > (eq? (caddr c) (caddr a)) #F > (eq? (cdaddr c) (cdddr b)) #T > (set-car! (caddr a) 7) okay > (set-car! (cdaddr a) 8) okay >b (1 2 7 8 5) _________________________ >c (1 2 (3 8 5) 6) _________________________ 11. ENVIRONMENT DIAGRAM This should go into an infinite loop 12. ENVIRONMENT DIAGRAM Use ENVDRAW to see the environment diagram 13. LAZY EVALUATOR This change makes ACTUAL-VALUE non-recursive. Which means it won't correctly handle "thunks of thunks" or "thunks of thunks of thunks" etc. Things will break down when you have more than one level of thunkification. (bar 3) => 3 BAR sees a thunk of 3 which when ACTUAL-VALUEd returns 3 -- one level of thunkification is cool. ((lambda (x) (* x x)) ((lambda (x) x) 5)) => error: wrong args to * * sees a thunk of ((lambda (x) x) 5) which when ACTUAL-VALUEd returns a thunk of 5 -- two levels of thunkification. (foo 6 7) => error: wrong args to * in BAR This time the * in BAR is given a thunk of A which when ACTUAL-VALUEd returns a thunk of 6 -- two levels. (let ((a +) (b 4)) (+ b b)) => 8 + sees a thunk of 4 which when ACTUAL-VALUEd returns 4. (identity (identity 6)) => a thunk is printed instead of 6 The driver loop sees a thunk of (identity 6) which when ACTUAL-VALUEd returns a thunk of 6 -- two levels. 14. MCE Sure it is! A compound procedure in the metacircular evaluator is represented as a four-element list. ;;; M-Eval input: (define (arg-count proc) (length (cadr proc))) (list 'map eval-map) 1. Query Evaluator Let's start with the Scheme definition: (define (remove x lst) (cond ((null? lst) lst) ((equal? x (car lst)) (remove x (cdr lst))) (else (cons x (remove x (cdr lst)))))) Note that this removes *all* occurrences ox X from LST. There are three conditional branches, so we'll have three separate rules: 1. ((null? lst) lst) (assert! (rule (removing ?x from () yields ()))) 2. ((equal? x (car lst)) (remove x (cdr lst))) This COND clause has a recursive call in it, so we'll rewrite it to add a temporary variable: ((equal? x (car lst)) (let ((result (remove x (cdr lst)))) result)) (assert! (rule (removing ?x from (?x . ?cdr) yields ?result) (removing ?x from ?cdr yields ?result))) 3. (else (cons x (remove x (cdr lst)))) We have another recursive call here, so we'll need a temporary variable: (else (let ((temp (remove x (cdr lst)))) (cons x temp))) Since we're trying to translate the ELSE clause, it is very important that we make our rule consistent with what we know to be true in the ELSE clause. Namely, we know that LST is not null, and -- importantly -- we know that the CAR of LST is *not* equal to X. (assert! (rule (removing ?x from (?a . ?cdr) yields (?a . ?temp)) (and (removing ?x from ?cdr yields ?temp) (not (same ?a ?x))))) It'd be a mistake to leave out the (not (same ?a ?x)) because then everything that matches the conclusion of Rule 2 would also match the conclusion of this rule. Therefore Rule 2 would tell the logic system to remove X while Rule 3 would tell it to keep X. The query system will do both, presenting you with both correct and incorrect results. Here is another, wordier way that will work: (assert! (rule (removing ?x from (?a . ?cdr) yields ?result) (and (removing ?x from ?cdr yields ?temp) (not (same ?x ?a)) (append-to-form (?a) ?temp ?result)))) 17. LEXICAL VS. DYNAMIC SCOPE In Lexical Scoping this will error In Dynamic Scoping this will return 14 You can change the MCE to be dynamically scoped just by adding an arg in mc-apply called env. So that you extend the env not with the procedure's environment but the current one. Also let you can add into mc-eval by adding this clause: ((type-tag? exp 'let) (mc-eval (cons (make-lambda (map car (cadr exp)) ;; the variables (cddr exp)) ;; the body of the let (map cadr (cadr exp))))) ;; the values