Structure and Interpretation of Computer Programs

This book is dedicated, in respect and admiration, to the spirit that
lives in the computer.

“I think that it's extraordinarily important that we in computer
science keep fun in computing. When it started out, it was an awful
lot of fun. Of course, the paying customers got shafted every now and
then, and after a while we began to take their complaints seriously.
We began to feel as if we really were responsible for the successful,
error-free perfect use of these machines. I don't think we are. I
think we're responsible for stretching them, setting them off in new
directions, and keeping fun in the house. I hope the field of
computer science never loses its sense of fun. Above all, I hope we
don't become missionaries. Don't feel as if you're Bible salesmen.
The world has too many of those already. What you know about
computing other people will learn. Don't feel as if the key to
successful computing is only in your hands. What's in your hands, I
think and hope, is intelligence: the ability to see the machine as
more than when you were first led up to it, that you can make it
more.”

Alan J. Perlis (April 1, 1922-February 7, 1990)

Foreword

Educators, generals, dieticians, psychologists, and parents program.
Armies, students, and some societies are programmed. An assault on
large problems employs a succession of programs, most of which spring
into existence en route. These programs are rife with issues that
appear to be particular to the problem at hand. To appreciate
programming as an intellectual activity in its own right you must turn
to computer programming; you must read and write computer
programs – many of them. It doesn't matter much what the programs are
about or what applications they serve. What does matter is how well
they perform and how smoothly they fit with other programs in the
creation of still greater programs. The programmer must seek both
perfection of part and adequacy of collection. In this book the use
of “program” is focused on the creation, execution, and study of
programs written in a dialect of Lisp for execution on a digital
computer. Using Lisp we restrict or limit not what we may program,
but only the notation for our program descriptions.

Our traffic with the subject matter of this book involves us with
three foci of phenomena: the human mind, collections of computer
programs, and the computer. Every computer program is a model,
hatched in the mind, of a real or mental process. These processes,
arising from human experience and thought, are huge in number,
intricate in detail, and at any time only partially understood. They
are modeled to our permanent satisfaction rarely by our computer
programs. Thus even though our programs are carefully handcrafted
discrete collections of symbols, mosaics of interlocking functions,
they continually evolve: we change them as our perception of the model
deepens, enlarges, generalizes until the model ultimately attains a
metastable place within still another model with which we struggle.
The source of the exhilaration associated with computer programming is
the continual unfolding within the mind and on the computer of
mechanisms expressed as programs and the explosion of perception they
generate. If art interprets our dreams, the computer executes them in
the guise of programs!

For all its power, the computer is a harsh taskmaster. Its programs
must be correct, and what we wish to say must be said accurately in
every detail. As in every other symbolic activity, we become
convinced of program truth through argument. Lisp itself can be
assigned a semantics (another model, by the way), and if a program's
function can be specified, say, in the predicate calculus, the proof
methods of logic can be used to make an acceptable correctness
argument. Unfortunately, as programs get large and complicated, as
they almost always do, the adequacy, consistency, and correctness of
the specifications themselves become open to doubt, so that complete
formal arguments of correctness seldom accompany large programs.
Since large programs grow from small ones, it is crucial that we
develop an arsenal of standard program structures of whose correctness
we have become sure – we call them idioms – and learn to combine them
into larger structures using organizational techniques of proven
value. These techniques are treated at length in this book, and
understanding them is essential to participation in the Promethean
enterprise called programming. More than anything else, the
uncovering and mastery of powerful organizational techniques
accelerates our ability to create large, significant programs.
Conversely, since writing large programs is very taxing, we are
stimulated to invent new methods of reducing the mass of function and
detail to be fitted into large programs.

