6.001 Structure and Interpretation of Computer Programs
Recitation #16
Wednesday, November 3, 2004

Review

Practice

Evaluate the following expressions, drawing the corresponding environment diagram in the space on the right.

1.
 
(define (fact n)
  (if (= n 1) 
      1   
      (* n (fact (- n 1))))) | GE

=> (define desugaring rule)

(define fact 
  (lambda (n)
    (if (= n 1) 
        1   
        (* n (fact (- n 1)))))) | GE

effects: creates double-bubble L1
         binds fact:L1 in environment GE




(define n 6) | GE

effects: binds n:6 in GE




(fact 3) | GE

effects: creates frame E1
         binds n:3 in E1
         links E1 to GE (from L1's pointer)
         evaluates body of L1 with respect to E1:

   (if (= n 1)
       1
       (* n (fact (- n 1)))) | E1

   => (reduces to)

   (<prim proc *> 3 (<L1> 2)) | E1

   effects: creates frame E2
            binds n:2 in E2
            links E2 to GE (**** not to E1!)
            evaluates L1's body with respect to E2:

      (if (= n 1)
          1
          (* n (fact (- n 1)))) | E2

      => (reduces to)

      (<prim proc *> 2 (<L1> 1)) | E2

      effects: creates frame E3
               binds n:1 in E3
               links E3 to GE
               evaluates L1's body with respect to E3:

         (if (= n 1)
             1
             (* n (fact (- n 1)))) | E3

         => 1
   
      => 2

   => 6

=> 6
 rec12image1
2. 
(define x 4) | GE

effects: binds x:4 in GE



(let ((x (+ 2 1))
      (y (square x)))
  (* x y)) | GE

=> (let desugaring rule)

((lambda (x y)
    (* x y))
 (+ 2 1)
 (square x)) | GE

effects: creates double-bubble L1

=>

(<L1> 3 16) | GE

effects: creates frame E1
         binds x:3, y:16 in E1
         links E1 to GE
         evaluates body of L1:

   (* x y) | E1

   => 48

=> 48
 rec12image2
3. 
(define make-counter
  (lambda () 
    (let ((count 0))
      (lambda () 
        (set! count (+ 1 count))
        count))))

;; effects: makes double-bubble L1
;;          binds make-counter:L1 in GE

(define days (make-counter))

;; effects: makes frame E1
;;          makes (temporary) double-bubble L2
;;          makes frame E2 with binding count:0
;;          makes double-bubble L3
;;          binds days:L3 in GE

(define dollars (make-counter))

;; effects: makes frame E3
;;          makes (temporary) double-bubble L4
;;          makes frame E4 with binding count:0
;;          makes double-bubble L5
;;          binds days:L5 in GE


(days)

;; effects: makes frame E5
;;          sets count in E2 to 1

=> 1


(days)

;; effects: makes frame E6
;;          sets count in E2 to 2

=> 2


(dollars)

;; effects: makes frame E7
;;          sets count in E4 to 1

=> 1


(dollars)

;; effects: makes frame E8
;;          sets count in E4 to 2

=> 2




 rec12image3

The key thing to notice in this example is that the days and dollars procedures have different instances of the variable count, because their double-bubbles (L3 and L5) point to different frames.  When days increments its count, nothing happens to dollar's count.
The key question in problems 4-6 is, which of these make-count-proc definitions creates a procedure that counts the number of times it's called?
4. 
(define make-count-proc-1
  (lambda (f) 
    (lambda (x)
      (let ((count 0))
        (cond ((eq? x 'count) count)
              (else (set! count (+ count 1))
                    (f x)))))))

(define sqrt* (make-count-proc-1 sqrt))

(sqrt* 4)
=> 2

(sqrt* 'count)
=> 0
 rec12image4

We see that this definition doesn't work -- the let expression that creates the count variable is so deep within the function that it's actually recreated on every call to sqrt*.  So when we call (sqrt* 'count) expecting to get the value of the counter, all we ever get is 0.
5. 
(define make-count-proc-2
  (lambda (f) 
    (let ((count 0))
      (lambda (x)
        (cond ((eq? x 'count) count)
              (else (set! count (+ count 1))
                    (f x)))))))

(define sqrt* (make-count-proc-2 sqrt))
(define square* (make-count-proc-2 square))

(sqrt* 4)
=> 2

(sqrt* 'count)
=> 1

(square* 4)
=> 16
(square* 'count)
=> 1
 rec12image5

Now the let expression is placed in such a way that every procedure created by make-count-proc-2 has a different instance of count.  Thus, sqrt* counts separately from square*, which is probably what we want.
6. 
(define make-count-proc-3
  (let ((count 0))
    (lambda (f) 
      (lambda (x)
        (cond ((eq? x 'count) count)
              (else (set! count (+ count 1))
                    (f x)))))))

(define sqrt* (make-count-proc-3 sqrt))
(define square* (make-count-proc-3 square))

(sqrt* 4)
=> 2

(sqrt* 'count)
=> 1

(square* 4)
=> 16

(square* 'count)
=> 2
 rec12image6

Now we see that making let the outermost expression makes only one instance of the count variable that is shared by all procedures produced by make-count-proc-3.  The calls to sqrt* and square* both increment the same count variable, and we'll get the same value regardless of whether we ask sqrt* or square* for the count.