Internal Definitions

Our environment model of evaluation and our metacircular evaluator execute definitions in sequence, extending the environment frame one definition at a time. This is particularly convenient for interactive program development, in which the programmer needs to freely mix the application of procedures with the definition of new procedures. However, if we think carefully about the internal definitions used to implement block structure (introduced in section ), we will find that name-by-name extension of the environment may not be the best way to define local variables.

Consider a procedure with internal definitions, such as

(define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) rest of body ofOur intention here is that the namef)

As it happens, our interpreter will evaluate calls to `f`
correctly, but for an ``accidental'' reason: Since the definitions of
the internal procedures come first, no calls to these procedures will
be evaluated until all of them have been defined. Hence, `odd?`
will have been defined by the time `even?` is executed. In fact,
our sequential evaluation mechanism will give the same result as a
mechanism that directly implements simultaneous definition for any
procedure in which the
internal definitions come first in a body and
evaluation of the value expressions for the defined variables doesn't
actually use any of the defined variables.
(For an example of a procedure that doesn't obey these restrictions,
so that sequential definition isn't equivalent to simultaneous definition,
see exercise .)
^{}

There is, however, a simple way to treat definitions so that
internally defined names have truly simultaneous scope--just create
all local variables that will be in the current environment before
evaluating any of the value expressions. One way to do this is by a
syntax transformation on `lambda` expressions. Before evaluating
the body of a `lambda` expression, we
``scan out'' and eliminate
all the internal definitions in the body. The internally defined
variables will be created with a `let` and then set to their
values by assignment. For example, the procedure

(lambda vars (define u e1) (define v e2) e3)would be transformed into

(lambda vars (let ((u '*unassigned*) (v '*unassigned*)) (set! u e1) (set! v e2) e3))where

An alternative strategy for scanning out internal definitions is shown
in exercise . Unlike the transformation
shown above, this enforces the restriction that the defined variables'
values can be evaluated without using any of the variables' values.
^{}

**Exercise.**
In this exercise we implement the method just described for
interpreting internal definitions.
We assume that the evaluator supports `let`
(see exercise ).

aChange `lookup-variable-value`
(section ) to signal an error if
the value it finds is the symbol `*unassigned*`.

bWrite a procedure `scan-out-defines` that takes a
procedure body and returns an equivalent one that has no internal
definitions, by making the transformation described above.

cInstall `scan-out-defines` in the interpreter, either in `
make-procedure` or in `procedure-body` (see
section ). Which place is better?
Why?

**Exercise.**
Draw diagrams of the environment in effect when evaluating the
expression e3 in the procedure in the text, comparing how this
will be structured when definitions are interpreted sequentially with
how it will be structured if definitions are scanned out as described.
Why is there an extra frame in the transformed program? Explain why
this difference in environment structure can never make a difference
in the behavior of a correct program. Design a way to make the
interpreter implement the ``simultaneous'' scope rule for internal
definitions without constructing the extra frame.

**Exercise.**
Consider an alternative strategy for scanning out definitions that
translates the example in the text to

(lambda vars (let ((u '*unassigned*) (v '*unassigned*)) (let ((a e1) (b e2)) (set! u a) (set! v b)) e3))Here

(define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y)Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain.

**Exercise.**
Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about
the desired result of evaluating the expression

(let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10))Ben asserts that the result should be obtained using the sequential rule for

**Exercise.**
Because internal definitions look sequential but are actually
simultaneous, some people prefer to avoid them entirely, and use the
special form `letrec` instead. `Letrec` looks like `let`,
so it is not surprising that the variables it binds are bound
simultaneously and have the same scope as each other. The sample
procedure `f` above can be written without internal definitions,
but with exactly the same meaning, as

(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 off))

(letrec ((varare a variation on_{1}exp_{1}) ... (var_{n}exp_{n})) body)

(letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10))

a. Implement `letrec` as a derived expression, by transforming
a `letrec` expression into a `let` expression as shown in
the text above or in exercise .
That is, the `letrec` variables should be created with a `let`
and then be assigned their values with `set!`.

b. Louis Reasoner is confused by all this fuss about internal
definitions. The way he sees it, if you don't like to use `
define` inside a procedure, you can just use `let`. Illustrate
what is loose about his reasoning by drawing an environment diagram
that shows the environment in which the rest of body of `f`
is evaluated during evaluation of the expression `(f 5)`, with
`f` defined as in this exercise. Draw
an environment diagram for the same evaluation, but with `let` in
place of `letrec` in the definition of `f`.

**Exercise.**
Amazingly, Louis's intuition in exercise
is correct. It is indeed possible to specify recursive procedures
without using `letrec` (or even `define`), although the method
for accomplishing this is much more subtle than Louis imagined. The
following expression computes 10 factorial by applying a recursive
factorial procedure:
^{}

((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10)

a. Check (by evaluating the expression) that this really does compute
factorials. Devise an analogous expression for computing Fibonacci numbers.

b. Consider the following procedure, which includes mutually recursive
internal definitions:

(define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) (even? x))Fill in the missing expressions to complete an alternative definition of

(define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? <??> <??> <??>))) (lambda (ev? od? n) (if (= n 0) false (ev? <??> <??> <??>)))))