Unlike programs, computers must obey the laws of physics. If they
wish to perform rapidly – a few nanoseconds per state change – they
must transmit electrons only small distances (at most 1
¹
/
2
feet). The heat generated by the huge number of devices so
concentrated in space has to be removed. An exquisite engineering art
has been developed balancing between multiplicity of function and
density of devices. In any event, hardware always operates at a level
more primitive than that at which we care to program. The processes
that transform our Lisp programs to “machine” programs are
themselves abstract models which we program. Their study and creation
give a great deal of insight into the organizational programs
associated with programming arbitrary models. Of course the computer
itself can be so modeled. Think of it: the behavior of the smallest
physical switching element is modeled by quantum mechanics described
by differential equations whose detailed behavior is captured by
numerical approximations represented in computer programs executing on
computers composed of
...
!

It is not merely a matter of tactical convenience to separately
identify the three foci. Even though, as they say, it's all in the
head, this logical separation induces an acceleration of symbolic
traffic between these foci whose richness, vitality, and potential is
exceeded in human experience only by the evolution of life itself. At
best, relationships between the foci are metastable. The computers
are never large enough or fast enough. Each breakthrough in hardware
technology leads to more massive programming enterprises, new
organizational principles, and an enrichment of abstract models.
Every reader should ask himself periodically “Toward what end, toward
what end?” – but do not ask it too often lest you pass up the fun of
programming for the constipation of bittersweet philosophy.

Among the programs we write, some (but never enough) perform a precise
mathematical function such as sorting or finding the maximum of a
sequence of numbers, determining primality, or finding the square
root. We call such programs algorithms, and a great deal is known of
their optimal behavior, particularly with respect to the two important
parameters of execution time and data storage requirements. A
programmer should acquire good algorithms and idioms. Even though
some programs resist precise specifications, it is the responsibility
of the programmer to estimate, and always to attempt to improve, their
performance.

Lisp is a survivor, having been in use for about a quarter of a
century. Among the active programming languages only Fortran has had
a longer life. Both languages have supported the programming needs of
important areas of application, Fortran for scientific and engineering
computation and Lisp for artificial intelligence. These two areas
continue to be important, and their programmers are so devoted to
these two languages that Lisp and Fortran may well continue in active
use for at least another quarter-century.

Lisp changes. The Scheme dialect used in this text has evolved from
the original Lisp and differs from the latter in several important
ways, including static scoping for variable binding and permitting
functions to yield functions as values. In its semantic structure
Scheme is as closely akin to Algol 60 as to early Lisps. Algol 60,
never to be an active language again, lives on in the genes of Scheme
and Pascal. It would be difficult to find two languages that are the
communicating coin of two more different cultures than those gathered
around these two languages. Pascal is for building
pyramids – imposing, breathtaking, static structures built by armies
pushing heavy blocks into place. Lisp is for building
organisms – imposing, breathtaking, dynamic structures built by squads
fitting fluctuating myriads of simpler organisms into place. The
organizing principles used are the same in both cases, except for one
extraordinarily important difference: The discretionary exportable
functionality entrusted to the individual Lisp programmer is more than
an order of magnitude greater than that to be found within Pascal
enterprises. Lisp programs inflate libraries with functions whose
utility transcends the application that produced them. The list,
Lisp's native data structure, is largely responsible for such growth
of utility. The simple structure and natural applicability of lists
are reflected in functions that are amazingly nonidiosyncratic. In
Pascal the plethora of declarable data structures induces a
specialization within functions that inhibits and penalizes casual
cooperation. It is better to have 100 functions operate on one data
structure than to have 10 functions operate on 10 data structures. As
a result the pyramid must stand unchanged for a millennium; the
organism must evolve or perish.

To illustrate this difference, compare the treatment of material and
exercises within this book with that in any first-course text using
Pascal. Do not labor under the illusion that this is a text
digestible at MIT only, peculiar to the breed found there. It is
precisely what a serious book on programming Lisp must be, no matter
who the student is or where it is used.

Note that this is a text about programming, unlike most Lisp books,
which are used as a preparation for work in artificial intelligence.
After all, the critical programming concerns of software engineering
and artificial intelligence tend to coalesce as the systems under
investigation become larger. This explains why there is such growing
interest in Lisp outside of artificial intelligence.