Harold Abelson - Structure and Interpretation of Computer Programs - 2nd Edition (MIT Electrical Engineering and Computer Science)

McGraw-Hill Book Company
New York St. Louis San Francisco Montreal Toronto

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

I think that it's extraordinarily important that we in computerscience keep fun in computing. When it started out, it was an awfullot of fun. Of course, the paying customers got shafted every now andthen, 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. Ithink we're responsible for stretching them, setting them off in newdirections, and keeping fun in the house. I hope the field ofcomputer science never loses its sense of fun. Above all, I hope wedon't become missionaries. Don't feel as if you're Bible salesmen.The world has too many of those already. What you know aboutcomputing other people will learn. Don't feel as if the key tosuccessful computing is only in your hands. What's in your hands, Ithink and hope, is intelligence: the ability to see the machine asmore than when you were first led up to it, that you can make itmore.

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

Educators, generals, dieticians, psychologists, and parents program.Armies, students, and some societies are programmed. An assault onlarge problems employs a succession of programs, most of which springinto existence en route. These programs are rife with issues thatappear to be particular to the problem at hand. To appreciateprogramming as an intellectual activity in its own right you must turnto computer programming; you must read and write computerprograms many of them. It doesn't matter much what the programs areabout or what applications they serve. What does matter is how wellthey perform and how smoothly they fit with other programs in thecreation of still greater programs. The programmer must seek bothperfection of part and adequacy of collection. In this book the useof program is focused on the creation, execution, and study ofprograms written in a dialect of Lisp for execution on a digitalcomputer. 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 withthree foci of phenomena: the human mind, collections of computerprograms, 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. Theyare modeled to our permanent satisfaction rarely by our computerprograms. Thus even though our programs are carefully handcrafteddiscrete collections of symbols, mosaics of interlocking functions,they continually evolve: we change them as our perception of the modeldeepens, enlarges, generalizes until the model ultimately attains ametastable place within still another model with which we struggle.The source of the exhilaration associated with computer programming isthe continual unfolding within the mind and on the computer ofmechanisms expressed as programs and the explosion of perception theygenerate. If art interprets our dreams, the computer executes them inthe guise of programs!

For all its power, the computer is a harsh taskmaster. Its programsmust be correct, and what we wish to say must be said accurately inevery detail. As in every other symbolic activity, we becomeconvinced of program truth through argument. Lisp itself can beassigned a semantics (another model, by the way), and if a program'sfunction can be specified, say, in the predicate calculus, the proofmethods of logic can be used to make an acceptable correctnessargument. Unfortunately, as programs get large and complicated, asthey almost always do, the adequacy, consistency, and correctness ofthe specifications themselves become open to doubt, so that completeformal arguments of correctness seldom accompany large programs.Since large programs grow from small ones, it is crucial that wedevelop an arsenal of standard program structures of whose correctnesswe have become sure we call them idioms and learn to combine theminto larger structures using organizational techniques of provenvalue. These techniques are treated at length in this book, andunderstanding them is essential to participation in the Prometheanenterprise called programming. More than anything else, theuncovering and mastery of powerful organizational techniquesaccelerates our ability to create large, significant programs.Conversely, since writing large programs is very taxing, we arestimulated to invent new methods of reducing the mass of function anddetail to be fitted into large programs.

Unlike programs, computers must obey the laws of physics. If theywish to perform rapidly a few nanoseconds per state change theymust transmit electrons only small distances (at most 1 1/2feet). The heat generated by the huge number of devices soconcentrated in space has to be removed. An exquisite engineering arthas been developed balancing between multiplicity of function anddensity of devices. In any event, hardware always operates at a levelmore primitive than that at which we care to program. The processesthat transform our Lisp programs to machine programs arethemselves abstract models which we program. Their study and creationgive a great deal of insight into the organizational programsassociated with programming arbitrary models. Of course the computeritself can be so modeled. Think of it: the behavior of the smallestphysical switching element is modeled by quantum mechanics describedby differential equations whose detailed behavior is captured bynumerical approximations represented in computer programs executing oncomputers composed of ...!