Structure and interpretation of computer programs / Harold Abelson, Gerald Jay Sussman, Julie Sussman.

CONTENIDO
Chapter 1. Building Abstractions with Procedures 1
The Elements of Programming 4
Expressions 5
Naming and the Environment 7
Evaluating Combinations 9
Compound Procedures 11
The Substitution Model for Procedure Application 13
Conditional Expressions and Predicates 17
Example: Square Roots by Newton's Method 21
Procedures as Black-Box Abstractions 26
Procedures and the Processes They Generate 31
Linear Recursion and Iteration 32
Tree Recursion 37
Orders of Growth 42
Exponentiation 44
Greatest Common Divisors 48
Example: Testing for Primality 50
Formulating Abstractions with Higher-Order Procedures 56
Procedures as Arguments 57
Constructing Procedures Using Lambda 62
Procedures as General Methods 66
Procedures as Returned Values 72
Chapter 2. Building Abstractions with Data 79
Introduction to Data Abstraction 83
Example: Arithmetic Operations for Rational Numbers 83
Abstraction Barriers 87
What Is Meant by Data? 90
Extended Exercise: Interval Arithmetic 93
Hierarchical Data and the Closure Property 97
Representing Sequences 99
Hierarchical Structures 107
Sequences as Conventional Interfaces 113
Example: A Picture Language 126
Symbolic Data 142
Quotation 142
Example: Symbolic Differentiation 145
Example: Representing Sets 151
Example: Huffman Encoding Trees 161
Multiple Representations for Abstract Data 169
Representations for Complex Numbers 171
Tagged data 175
Data-Directed Programming and Additivity 179
Systems with Generic Operations 187
Generic Arithmetic Operations 189
Combining Data of Different Types 193
Example: Symbolic Algebra 202
Chapter 3. Modularity, Objects, and State 217
Assignment and Local State 218
Local State Variables 219
The Benefits of Introducing Assignment 225
The Costs of Introducing Assignment 229
The Environment Model of Evaluation 236
The Rules for Evaluation 238
Applying Simple Procedures 241
Frames as the Repository of Local State 244
Internal Definitions 249
Modeling with Mutable Data 251
Mutable List Structure 252
Representing Queues 261
Representing Tables 266
A Simulator for Digital Circuits 273
Propagation of Constraints 285
Concurrency: Time Is of the Essence 297
The Nature of Time in Concurrent Systems 298
Mechanisms for Controlling Concurrency 303
Streams 316
Streams Are Delayed Lists 317
Infinite Streams 326
Exploiting the Stream Paradigm 334
Streams and Delayed Evaluation 346
Modularity of Functional Programs and Modularity of Objects 352
Chapter 4. Metalinguistic Abstraction 359
The Metacircular Evaluator 362
The Core of the Evaluator 364
Representing Expressions 368
Evaluator Data Structures 376
Running the Evaluator as a Program 381
Data as Programs 384
Internal Definitions 388
Separating Syntactic Analysis from Execution 393
Variations on a Scheme--Lazy Evaluation 398
Normal Order and Applicative Order 399
An Interpreter with Lazy Evaluation 401
Streams as Lazy Lists 409
Variations on a Scheme--Nondeterministic Computing 412
Amb and Search 414
Examples of Nondeterministic Programs 418
Implementing the Amb Evaluator 426
Logic Programming 438
Deductive Information Retrieval 441
How the Query System Works 453
Is Logic Programming Mathematical Logic? 462
Implementing the Query System 468
Chapter 5. Computing with Register Machines 491
Designing Register Machines 492
A Language for Describing Register Machines 494
Abstraction in Machine Design 499
Subroutines 502
Using a Stack to Implement Recursion 506
Instruction Summary 512
A Register-Machine Simulator 513
The Machine Model 515
The Assembler 520
Generating Execution Procedures for Instructions 523
Monitoring Machine Performance 530
Storage Allocation and Garbage Collection 533
Memory as Vectors 534
Maintaining the Illusion of Infinite Memory 540
The Explicit-Control Evaluator 547
The Core of the Explicit-Control Evaluator 549
Sequence Evaluation and Tail Recursion 555
Conditionals, Assignments, and Definitions 558
Running the Evaluator 560
Compilation 566
Structure of the Compiler 569
Compiling Expressions 574
Compiling Combinations 581
Combining Instruction Sequences 587
An Example of Compiled Code 591
Lexical Addressing 600
Interfacing Compiled Code to the Evaluator 603
References 611
List of Exercises 619
Index 621