Structure and Interpretation of Computer Programs (74 page)

From this perspective, our evaluator is seen to be a
universal machine
.
It mimics other machines when these are described as Lisp programs.
¹⁹
This is striking. Try to imagine an analogous evaluator for electrical
circuits. This would be a circuit that takes as input a signal
encoding the plans for some other circuit, such as a filter. Given
this input, the circuit evaluator would then behave like a filter with
the same description. Such a universal electrical circuit is
almost unimaginably complex. It is remarkable that the program
evaluator is a rather simple program.
²⁰

Another striking aspect of the evaluator is that it acts as a bridge
between the data objects that are manipulated by our programming
language and the programming language itself. Imagine that the
evaluator program (implemented in Lisp) is running, and that a user is
typing expressions to the evaluator and observing the results. From
the perspective of the user, an input expression such as
(* x x)
is an expression in the programming language, which the evaluator
should execute. From the perspective of the evaluator, however, the
expression is simply a list (in this case, a list of three symbols:
*
,
x
, and
x
) that is to be manipulated according to
a well-defined set of rules.

That the user's programs are the evaluator's data need not be a source
of confusion. In fact, it is sometimes convenient to ignore this
distinction, and to give the user the ability to explicitly evaluate a
data object as a Lisp expression, by making
eval
available for
use in programs. Many Lisp dialects provide a
primitive
eval
procedure that takes as arguments an expression and an environment and
evaluates the expression relative to the environment.
²¹
Thus,

(eval '(* 5 5) user-initial-environment)

and

(eval (cons '* (list 5 5)) user-initial-environment)

will both return 25.
²²

Exercise 4.15.
  
Given a one-argument procedure
p
and an object
a
,
p
is said to “halt” on
a
if evaluating the expression
(p
a)
returns a value (as opposed to terminating with an error message
or running forever). Show that it is impossible to write a procedure
halts?
that correctly determines whether
p
halts on
a
for any procedure
p
and object
a
. Use the following
reasoning: If you had such a procedure
halts?
, you could
implement the following program:

(define (run-forever) (run-forever))
(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

Now consider evaluating the expression
(try try)
and show that
any possible outcome (either halting or running forever) violates the
intended behavior of
halts?
.
²³

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 
1.1.8
), 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 of 
f
>)

Our intention here is that the name
odd?
in the body of the
procedure
even?
should refer to the procedure
odd?
that is
defined after
even?
. The scope of the name
odd?
is the
entire body of
f
, not just the portion of the body of
f
starting at the point where the
define
for
odd?
occurs.
Indeed, when we consider that
odd?
is itself defined in terms of
even?
– so that
even?
and
odd?
are mutually
recursive procedures – we see that the only satisfactory
interpretation of the two
define
s is to regard them as if the
names
even?
and
odd?
were being added to the environment
simultaneously.
More generally, in block structure, the scope of a local name is the
entire procedure body in which the
define
is evaluated.

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 
4.19
.)
²⁴

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
*unassigned*
is a special symbol that causes looking up a
variable to signal an error if an attempt is made to use the value of
the not-yet-assigned variable.

An alternative strategy for scanning out internal definitions is shown
in exercise 
4.18
. 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 4.16.
  In this exercise we implement the method just described for
interpreting internal definitions.
We assume that the evaluator supports
let
(see exercise 
4.6
).

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

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

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

Exercise 4.17.
  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 4.18.
  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
a
and
b
are meant to represent new variable names,
created by the interpreter, that do not appear in the user's
program.
Consider the
solve
procedure from
section 
3.5.4
:

(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 4.19.
  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
define
:
b
is defined to be 11, then
a
is
defined to be 5, so the result is 16. Alyssa objects that mutual
recursion requires the simultaneous scope rule for internal procedure
definitions, and that it is unreasonable to treat procedure names
differently from other names. Thus, she argues for the mechanism
implemented in exercise 
4.16
. This would lead to
a
being unassigned at the time that the value for
b
is to
be computed. Hence, in Alyssa's view the procedure should produce an
error. Eva has a third opinion. She says that if the definitions of
a
and
b
are truly meant to be simultaneous, then the value
5 for
a
should be used in evaluating
b
. Hence, in Eva's
view
a
should be 5,
b
should be 15, and the result should
be 20. Which (if any) of these viewpoints do you support? Can you
devise a way to implement internal definitions so that they behave as
Eva prefers?
²⁶

Exercise 4.20.
  
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 of 
f
>))

Letrec
expressions, which have the form

(letrec ((<
var
₁
> <
exp
₁
>) 
...
(<
var
_n
> <
exp
_n
>))
  <
body
>)

are a variation on
let
in which the expressions
<
exp
_k
> that provide the initial values for the variables <
var
_k
>
are evaluated in an environment that includes all the
letrec
bindings. This permits recursion in the bindings, such as the mutual
recursion of
even?
and
odd?
in the example above, or
the evaluation of 10 factorial with

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