CS61a Spring 2004 
Final Review 


1. MCE
    
  Fill in the blank in the following interaction with the
  metacircular evaluator: 

  ;;; M-Eval input:
  if

   
  _____________________________________



2. ANALYZING EVALUATOR
Which of the following interactions will execute faster, slower, or the 
same in the analyzing evaluator than in the original metacircular evaluator? 
Circle FASTER, SLOWER or SAME for each.

> (define (gauss-recur n) ;; sum of #s from 1 to n
    (if (= n 1)
         1
        (+ n (gauss-recur (- n 1)))))

(Analyzing will be) 

FASTER SLOWER SAME > (gauss-recur 1000)

> (define (gauss n) ;; sum of #s from 1 to n
    (/ (* (+ n 1) n) 2)

(Analyzing will be) 

FASTER SLOWER SAME > (gauss 1000)



3. EVALUATORS
For each evaluator, will the following expression return a value or cause 
an error? Circle VALUE or ERROR for each.
> (let ((a 3)
        (b a))
    (+ a 4))

VALUE ERROR The MCE

VALUE ERROR Analyzing evaluator

VALUE ERROR Lazy evaluator

VALUE ERROR The MCE with dynamic scope







For each evaluator, will the following expression return a value or cause 
an error? Circle VALUE or ERROR for each.
> (let ((a 3)
        (b a))
    (+ a b)) ;; this line different from the one above

VALUE ERROR The MCE

VALUE ERROR Analyzing evaluator

VALUE ERROR Lazy evaluator

VALUE ERROR The MCE with dynamic scope



4. MCE
Lem E. Tweakit makes the following change to mc-eval in the meta-circular 
evaluator:

((application? exp)
 (mc-apply (mc-eval (operator exp) env)
           (list (eval-sequence (operands exp) env)))) ;; <-- changed
;; was: (list-of-values (operands exp) env)))

He finds that the modified evaluator doesn't work correctly. Indicate 
which of the following expressions now cause an error, return incorrect 
results, or return the correct (usual) values. 
Circle ERROR, INCORRECT, or CORRECT for each. 
Assume square is defines as always: (define (square x) (* x x)).

ERROR INCORRECT CORRECT (square 1)

ERROR INCORRECT CORRECT (square 2)

ERROR INCORRECT CORRECT (+ 3 4)

ERROR INCORRECT CORRECT (lambda (x y) y)

ERROR INCORRECT CORRECT ((lambda (x y) y) 6 7)

ERROR INCORRECT CORRECT ((lambda (x) (+ x 5)) 9)



5. AMB EVALUATOR
This question concerns continuations in the non-deterministic evaluator. 
Consider the following expression, which is typed at the ambeval prompt:
> (* 2 (if (amb #t #f #t)
           (amb 3 4)
            5))
(a) What are all the values we get before the evaluator responds with 
"No More Values" ?






(b) When ambeval is called to evaluate (amb 3 4), it is given a success 
continuation. What does this success continuation do first? (Check one)

___ Print the words ";;; Amb-Eval value:"

___ Print the value

___ Multiply the value by 2

___ Check if the value is true

___ Return 3

___ Return 4

___ Return 5

___ Call a failure continuation

___ Evaluate (amb #t #f #t)

___ Evaluate (amb #t #f)

___ Evaluate (amb #t)

___ Evaluate (amb)



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?
    What are the possible results?

b)  (parallel-execute (s (t (lambda () (set! y (+ x 1)))))
                      (t (s (lambda () (set! x (* y 2))))))
    Is deadlock possible?
    What are the possible results?




7. QUERY EVALUATOR
    Write subseq in the query evaluator.  Subseq takes two arguments.
    The first is a list contatining several elements and the second
    is also a list.  The query evaluator should return a solution
    if the elements in the first list are present in the second list
    in the same order.  For example:

>  (subseq (a b c) (a z b y c))  ;; returns a solution
   (subseq (a b c) (a z b y c)) 



8. QUERY EVALUATOR
    Write logic rules for the following relation:

    ;; Query input:
    (the fib of (a a a a) is ?what)
    
    ;; Query results:
    (the fib of (a a a a) is (a a a a a a a a))   ;; 1 1 2 3 5 8 
    
    ;; Query input:
    (the fib of () is ?what)
    
    ;; Query results:
    (the fib of () is (a)) 

    ****it would be beneficial to write the rule for adding two numbers
     ((a) + (a) = (a a)) ****

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?




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

_________________________
>c

_________________________




11. ENVIRONMENT DIAGRAM
   Draw this baby, but stop drawing when you have a feel for how
   things will work out in the end. 

   (define x 4)

   (define (define-x x) (define x x) x)

   (define (confusing x y)
     (let ((z (x y)))
       (set! confusing z))
       (set! x 10)
       (confusing))
       
   (confusing define-x (let ((total 0))
                          (lambda () 
			    (set! total (+ total x))
			    (confusing))))


12. ENVIRONMENT DIAGRAM
What is the environment diagram of the sequence of these expressions.  
And what is the return value.
(define (bo-peep)
     (let ((sheep 1000))
         (define (herd msg)
	 (cond ((eq? msg 'one) (set! sheep (/ sheep 2)) sheep)
	           ((eq? msg 'two)
		(let ((m (herd 'one)))
		    (set! sheep (* m 4))
		    sheep))))
         herd))

(define flock (bo-peep))

(flock 'two)



13. LAZY EVALUATOR
In the lazy evaluator you are given:
(define (actual-value exp env)
  (force-it (mc-eval exp env)))

(define (force-it obj)
  (if (thunk? obj)
    (actual-value (thunk-exp obj)
                  (thunk-env obj))
    obj)) 

Consider this modication in all capitals:
(define (force-it obj)
  (if (thunk? obj)
    (MC-EVAL (thunk-exp obj)
             (thunk-env obj))
    obj))




Assume the following functions are typed at the lazy prompt:

    (define (identity x) x)

    (define (foo a b)
      (+ (bar a) b))

    (define (bar a) (* a a))  

Fill in the blanks with the value returned by the lazy evaluator for 
each of the following expressions (if something abnormal happens, 
please describe): 

    (bar 3)


    ((lambda (x) (* x x)) ((lambda (x) x) 5))


    (foo 6 7)
    

    (let ((a +) (b 4))
       (+ b b))


    (identity (identity 6))




14. MCE    
    Is it possible to define at the metacircular evaluator prompt a
    procedure ARG-COUNT that takes a compound-procedure and returns
    the number of arguments that procedure takes? If it's possible
    define it. Otherwise explain why it is not possible. It should
    work like this:
  
    ;;; M-Eval input:
    (define (square x) (* x x))

    ;;; M-Eval value:
    ok

    ;;; M-Eval input:
    (arg-count square)

    ;;; M-Eval value:
    1

    ;;; M-Eval input:
    (arg-count (lambda (x y z w) 'booyah))

    ;;; M-Eval value:
    4
   
    Remember, we want to define ARG-COUNT in the metacircular evaluator, 
    not add it as a primitive or a special form.







15. Query Evaluator
Write remove such that it has the following behavior:

(remove a (a b r a c a d a b r a) ?what)
--> (remove a (a b r a c a d a b r a) (b r c d b r))



16. LEXICAL VS. DYNAMIC SCOPE
Draw the environment diagram for these sequence of expressions both for 
lexical and dynamic scope.  What are the values returned for both?

     (define (square) (* a a))
     (define a 3)
     (define b 4)

     ((let ((a 1)
            (b 2))
         (let ((c b) 
               (d a))
	   (lambda () (+ (square) b c d)))))