sicp-ex-4.20



<< Previous exercise (4.19) | Index | Next exercise (4.21) >>


meteorgan

  
  
  
 ;; a 
 ;; letrec expression 
 (define (letrec? expr) (tagged-list? expr 'letrec)) 
 (define (letrec-inits expr) (cadr expr)) 
 (define (letrec-body expr) (cddr expr)) 
 (define (declare-variables expr) 
         (map (lambda (x) (list (car x) '*unassigned*)) (letrec-inits expr))) 
 (define (set-variables expr) 
         (map (lambda (x) (list 'set! (car x) (cadr x))) (letrec-inits expr))) 
 (define (letrec->let expr) 
         (list 'let (declare-variables expr)  
                (make-begin (append (set-variables expr) (letrec-body expr))))) 

leafac

 ;; The lambda in `let' is evaluated in the context of the enclosing environment, 
 ;; in which the bindings of the lambda itself are not in place. 
  
 ;; The trick of encoding `letrec' is that we first establish the bindings, and 
 ;; then define the lambdas in an environment where the bindings are there, so 
 ;; the recursive call can succeed. 
  
 ;; The following snippets illustrate the difference: 
  
 (let ((fact <fact-body>)) 
   <let-body>) 
  
 ;; is encoded by 
  
 ((lambda (fact) 
    <let-body>) 
  <fact-body>) 
  
 ;; such that `<fact-body>' can't refer to `fact'. While: 
  
 (letrec ((fact <fact-body>)) 
   <let-body>) 
  
 ;; is encoded by 
  
 ((lambda (fact) 
    (set! fact <fact-body>) 
    <fact-body>) 
  '*unassigned*) 
  
 ;; note that in the context of `<fact-body>', the variable `fact' itself is 
 ;; bound. 
  

codybartfast




Letrec Environment Diagram
==========================
Even? and odd? procs reference E2 because the are created when evaluating
set! within the body of the lambda.  This means they can lookup the even?
and odd? variables defined in this frame.

global env ──┐
             v
┌───────────────────────────┐
│                           │
│(after call to define)     │
│f:┐                        │<─────────────────────────────┐
└───────────────────────────┘                              │
   │  ^                                                    │
   │  │                                  call to f         │
   v  │                          ┌─────────────────────────┴─┐
  @ @ │                          │x: 5                       │
  │ └─┘                     E1 ->│                           │
  v                              │                           │<───┐
parameter: x                     └───────────────────────────┘    │
((lambda (even? odd?)                                             │
   (set! even? (lambda (n) ...)                                   │
   (set! odd? (lambda (n) ...)             call to letrec/lambda  │
   (even? x))                           ┌─────────────────────────┴─┐
 *unassigned* *unassigned*)             │even?:─────────────────┐   │
                                   E2 ->│odd?:┐                 │   │
                                        │     │                 │   │
                                        └───────────────────────────┘
                                              │  ^              │  ^
                                              │  │              │  │
                                              v  │              v  │
                                             @ @ │             @ @ │
                                             │ └─┘             │ └─┘
                                             v                 v
                                        parameter: n      parameter: n
                                      (if (equal? n 0)  (if (equal? n 0)
                                          false             true
                                          ...               ...

Let Environment Diagram
=======================
Even? and odd? procs reference E1 because they are evaluated in the body of
f but outside the 'let lambda' because they are passed as arguments to that
lambda.  This means they can't lookup the even? and odd? variables defined
in E2.

global env ──┐
             v
┌───────────────────────────┐
│                           │
│(after call to define)     │
│f:┐                        │<─────────────────────────────┐
└───────────────────────────┘                              │
   │  ^                                                    │
   │  │                                  call to f         │
   v  │                          ┌─────────────────────────┴─┐
  @ @ │                          │x: 5                       │<───────────┐
  │ └─┘                     E1 ->│                           │<─────────┐ │
  v                              │                           │<───┐     │ │
parameter: x                     └───────────────────────────┘    │     │ │
((lambda (even? odd?)                                             │     │ │
   (even? x))                                                     │     │ │
 (lambda (n) (if (equal? n ...))           call to let/lambda     │     │ │
 (lambda (n) (if (equal? n ...)))       ┌─────────────────────────┴─┐   │ │
                                        │even?:─────────────────┐   │   │ │
                                   E2 ->│odd?:┐                 │   │   ^ │
                                        │     │                 │   │   │ │
                                        └───────────────────────────┘   │ │
                                              │                 │       │ │
                                              │  ┌──────────────────────┘ ^
                                              │  │              │         │
                                              v  │              v         │
                                             @ @ │             @ @        │
                                             │ └─┘             │ └────────┘
                                             v                 v
                                        parameter: n      parameter: n
                                      (if (equal? n 0)  (if (equal? n 0)
                                          false             true
                                          ...               ...