Overview

• Structure and Interpretation of Computer Programs (SICP) teaches programming by building abstractions using procedures and data, primarily via Scheme.
• Emphasizes design principles: modularity, representation independence, and reasoning about processes and complexity.

Part I — Building Abstractions with Procedures

1. The Elements of Programming

• Expression: basic unit of computation (constants, names, combinations).
• Naming & environment: names map to values in environments; lexical scoping determines binding.
• Evaluation of combinations: evaluate operator and operands, then apply operator to operand values.
• Compound procedures: user-defined functions that package computations into reusable abstractions.
• Substitution model: reason about procedure application by substituting argument expressions into the procedure body; useful for understanding semantics.
• Conditionals & predicates: use conditional expressions to control flow and predicates to make true/false decisions.

Example: Newton's Method (square roots)

• Iteratively improve guess \(x_n\) for root of \(f(x)=0\) using the update

• For square root of \(a\), use \(f(x)=x^2-a\), so

• Stop when successive guesses are within a tolerance.

1.1 Procedures as Abstractions

• Treat procedures as black boxes: call site relies only on inputs/outputs, not implementation.
• Encapsulation and clear interfaces enable modular design and substitution of implementations.

1.2 Procedures and Processes

• Linear recursion: each step makes a single recursive call; can often be transformed to iteration with constant state.
• Iteration: state variables are updated repeatedly; uses constant space.
• Tree recursion: multiple recursive calls per step; typically grows exponentially unless pruned or memoized.
• Analyze processes by distinguishing procedure (code) vs process (time/space behavior).

Orders of Growth (complexity)

• Compare algorithms by asymptotic growth: constant \(O(1)\), logarithmic \(O(\log n)\), linear \(O(n)\), polynomial \(O(n^k)\), exponential \(O(c^n)\).
• Use recurrence relations to reason about recursive algorithms (e.g., divide-and-conquer gives \(T(n)=T(n/2)+O(1)\) leading to \(O(\log n)\)).

Selected Examples

• Exponentiation: repeated-squaring gives \(O(\log n)\) multiplications for integer exponentiation.
• Greatest Common Divisor (Euclid): repeatedly replace \((a,b)\) by \((b, a\bmod b)\) until \(b=0\); final \(a\) is gcd.
• Primality testing: example algorithms contrast trial division (slow) vs smarter heuristics; focus on algorithmic trade-offs.

1.3 Higher-Order Procedures and lambda

• Higher-order procedures: procedures that take or return procedures (e.g., map, filter, accumulate).
• lambda: creates anonymous functions and closures; closures capture surrounding environment.
• Use higher-order abstraction to factor common patterns and create general methods.
• Procedures as returned values enable encapsulation and state via closures.

Part II — Building Abstractions with Data

2. Introduction to Data Abstraction

• Data abstraction separates representation from interface using constructors and selectors.
• Abstraction barrier: client code should use the interface, not depend on underlying representation.

Example: Rational Numbers

• Represent rationals with constructor make-rat(n,d) and selectors numer/denom.
• Normalize by reducing via gcd so equal rationals have equal representations.
• Implement arithmetic via the abstract interface so representation can change without affecting clients.

Abstraction Barriers and Representation Independence

• Good designs maintain invariants inside constructors and expose only intended operations.
• Swapping internal representation (e.g., pair vs record) should not affect code that uses the abstract interface.

Extended Exercise: Interval Arithmetic

• Represent uncertain values as intervals \([a,b]\) and define arithmetic operations that produce conservative bounds.
• Illustrates subtleties of representation affecting numerical results.

2.2 Hierarchical Data and Closure Property

• Hierarchical structures: trees built from smaller components; allow recursive processing.
• Closure property: operations on a type yield values of the same type, enabling composability (e.g., combining pictures produces a picture).

Sequences and Interfaces

• Sequences can be implemented in multiple ways (linked lists, arrays) but share common operations (first, rest, length, map).
• Use conventional interfaces so algorithms work over different implementations.

Example: Picture Language

• A domain-specific representation of images where primitives and composition operators build complex pictures.
• Demonstrates design of a data abstraction for a specific problem domain.

2.3 Symbolic Data

• Quotation: represent code or symbols as data (e.g., 'x to denote symbol x) enabling symbolic processing.
• Symbolic data supports interpreters, symbolic algebra, and program transformation techniques.

Design Principles & Takeaways

• Favor abstraction: hide details, expose clear interfaces, and reason at the right level.
• Distinguish algorithms (what) from processes (how resources scale).
• Use higher-order procedures and data abstraction to build reusable, composable components.
• Test understanding by using simple models (substitution) and by analyzing orders of growth.

Quick Reference — Algorithms & Patterns

• Newton's method update: \(\(x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}.\)\)
• Euclid's gcd: repeat \((a,b)\rightarrow(b, a\bmod b)\) until \(b=0\).
• Fast exponentiation: use repeated squaring to reduce multiplications to \(O(\log n)\).
• Higher-order pattern: abstraction via functions that accept or return procedures (map, accumulate).

How to Study SICP Effectively

• Work through examples by hand using the substitution model to trace evaluations.
• Implement and test small interpreters and data abstractions to internalize design trade-offs.
• Analyze time/space of processes produced by your procedures, not only the source code.