Structure and Interpretation of Computer Programs

Problems and projects from the legendary MIT 6.001 Purple Book.

Chapter 1 - Expressions, Naming and Environment, Evaluating Combinations, Compound Procedures, Substitution Model, Applicative Order Evaluation, Normal Order Evaluation, Conditional Expressions and Predicates, Numerical Analysis, Square Roots, Cube Roots, Black-Box Abstractions, Recursion, Iteration, Linear Recursion, Tree Recursion, Orders of Growth, Exponentiation, Greatest Common Divisors, Prime Numbers, Primality Testing, Fermat Test, Probabilistic Methods, Higher-Order Procedures, Procedures as Arguments, Numerical Integration, Lambda Calculus, Local Variables, Fixed-Points of Functions, Procedures as Returned Values.

Chapter 2 - Compound Data, Data Abstraction, Abstraction Barriers, Pairs, Lists, Church Numerals, Interval Arithmetic, Hierarchical Data, Closure, Pointers, Sequences, List Operations, Dotted-Tail Notation, Mappings, Nested Mappings, Hierarchical Structures, Trees, Seequence Operations, Filtering, Accumulation, Matrix Algebra, Eight Queens, Picture Language, Symbolic Data, Symbolic Expressions, Quotation, Symbolic Differentiation, Set Representation, Sets as Ordered Lists, Sets as Binary Trees, Huffman Encoding Trees, Multiple Representations for Abstract Data, Tagged Data, Data-Directed Programming, Additivity, Message Passing, Generic Operations, Coercion, Type Hierarchies, Generic Arithmetic Operations, Symbolic Algebra.

Chapter 3 - xx

Some useful links:

• The SICP Web Site (includes full text)

• The "Don't Panic" Guide to 6.001 Scheme

• Compiling Up to Lambda Calculus

• Fixed-Point Combinators in JavaScript: Memoizing Recursive Functions

• Deriving the Y-Combinator

• The Why of Y

• Hyperpolyglot - Commands for Common Lisp / Scheme / Clojure / Emacs

The wiki contains answers to some of the more mathematically oriented questions.

John McCarthy, Inventor of Lisp