Structure And Interpretation Of Computer Programs.pdf

1 Structure and Interpretation of Computer Programssecond edition Harold Abelson and Gerald Jay Sussman with Julie Sussman foreword by Alan J.Perlis The MIT Press Cambridge,Massachusetts London,England McGraw-Hill Book Company New York St.Louis San Francisco Montreal Toronto 2This book is one of a series of texts written by faculty of the Electrical Engineering and ComputerScience Department at the Massachusetts Institute of Technology.It was edited and produced byThe MIT Press under a joint production-distribution arrangement with the McGraw-Hill BookCompany.Ordering Information:North AmericaText orders should be addressed to the McGraw-Hill Book Company.All other orders should be addressed to The MIT Press.Outside North AmericaAll orders should be addressed to The MIT Press or its local distributor.1996 by The Massachusetts Institute of TechnologySecond edition All rights reserved.No part of this book may be reproduced in any form or by any electronic ormechanical means(including photocopying,recording,or information storage and retrieval)without permission in writing from the publisher.This book was set by the authors using the LATEX typesetting system and was printed and boundin the United States of America.Library of Congress Cataloging-in-Publication Data Abelson,Harold Structure and interpretation of computer programs/Harold Abelson and Gerald Jay Sussman,with Julie Sussman.-2nd ed.p.cm.-(Electrical engineering and computer science series)Includes bibliographical references and index.ISBN 0-262-01153-0(MIT Press hardcover)ISBN 0-262-51087-1(MIT Press paperback)ISBN 0-07-000484-6(McGraw-Hill hardcover)1.Electronic digital computers-Programming.2.LISP(Computer program language)I.Sussman,Gerald Jay.II.Sussman,Julie.III.Title.IV.Series:MIT electrical engineering and computer science series.QA76.6.A255 1996 005.133-dc20 96-17756 Fourth printing,1999 3This book is dedicated,in respect and admiration,to the spirit that lives in the computer.I think that its 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 everynow and then,and after a while we began to take their complaints seriously.We began to feel as ifwe really were responsible for the successful,error-free perfect use of these machines.I dont thinkwe are.I think were responsible for stretching them,setting them off in new directions,and keepingfun in the house.I hope the field of computer science never loses its sense of fun.Above all,I hopewe dont become missionaries.Dont feel as if youre Bible salesmen.The world has too many ofthose already.What you know about computing other people will learn.Dont feel as if the key tosuccessful computing is only in your hands.Whats 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 itmore.Alan J.Perlis(April 1,1922-February 7,1990)4 Contents Foreword Preface to the Second Edition Preface to the First Edition Acknowledgments 1 Building Abstractions with Procedures 1.1 The Elements of Programming 1.1.1 Expressions 1.1.2 Naming and the Environment 1.1.3 Evaluating Combinations 1.1.4 Compound Procedures 1.1.5 The Substitution Model for Procedure Application 1.1.6 Conditional Expressions and Predicates 1.1.7 Example:Square Roots by Newtons Method 1.1.8 Procedures as Black-Box Abstractions 1.2 Procedures and the Processes They Generate 1.2.1 Linear Recursion and Iteration 1.2.2 Tree Recursion 1.2.3 Orders of Growth 1.2.4 Exponentiation 1.2.5 Greatest Common Divisors 1.2.6 Example:Testing for Primality 1.3 Formulating Abstractions with Higher-Order Procedures 1.3.1 Procedures as Arguments 1.3.2 Constructing Procedures Using Lambda 1.3.3 Procedures as General Methods 1.3.4 Procedures as Returned Values 2 Building Abstractions with Data 2.1 Introduction to Data Abstraction 2.1.1 Example:Arithmetic Operations for Rational Numbers 2.1.2 Abstraction Barriers 2.1.3 What Is Meant by Data?2.1.4 Extended Exercise:Interval Arithmetic 2.2 Hierarchical Data and the Closure Property 2.2.1 Representing Sequences 2.2.2 Hierarchical Structures 2.2.3 Sequences as Conventional Interfaces 2.2.4 Example:A Picture Language 2.3 Symbolic Data 2.3.1 Quotation 2.3.2 Example:Symbolic Differentiation 2.3.3 Example:Representing Sets 5 2.3.4 Example:Huffman Encoding Trees 2.4 Multiple Representations for Abstract Data 2.4.1 Representations for Complex Numbers 2.4.2 Tagged data 2.4.3 Data-Directed Programming and Additivity 2.5 Systems with Generic Operations 2.5.1 Generic Arithmetic Operations 2.5.2 Combining Data of Different Types 2.5.3 Example:Symbolic Algebra 3 Modularity,Objects,and State 3.1 Assignment and Local State 3.1.1 Local State Variables 3.1.2 The Benefits of Introducing Assignment 3.1.3 The Costs of Introducing Assignment 3.2 The Environment Model of Evaluation 3.2.1 The Rules for Evaluation 3.2.2 Applying Simple Procedures 3.2.3 Frames as the Repository of Local State 3.2.4 Internal Definitions 3.3 Modeling with Mutable Data 3.3.1 Mutable List Structure 3.3.2 Representing Queues 3.3.3 Representing Tables 3.3.4 A Simulator for Digital Circuits 3.3.5 Propagation of Constraints 3.4 Concurrency:Time Is of the Essence 3.4.1 The Nature of Time in Concurrent Systems 3.4.2 Mechanisms for Controlling Concurrency 3.5 Streams 3.5.1 Streams Are Delayed Lists 3.5.2 Infinite Streams 3.5.3 Exploiting the Stream Paradigm 3.5.4 Streams and Delayed Evaluation 3.5.5 Modularity of Functional Programs and Modularity of Objects 4 Metalinguistic Abstraction 4.1 The Metacircular Evaluator 4.1.1 The Core of the Evaluator 4.1.2 Representing Expressions 4.1.3 Evaluator Data Structures 4.1.4 Running the Evaluator as a Program 4.1.5 Data as Programs 4.1.6 Internal Definitions 4.1.7 Separating Syntactic Analysis from Execution 4.2 Variations on a Scheme-Lazy Evaluation 4.2.1 Normal Order and Applicative Order 4.2.2 An Interpreter with Lazy Evaluation 4.2.3 Streams as Lazy Lists 4.3 Variations on a Scheme-Nondeterministic Computing 4.3.1 Amb and Search 6 4.3.2 Examples of Nondeterministic Programs 4.3.3 Implementing the Amb Evaluator 4.4 Logic Programming 4.4.1 Deductive Information Retrieval 4.4.2 How the Query System Works 4.4.3 Is Logic Programming Mathematical Logic?4.4.4 Implementing the Query System 5 Computing with Register Machines 5.1 Designing Register Machines 5.1.1 A Language for Describing Register Machines 5.1.2 Abstraction in Machine Design 5.1.3 Subroutines 5.1.4 Using a Stack to Implement Recursion 5.1.5 Instruction Summary 5.2 A Register-Machine Simulator 5.2.1 The Machine Model 5.2.2 The Assembler 5.2.3 Generating Execution Procedures for Instructions 5.2.4 Monitoring Machine Performance 5.3 Storage Allocation and Garbage Collection 5.3.1 Memory as Vectors 5.3.2 Maintaining the Illusion of Infinite Memory 5.4 The Explicit-Control Evaluator 5.4.1 The Core of the Explicit-Control Evaluator 5.4.2 Sequence Evaluation and Tail Recursion 5.4.3 Conditionals,Assignments,and Definitions 5.4.4 Running the Evaluator 5.5 Compilation 5.5.1 Structure of the Compiler 5.5.2 Compiling Expressions 5.5.3 Compiling Combinations 5.5.4 Combining Instruction Sequences 5.5.5 An Example of Compiled Code 5.5.6 Lexical Addressing 5.5.7 Interfacing Compiled Code to the Evaluator References List of Exercises Index7 ForewordEducators,generals,dieticians,psychologists,and parents program.Armies,students,and somesocieties are programmed.An assault on large problems employs a succession of programs,most ofwhich spring into existence en route.These programs are rife with issues that appear to be particularto the problem at hand.To appreciate programming as an intellectual activity in its own right youmust turn to computer programming;you must read and write computer programs-many of them.It doesnt matter much what the programs are about or what applications they serve.What doesmatter is how well they perform and how smoothly they fit with other programs in the creation ofstill greater programs.The programmer must seek both perfection of part and adequacy ofcollection.In this book the use of program is focused on the creation,execution,and study ofprograms written in a dialect of Lisp for execution on a digital computer.Using Lisp we restrict orlimit 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:thehuman mind,collections of computer programs,and the computer.Every computer program is amodel,hatched in the mind,of a real or mental process.These processes,arising from humanexperience and thought,are huge in number,intricate in detail,and at any time only partiallyunderstood.They are modeled to our permanent satisfaction rarely by our computer programs.Thuseven though our programs are carefully handcrafted discrete collections of symbols,mosaics ofinterlocking functions,they continually evolve:we change them as our perception of the modeldeepens,enlarges,generalizes until the model ultimately attains a metastable place within stillanother model with which we struggle.The source of the exhilaration associated with computerprogramming is the continual unfolding within the mind and on the computer of mechanismsexpressed 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 wewish to say must be said accurately in every detail.As in every other symbolic activity,we becomeconvinced of program truth through argument.Lisp itself can be assigned a semantics(anothermodel,by the way),and if a programs function can be specified,say,in the predicate calculus,theproof methods of logic can be used to make an acceptable correctness argument.Unfortunately,asprograms get large and complicated,as they almost always do,the adequacy,consistency,andcorrectness of the specifications themselves become open to doubt,so that complete formalarguments of correctness seldom accompany large programs.Since large programs grow from smallones,it is crucial that we develop an arsenal of standard program structures of whose correctnesswe have become sure-we call them idioms-and learn to combine them into larger structuresusing 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 calledprogramming.More than anything else,the uncovering and mastery of powerful organizationaltechniques accelerates our ability to create large,significant programs.Conversely,since writinglarge programs is very taxing,we are stimulated to invent new methods of reducing the mass offunction and detail to be fitted into large programs.Unlike programs,computers must obey the laws of physics.If they wish to perform rapidly-a fewnanoseconds per state change-they must transmit electrons only small distances(at most 1 1/2feet).The heat generated by the huge number of devices so concentrated in space has to beremoved.An exquisite engineering art has been developed balancing between multiplicity of8function and density of devices.In any event,hardware always operates at a level more primitivethan that at which we care to program.The processes that transform our Lisp programs tomachine programs are themselves abstract models which we program.Their study and creationgive a great deal of insight into the organizational programs associated with programming arbitrarymodels.Of course the computer itself can be so modeled.Think of it:the behavior of the smallestphysical switching element is modeled by quantum mechanics described by differential equationswhose detailed behavior is captured by numerical approximations represented in computerprograms 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,its all in the head,this logical separation induces an acceleration of symbolic trafficbetween these foci whose richness,vitality,and potential is exceeded in human experience only bythe evolution of life itself.At best,relationships between the foci are metastable.The computers arenever large enough or fast enough.Each breakthrough in hardware technology leads to moremassive programming enterprises,new organizational principles,and an enrichment of abstractmodels.Every reader should ask himself periodically Toward what end,toward what end?-butdo not ask it too often lest you pass up the fun of programming for the constipation of bittersweetphilosophy.Among the programs we write,some(but never enough)perform a precise mathematical functionsuch as sorting or finding the maximum of a sequence of numbers,determining primality,or findingthe square root.We call such programs algorithms,and a great deal is known of their optimalbehavior,particularly with respect to the two important parameters of execution time and datastorage requirements.A programmer should acquire good algorithms and idioms.Even thoughsome 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 activeprogramming languages only Fortran has had a longer life.Both languages have supported theprogramming needs of important areas of application,Fortran for scientific and engineeringcomputation and Lisp for artificial intelligence.These two areas continue to be important,and theirprogrammers are so devoted to these two languages that Lisp and Fortran may well continue inactive use for at least another quarter-century.Lisp changes.The Scheme dialect used in this text has evolved from the original Lisp and differsfrom the latter in several important ways,including static scoping for variable binding andpermitting functions to yield functions as values.In its semantic structure Scheme is as closely akinto Algol 60 as to early Lisps.Algol 60,never to be an active language again,lives on in the genesof Scheme and Pascal.It would be difficult to find two languages that are the communicating coinof two more different cultures than those gathered around these two languages.Pascal is forbuilding pyramids-imposing,breathtaking,static structures built by armies pushing heavy blocksinto place.Lisp is for building organisms-imposing,breathtaking,dynamic structures built bysquads fitting fluctuating myriads of simpler organisms into place.The organizing principles usedare the same in both cases,except for one extraordinarily important difference:The discretionaryexportable functionality entrusted to the individual Lisp programmer is more than an order ofmagnitude greater than that to be found within Pascal enterprises.Lisp programs inflate librar