4.20 Exercise 4.20

Consider the given use of letrec:

(define (f x)

(letrec ((even?

(lambda (n)

(if (= n 0)

true

(odd? (- n 1)))))

(odd?

(lambda (n)

(if (= n 0)

false

(even? (- n 1))))))

<rest of body of f>))

This is equivalent to the following:

(define (f x)

(let ((even? '*unassigned*)

(odd? '*unassigned*))

(set! even?

(lambda (n)

(if (= n 0)

true

(odd? (- n 1)))))

(set! odd?

(lambda (n)

(if (= n 0)

false

(even? (- n 1)))))

<rest of body of f>))

We can write a transformation procedure similar to scan-out-defines as follows:

(define (letrec->nested-let exp)

(let ((names (let-names exp))

(body (let-body exp)))

(let ((unassigned-bindings

(map (lambda (n) (list n '*unassigned)) names))

(set-expressions

(map (lambda (p) (make-set (car p) (cdr p))) (let-bindings exp))))

(append (list 'let unassigned-bindings) (append set-expressions body)))))

Louis is wrong because, if using a standard let expression, the definition of even? will fail because odd? is not yet present in the environment, meaning that the attempt to set the initial value will error on trying to reference the value of this binding.

TODO: Environment diagram