• LFE Documentation Site
  • Structure and Interpretation of Computer Programs
  • Introduction
    • 0.1. Title Page
    • 0.2. Copyright Page
    • 0.3. Dedication
    • 0.4. Foreword
    • 0.5. Foreword to the LFE Edition
    • 0.6. Preface to the LFE Edition
      • 0.6.1. The Hidden Origins of Lisp
        • 0.6.1.1. Giuseppe Peano
        • 0.6.1.2. Bertrand Russell
        • 0.6.1.3. Alonzo Church
        • 0.6.1.4. John McCarthy
      • 0.6.2. A Recap of Erlang's Genesis
      • 0.6.3. The Inspiration for LFE
      • 0.6.4. The Place of Lisp in the 21st Century
      • 0.6.5. Notes on Changes from the Original
      • 0.6.6. Obtaining the Book and Related Code
    • 0.7. Preface to the Second Edition
    • 0.8. Preface to the First Edition
    • 0.9. Acknowledgments
  • 1. Building Abstractions with Functions
    • 1.1. Programming in Lisp
    • 1.2. The Elements of Programming
      • 1.2.1. Expressions
      • 1.2.2. Naming and the Environment
      • 1.2.3. Evaluating Combinations
      • 1.2.4. Compound Functions
      • 1.2.5. The Substitution Model for Function Application
      • 1.2.6. Conditional Expressions and Predicates
      • 1.2.7. Exercises
      • 1.2.8. Example: Square Roots by Newton's Method
      • 1.2.9. Exercises
      • 1.2.10. Functions as Black-Box Abstractions
    • 1.3. Functions and the Processes They Generate
      • 1.3.1. Linear Recursion and Iteration
      • 1.3.2. Exercises
      • 1.3.3. Tree Recursion
      • 1.3.4. Exercises
      • 1.3.5. Orders of Growth
      • 1.3.6. Exercises
      • 1.3.7. Exponentiation
      • 1.3.8. Exercises
      • 1.3.9. Greatest Common Divisors
      • 1.3.10. Exercises
      • 1.3.11. Example: Testing for Primality
      • 1.3.12. Exercises
    • 1.4. Formulating Abstractions with Higher-Order Functions
      • 1.4.1. Functions as Arguments
      • 1.4.2. Exercises
      • 1.4.3. Constructing Functions Using Lambda
      • 1.4.4. Exercises
      • 1.4.5. Functions as General Methods
      • 1.4.6. Exercises
      • 1.4.7. Functions as Returned Values
      • 1.4.8. Exercises
  • 2. Building Abstractions with Data
    • 2.1. Introduction to Data Abstraction
      • 2.1.1. Example: Arithmetic Operations for Rational Numbers
      • 2.1.2. Exercises
      • 2.1.3. Abstraction Barriers
      • 2.1.4. Exercises
      • 2.1.5. What Is Meant by Data?
      • 2.1.6. Exercises
      • 2.1.7. Extended Exercise: Interval Arithmetic
      • 2.1.8. Exercises
    • 2.2. Hierarchical Data and the Closure Property
      • 2.2.1. Representing Sequences
        • 2.2.1.1. List operations
        • 2.2.1.2. Exercises
        • 2.2.1.3. Mapping over lists
        • 2.2.1.4. Exercises
      • 2.2.2. Hierarchical Structures
        • 2.2.2.1. Exercises
        • 2.2.2.2. Mapping over trees
        • 2.2.2.3. Exercises
      • 2.2.3. Sequences as Conventional Interfaces
        • 2.2.3.1. Sequence operations
        • 2.2.3.2. Exercises
        • 2.2.3.3. Nested mappings
        • 2.2.3.4. Exercises
      • 2.2.4. Example: A Picture Language
        • 2.2.4.1. The picture language
        • 2.2.4.2. Exercises
        • 2.2.4.3. Higher order operations
        • 2.2.4.4. Frames
        • 2.2.4.5. Exercises
        • 2.2.4.6. Painters
        • 2.2.4.7. Exercises
        • 2.2.4.8. Transforming and combining painters
        • 2.2.4.9. Exercises
        • 2.2.4.10. Levels of language for robust design
        • 2.2.4.11. Exercises
    • 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 Functions
      • 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 Functions 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
  • 6. References
  • 7. List of Exercises
Powered by GitBook

Structure and Interpretation of Computer Programs