Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman

(2 отзыва клиентов)


Нет в наличии


Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman купить Украина книга

Издательство — MIT Press

Язык — Английский

Обложка — Твердая

Год издания — 1996

Количество страниц — 657

ISBN — 978-0262510875

Бумага — белая, офсетная

О книге Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman

Structure and Interpretation of Computer Programs

has had a dramatic impact on computer science curricula over the past decade. This long-awaited revision contains changes throughout the text. There are new implementations of most of the major programming systems in the book, including the interpreters and compilers, and the authors have incorporated many small changes that reflect their experience teaching the course at MIT since the first edition was published. A new theme has been introduced that emphasizes the central role played by different approaches to dealing with time in computational models: objects with state, concurrent programming, functional programming and lazy evaluation, and nondeterministic programming. There are new example sections on higher-order procedures in graphics and on applications of stream processing in numerical programming, and many new exercises. In addition, all the programs have been reworked to run in any Scheme implementation that adheres to the IEEE standard.


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 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.

As one would expect from its goals, artificial intelligence research generates many significant programming problems. In other programming cultures this spate of problems spawns new languages. Indeed, in any very large programming task a useful organizing principle is to control and isolate traffic within the task modules via the invention of language. These languages tend to become less primitive as one approaches the boundaries of the system where we humans interact most often. As a result, such systems contain complex language-processing functions replicated many times. Lisp has such a simple syntax and semantics that parsing can be treated as an elementary task. Thus parsing technology plays almost no role in Lisp programs, and the construction of language processors is rarely an impediment to the rate of growth and change of large Lisp systems. Finally, it is this very simplicity of syntax and semantics that is responsible for the burden and freedom borne by all Lisp programmers. No Lisp program of any size beyond a few lines can be written without being saturated with discretionary functions. Invent and fit; have fits and reinvent! We toast the Lisp programmer who pens his thoughts within nests of parentheses.

Alan J. Perlis

New Haven, Connecticut

About the Author

Hal Abelson

is Class of 1922 Professor of Computer Science and Engineering at Massachusetts Institute of Technology and a fellow of the IEEE. He is a founding director of Public Knowledge, and the Free Software Foundation. Additionally, he serves as co-chair for the MIT Council on Educational Technology.

Gerald Jay Sussman

is the Matsushita Professor of Electrical Engineering in the Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. He is also the coauthor of Structure and Interpretation of Computer Programs (MIT Press, second edition, 1996).



Preface to the Second Edition

Preface to the First Edition


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 Newton’s 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

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

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


List of Exercises


Также вы можете оставить вопрос или отзыв о книге: Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman

2 отзыва на Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman

  1. Игорь

    Книга огромна и прекрасна. Качество печати отличное. Надеюсь, что когда-нибудь смогу дочитать.

    Продавцы молодцы, быстро связались с нами, быстро отправили, пришла хорошо упакованная. Будем заказывать ещё!

  2. Максим Веровенко (проверенный владелец)

    Как всегда 5 из 5.

Добавить отзыв

Ваш e-mail не будет опубликован. Обязательные поля помечены *