Structure and Interpretation of Computer Programs (SICP)

SICP, short for “Structure and Interpretation of Computer Programs”, is a legendary computer science textbook used in universities all over the world. It was written by Harold Abelson and Gerald Jay Sussmann, two professors at MIT, and released in 1985.

Although it’s been getting on in years, the book has aged remarkably well and has amassed somewhat of a cult following among many computer scientists. I am working through all the exercises in the book and sharing the results here.

If you would like to follow along, a free PDF copy of the book is available here.

1 Building Abstractions with Procedures

1.1 The Elements of Programming

This section introduces the idea of expressions and explains the prefix notation used by Scheme. It also explains the use of variables as the simplest means of abstraction. The substitution model is introduced and a differentiation made between applicative and normal order. We also learn about conditional expressions.

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8

1.2 Procedures and the Processes They Generate

In this section, we learn about recursion and iteration. The concept of order of growth is introduced with the Fermat test as an example.

1.9 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28

1.3 Formulating Abstractions with Higher-Order Procedures

Here, we go into functional programming theory by learning about procedures being passed as arguments for other procedures. We learn about lambda procedures and local variables.

1.29 1.30 1.31 1.32 1.33 1.34 1.35 1.36 1.37 1.38 1.39 1.40 1.41 1.42 1.43 1.44 1.45 1.46

2 Building Abstractions with Data

2.1 Introduction to Data Abstraction

Data abstraction is introduced via the concept of selectors and constructors and pairs as the fundamental building block for data structures.

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16

2.2 Hierarchical Data and the Closure Property

The box-and-pointer notation is introduced here, as well as hierarchical structures. We learn about list operation and tree structures as well as the closure property and the picture language.

2.17 2.18 2.19 2.20 2.21 2.22 2.23 2.24 2.25 2.26 2.27 2.28 2.29 2.30 2.31 2.32 2.33 2.34 2.35 2.36 2.37 2.38 2.39 2.40 2.41 2.42 2.43 2.44 2.45 2.46 2.47 2.48 2.49 2.50 2.51 2.52

2.3 Symbolic Data

This section introduces quotation as a means of representing non-numerical values called symbols.

2.53 2.54 2.55 2.56 2.57 2.58 2.59 2.60 2.61 2.62 2.63 2.64 2.65 2.66 2.67 2.68 2.69 2.70 2.71 2.72

2.4 Multiple Representations for Abstract Data

We learn about generic procedures which can work on multiple different representations of data and the different ways to accomplish it, such as type tags and data-directed programming.

2.73 2.74 2.75 2.76

2.5 Systems with Generic Operations

The concept of coercion is introduced together with the idea of a hierarchy of types.

2.77 2.78 2.79 2.80 2.81

3 Modularity, Objects, and State

3.1 Assignment and Local State

Here, we learn about assignment and introduce the environment model of computation, introducing state to our programs.

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8

3.2 The Environment Model of Evaluation

This section goes into further detail on the environment model.

3.9

3.3 Modelling with Mutable Data

This chapter introduces mutators and the concept of mutable data objects.

3.16 3.17 3.18 3.19 3.21 3.22 3.23 3.24 3.25 3.27 3.28 3.29 3.30 3.31 3.33 3.34 3.35 3.37