Structure and Interpretation of Computer Programs (Python)

Higher-Order Functions — Pass a function, return a function, and count the calls

Turn three near-identical sums into one function that takes its rule as an argument, then build fixed-point search, average damping and Newton’s method from functions that take and return functions.

You build: A general fold, compose and repeated (SICP 1.32, 1.42, 1.43)

• functions as arguments
• lambda
• closures
• fixed points

Environment Diagrams — SICP’s environment model in Python: frames, parents, and local state

Trace the frames a call creates, find the binding a name refers to, see why a function resolves free names where it was defined, and explain how make_withdraw keeps private state.

You build: define, assign and call frames in a small frame model

• frames
• lexical scope
• nonlocal
• local state

Recursive Functions — Linear and tree recursion, the processes they generate, and how to avoid repeated work

Factorial as a recursive and an iterative process, Fibonacci and counting change as tree recursion, orders of growth, exponentiation by squaring and Euclid’s algorithm.

You build: Traced recursive processes and a memoized route counter

• recursion
• iteration
• tree recursion
• memoization

Data Abstraction — Rational numbers, geometry and procedural pairs behind tested interfaces

Follow SICP’s rational-number, point and segment, procedural-pair and interval examples in Python. Specify constructor-selector laws, keep clients independent of storage, count where normalization work happens, and see why interval formulas that are algebraically equal give different bounds.

You build: A signed rational constructor, two rectangle representations and a pair made of functions (SICP 2.1, 2.3, 2.4)

• constructors and selectors
• abstraction barriers
• procedural pairs
• interval arithmetic

Sequences — Lists, conventional sequence stages and Python generators

Represent ordered sequences, map and filter while preserving order, distinguish fold direction, and trace how generators respond to demand. Measure actual source reads and stop a preview at its requested boundary.

You build: same-parity (SICP 2.20), Horner evaluation (2.34) and a traced lazy pipeline

• map and filter
• folds
• sequence pipelines
• generators

Trees — Follow structure, specify answers, map and search, and count traversal work

Separate labels from structure; count leaves and map over trees as SICP does; justify aggregation, transformation and first-match search; measure node visits and reuse completed answers.

You build: height, deep_reverse (SICP 2.27) and a first-match path search

• trees
• structural recursion
• tree map
• search

Mutable Data — Local state, shared identity and mutable links

Build stateful closures, trace aliases and link updates, count pairs by identity instead of by path, and give several passwords access to one shared balance.

You build: An accumulator, a destructive append, a password account and an identity-based pair counter (SICP 3.1–3.3, 3.12, 3.17)

• local state
• identity and sharing
• mutable pairs
• aliasing

Object-Oriented Programming — Objects as an alternative abstraction boundary

Organize state and behavior into classes. Connect OOP back to closures and message passing, then explore inheritance, method resolution, and how polymorphism enables multiple data representations.

Interpreters — Rebuilding the evaluator to understand computation itself

The capstone: build a working interpreter in ~100 lines of Python. Understand parsing, the Eval/Apply cycle, environments inside the interpreter, and how a language can describe itself.