Solutions to Hand Evaluation Problems from Assignment 9 and the Second Exam

Assignment 9

1. 
  (define (make-cons f r)
    (local [(define first f) (define rest r)]
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first)]
	      [(symbol=? msg 'rest)
	       (lambda () rest)]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest v))]))))
  (define (first c) ((c 'first)))
  (define (rest c) ((c 'rest)))
  (define (set-cons-first! c v) ((c 'set-first!) v))
  (define (set-cons-rest! c v) ((c 'set-rest!) v))
  (define zeroes (make-cons 0 empty))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define zeroes
    (local [(define first 0) (define rest empty)]
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first)]
	      [(symbol=? msg 'rest)
	       (lambda () rest)]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest v))]))))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first')]
	      [(symbol=? msg 'rest)
	       (lambda () rest')]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first' v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest' v))])))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  (set-cons-rest! 
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first')]
	      [(symbol=? msg 'rest)
	       (lambda () rest')]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first' v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest' v))]))
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first')]
	      [(symbol=? msg 'rest)
	       (lambda () rest')]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first' v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  (((lambda (msg)
      (cond [(symbol=? msg 'first)
	     (lambda () first')]
	    [(symbol=? msg 'rest)
	     (lambda () rest')]
	    [(symbol=? msg 'set-first!)
	     (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))]))
     'set-rest)
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  ((cond [(symbol=? 'set-rest 'first)
	  (lambda () first')]
	 [(symbol=? 'set-rest 'rest)
	  (lambda () rest')]
         [(symbol=? 'set-rest 'set-first!)
	  (lambda (v) (set! first' v))]
	 [(symbol=? 'set-rest 'set-rest!)
	  (lambda (v) (set! rest' v))])
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  ((lambda (v) (set! rest' v))
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  (set! rest'
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest'    
    (lambda (msg)
      (cond [(symbol=? msg 'first)
	     (lambda () first')]
	    [(symbol=? msg 'rest)
	     (lambda () rest')]
	    [(symbol=? msg 'set-first!)
	     (lambda (v) (set! first' v))]
	     [(symbol=? msg 'set-rest!)
	      (lambda (v) (set! rest' v))])))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first (rest (lambda (msg)
	  	 (cond [(symbol=? msg 'first)
		        (lambda () first')]
		       [(symbol=? msg 'rest)
		        (lambda () rest')]
                       [(symbol=? msg 'set-first!)
                        (lambda (v) (set! first' v))]
                       [(symbol=? msg 'set-rest!)
                        (lambda (v) (set! rest' v))]))))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first ((lambda (msg)
	    (cond [(symbol=? msg 'first)
		   (lambda () first')]
		  [(symbol=? msg 'rest)
		   (lambda () rest')]
                  [(symbol=? msg 'set-first!)
                   (lambda (v) (set! first' v))]
                  [(symbol=? msg 'set-rest!)
                   (lambda (v) (set! rest' v))])) 'rest))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first (cond [(symbol=? 'rest 'first)
                (lambda () first')]
	       [(symbol=? 'rest 'rest)
		(lambda () rest')]
               [(symbol=? 'rest 'set-first!)
                (lambda (v) (set! first' v))]
               [(symbol=? 'rest 'set-rest!)
                (lambda (v) (set! rest' v))])) 'rest))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first ((lambda () rest')))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first rest')

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  (first (lambda (msg)
           (cond [(symbol=? msg 'first)
	          (lambda () first')]
                 [(symbol=? msg 'rest)
	          (lambda () rest')]
	         [(symbol=? msg 'set-first!)
	          (lambda (v) (set! first' v))]
	         [(symbol=? msg 'set-rest!)
	          (lambda (v) (set! rest' v))])))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  ((lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
           [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	   [(symbol=? msg 'set-rest!)
	    (lambda (v) (set! rest' v))]))
   'first)

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  ((cond [(symbol=? 'first 'first)
	    (lambda () first')]
           [(symbol=? 'first 'rest)
	    (lambda () rest')]
	   [(symbol=? 'first 'set-first!)
	    (lambda (v) (set! first' v))]
	   [(symbol=? 'first 'set-rest!)
	    (lambda (v) (set! rest' v))]))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  ((lambda () first'))


=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  first'

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' 
    (lambda (msg) ...))
  (define zeroes
      (lambda (msg) ...))
  (void)
  0

Commentary: according to our evaluation rules, an application (M N)
reduces to (V N) where V is the value of the expression M.  If M is a
name of a function defined earlier in the program, this step is awkward
to trace by hand, because it replaces M by the lambda-expression
forming the body of the specified function.  In the absence of a set!
operation that changes the binding of the name M, we can simply ignore
this substitution, simplify N to a value V' and then reduce (M V')
to the body of function definition for M with V' replacing the formal
parameter of the function definition.

If we exactly follow our evaluation rules for this computation,
we perform the following evaluation:

  (define (make-cons f r)
    (local [(define first f) (define rest r)]
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first)]
	      [(symbol=? msg 'rest)
	       (lambda () rest)]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest v))]))))
  (define (first c) ((c 'first)))
  (define (rest c) ((c 'rest)))
  (define (set-cons-first! c v) ((c 'set-first!) v))
  (define (set-cons-rest! c v) ((c 'set-rest!) v))
  (define zeroes (make-cons 0 empty))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define zeroes
    (local [(define first 0) (define rest empty)]
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first)]
	      [(symbol=? msg 'rest)
	       (lambda () rest)]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest v))]))))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first')]
	      [(symbol=? msg 'rest)
	       (lambda () rest')]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first' v))]
	      [(symbol=? msg 'set-rest!)
	       (lambda (v) (set! rest' v))])))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  ((lambda (c v) ((c 'set-rest!) v))    
   (lambda (msg)                         
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	   [(symbol=? msg 'set-rest!)
	    (lambda (v) (set! rest' v))]))
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	   [(symbol=? msg 'set-rest!)
	    (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

[*** This step replaced set-cons-rest! by its value in addition to replacing
     zeroes by its value in two places. Technically, it is the combination of
     three reduction steps: 
     - reduce the "head" set-cons-first to its value
     - reduce the first argument zeroes to its value
     - reduce the third argument zeroes to its value
***]

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  (((lambda (msg)
      (cond [(symbol=? msg 'first)
	     (lambda () first')]
	    [(symbol=? msg 'rest)
	     (lambda () rest')]
	    [(symbol=? msg 'set-first!)
	     (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))]))
     'set-rest)
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

[*** This step brings up back to the same point that we reached in the
     preceding "abbreviated" evaluation.
***]

=>(define (make-cons f r) ...)
  (define (first c) ...)
  (define (rest c) ...)
  (define (set-cons-first! c v) ...)  
  (define (set-cons-rest! c v) ...)  
  (define first' 0)
  (define rest' empty)
  (define zeroes
      (lambda (msg) ...))
  ((cond [(symbol=? 'set-rest 'first)
	  (lambda () first')]
	 [(symbol=? 'set-rest 'rest)
	  (lambda () rest')]
         [(symbol=? 'set-rest 'set-first!)
	  (lambda (v) (set! first' v))]
	 [(symbol=? 'set-rest 'set-rest!)
	  (lambda (v) (set! rest' v))])
   (lambda (msg)
     (cond [(symbol=? msg 'first)
	    (lambda () first')]
	   [(symbol=? msg 'rest)
	    (lambda () rest')]
	   [(symbol=? msg 'set-first!)
	    (lambda (v) (set! first' v))]
	    [(symbol=? msg 'set-rest!)
	     (lambda (v) (set! rest' v))])))
  (first (rest zeroes))

...

[*** And so on.  ***]

On the exam, you may defer evaluating the head of an application (M
N) when it is a variable bound to a function (lambda-expression) in the
block of top-level "define"s preceding the application.  None of the
hand-evaluation examples on the test will use set! to modify the
values of variables bound to functions.


2. 
  (define-struct Cons (first rest))
  (define zeroes (make-Cons 0 empty))
  (set-Cons-rest! zeroes zeroes)
  (Cons-first (Cons-rest zeroes))

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 empty))
  (define zeroes loc$0)
  (set-Cons-rest! zeroes zeroes)
  (Cons-first (Cons-rest zeroes))

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 empty))
  (define zeroes loc$0)
  (set-Cons-rest! loc$0 loc$0)
  (Cons-first (Cons-rest zeroes))

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 loc$0))
  (define zeroes loc$0)
  (void)
  (Cons-first (Cons-rest zeroes))

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 loc$0))
  (define zeroes loc$0)
  (void)
  (Cons-first (Cons-rest loc$0))

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 loc$0))
  (define zeroes loc$0)
  (void)
  (Cons-first loc$0)

=>(define-struct Cons (first rest))
  (define loc$0 (make-Cons 0 loc$0))
  (define zeroes loc$0)
  (void)
  0

3.
  (define-struct Box (contents))
  (define (swap box1 box2)
    (local [(define temp (Box-contents box1))]
      (begin
	(set-Box-contents! box1 (Box-contents box2))
	(set-Box-contents! box2 temp))))
  (define a (make-Box 'A))
  (define b (make-Box 'B))
  (define c a)
  (begin (swap b c) (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define b (make-Box 'B))
  (define c a)
  (begin (swap b c) (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c a)
  (begin (swap b c) (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c loc$0)
  (begin (swap b c) (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c loc$0)
  (begin (swap loc$1 loc$0) (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c loc$0)
  (begin 
    (local [(define temp (Box-contents loc$1))]
      (begin
	(set-Box-contents! loc$1 (Box-contents loc$0))
	(set-Box-contents! loc$0 temp)))
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
      (begin
	(set-Box-contents! loc$1 (Box-contents loc$0))
	(set-Box-contents! loc$0 temp'))
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'B))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
    (begin
      (set-Box-contents! loc$1 'A)
      (set-Box-contents! loc$0 temp'))
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'A))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
    (begin
      (set-Box-contents! loc$0 temp'))
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'A))
  (define a loc$0)
  (define loc$1 (make-Box 'A))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
    (begin
      (set-Box-contents! loc$0 'B))
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'B))
  (define a loc$0)
  (define loc$1 (make-Box 'A))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
    (Box-contents a))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'B))
  (define a loc$0)
  (define loc$1 (make-Box 'A))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  (begin
    (Box-contents loc$0))

=>(define-struct Box (contents))
  (define (swap box1 box2) ...)
  (define loc$0 (make-Box 'B))
  (define a loc$0)
  (define loc$1 (make-Box 'A))
  (define b loc$1)
  (define c loc$0)
  (define temp' 'B)
  'B


Hand Evaluation Problems from Exam II

1 a.
  (define (f x)
    (local [(define x 1)] x))
  (f 3)

=>(define (f x)
    (local [(define x 1)] x))
  (local [(define x 1) x))

=>(define (f x)
    (local [(define x 1)] x))
  (define x' 1)
  x'

=>(define (f x)
    (local [(define x 1)] x))
  (define x' 1)
  1

1 b.
  (define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (g 3)

=>(define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (local [(define y 2) (define z 3)]
    (local [(define y 4) (* 3 y z)]))

=>(define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (define y' 2)
  (define z' 3)
  (local [(define y 4) (* 3 y z')]))

=>(define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (define y' 2)
  (define z' 3)
  (define y'' 4)
  (* 3 y'' z')

=>(define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (define y' 2)
  (define z' 3)
  (define y'' 4)
  (* 3 4 3)

=>(define (g x)
    (local [(define y 2) (define z 3)]
      (local [(define y 4)] (* x y z))))
  (define y' 2)
  (define z' 3)
  (define y'' 4)
  36

1 c.
  (define (compose f g) (lambda (x) (f (g x))))
  ((compose first rest) (list 1 2))

=>(define (compose f g) (lambda (x) (f (g x))))
  ((lambda (x) (first (rest x))) (list 1 2))

=>(define (compose f g) (lambda (x) (f (g x))))
  (first (rest (list 1 2)))

=>(define (compose f g) (lambda (x) (f (g x))))
  (first (list 2))

=>(define (compose f g) (lambda (x) (f (g x))))
  2