4.16 Exercise 4.16

lookup-variable-value should be modified to look like this (modified to check the value after the binding has been found, only returning successfully if it is assigned):

(define (lookup-variable-value var env)

(define (env-loop env)

(define (scan vars vals)

(cond ((null? vars) (env-loop (enclosing-environment env)))

((eq? var (car vars))

(let ((val (car vals)))

(if (eq? val '*unassigned*)

(error "Use of unassigned variable" var)

val)))

(else (scan (cdr vars) (cdr vals)))))

(if (eq? env the-empty-environment)

(error "Unbound variable" var)

(let ((frame (first-frame env)))

(scan (frame-variables frame)

(frame-values frame)))))

(env-loop env))

The basic strategy for defining scan-out-defines will be as follows:

• Grab all of the definition at the start of the procedure body. (It is illegal to have internal definitions after any non-definition expressions)

• If there are no internal definitions, return the body

• Zip each of the variables of the internal definition in a list with ’*unassigned*

• Create set! expressions for each of the definitions

• Make a let expression with our bindings and the set! expressions appended with the original body

To do this, we will first define helper procedures partition and make-set:

(define (partition pred lst)

(define (go acc rest)

(if (null? rest)

(cons (reverse acc) '())

(let ((x (car rest))

(xs (cdr rest)))

(if (pred x)

(go (cons x acc) xs)

(cons (reverse acc) rest)))))

(go '() lst))

(define (make-set var val)

(list 'set! var val))

The definition of scan-out-defines is as follows:

(define (scan-out-defines procedure-body)

(let* ((define-partition (partition definition? procedure-body))

(defines (car define-partition))

(body (cdr define-partition)))

(if (null? defines)

body

(let ((unassigned-bindings

(map (lambda (d) (list (definition-variable d) ''*unassigned*)) defines))

(set-expressions

(map (lambda (d) (make-set (definition-variable d) (definition-value d))) defines)))

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

One thing to note is that the return value is wrapped in a list. I got this wrong before. Also of note is the fact that the unassigned value is passed as ”*unassigned*. I also got this wrong initially, but it is very important – otherwise this is taken to be the variable *unassigned*, which of course has no value and is not what we want to do.

I believe that make-procedure is the best place to transform the body into our new normalized form – it seems better to me that having the body in the form we want is best guaranteed when the procedure object is defined, rather than (hopefully!) normalizing it when it is accessed.