內(nèi)容講義課件教程structure and interpretation of computer programs2nd edition

1、1Structure and Interpretation of Computer Programssecond editionHarold Abelson and Gerald Jay Sussman with Julie Sussmanforeword by Alan J. PerlisThe MIT Press Cambridge, MassachusettsLondon, EnglandMcGraw-Hill Book CompanyNew YorkSt. LouisSan FranciscoMontrealToronto2This book is one of a series of

2、 texts written by faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology. It was edited and produced by The MIT Press under a joint production-distribution arrangement with the McGraw-Hill Book Company.Ordering Information:North AmericaText

3、 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 editions. No part of this bo

4、ok 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 bound in the Uni

5、ted States of America.Library of Congress Cataloging-in-Publication DataAbelson, HaroldStructure 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 referen

6、ces 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 electri

7、cal engineering and computer science series.QA76.6.A255 005.13'3 - dc20199696-17756Fourth printing, 19993This 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.

8、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

9、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. Th

10、e 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 u

11、p to it, that you can make it more.''Alan J. Perlis (April 1, 1922-February 7, 1990)4ContentsForewordPreface to the Second EditionPreface to the First EditionAcknowledgments1 Building Abstractions with Procedures1.1 The Elements of Programming 1.1.1 Expressions1.1.2 Naming and the Environmen

12、t 1.1.3 Evaluating Combinations1.1.4 Compound Procedures1.1.5 The Substitution M for Procedure Application1.1.6 Conditional Expressions and Predicates1.1.7 Example: Square Roots by Newton's Method 1.1.8 Procedures as Black-Box Abstractions1.2 Procedures and the Processes They Generate 1.2.1 Line

13、ar Recursion and Iteration1.2.2 Tree Recursion 1.2.3 Orders of Growth 1.2.4 Exponentiation1.2.5 Greatest Common Divisors 1.2.6 Example: Testing for Primality1.3 Formulating Abstractions with Higher-Order Procedures 1.3.1 Procedures as Arguments1.3.2 Constructing Procedures Using Lambda 1.3.3 Procedu

14、res as General Methods1.3.4 Procedures as Returned Values2 Building Abstractions with Data2.1 Introduction to Data Abstraction2.1.1 Example: Arithmetic Operations for Rational Numbers 2.1.2 Abstraction Barriers2.1.3 What Is Meant by Data?2.1.4 Extended Exercise: Interval Arithmetic 2.2 Hierarchical

15、Data and the Closure Property2.2.1 Representing Sequences2.2.2 Hierarchical Structures2.2.3 Sequences as Conventional Interfaces 2.2.4 Example: A Picture Language2.3 Symbolic Data2.3.1 Quotation2.3.2 Example: Symbolic Differentiation 2.3.3 Example: Representing Sets52.3.4 Example: Huffman Encoding T

16、rees 2.4 Multiple Representations for Abstract Data2.4.1 Representations for Complex Numbers 2.4.2 Tagged data2.4.3 Data-Directed Programming and Additivity 2.5 Systems with Generic Operations2.5.1 Generic Arithmetic Operations 2.5.2 Combining Data of Different Types 2.5.3 Example: Symbolic Algebra3

17、 Modularity, Objects, and State3.1 Assignment and Local State 3.1.1 Local State Variables3.1.2 The Benefits of Introducing Assignment 3.1.3 The Costs of Introducing Assignment3.2 The Environment M of Evaluation3.2.1 The Rules for Evaluation3.2.2 Applying Simple Procedures3.2.3 Frames as the Reposito

18、ry of Local State 3.2.4 Internal Definitions3.3 Ming with Mutable Data3.3.1 Mutable List Structure 3.3.2 Representing Queues3.3.3 Representing Tables3.3.4 A Simulator for Digital Circuits 3.3.5 Propagation of Constraints3.4 Concurrency: Time Is of the Essence3.4.1 The Nature of Time in Concurrent Sy

19、stems 3.4.2 Mechanisms for Controlling Concurrency3.5 Streams3.5.1 Streams Are Delayed Lists 3.5.2 Infinite Streams3.5.3 Exploiting the Stream Paradigm 3.5.4 Streams and Delayed Evaluation3.5.5 Modularity of Functional Programs and Modularity of Objects4 Minguistic Abstraction4.1 The Metacircular Ev

