Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
Structure and Interpretation of Computer Programs (75 page)
Exercise 4.21.
Amazingly, Louis's intuition in exercise
4.20
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:
27
((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
f
, which uses neither internal definitions nor
letrec
:
(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? )))))
The evaluator implemented above is simple, but it is very
inefficient, because the syntactic analysis of expressions is interleaved
with their execution. Thus if a program is executed many times, its
syntax is analyzed many times. Consider, for example, evaluating
(factorial 4)
using the following definition of
factorial
:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
Each time
factorial
is called, the evaluator must determine that
the body is an
if
expression and extract the predicate.
Only then can it evaluate the
predicate and dispatch on its value. Each time it evaluates the
expression
(* (factorial (- n 1)) n)
,
or the subexpressions
(factorial (- n 1))
and
(- n 1)
,
the evaluator must perform
the case analysis in
eval
to determine that the expression is an
application, and must extract its operator and operands. This
analysis is expensive. Performing it repeatedly is wasteful.
We can transform the evaluator to be significantly more efficient by
arranging things so that syntactic analysis is performed only
once.
28
We split
eval
, which takes an
expression and an environment, into two parts. The procedure
analyze
takes only the expression. It performs the syntactic
analysis and returns a new procedure, the
execution procedure
, that
encapsulates the work to be done in executing the analyzed
expression. The execution procedure takes an environment as its
argument and completes the evaluation. This saves work because
analyze
will be called only once on an expression, while the
execution procedure may be called many times.
With the separation into analysis and execution,
eval
now becomes
(define (eval exp env)
((analyze exp) env))
The result of calling
analyze
is the execution procedure to
be applied to the environment. The
analyze
procedure is
the same case analysis as performed by the original
eval
of
section
4.1.1
, except that the procedures to
which we dispatch perform only analysis, not full evaluation:
(define (analyze exp)
(cond ((self-evaluating? exp)
(analyze-self-evaluating exp))
((quoted? exp) (analyze-quoted exp))
((variable? exp) (analyze-variable exp))
((assignment? exp) (analyze-assignment exp))
((definition? exp) (analyze-definition exp))
((if? exp) (analyze-if exp))
((lambda? exp) (analyze-lambda exp))
((begin? exp) (analyze-sequence (begin-actions exp)))
((cond? exp) (analyze (cond->if exp)))
((application? exp) (analyze-application exp))
(else
(error "Unknown expression type -- ANALYZE" exp))))
Here is the simplest syntactic analysis procedure, which handles
self-evaluating expressions. It returns an execution procedure that
ignores its environment argument and just returns the expression:
(define (analyze-self-evaluating exp)
(lambda (env) exp))
For a quoted expression, we can gain a little efficiency by
extracting the text of the quotation only once, in the analysis phase,
rather than in the execution phase.
(define (analyze-quoted exp)
(let ((qval (text-of-quotation exp)))
(lambda (env) qval)))
Looking up a variable value must still be done in the execution phase,
since this depends upon knowing the environment.
29
(define (analyze-variable exp)
(lambda (env) (lookup-variable-value exp env)))
Analyze-assignment
also must defer actually setting the variable
until the execution, when the environment has been supplied. However,
the fact that the
assignment-value
expression can be
analyzed (recursively) during analysis is a major gain in efficiency,
because the
assignment-value
expression will now be analyzed
only once. The same holds true for definitions.
(define (analyze-assignment exp)
(let ((var (assignment-variable exp))
(vproc (analyze (assignment-value exp))))
(lambda (env)
(set-variable-value! var (vproc env) env)
'ok)))
(define (analyze-definition exp)
(let ((var (definition-variable exp))
(vproc (analyze (definition-value exp))))
(lambda (env)
(define-variable! var (vproc env) env)
'ok)))
For
if
expressions, we extract and analyze the predicate,
consequent, and alternative at analysis time.
(define (analyze-if exp)
(let ((pproc (analyze (if-predicate exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env)
(if (true? (pproc env))
(cproc env)
(aproc env)))))
Analyzing a
lambda
expression also achieves a major
gain in efficiency: We analyze the
lambda
body only once, even though
procedures resulting from evaluation of the
lambda
may be applied many times.
(define (analyze-lambda exp)
(let ((vars (lambda-parameters exp))
(bproc (analyze-sequence (lambda-body exp))))
(lambda (env) (make-procedure vars bproc env))))
Analysis of a sequence of expressions (as in a
begin
or the body
of a
lambda
expression) is more involved.
30
Each expression
in the sequence is analyzed, yielding an execution
procedure. These execution procedures are combined to produce an
execution
procedure that takes an environment as argument and sequentially calls
each individual execution procedure with the environment as argument.
(define (analyze-sequence exps)
(define (sequentially proc1 proc2)
(lambda (env) (proc1 env) (proc2 env)))
(define (loop first-proc rest-procs)
(if (null? rest-procs)
first-proc
(loop (sequentially first-proc (car rest-procs))
(cdr rest-procs))))
(let ((procs (map analyze exps)))
(if (null? procs)
(error "Empty sequence -- ANALYZE"))
(loop (car procs) (cdr procs))))
To analyze an application, we analyze the operator and operands and
construct an execution procedure that
calls the operator execution procedure (to obtain the
actual procedure to be applied) and the operand execution
procedures (to obtain the actual arguments). We then pass these to
execute-application
, which is the analog of
apply
in
section
4.1.1
.
Execute-application
differs from
apply
in that the procedure body for a compound procedure has already
been analyzed, so there is no need to do further analysis. Instead,
we just call the execution procedure for the body on the extended
environment.
(define (analyze-application exp)
(let ((fproc (analyze (operator exp)))
(aprocs (map analyze (operands exp))))
(lambda (env)
(execute-application (fproc env)
(map (lambda (aproc) (aproc env))
aprocs)))))
(define (execute-application proc args)
(cond ((primitive-procedure? proc)
(apply-primitive-procedure proc args))
((compound-procedure? proc)
((procedure-body proc)
(extend-environment (procedure-parameters proc)
args
(procedure-environment proc))))
(else
(error
"Unknown procedure type -- EXECUTE-APPLICATION"
proc))))
Our new evaluator uses the same data structures, syntax
procedures, and run-time support procedures as in
sections
4.1.2
,
4.1.3
, and
4.1.4
.
Exercise 4.22.
Extend the evaluator in this section to support the special form
let
.
(See exercise
4.6
.)
Exercise 4.23.
Alyssa P. Hacker doesn't understand why
analyze-sequence
needs to be
so complicated. All the other analysis procedures
are straightforward transformations of the corresponding evaluation
procedures (or
eval
clauses) in section
4.1.1
.
She expected
analyze-sequence
to look like this:
(define (analyze-sequence exps)
(define (execute-sequence procs env)
(cond ((null? (cdr procs)) ((car procs) env))
(else ((car procs) env)
(execute-sequence (cdr procs) env))))
(let ((procs (map analyze exps)))
(if (null? procs)
(error "Empty sequence -- ANALYZE"))
(lambda (env) (execute-sequence procs env))))
Eva Lu Ator explains to Alyssa that the version in the text does more
of the work of evaluating a sequence at analysis time. Alyssa's
sequence-execution procedure, rather than having the calls to the
individual execution procedures built in, loops through the procedures
in order to call them: In effect, although the individual expressions
in the sequence have been analyzed, the sequence itself has not been.
Compare the two versions of
analyze-sequence
. For example,
consider the common case (typical of procedure bodies) where the
sequence has just one expression. What work will the execution
procedure produced by Alyssa's program do? What about the execution
procedure produced by the program in the text above? How do the two
versions compare for a sequence with two expressions?
Exercise 4.24.
Design and carry out some experiments to
compare the speed of the original metacircular evaluator
with the version in this section. Use your results to estimate the fraction
of time that is spent in analysis versus execution for various
procedures.
3
Even so, there will remain important aspects of
the evaluation process that are not elucidated by our evaluator. The
most important of these are the detailed mechanisms by which
procedures call other procedures and return values to their callers.
We will address these issues in chapter 5, where we take a closer look
at the evaluation process by implementing the evaluator as a simple
register machine.
4
If we grant ourselves the ability to apply primitives,
then what remains for us to implement in the evaluator? The job of
the evaluator is not to specify the primitives of the language, but rather
to provide the connective tissue – the means of combination and the
means of abstraction – that binds a collection of primitives to form a
language. Specifically:
- The evaluator enables us to deal with nested expressions. For
example, although simply applying primitives
would suffice for evaluating
the expression
(+ 1 6)
, it is not adequate for handling
(+ 1 (* 2
3))
. As far as the primitive procedure
+
is concerned,
its arguments must be numbers, and it would choke if we passed it the
expression
(* 2 3)
as an argument. One important role of the
evaluator is to choreograph procedure composition so that
(* 2
3)
is reduced to 6 before being passed as an argument to
+
. - The evaluator allows us to use variables. For example, the
primitive procedure for addition has no way to deal with expressions such
as
(+ x 1)
. We need an evaluator to keep track of variables and
obtain their values before invoking the primitive
procedures. - The evaluator allows us to define compound procedures. This
involves keeping track of procedure definitions, knowing how to use
these definitions in evaluating expressions, and providing a mechanism
that enables procedures to accept arguments. - The evaluator provides the special forms, which must be
evaluated differently from procedure calls.
5
We could have simplified the
application?
clause in
eval
by using
map
(and stipulating that
operands
returns a list) rather than
writing an explicit
list-of-values
procedure. We chose not to
use
map
here to emphasize the fact that the
evaluator can be
implemented without any use of higher-order procedures
(and thus could be written in a language that doesn't have
higher-order procedures), even though
the language that it supports will include higher-order procedures.
6
In this case, the language being implemented and the
implementation language are the same. Contemplation of the meaning of
true?
here yields expansion of consciousness without the abuse
of substance.
7
This implementation of
define
ignores a subtle
issue in the handling of internal definitions, although it works
correctly in most cases. We will see what the problem is and how to
solve it in section
4.1.6
.
8
As we said when we
introduced
define
and
set!
, these values
are implementation-dependent in Scheme – that is, the implementor
can choose what value to return.
9
As mentioned in
section
2.3.1
, the evaluator sees a quoted expression as
a list beginning with
quote
, even if the
expression is typed with the quotation mark. For example, the
expression
'a
would be seen by the evaluator as
(quote a)
.
See exercise
2.55
.
10
The value of an
if
expression when the predicate
is false and there is no alternative
is unspecified in Scheme; we have chosen here to make it false.
We will support the use of the variables
true
and
false
in expressions to be evaluated by binding them in the global
environment. See section
4.1.4
.
11
These selectors for a list of expressions – and the
corresponding ones for a list of operands – are not intended as a data
abstraction. They are introduced as mnemonic names for the basic list
operations in order to make it easier to understand the explicit-control
evaluator in section
5.4
.
12
The value of a
cond
expression when all the predicates
are false and there is no
else
clause
is unspecified in Scheme; we have chosen here to make it false.
13
Practical Lisp systems provide a
mechanism that allows a user to add new derived expressions and
specify their implementation as syntactic transformations without
modifying the evaluator. Such a user-defined transformation is called a
macro
.
Although it is easy to add an elementary mechanism for defining macros,
the resulting language has subtle name-conflict problems.
There has been much research on mechanisms for macro definition
that do not cause these difficulties. See,
for example, Kohlbecker 1986, Clinger and Rees 1991, and Hanson 1991.
14
Frames are not really a data abstraction in the following code:
Set-variable-value!
and
define-variable!
use
set-car!
to directly modify the values in a frame. The purpose of the frame
procedures is to make the environment-manipulation procedures easy to read.
15
The drawback of this representation (as well as the variant in
exercise
4.11
) is that the evaluator
may have to search through many frames in order to find the binding
for a given variable.
(Such an approach is referred to as
deep binding
.)
One way to avoid
this inefficiency is to make use of a strategy called
lexical
addressing
, which will be discussed in
section
5.5.6
.
16
Any procedure defined in the underlying Lisp can be used as
a primitive for the metacircular evaluator. The name of a
primitive installed in the evaluator need not be the same as the name
of its implementation in the underlying Lisp; the names are the same
here because the metacircular evaluator implements Scheme itself.
Thus, for example, we could put
(list 'first car)
or
(list
'square (lambda (x) (* x x)))
in the list of
primitive-procedures
.
17
Apply-in-underlying-scheme
is the
apply
procedure
we have used in earlier chapters. The metacircular evaluator's
apply
procedure (section
4.1.1
) models the
working of this primitive. Having two different things called
apply
leads to a technical problem in running the metacircular
evaluator, because defining the metacircular evaluator's
apply
will mask the definition of the primitive. One way around this is to
rename the metacircular
apply
to avoid conflict with the name of
the primitive procedure. We have assumed instead that we have saved a
reference to the underlying
apply
by doing
(define apply-in-underlying-scheme apply)
before defining the metacircular
apply
. This allows us to
access the original version of
apply
under a different name.
18
The primitive procedure
read
waits for input from the user,
and returns the next complete expression that is typed.
For example, if the user types
(+ 23 x)
,
read
returns
a three-element list containing the symbol
+
, the number 23,
and the symbol
x
.
If the user types
'x
,
read
returns a two-element list
containing the symbol
quote
and the symbol
x
.
19
The fact that the machines are described in Lisp is
inessential. If we give our evaluator a Lisp program
that behaves as an evaluator for
some other language, say C, the Lisp evaluator will emulate the C
evaluator, which in turn can emulate any machine described as a C
program. Similarly, writing a Lisp evaluator in C produces a C
program that can execute any Lisp program. The deep idea here is that
any evaluator can emulate any other. Thus, the notion of “what can
in principle be computed” (ignoring practicalities of time and
memory required) is independent of the language or the computer, and
instead reflects an underlying notion of
computability
. This
was first demonstrated in a clear way by
Alan M. Turing (1912-1954),
whose 1936 paper laid the foundations for theoretical
computer
science. In the paper, Turing presented a simple computational
model – now known as a
Turing machine
– and argued that any
“effective process” can be formulated as a program for such a
machine. (This argument is known as the
Church-Turing thesis
.)
Turing then implemented a universal machine, i.e., a Turing machine
that behaves as an evaluator for Turing-machine programs. He used
this framework to demonstrate that there are well-posed problems that
cannot be computed by Turing machines (see
exercise
4.15
), and so by implication cannot be
formulated as “effective processes.” Turing went on to make
fundamental contributions to practical computer science as well. For
example, he invented the idea of
structuring programs using
general-purpose subroutines. See
Hodges 1983 for a biography of
Turing.
20
Some people find it
counterintuitive that an evaluator, which is implemented by a
relatively simple procedure, can emulate programs that are more
complex than the evaluator itself. The existence of a universal
evaluator machine is a deep and wonderful property of computation.
Recursion theory
, a branch of mathematical logic, is concerned
with logical limits of computation.
Douglas Hofstadter's beautiful
book
Gödel, Escher, Bach
(1979) explores some of these ideas.
21
Warning:
This
eval
primitive is not
identical to the
eval
procedure we implemented in
section
4.1.1
, because it uses
actual
Scheme environments rather than the sample environment structures we
built in section
4.1.3
. These actual
environments cannot be manipulated by the user as ordinary lists; they
must be accessed via
eval
or other special operations.
Similarly, the
apply
primitive we saw earlier is not identical
to the metacircular
apply
, because it uses actual Scheme procedures
rather than the procedure objects we constructed in
sections
4.1.3
and
4.1.4
.
22
The MIT
implementation of Scheme includes
eval
, as well as a symbol
user-initial-environment
that is bound to the initial environment in
which the user's input expressions are evaluated.
23
Although we stipulated that
halts?
is given a procedure object,
notice that this reasoning still applies even if
halts?
can gain
access to the procedure's text and its environment.
This is Turing's celebrated
Halting Theorem
, which gave
the first clear example of a
non-computable
problem, i.e., a
well-posed task that cannot be carried out as a computational
procedure.
24
Wanting programs to not depend on this evaluation
mechanism is the reason for the “management is not
responsible” remark in footnote
28
of chapter 1.
By insisting that internal definitions come first and do not use each
other while the definitions are being evaluated, the IEEE standard
for Scheme leaves implementors some choice in the mechanism used to
evaluate these definitions. The choice of one evaluation rule rather
than another here may seem like a small issue, affecting only the
interpretation of “badly formed” programs. However, we will see in
section
5.5.6
that moving to a model of
simultaneous scoping for internal definitions avoids some nasty
difficulties that would otherwise arise in implementing a compiler.
25
The IEEE standard for Scheme
allows for different implementation strategies by specifying that it
is up to the programmer to obey this restriction, not up to the
implementation to enforce it. Some Scheme implementations, including
MIT Scheme, use the transformation shown above. Thus, some programs
that don't obey this restriction will in fact run in such implementations.
26
The MIT implementors of Scheme support Alyssa on
the following grounds: Eva is in principle correct – the definitions
should be regarded as simultaneous. But it seems difficult to
implement a general, efficient mechanism that does what Eva requires.
In the absence of such a mechanism, it is better to generate an error
in the difficult cases of simultaneous definitions (Alyssa's notion)
than to produce an incorrect answer (as Ben would have it).
27
This example illustrates a programming trick for
formulating recursive procedures without using
define
. The
most general trick of this sort is the
Y
operator
, which can
be used to give a “pure λ-calculus” implementation of
recursion. (See Stoy 1977 for details on the lambda calculus, and
Gabriel 1988 for an exposition of the
Y
operator in Scheme.)