Structure and Interpretation of Computer Programs — universally called SICP — is the most influential computer science textbook ever written. It was the required text for MIT's introductory CS course for two decades. Hal Abelson and Gerald Jay Sussman designed it around a single idea: that programming is not primarily about computers or about programming languages, but about controlling complexity through abstraction.
These sicp notes cover the major themes and key techniques from SICP and the corresponding MIT 6.001 lecture series. Whether you are working through the book for the first time, reviewing before a systems-level interview, or returning to first principles after years of framework-driven development, this document gives you the ideas that make SICP worth the effort.
MIT 6.001 SICP Lecture 1 with Hal Abelson (1986 recording). The full 20-lecture series is available free on MIT OpenCourseWare and YouTube. The full text is available at mitpress.mit.edu.
For other foundational MIT course notes, see our MIT 6.034 AI notes. For a Python-based approach to programming fundamentals, see our learn Python from YouTube guide. For a structured path through CS fundamentals, see our guide on reverse engineering college courses.
What Is SICP, and Why Does It Still Matter?
SICP was written in 1984, uses Scheme (a dialect of Lisp), and has essentially nothing to say about the web, mobile apps, microservices, or any technology you are likely to be working with in 2026. It is, in some ways, deliberately out of time.
That is exactly why it matters.
SICP is about the fundamental operations of computing — the ideas that are true regardless of which language, framework, or paradigm you use. The book argues that there are exactly three mechanisms for controlling complexity in any programming system:
- Primitive elements: the simplest things the language can do
- Means of combination: ways to build compound things from simpler things
- Means of abstraction: ways to treat compound things as single units and name them
Everything else in programming is built from these three mechanisms. Understanding them deeply — in a language like Scheme, where the syntax is so minimal that it gets out of the way — is what SICP offers.
Why Scheme? Scheme has almost no syntax. The entire language fits on a page. By stripping away syntax, SICP forces you to confront the semantics — what the computations actually mean — without the distraction of parsing rules. Every language designer's choice becomes visible.
What the book is not: SICP is not a practical programming course. It does not teach you how to build web applications or use databases. It teaches you how to think about programs — how to decompose problems, how to reason about evaluation, and how to build programming languages themselves.
Procedures, Abstraction, and the Substitution Model
The first chapter of SICP builds the foundation: expressions, procedures, and the substitution model of evaluation.
Expressions and evaluation. The most primitive expressions are self-evaluating: 42, "hello", #t. Procedure application is written (operator operands...). The parentheses are not grouping — they signal application. This uniformity means there are no precedence rules and no operator/function distinction.
(+ 1 2) ; => 3
(* 3 (+ 1 2)) ; => 9
(define x 10) ; binds x to 10
x ; => 10
Defining procedures:
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
The define form binds a name to a value in the current environment. When the value is a lambda, define creates a procedure.
The substitution model is the simplest model of how procedures are evaluated: to evaluate (f arg1 arg2), substitute the arguments for the formal parameters in the body of f and evaluate the resulting expression.
The substitution model is not how real interpreters work (environments and closures handle this correctly), but it is accurate enough to reason about most programs and introduces the key distinction:
Applicative-order evaluation (most languages): evaluate the arguments first, then apply the procedure. Scheme uses applicative order by default.
Normal-order evaluation (lazy evaluation): substitute the unevaluated argument expressions first, evaluate only when needed. Haskell uses normal order. The two orders produce the same result for well-defined functions but differ when side effects or non-termination are involved.
Recursive versus iterative processes. This is one of SICP's most important contributions to how programmers think.
Recursive factorial:
(define (factorial n)
(if (= n 0) 1 (* n (factorial (- n 1)))))
Iterative factorial:
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product) (+ counter 1))))
(iter 1 1))
Both are recursive procedure definitions — both call themselves. The difference is the process they generate. The first generates a chain of deferred multiplications that must be held in memory. The second generates a process where all the state is captured in product and counter — a constant-space iterative process.
Tail recursion means that the iterative process, despite being written as a recursive call, executes in constant space. Proper Scheme implementations guarantee this — an iterative process written as tail recursion uses no more stack space than a loop. This is why SICP says there is no need for a separate loop construct: recursion with tail calls is iteration.
Higher-Order Procedures: Functions as Values
Chapter 1 culminates in one of SICP's central themes: procedures are values. You can pass them as arguments, return them from other procedures, and store them in data structures. This is not a syntactic trick — it fundamentally changes what you can abstract.
Procedures as arguments. Consider summing a sequence of values from a to b:
(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
sum takes a procedure term (what to compute for each element) and next (how to advance to the next element). Instantiate it:
(define (sum-integers a b)
(sum identity a add1 b))
(define (sum-squares a b)
(sum square a add1 b))
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))
The pattern is abstracted once in sum; variations are expressed by passing different procedures. This is the fundamental idea behind higher-order functions, functional programming, and (at a more abstract level) monads.
Lambda: anonymous procedures. (lambda (x) (* x x)) is the procedure that squares its argument, with no name required. Lambda is the primitive building block — define is syntactic sugar for binding a lambda to a name.
Returning procedures as values:
(define (make-adder n)
(lambda (x) (+ x n)))
(define add5 (make-adder 5))
(add5 3) ; => 8
make-adder returns a procedure — and that procedure "remembers" the value of n from the environment where it was created. This is a closure: a procedure together with its defining environment.
The Newton's method example shows higher-order functions solving a real numerical problem. The fixed-point procedure and the Newton's method transformer are written as higher-order functions that take procedures as arguments and return procedures as values. The same fixed-point procedure implements Newton's method, the square root, and the cube root — all without code duplication.
Data Abstraction: Pairs, Lists, and Abstraction Barriers
Chapter 2 extends the abstraction approach from procedures to data. The key principle: separate the implementation of data from its use. Code that uses a data structure should only depend on the operations the abstraction provides, not on how the data is represented internally.
Pairs are the fundamental data structure in Scheme:
(cons 1 2) ; creates a pair
(car (cons 1 2)) ; => 1 (first element)
(cdr (cons 1 2)) ; => 2 (second element)
Pairs compose into lists: a list is either empty '() or a pair whose cdr is a list. (list 1 2 3) is (cons 1 (cons 2 (cons 3 '()))).
Abstraction barriers. Consider rational numbers implemented as pairs of integers:
(define (make-rat n d) (cons n d))
(define (numer r) (car r))
(define (denom r) (cdr r))
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
Code that uses rational numbers only calls make-rat, numer, and denom. It does not know they are pairs. If the implementation changes (say, storing the reduced form), the code using rational numbers does not change. This is data abstraction — the same principle as interfaces in Java or protocols in Swift, at a more fundamental level.
Data as procedures. SICP makes a shocking point: you do not need a built-in pair data structure. You can implement cons, car, and cdr using only procedures:
(define (cons x y) (lambda (m) (if (= m 0) x y)))
(define (car z) (z 0))
(define (cdr z) (z 1))
This works. A pair is a procedure that remembers its two components and returns the right one when asked. This is not a curiosity — it demonstrates that the boundary between "data" and "procedures" is not as fundamental as it appears. Data structures are patterns of procedures. Procedures are patterns of evaluation.
List processing. SICP introduces the full repertoire of list operations:
map: apply a procedure to every element, return the list of resultsfilter: return the elements satisfying a predicateaccumulate(fold): reduce a list to a single value with a combining operation and initial value
These three operations — map, filter, reduce — are the complete vocabulary for list processing. Any list computation can be expressed as a composition of these three. This insight predates MapReduce and functional programming frameworks by decades.
Trees and hierarchical data. Lists of lists form trees. SICP's tree-recursive procedures (Fibonacci, counting change) illustrate how recursive problems arise naturally from recursive data structures.
Modularity, State, and the Assignment Problem
Chapter 3 introduces the one idea that breaks the mathematical purity of the substitution model: assignment and mutable state.
In a purely functional program, (f 1) always returns the same value regardless of when you call it. Once you introduce assignment — (set! x 5) — this is no longer true. The same procedure can return different values at different times.
Objects with local state. A bank account:
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount)) balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount)) balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'balance) balance)))
dispatch)
Each call to make-account creates a separate account object with its own private balance state. This is object-oriented programming — encapsulated state and message dispatch — implemented entirely from closures and assignment.
The environmental model of evaluation. Assignment breaks the substitution model. You need a model that tracks where names are bound and how those bindings change over time. The environmental model introduces environments (frames mapping names to values) chained into a hierarchy. When a procedure is applied, a new frame is created extending the procedure's defining environment.
This is how closures work: when make-account returns dispatch, dispatch closes over the frame containing balance. Subsequent calls to dispatch see the current value of balance in that frame.
The problems with mutation. SICP argues that mutable state introduces two deep problems:
- Identity: two things that started with the same value may diverge after mutation. Are they the same object?
- Time: the order of operations matters.
(withdraw 10)then(withdraw 20)produces a different result than the reverse. Programs must reason about sequences of events.
These problems are exactly what concurrent programming magnifies: race conditions, deadlocks, and consistency problems are all consequences of shared mutable state. SICP introduces semaphores and serializers to address them.
The key insight: pure functional programs are easy to reason about — referential transparency means you can substitute equals for equals anywhere. Mutable state is necessary for many practical programs but it comes at a cost: you can no longer think of programs as mathematical functions.
Metalinguistic Abstraction: Building Interpreters
Chapter 4 and Chapter 5 are where SICP reveals its deepest lesson: a programming language is itself a program, and building an interpreter for a language gives you the deepest possible understanding of how programming works.
The metacircular evaluator. SICP implements a Scheme interpreter in Scheme. The core of any interpreter is the eval-apply cycle:
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp) (make-procedure (lambda-parameters exp)
(lambda-body exp) env))
((begin? exp) (eval-sequence (begin-actions exp) env))
((application? exp) (apply (eval (operator exp) env)
(list-of-values (operands exp) env)))))
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence (procedure-body procedure)
(extend-environment (procedure-parameters procedure)
arguments
(procedure-environment procedure))))))
eval dispatches on the type of expression. apply applies a procedure to evaluated arguments. Together they implement the full evaluation semantics of Scheme in about 50 lines of Scheme.
Why this matters. When you write (+ 1 2), something evaluates it. When you ask "what does this program do?", something answers that question. The metacircular evaluator makes that "something" explicit and modifiable. You can change evaluation semantics by modifying eval and apply.
Lazy evaluation. By adding a single case to eval and apply, you can implement lazy (normal-order) evaluation, where procedure arguments are not evaluated until needed. The resulting interpreter implements a fundamentally different language, with different expressiveness and performance characteristics.
Nondeterministic computing and amb. SICP's most memorable example: adding amb (ambiguous choice) to the interpreter creates a nondeterministic language where programs express constraints and the interpreter automatically searches for values satisfying them. The amb operator can be implemented by making the evaluator use continuation-passing style and backtracking.
The register machine model. Chapter 5 descends below the interpreter to the hardware level: a model of computation in terms of registers, operations, and a program counter. SICP compiles Scheme to this register machine model, making explicit the connection between the abstract recursive model of Chapter 1 and the iterative machine execution that actually happens. Tail call optimization — why iterative processes use constant space — is visible directly in the compiled register machine code.
Why Is SICP So Hard, and What Do You Get From Working Through It?
SICP is not easy. The exercises range from accessible to genuinely difficult. Some exercises (especially in Chapter 3 and 4) require hours of thinking before the solution is apparent. This is deliberate.
The book is hard because the problems are hard. Not hard in the sense of requiring specialized knowledge, but hard in the sense of requiring you to hold multiple levels of abstraction in your head simultaneously. This is the skill SICP is teaching.
What you get from working through SICP:
- A deep understanding of how procedures and data relate, and how the distinction between them is less fundamental than it appears
- The ability to think about programs at multiple levels of abstraction simultaneously
- An understanding of how evaluation works — how expressions become values — that you can apply to any language
- The ability to design and implement domain-specific languages, which is one of the most powerful tools in software engineering
- A mental model of objects (encapsulated state + message dispatch) that predates Java by a decade and makes object-oriented programming comprehensible at a fundamental level
What SICP does not give you: practical programming skills for current tools, data structures and algorithms for interviews (use a different resource for that), or any familiarity with modern languages.
If you work through SICP seriously — reading carefully, doing the exercises — you will be a better programmer in any language. The understanding is not specific to Scheme. It is about how computation works.
For further depth on programming systems and language design, pair SICP with the MIT 6.001 lecture recordings (Abelson and Sussman's delivery is excellent). For a Python-based approach to similar ideas, see our learn Python from YouTube guide. For the broader context of computer science fundamentals, our YouTube to notes complete guide covers how to extract maximum value from technical lecture series.
How Should You Approach SICP as a Self-Learner?
Most people who start SICP do not finish it. This is partly because it is hard, but mostly because they underestimate how much active work it requires.
The approach that works: treat it like a graduate-level course, not a tutorial. Read the text once to understand the ideas, then do the exercises before moving on. The exercises are not optional reinforcement — they are how you find out whether you actually understood what you read.
The exercises to prioritize:
- Every exercise in Chapter 1 through Section 2.2 (these build the core intuitions)
- All the interpreter exercises in Chapter 4 (implementing
evalandapplyfrom scratch) - The metacircular evaluator modifications (lazy evaluation,
amb, nondeterminism)
The exercises to skip if you are short on time:
- The most combinatorial exercises in Chapter 2 (symbolic differentiation and the picture language) — they are interesting but not load-bearing for the core ideas
- Chapter 5 register machine exercises unless you specifically want to understand compilation
SICP is a course in thinking. No amount of reading these notes replaces the work of working through the exercises yourself — but these notes give you the map, so you know where you are going.
SICP is one of the most rewarding technical texts you will ever read — and one of the most demanding. Notiq turns dense lecture content into structured notes so you can review key concepts between reading sessions, extract the ideas that matter, and hold onto them long after you finish the course.
