sicp-ex-4.20

  
  
  
 ;; 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))))) 

 ;; 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. 
  

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
                                          ...               ...

I implemented the exercise 4.18 form

 ;- we use the form from ex 4.18 because this makes the bindings truly simultaneous 
 ;- we expect it to throw an error for evaluations like the one in 4.18 
 ;- in essence, cyclic dependencies will only be allowed by letrec if they are wrapped 
 ;by a lambda 
  
 (define (letrec? exp) (tagged-list? exp letrec)) 
 (define (letrec-inits exp) (cadr exp)) 
 (define (letrec-vars exp) (map car (letrec-inits exp))) 
 (define (letrec-bindings exp) (map cadr (letrec-inits exp))) 
 (define (letrec-body exp) (caddr exp)) 
 (define (get-symbols exp) (map 
                            (lambda (x) (next-symbol interpreter-symbol-list)) 
                            (letrec-inits exp))) 
 ;where interpreter-symbol-list is an infinite stream of randomly generated symbols 
 (define (letrec->let exp) 
   (let ((intermediate-symbols (get-symbols exp))) 
     (make-let (map (lambda (var) (list var '*unassigned*)) (letrec-vars exp)) 
               (list (make-let (map list intermediate-symbols (letrec-bindings exp)) 
                               (map (lambda (var value) (list 'set! var value)) (letrec-vars exp) intermediate-symbols)) 
                     (letrec-body exp)))))