Structure and Interpretation of Computer Programs

Citation

Abelson, H., & Sussman, G. J., with Sussman, J. (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. Free official edition: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/index.html

Chapter Summary

The book has five chapters, each about one means of controlling complexity: procedures, data, state and streams, new languages, and machines. The authors teach Scheme in passing, arguing that a Lisp dialect has so little syntax that the language can be learned in a few days. The first edition's preface describes the aim as teaching techniques for controlling the intellectual complexity of large systems rather than the syntax of a language or clever algorithms.

Chapter 1: Building Abstractions with Procedures

Section 1.1 introduces expressions, naming and the environment, the evaluation of combinations, compound procedures, the substitution model, conditionals, Newton's method for square roots, and procedures as black-box abstractions. Section 1.2 looks at the processes procedures generate: linear recursion versus iteration, tree recursion, orders of growth, exponentiation, greatest common divisors and primality testing. Section 1.3 raises the level with higher-order procedures: procedures as arguments, lambda, procedures as general methods (fixed points, Newton's method) and as returned values.

Chapter 2: Building Abstractions with Data

Chapter 2 moves from procedures to compound data. Section 2.1 develops data abstraction through rational-number arithmetic, abstraction barriers, the question of what "data" means, and an interval-arithmetic exercise. Section 2.2 covers sequences, hierarchical structures and the closure property, sequences as conventional interfaces, and a picture language. Section 2.3 brings in symbolic data: quotation, symbolic differentiation, sets and Huffman encoding trees. Sections 2.4 and 2.5 treat multiple representations, tagged data, data-directed programming and generic operations, ending with symbolic algebra.

Chapter 3: Modularity, Objects, and State

This chapter contrasts two ways of organising programs: around objects that change over time and around streams of information. Section 3.1 introduces assignment and local state, and weighs its benefits and costs. Section 3.2 replaces the substitution model with the environment model of evaluation. Section 3.3 models mutable data (lists, queues, tables), a digital-circuit simulator and constraint propagation. Section 3.4 raises concurrency and the mechanisms for controlling it. Section 3.5 develops streams as delayed lists, infinite streams and delayed evaluation, and compares the modularity of functional programs with that of objects.

Chapter 4: Metalinguistic Abstraction

The chapter's premise is that the evaluator is just another program. Section 4.1 builds the metacircular evaluator, the core of evaluation, expression representation, running it as a program and separating syntactic analysis from execution. Section 4.2 varies it into a lazy-evaluation interpreter, contrasting normal and applicative order. Section 4.3 adds nondeterministic computing with amb and search. Section 4.4 is a logic-programming query system, including the question whether it is mathematical logic and an implementation.

Chapter 5: Computing with Register Machines

The final chapter explains the control mechanisms that the metacircular evaluator inherits from its host. Section 5.1 designs register machines, with a stack for recursion. Section 5.2 builds a register-machine simulator. Section 5.3 covers memory as vectors and garbage collection. Section 5.4 presents the explicit-control evaluator, including tail recursion. Section 5.5 describes a compiler from Scheme to register-machine code.

Key Concepts

Chapter 1: Procedures and Processes

• Substitution model: a way of reasoning about how a procedure application is evaluated.
• Recursive and iterative processes: how a recursive procedure can generate either, with different space and time growth.
• Higher-order procedure: a procedure that takes or returns procedures.

Chapter 2: Data Abstraction

• Abstraction barrier: the interface that separates use of a data type from its representation.
• Closure property: combining data with a method that works again on the results.
• Data-directed programming: dispatching on type tags so representations can be added without changing existing code.

Chapter 3: State and Streams

• Local state and assignment: objects that change, and the loss of the substitution model they cause.
• Environment model: frames and bindings as the account of evaluation with assignment.
• Stream: a delayed list that lets a program treat a sequence as a whole.

Chapter 4: Evaluators

• Metacircular evaluator: an interpreter for a language written in that language.
• Lazy evaluation and amb: variations on the evaluator that change when expressions are evaluated.
• Query system: pattern matching and unification as a computational model.

Chapter 5: Machines

• Register machine: a stepwise machine with registers and a stack.
• Explicit-control evaluator and compiler: the evaluator and its compilation expressed at machine level.

Critical Analysis

Strengths

• A clear, unified thesis. The book organises everything around controlling complexity through abstraction, conventional interfaces and new languages, and every chapter extends one language or model.
• Depth through few ingredients. Because Scheme has so little syntax, space is spent on ideas such as environments, streams, evaluators and compilation. The reader implements an evaluator, a query system and a compiler, rather than only reading about them.
• Carefully revised. The second edition redesigned the major systems (generic arithmetic, interpreters, register-machine simulator and compiler), rewrote the code to run in any IEEE-standard Scheme and added sections on concurrency and nondeterminism.
• Exercises and companion material. The text is accompanied by a large set of exercises, code from the book, sample MIT assignments, an instructor's manual and Scheme implementations on the book's website.
• Open licence. The full text is free under a Creative Commons Attribution-ShareAlike 4.0 licence, with a linked table of contents.

Limitations

• Demanding for beginners. The first-edition preface describes the book as the entry subject at MIT, taken as one quarter of the common core for electrical engineering and computer science majors. Chapters 3–5 move quickly, and the book assumes first-year university mathematics and time for the exercises.
• Too much for one term. The second edition's preface says the full book cannot be covered in a semester; the authors themselves often skip logic programming (4.4), the simulator implementation (5.2) and most of the compiler (5.5).
• Scheme-centred. The book does not teach a mainstream industry language, and the register-machine material uses the book's own register-machine language rather than a real instruction set.
• Dated edition. The second edition appeared in 1996, and the errata page was last updated in 1999.

Where It Fits in the Course

This is the demanding, idea-driven end of the introductory-programming shelf. How to Design Programs is also free and also uses a Lisp-family language, but it builds a step-by-step design recipe for beginners, so it suits a first course; SICP works well as a second pass or for readers who already program. Think Python and Python Crash Course are gentle, practical introductions to one popular language; Introduction to Computation and Programming Using Python is a Python-based course on computational problem solving; and The C Programming Language is a short classic on a low-level language. SICP does not teach a language so much as a way of thinking about programs, and the other books are good companions when a mainstream language is also needed.

How to Use This Book

The book suits motivated readers with first-year university mathematics who can commit time to the exercises. Install a Scheme (the book's website lists MIT Scheme and others) and run the code from the book.

A practical plan:

• Core: Chapters 1 and 2 in full, then Sections 3.1–3.3 and 3.5 (state, the environment model and streams), and Sections 4.1 and 4.2 (the metacircular and lazy evaluators).
• Optional: Sections 3.4 (concurrency), 4.3 (amb), 4.4 (logic programming) and all of Chapter 5, which the authors themselves treat selectively; read 5.1 and 5.4 first if you want the machine-level view of recursion.
• Exercises: work through the exercises in each section before moving on, especially the data-abstraction exercises in Chapter 2 and the interpreter exercises in Chapter 4.

If you want less theory first, begin with a gentler Scheme-based introduction and return to Chapter 1 later.

Edition and Sources

This guide covers the second edition (MIT Press, 1996), read in the official HTML version on the MIT Press SICP site, which states that the text is licensed under Creative Commons Attribution-ShareAlike 4.0. It is based on the forewords and prefaces, the full table of contents, and the chapter introductions and section structure of all five chapters, together with the companion site's description of the supporting materials.