20、aluator 4.1.1 The Core of the Evaluator 4.1.2 Representing Expressions 4.1.3 Evaluator Data Structures4.1.4 Running the Evaluator as a Program 4.1.5 Data as Programs4.1.6 Internal Definitions4.1.7 Separating Syntactic Analysis from Execution 4.2 Variations on a Scheme - Lazy Evaluation4.2.1 Normal O

21、rder and Applicative Order 4.2.2 An Interpreter with Lazy Evaluation 4.2.3 Streams as Lazy Lists4.3 Variations on a Scheme - Nondeterministic Computing 4.3.1 Amb and Search64.3.2 Examples of Nondeterministic Programs 4.3.3 Implementing the Amb Evaluator4.4 Logic Programming4.4.1 Deductive Informatio

22、n Retrieval 4.4.2 How the Query System Works4.4.3 Is Logic Programming Mathematical Logic? 4.4.4 Implementing the Query System5 Computing with Register Machines5.1 Designing Register Machines5.1.1 A Language for Describing Register Machines 5.1.2 Abstraction in Machine Design5.1.3 Subroutines5.1.4 U

23、sing a Stack to Implement Recursion 5.1.5 Instruction Summary5.2 A Register-Machine Simulator 5.2.1 The Machine M5.2.2 The Assembler5.2.3 Generating Execution Procedures for Instructions 5.2.4 Monitoring Machine Performance5.3 Storage Allocation and Garbage Collection 5.3.1 Memory as Vectors5.3.2 Ma

24、intaining the Illusion of Infinite Memory 5.4 The Explicit-Control Evaluator5.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 Evaluator5.5 Compilation5.5.1 Structure of the Compiler 5.5.2 C

25、ompiling Expressions5.5.3 Compiling Combinations5.5.4 Combining Instruction Sequences 5.5.5 An Example of Compiled Code 5.5.6 Lexical Addressing5.5.7 Interfacing Compiled Code to the EvaluatorReferencesList of ExercisesIndex7ForewordEducators, generals, dieticians, psychologists, and parents program

26、. 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 ac

27、tivity 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

28、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

29、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 am, hatched in the mi

30、nd, 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 med to our permanent satisfaction rarely by our computer programs. Thuseven though our programs are carefully handcr

31、afted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the mdeepens, enlarges, generalizes until the multimately attains a metastable place within stillanother mwith which we struggle. The source of the exhilaration asso

32、ciated 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 hars

33、h 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 (anotherm, by the way), and if a program's function can

34、 be specified, say, in the predicate calculus, theproof 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

35、doubt, so that complete formalarguments 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 l

36、arger 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

37、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 phy

38、sics. If they wish to perform rapidly - a few nanoseconds per state change - they must transmit electrons only small distances (at most 1 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

39、between multiplicity of8function 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 tomachine'' programs are themselves abstract ms which we program. Their study and cr

40、eationgive a great deal of insight into the organizational programs associated with programming arbitraryms. Of course the computer itself can be so med. Think of it: the behavior of the smallestphysical switching element is med by quantum mechanics described by differential equationswhose detailed

41、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 accel

42、eration 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 tech

43、nology leads to more massive programming enterprises, new organizational principles, and an enrichment of abstractms. 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

44、bittersweet philosophy.Among the programs we write, some (but never enough) perform a precise mathematical functionsuch as sorting or finding theum of a sequence of numbers, determining primality, or findingthe square root. We call such programs algorithms, and a great deal is known of their optimal

45、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

46、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

47、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

48、 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 akinto Algol 60 as to early Lisps. Algol 60, never to be

49、 an active language again, lives on in tesof 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

50、 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 dif

51、ference: 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

52、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 func

53、tions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to9have 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 differe

54、nce, 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 ma

55、tter 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 th

56、e systems under investigation become larger. This explains why there is such growing interest in Lisp outside of artificial intelligence.As one would expect from its goals, artificial intelligence research generates many significant programming problems. In other programming cultures this spate of problems spawns newlanguages., in any very large programming ta