sicp.pdf

(7243 KB) Pobierz
Structure and
Interpretation
of
Computer
Programs
second edition
Unofficial Texinfo Format 2.andresraba5.6
Harold Abelson and
Gerald Jay Sussman
with Julie Sussman
foreword by Alan J. Perlis
©1996 by e Massachuses Institute of Technology
Structure and Interpretation of Computer Programs,
second edition
Harold Abelson and Gerald Jay Sussman
with Julie Sussman, foreword by Alan J. Perlis
is work is licensed under a Creative Commons
Aribution-ShareAlike 4.0 International License
(
 .).
Based on a work at
mitpress.mit.edu.
e  Press
Cambridge, Massachuses
London, England
McGraw-Hill Book Company
New York, St. Louis, San Francisco,
Montreal, Toronto
Unofficial Texinfo Format
2.andresraba5.6
(February 2, 2016),
based on
2.neilvandyke4
(January 10, 2007).
Contents
Unofficial Texinfo Format
Dedication
Foreword
Preface to the Second Edition
Preface to the First Edition
Anowledgments
1
ix
xii
xiii
xix
xxi
xxv
1
6
7
10
12
15
18
22
28
Building Abstractions with Procedures
1.1 e 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 e Substitution Model for Procedure Application
1.1.6 Conditional Expressions and Predicates
. . . .
1.1.7 Example: Square Roots by Newton’s Method
. .
iii
1.2
1.3
1.1.8 Procedures as Black-Box Abstractions
Procedures and the Processes ey 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
. . . .
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
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
40
41
47
54
57
62
65
74
76
83
89
97
107
112
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 otation
. . . . . . . . . . . . . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
113
118
122
126
132
134
147
154
172
192
192
iv
2.4
2.5
2.3.2 Example: Symbolic Differentiation
. . . . .
2.3.3 Example: Representing Sets
. . . . . . . . .
2.3.4 Example: Huffman Encoding Trees
. . . . .
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
Systems with Generic Operations
. . . . . . . . . .
2.5.1 Generic Arithmetic Operations
. . . . . . .
2.5.2 Combining Data of Different Types
. . . . .
2.5.3 Example: Symbolic Algebra
. . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
197
205
218
229
232
237
242
254
255
262
274
294
296
297
305
311
320
322
327
330
337
341
342
353
360
369
386
401
3
Modularity, Objects, and State
3.1 Assignment and Local State
. . . . . . . . . . .
3.1.1 Local State Variables
. . . . . . . . . . .
3.1.2 e Benefits of Introducing Assignment
3.1.3 e Costs of Introducing Assignment
. .
3.2 e Environment Model of Evaluation
. . . . . .
3.2.1 e 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 eues
. . . . . . . . . . .
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
. . . . . . .
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin