Structure and Interpretation of Computer Programs
اسم المؤلف
Harold Abelson and Gerald Jay Sussman with Julie Sussman foreword by Alan J. Perlis
التاريخ
المشاهدات
222
التقييم
(لا توجد تقييمات)
Loading...
التحميل

Structure and Interpretation of Computer Programs
Harold Abelson and Gerald Jay Sussman
with Julie Sussman foreword by Alan J. Perlis
Contents
Unofficial Texinfo Format ix
Dedication xii
Foreword xiii
Preface to the Second Edition xix
Preface to the First Edition xxi
Anowledgments xxv
1 Building Abstractions with Procedures 1
1.1 e Elements of Programming 6
1.1.1 Expressions 7
1.1.2 Naming and the Environment 10
1.1.3 Evaluating Combinations 12
1.1.4 Compound Procedures 15
1.1.5 e Substitution Model for Procedure Application 18
1.1.6 Conditional Expressions and Predicates 22
1.1.7 Example: Square Roots by Newton’s Method 28
iii1.1.8 Procedures as Black-Box Abstractions . 33
1.2 Procedures and the Processes ey Generate 40
1.2.1 Linear Recursion and Iteration . 41
1.2.2 Tree Recursion 47
1.2.3 Orders of Growth . 54
1.2.4 Exponentiation 57
1.2.5 Greatest Common Divisors . 62
1.2.6 Example: Testing for Primality . 65
1.3 Formulating Abstractions
with Higher-Order Procedures 74
1.3.1 Procedures as Arguments 76
1.3.2 Constructing Procedures Using lambda . 83
1.3.3 Procedures as General Methods . 89
1.3.4 Procedures as Returned Values . 97
2 Building Abstractions with Data 107
2.1 Introduction to Data Abstraction . 112
2.1.1 Example: Arithmetic Operations
for Rational Numbers . 113
2.1.2 Abstraction Barriers . 118
2.1.3 What Is Meant by Data? . 122
2.1.4 Extended Exercise: Interval Arithmetic . 126
2.2 Hierarchical Data and the Closure Property . 132
2.2.1 Representing Sequences . 134
2.2.2 Hierarchical Structures 147
2.2.3 Sequences as Conventional Interfaces . 154
2.2.4 Example: A Picture Language 172
2.3 Symbolic Data . 192
2.3.1 otation . 192
iv2.3.2 Example: Symbolic Differentiation . 197
2.3.3 Example: Representing Sets . 205
2.3.4 Example: Huffman Encoding Trees . 218
2.4 Multiple Representations for Abstract Data . 229
2.4.1 Representations for Complex Numbers . 232
2.4.2 Tagged data 237
2.4.3 Data-Directed Programming and Additivity 242
2.5 Systems with Generic Operations 254
2.5.1 Generic Arithmetic Operations . 255
2.5.2 Combining Data of Different Types . 262
2.5.3 Example: Symbolic Algebra . 274
3 Modularity, Objects, and State 294
3.1 Assignment and Local State . 296
3.1.1 Local State Variables . 297
3.1.2 e Benefits of Introducing Assignment 305
3.1.3 e Costs of Introducing Assignment 311
3.2 e Environment Model of Evaluation 320
3.2.1 e Rules for Evaluation . 322
3.2.2 Applying Simple Procedures . 327
3.2.3 Frames as the Repository of Local State 330
3.2.4 Internal Definitions 337
3.3 Modeling with Mutable Data . 341
3.3.1 Mutable List Structure 342
3.3.2 Representing eues . 353
3.3.3 Representing Tables . 360
3.3.4 A Simulator for Digital Circuits . 369
3.3.5 Propagation of Constraints . 386
3.4 Concurrency: Time Is of the Essence . 401
v3.4.1 e Nature of Time in Concurrent Systems 403
3.4.2 Mechanisms for Controlling Concurrency . 410
3.5 Streams . 428
3.5.1 Streams Are Delayed Lists 430
3.5.2 Infinite Streams 441
3.5.3 Exploiting the Stream Paradigm . 453
3.5.4 Streams and Delayed Evaluation 470
3.5.5 Modularity of Functional Programs
and Modularity of Objects 479
4 Metalinguistic Abstraction 487
4.1 e Metacircular Evaluator 492
4.1.1 e Core of the Evaluator 495
4.1.2 Representing Expressions 501
4.1.3 Evaluator Data Structures 512
4.1.4 Running the Evaluator as a Program 518
4.1.5 Data as Programs . 522
4.1.6 Internal Definitions 526
4.1.7 Separating Syntactic Analysis from Execution . 534
4.2 Variations on a Scheme — Lazy Evaluation . 541
4.2.1 Normal Order and Applicative Order 542
4.2.2 An Interpreter with Lazy Evaluation 544
4.2.3 Streams as Lazy Lists . 555
4.3 Variations on a Scheme — Nondeterministic Computing 559
4.3.1 Amb and Search . 561
4.3.2 Examples of Nondeterministic Programs 567
4.3.3 Implementing the amb Evaluator 578
4.4 Logic Programming 594
4.4.1 Deductive Information Retrieval 599
vi4.4.2 How the ery System Works . 615
4.4.3 Is Logic Programming Mathematical Logic? 627
4.4.4 Implementing the ery System 635
4.4.4.1 e Driver Loop and Instantiation 636
4.4.4.2 e Evaluator . 638
4.4.4.3 Finding Assertions
by Paern Matching . 642
4.4.4.4 Rules and Unification . 645
4.4.4.5 Maintaining the Data Base 651
4.4.4.6 Stream Operations 654
4.4.4.7 ery Syntax Procedures . 656
4.4.4.8 Frames and Bindings . 659
5 Computing with Register Maines 666
5.1 Designing Register Machines . 668
5.1.1 A Language for Describing Register Machines . 672
5.1.2 Abstraction in Machine Design . 678
5.1.3 Subroutines 681
5.1.4 Using a Stack to Implement Recursion . 686
5.1.5 Instruction Summary . 695
5.2 A Register-Machine Simulator 696
5.2.1 e Machine Model 698
5.2.2 e Assembler 704
5.2.3 Generating Execution Procedures
for Instructions 708
5.2.4 Monitoring Machine Performance . 718
5.3 Storage Allocation and Garbage Collection . 723
5.3.1 Memory as Vectors 724
5.3.2 Maintaining the Illusion of Infinite Memory 731
vii5.4 e Explicit-Control Evaluator 741
5.4.1 e Core of the Explicit-Control Evaluator . 743
5.4.2 Sequence Evaluation and Tail Recursion 751
5.4.3 Conditionals, Assignments, and Definitions 756
5.4.4 Running the Evaluator 759
5.5 Compilation 767
5.5.1 Structure of the Compiler 772
5.5.2 Compiling Expressions 779
5.5.3 Compiling Combinations 788
5.5.4 Combining Instruction Sequences 797
5.5.5 An Example of Compiled Code . 802
5.5.6 Lexical Addressing 817
5.5.7 Interfacing Compiled Code to the Evaluator 823
References 834
List of Exercises 844
List of Figures 846
Index 848
Colophon 855
Index
Any inaccuracies in this index may be explained by the fact
that it has been prepared with the help of a computer.
—Donald E. Knuth, Fundamental Algorithms
(Volume 1 of e Art of Computer Programming)
Symbols
k-term finite continued fraction . 95
n-fold smoothed function 104
A
abstract models . 123
abstract syntax 495
abstraction barriers . 111, 119
accumulator 156, 303
acquired 421
action 677
additive 243
additively 112, 230
address . 724
address arithmetic . 724
agenda . 379
algebraic specification . 123
aliasing .316
and-gate 370
applicative-order 542
applicative-order evaluation . 21
arbiter 424
arguments 8
assembler .698
assertions .600
assignment operator . 297
atomically 423
automatic storage allocation 723
average damping . 94
B
B-trees . 213
backbone . 361
backquote 779
backtracks 564
balanced 151
848barrier synchronization 427
base address 725
Bertrand’s hypothesis . 447
bignum . 726
bindings 321
binds 36
binomial coefficients 54
block structure . 39
bound variable . 36
box-and-pointer notation 132
breakpoint 722
broken heart 735
bugs 2
C
cache-coherence 406
call-by-name . 439, 545
call-by-name thunks . 439
call-by-need 439, 545
call-by-need thunks . 439
capturing 37
Carmichael numbers 69
case analysis . 22
cell . 422
chronological backtracking .564
Church numerals 126
Church-Turing thesis 524
clauses 23
closed world assumption . 632
closure . 111
closure property 133
code generator 773
coerce 270
coercion 263
combinations . 8
comments 168
compacting . 734
compilation . 768
compile-time environment . 819
composition 103
compound data . 108
compound data object . 109
compound procedure . 16
computability . 523
computational process . 1
concurrently 402
congruent modulo 67
connectors 387
consequent expression 23
constraint networks . 387
constructors 113
continuation procedures . 579
continued fraction 94
control structure 628
controller . 668
conventional interfaces 111, 154
current time 383
D
data 1, 122
data abstraction . 109, 112
data paths 668
data-directed 231
data-directed programming 112, 243
deadlock 425
deadlock-recovery . 426
debug 2
deep binding 517
deferred operations . 44
delayed argument . 472
delayed evaluation 296, 430
delayed object 434
849dense 281
dependency-directed backtracking 565
depth-first search . 564
deque 360
derived expressions 507
digital signals . 370
dispatching on type . 242
displacement number 818
doed-tail notation 141
driver loop 520
E
empty list .137
encapsulated 300
enclosing environment 321
entry points 673
enumerator . 156
environment . 11
environment model 295
environments . 321
Euclid’s Algorithm . 63
Euclidean ring 288
evaluating 7
evaluator . 489
event-driven simulation 369
evlis tail recursion . 748
execution procedure . 535
explicit-control evaluator 741
expression 7
F
failure continuation . 579
FIFO . 354
filter 82, 156
first-class . 102
fixed point . 92
fixed-length .219
forcing . 545
forwarding address 735
frame 616
frame coordinate map . 182
frame number . 818
framed-stack 746
frames 321
free . 37
free list . 729
front . 353
full-adder . 372
function boxes 370
functional programming . 312
functional programming languages484
G
garbage .732
garbage collection . 724, 732
garbage collector 342
garbage-collected 550
generic operations . 112
generic procedures 224, 231
glitches . 2
global . 41, 321
global environment . 11
golden ratio 49
grammar . 572
H
half-adder 370
half-interval method 89
Halting eorem 526
headed list 361
hiding principle . 300
hierarchical . 134
850hierarchy of types . 266
higher-order procedures 75
Horner’s rule . 162
I
imperative programming .317
indeterminates 275
index . 725
indexing 617
instantiated with 604
instruction counting . 721
instruction execution procedure 701
instruction sequence .775
instruction tracing 721
instructions 667, 673
integerizing factor . 290
integers 7
integrator 465
interning . 728
interpreter 3, 489
invariant quantity 60
inverter 370
iterative improvement . 105
iterative process 44
K
key 217
L
labels .673
lazy evaluation 542
lexical address 818
lexical addressing . 517
lexical scoping . 39
linear iterative process 44
linear recursive process . 44
linkage descriptor . 774
list . 135, 141
list structure 135
list-structured . 116
list-structured memory 723
local evolution . 40
local state variables 297
location 724
logic-programming 491
logical and 370
logical deductions . 612
logical or . 370
M
machine language . 768
macro 507
map 156
mark-sweep 733
Memoization 368
memoization . 53
memoize . 545
merge 485
message passing 125, 253
message-passing 303
metacircular 492
Metalinguistic abstraction 489
Miller-Rabin test . 73
modular 295
modulo 67
modus ponens 627
moments in time 402
Monte Carlo integration . 309
Monte Carlo simulation 306
mutable data objects . 341
mutators . 341
mutex 421
851mutual exclusion 421
N
native language . 768
needed . 777
networks . 488
Newton’s method 98
nil . 137
non-computable .526
non-strict .543
nondeterministic 409
nondeterministic choice point 563
nondeterministic computing . 491, 559
normal-order . 542
normal-order evaluation 21, 491
O
obarray .727
object program 768
objects . 295
open-code 815
operands . 8
operator 8, 533
or-gate . 370
order of growth 54
ordinary 256
output prompt 520
P
package 245
painter . 173
pair 115, 116
parse . 571
Pascal’s triangle 53
paern . 602
paern matcher . 616
paern matching 616
paern variable . 602
pipelining 402
pointer . 132
poly 276
power series 450
predicate 23
prefix 219
prefix code 219
prefix notation 8
prey-printing 9
primitive constraints 387
probabilistic algorithms . 70
procedural abstraction 35
procedural epistemology xxiii
procedure . 45
procedure definitions . 15
procedures 5
process 45
program 2
programming languages . 2
prompt . 520
pseudo-random . 306
pseudodivision 290
pseudoremainder 290
Q
quasiquote 779
queries . 598
query language . 598
queue 353
quote .193
R
Ramanujan numbers .464
rational functions . 287
852RC circuit 466
read-eval-print loop 10
reader macro characters . 657
real numbers 7
rear 353
recursion equations 3
Recursion theory 524
recursive . 12, 33
recursive process . 44
red-black trees 213
referentially transparent . 315
register machine 667
register table 700
registers 667
released 421
remainder of . 67
resolution principle 596
ripple-carry adder . 376
robust 191
RSA algorithm . 70
rules . 599, 608
S
satisfy 604
scope 37
selectors 113
semaphore 421
separator code 219
sequence . 134
sequence accelerator .455
sequences . 81
serializer . 411
serializers 412
series RLC circuit . 475
shadow . 321
shared 348
side-effect bugs . 317
sieve of Eratosthenes 443
smoothing 104
source language . 768
source program . 768
sparse 281
special forms .14
stack 45, 689
state variables . 44, 296
statements 777
stop-and-copy 733
stratified design . 190
stream processing 22
streams 295, 429
strict . 543
subroutine 683
substitution 20
substitution model . 19
subtype 266
success continuation .579
summation of a series .77
summer 465
supertype .267
symbolic expressions 111
syntactic sugar . 15
syntax 494
systematically search 564
systems 488
T
tableau . 456
tabulation . 53, 368
tagged architectures . 726
tail-recursive 46, 754
target 774
thrashing ix
853thunk 545
thunks . 545
time 401
time segments 382
tower 267
tree accumulation 13
tree recursion 47
trees . 147
truth maintenance .565
Turing machine . 523
type field . 726
type tag 237
type tags . 231
type-inferencing 478
typed pointers 725
U
unbound . 321
unification . 596, 616, 622
unification algorithm 596
univariate polynomials 275
universal machine . 523
upward-compatible extension 554
V
value 10
value of a variable . 321
values 193
variable . 10
variable-length 219
vector 724
W
width 128
wires . 370
wishful thinking 114
Z
zero crossings . 467

كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net

تحميل

يجب عليك التسجيل في الموقع لكي تتمكن من التحميل

تسجيل | تسجيل الدخول