Table of Contents
- Structure and Interpretation of Computer Programs
- 40 Contents
- 40 Foreword
- 40 Preface to the Second Edition
- 40 Preface to the First Edition
- 40 Acknowledgments
- Chapter 1 Building Abstractions with Procedures
- 1.14040The Elements of Programming
- 1.1.14040Expressions
- 1.1.24040Naming and the Environment
- 1.1.34040Evaluating Combinations
- 1.1.44040Compound Procedures
- 1.1.54040The Substitution Model for Procedure Application
- Applicative order versus normal order
- 1.1.64040Conditional Expressions and Predicates
- 1.1.74040Example: Square Roots by Newton's Method
- 1.1.84040Procedures as Black-Box Abstractions
- Local names
- Internal definitions and block structure
- 1.24040Procedures and the Processes They Generate
- 1.2.14040Linear Recursion and Iteration
- 1.2.24040Tree Recursion
- 1.2.34040Orders of Growth
- 1.2.44040Exponentiation
- 1.2.54040Greatest Common Divisors
- 1.2.64040Example: Testing for Primality
- Searching for divisors
- The Fermat test
- Probabilistic methods
- 1.34040Formulating Abstractions with Higher-Order Procedures
- 1.3.14040Procedures as Arguments
- 1.3.24040Constructing Procedures Using Lambda
- Using let to create local variables
- 1.3.34040Procedures as General Methods
- Finding roots of equations by the half-interval method
- Finding fixed points of functions
- 1.3.44040Procedures as Returned Values
- Newton's method
- Abstractions and first-class procedures
- Chapter 2 Building Abstractions with Data
- 2.14040Introduction to Data Abstraction
- 2.1.14040Example: Arithmetic Operations for Rational Numbers
- Pairs
- Representing rational numbers
- 2.1.24040Abstraction Barriers
- 2.1.34040What Is Meant by Data?
- 2.1.44040Extended Exercise: Interval Arithmetic
- 2.24040Hierarchical Data and the Closure Property
- 2.2.14040Representing Sequences
- List operations
- Mapping over lists
- 2.2.24040Hierarchical Structures
- 2.2.34040Sequences as Conventional Interfaces
- Sequence Operations
- Nested Mappings
- 2.2.44040Example: A Picture Language
- The picture language
- Higher-order operations
- Frames
- Painters
- Transforming and combining painters
- Levels of language for robust design
- 2.34040Symbolic Data
- 2.3.14040Quotation
- 2.3.24040Example: Symbolic Differentiation
- The differentiation program with abstract data
- Representing algebraic expressions
- 2.3.34040Example: Representing Sets
- Sets as unordered lists
- Sets as ordered lists
- Sets as binary trees
- Sets and information retrieval
- 2.3.44040Example: Huffman Encoding Trees
- Generating Huffman trees
- Representing Huffman trees
- The decoding procedure
- Sets of weighted elements
- 2.44040Multiple Representations for Abstract Data
- 2.4.14040Representations for Complex Numbers
- 2.4.24040Tagged data
- 2.4.34040Data-Directed Programming and Additivity
- 2.54040Systems with Generic Operations
- 2.5.14040Generic Arithmetic Operations
- 2.5.24040Combining Data of Different Types
- Coercion
- Hierarchies of types
- Inadequacies of hierarchies
- 2.5.34040Example: Symbolic Algebra
- Arithmetic on polynomials
- Representing term lists
- Hierarchies of types in symbolic algebra
- Extended exercise: Rational functions
- Chapter 3 Modularity, Objects, and State
- 3.14040Assignment and Local State
- 3.1.14040Local State Variables
- 3.1.24040The Benefits of Introducing Assignment
- 3.1.34040The Costs of Introducing Assignment
- Sameness and change
- Pitfalls of imperative programming
- 3.24040The Environment Model of Evaluation
- 3.2.14040The Rules for Evaluation
- 3.2.24040Applying Simple Procedures
- 3.2.34040Frames as the Repository of Local State
- 3.2.44040Internal Definitions
- 3.34040Modeling with Mutable Data
- 3.3.14040Mutable List Structure
- Sharing and identity
- Mutation is just assignment
- 3.3.24040Representing Queues
- 3.3.34040Representing Tables
- Two-dimensional tables
- Creating local tables
- 3.3.44040A Simulator for Digital Circuits
- Primitive function boxes
- Representing wires
- The agenda
- A sample simulation
- Implementing the agenda
- 3.3.54040Propagation of Constraints
- Using the constraint system
- Implementing the constraint system
- Representing connectors
- 3.44040Concurrency: Time Is of the Essence
- 3.4.14040The Nature of Time in Concurrent Systems
- Correct behavior of concurrent programs
- 3.4.24040Mechanisms for Controlling Concurrency
- Serializing access to shared state
- Serializers in Scheme
- Complexity of using multiple shared resources
- Implementing serializers
- Deadlock
- Concurrency, time, and communication
- 3.54040Streams
- 3.5.14040Streams Are Delayed Lists
- The stream implementation in action
- Implementing delay and force
- 3.5.24040Infinite Streams
- Defining streams implicitly
- 3.5.34040Exploiting the Stream Paradigm
- Formulating iterations as stream processes
- Infinite streams of pairs
- Streams as signals
- 3.5.44040Streams and Delayed Evaluation
- 3.5.54040Modularity of Functional Programs and Modularity of Objects
- A functional-programming view of time
- Chapter 4 Metalinguistic Abstraction
- 4.14040The Metacircular Evaluator
- 4.1.14040The Core of the Evaluator
- Eval
- Primitive expressions
- Special forms
- Combinations
- Apply
- Procedure arguments
- Conditionals
- Sequences
- Assignments and definitions
- 4.1.24040Representing Expressions
- 4.1.34040Evaluator Data Structures
- Testing of predicates
- Representing procedures
- Operations on Environments
- 4.1.44040Running the Evaluator as a Program
- 4.1.54040Data as Programs
- 4.1.64040Internal Definitions
- 4.1.74040Separating Syntactic Analysis from Execution
- 4.24040Variations on a Scheme -- Lazy Evaluation
- 4.2.14040Normal Order and Applicative Order
- 4.2.24040An Interpreter with Lazy Evaluation
- Modifying the evaluator
- Representing thunks
- 4.2.34040Streams as Lazy Lists
- 4.34040Variations on a Scheme -- Nondeterministic Computing
- 4.3.14040Amb and Search
- 4.3.24040Examples of Nondeterministic Programs
- Logic Puzzles
- Parsing natural language
- 4.3.34040Implementing the Amb Evaluator
- Execution procedures and continuations
- Structure of the evaluator
- Simple expressions
- Conditionals and sequences
- Definitions and assignments
- Procedure applications
- Evaluating amb expressions
- Driver loop
- 4.44040Logic Programming
- 4.4.14040Deductive Information Retrieval
- A sample data base
- Simple queries
- Compound queries
- Rules
- Logic as programs
- 4.4.24040How the Query System Works
- Pattern matching
- Streams of frames
- Compound queries
- Unification
- Applying rules
- Simple queries
- The query evaluator and the driver loop
- 4.4.34040Is Logic Programming Mathematical Logic?
- Infinite loops
- Problems with not
- 4.4.44040Implementing the Query System
- 4.4.4.14040The Driver Loop and Instantiation
- 4.4.4.24040The Evaluator
- Simple queries
- Compound queries
- Filters
- 4.4.4.34040Finding Assertions by Pattern Matching
- Patterns with dotted tails
- 4.4.4.44040Rules and Unification
- 4.4.4.54040Maintaining the Data Base
- 4.4.4.64040Stream Operations
- 4.4.4.74040Query Syntax Procedures
- 4.4.4.84040Frames and Bindings
- Chapter 5 Computing with Register Machines
- 5.14040Designing Register Machines
- 5.1.14040A Language for Describing Register Machines
- 5.1.24040Abstraction in Machine Design
- 5.1.34040Subroutines
- 5.1.44040Using a Stack to Implement Recursion
- 5.1.54040Instruction Summary
- 5.24040A Register-Machine Simulator
- 5.2.14040The Machine Model
- Registers
- The stack
- The basic machine
- 5.2.24040The Assembler
- 5.2.34040Generating Execution Procedures for Instructions
- Assign instructions
- Test, branch, and goto instructions
- Other instructions
- Execution procedures for subexpressions
- 5.2.44040Monitoring Machine Performance
- 5.34040Storage Allocation and Garbage Collection
- 5.3.14040Memory as Vectors
- Representing Lisp data
- Implementing the primitive list operations
- Implementing stacks
- 5.3.24040Maintaining the Illusion of Infinite Memory
- Implementation of a stop-and-copy garbage collector
- 5.44040The Explicit-Control Evaluator
- 5.4.14040The Core of the Explicit-Control Evaluator
- Evaluating simple expressions
- Evaluating procedure applications
- Procedure application
- 5.4.24040Sequence Evaluation and Tail Recursion
- 5.4.34040Conditionals, Assignments, and Definitions
- Assignments and definitions
- 5.4.44040Running the Evaluator
- Monitoring the performance of the evaluator
- 5.54040Compilation
- An overview of the compiler
- 5.5.14040Structure of the Compiler
- Targets and linkages
- Instruction sequences and stack usage
- 5.5.24040Compiling Expressions
- Compiling linkage code
- Compiling simple expressions
- Compiling conditional expressions
- Compiling sequences
- Compiling lambda expressions
- 5.5.34040Compiling Combinations
- Applying procedures
- Applying compiled procedures
- 5.5.44040Combining Instruction Sequences
- 5.5.54040An Example of Compiled Code
- 5.5.64040Lexical Addressing
- 5.5.74040Interfacing Compiled Code to the Evaluator
- Interpretation and compilation
- 40 References
- 40 List of Exercises
- 40 Index