Structure and Interpretation of Computer Programs

Underlying our approach to this subject is our conviction that ‘‘computer science’’ is not a science and

that its significance has little to do with computers. The computer revolution is a revolution in the way

we think and in the way we express what we think. The essence of this change is the emergence of

what might best be called procedural epistemology -- the study of the structure of knowledge from an

imperative point of view, as opposed to the more declarative point of view taken by classical

mathematical subjects. Mathematics provides a framework for dealing precisely with notions of ‘‘what

is.’’ Computation provides a framework for dealing precisely with notions of ‘‘how to.’’

In teaching our material we use a dialect of the programming language Lisp. We never formally teach

the language, because we don’t have to. We just use it, and students pick it up in a few days. This is

one great advantage of Lisp-like languages: They have very few ways of forming compound

expressions, and almost no syntactic structure. All of the formal properties can be covered in an hour,

like the rules of chess. After a short time we forget about syntactic details of the language (because

there are none) and get on with the real issues -- figuring out what we want to compute, how we will

decompose problems into manageable parts, and how we will work on the parts. Another advantage of

Lisp is that it supports (but does not enforce) more of the large-scale strategies for modular

decomposition of programs than any other language we know. We can make procedural and data

abstractions, we can use higher-order functions to capture common patterns of usage, we can model

local state using assignment and data mutation, we can link parts of a program with streams and

delayed evaluation, and we can easily implement embedded languages. All of this is embedded in an

interactive environment with excellent support for incremental program design, construction, testing,

and debugging. We thank all the generations of Lisp wizards, starting with John McCarthy, who have

fashioned a fine tool of unprecedented power and elegance.

Scheme, the dialect of Lisp that we use, is an attempt to bring together the power and elegance of Lisp

and Algol. From Lisp we take the metalinguistic power that derives from the simple syntax, the

uniform representation of programs as data objects, and the garbage-collected heap-allocated data.

From Algol we take lexical scoping and block structure, which are gifts from the pioneers of

programming-language design who were on the Algol committee. We wish to cite John Reynolds and

Peter Landin for their insights into the relationship of Church’s lambda calculus to the structure of

programming languages. We also recognize our debt to the mathematicians who scouted out this

territory decades before computers appeared on the scene. These pioneers include Alonzo Church,

Barkley Rosser, Stephen Kleene, and Haskell Curry.

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

 

Acknowledgments

We would like to thank the many people who have helped us develop this book and this curriculum.

Our subject is a clear intellectual descendant of ‘‘6.231,’’ a wonderful subject on programming

linguistics and the lambda calculus taught at MIT in the late 1960s by Jack Wozencraft and Arthur

Evans, Jr.

We owe a great debt to Robert Fano, who reorganized MIT’s introductory curriculum in electrical

engineering and computer science to emphasize the principles of engineering design. He led us in

starting out on this enterprise and wrote the first set of subject notes from which this book evolved.

Much of the style and aesthetics of programming that we try to teach were developed in conjunction

with Guy Lewis Steele Jr., who collaborated with Gerald Jay Sussman in the initial development of the

Scheme language. In addition, David Turner, Peter Henderson, Dan Friedman, David Wise, and Will

Clinger have taught us many of the techniques of the functional programming community that appear

in this book.

Joel Moses taught us about structuring large systems. His experience with the Macsyma system for

symbolic computation provided the insight that one should avoid complexities of control and

concentrate on organizing the data to reflect the real structure of the world being modeled.

Marvin Minsky and Seymour Papert formed many of our attitudes about programming and its place in

our intellectual lives. To them we owe the understanding that computation provides a means of

expression for exploring ideas that would otherwise be too complex to deal with precisely. They

emphasize that a student’s ability to write and modify programs provides a powerful medium in which

exploring becomes a natural activity.

We also strongly agree with Alan Perlis that programming is lots of fun and we had better be careful to

support the joy of programming. Part of this joy derives from observing great masters at work. We are

fortunate to have been apprentice programmers at the feet of Bill Gosper and Richard Greenblatt.

It is difficult to identify all the people who have contributed to the development of our curriculum. We

thank all the lecturers, recitation instructors, and tutors who have worked with us over the past fifteen

years and put in many extra hours on our subject, especially Bill Siebert, Albert Meyer, Joe Stoy,

Randy Davis, Louis Braida, Eric Grimson, Rod Brooks, Lynn Stein, and Peter Szolovits. We would

like to specially acknowledge the outstanding teaching contributions of Franklyn Turbak, now at

Wellesley; his work in undergraduate instruction set a standard that we can all aspire to. We are

grateful to Jerry Saltzer and Jim Miller for helping us grapple with the mysteries of concurrency, and

to Peter Szolovits and David McAllester for their contributions to the exposition of nondeterministic

evaluation in chapter 4.

Many people have put in significant effort presenting this material at other universities. Some of the

people we have worked closely with are Jacob Katzenelson at the Technion, Hardy Mayer at the

University of California at Irvine, Joe Stoy at Oxford, Elisha Sacks at Purdue, and Jan Komorowski at

the Norwegian University of Science and Technology. We are exceptionally proud of our colleagues

---