MIT 6.001 - SICP - Structure and Interpretation of Computer Programs: Notes and solutions

# MIT 6.001 - SICP - Structure and Interpretation of Computer Programs: Notes and solutions #

This site contains my notes and answers to the exercices of the textbook Structure and Interpretation of Computer Programs, usually just refered to as “SICP”. The book has its origins in the popular MIT’s entry-level com­puter science course “ MIT 6.001 introductory course in computer science” taught by Harold Abelson and Gerald Jay Sussman at the Massachusetts Institute of Technology, starting in 1980.

The second edition of the book, published in 1996, has been licensed under a Creative Commons License by MIT Press and can be downloaded freely (see links at bottom of this page). The videos of the original course have also been made public by MIT. Since the videos are based on the first edition of the book, and I am following the second edition, some discrependency will occure if you follow along.

In my opinion, the strength of the book is in its ability to introduce many fundamental topics in computer science and engineering, in a well organized way.

SICP was revolutionary in many different ways. Most importantly, it dramatically raised the bar for the intellectual content of introductory computer science. Before SICP, the first CS course was almost always entirely filled with learning the details of some programming language. SICP is about standing back from the details to learn big-picture ways to think about the programming process. It focused attention on the central idea of abstraction – finding general patterns from specific problems and building software tools that embody each pattern. It made heavy use of the idea of functions as data, an idea that’s hard to learn initially, but immensely powerful once learned.

These solutions are for reference only. The value of this book is in solving each exercise by oneself. Please consider only checking my solution after being stuck or after having solved the problem yourself.

## Table of Content (based on second edition of the book) #

• ✓ : Solved
• 🔬 : somewhat of a detailed explanation

### Chapter 2: Building Abstractions with Data #

#### 2.2 Hierarchical Data and the Closure Property #

##### 2.2.1 Representing Sequences #
• Exercise 2.17
• Exercise 2.18
• Exercise 2.19
• Exercise 2.20
• Exercise 2.21
• Exercise 2.22
• Exercise 2.23
##### 2.2.2 Hierarchical Structures #
• Exercise 2.24
• Exercise 2.25
• Exercise 2.26
• Exercise 2.27
• Exercise 2.28
• Exercise 2.29
• Exercise 2.30
• Exercise 2.31
• Exercise 2.32
##### 2.2.3 Sequences as Conventional Interfaces #
• Exercise 2.33
• Exercise 2.34
• Exercise 2.35
• Exercise 2.36
• Exercise 2.37
• Exercise 2.38
• Exercise 2.39
• Exercise 2.40
• Exercise 2.41
• Exercise 2.42
• Exercise 2.43
##### 2.2.4 Example: A Picture Language #
• Exercise 2.44
• Exercise 2.45
• Exercise 2.46
• Exercise 2.47
• Exercise 2.48
• Exercise 2.49
• Exercise 2.50
• Exercise 2.51
• Exercise 2.52

#### 2.3 Symbolic Data #

##### 2.3.1 Quotation #
• Exercise 2.53
• Exercise 2.54
• Exercise 2.55
##### 2.3.2 Example: Symbolic Differentiation #
• Exercise 2.56
• Exercise 2.57
• Exercise 2.58
##### 2.3.3 Example: Representing Sets #
• Exercise 2.59
• Exercise 2.60
• Exercise 2.61
• Exercise 2.62
• Exercise 2.63
• Exercise 2.64
• Exercise 2.65
• Exercise 2.66
##### 2.3.4 Example: Huffman Encoding Trees #
• Exercise 2.67
• Exercise 2.68
• Exercise 2.69
• Exercise 2.70
• Exercise 2.71
• Exercise 2.72

#### 2.4 Multiple Representations for Abstract Data #

##### 2.4.3 Data-Directed Programming and Additivity #
• Exercise 2.73
• Exercise 2.74
• Exercise 2.75
• Exercise 2.76
• Exercise 2.77

#### 2.5 Systems with Generic Operations #

##### 2.5.1 Generic Arithmetic Operations #
• Exercise 2.78
• Exercise 2.79
• Exercise 2.80
##### 2.5.2 Combining Data of Different Types #
• Exercise 2.81
• Exercise 2.82
• Exercise 2.83
• Exercise 2.84
• Exercise 2.85
• Exercise 2.86
##### 2.5.3 Example: Symbolic Algebra #
• Exercise 2.87
• Exercise 2.88
• Exercise 2.89
• Exercise 2.90
• Exercise 2.91
• Exercise 2.92
• Exercise 2.93
• Exercise 2.94
• Exercise 2.95
• Exercise 2.96
• Exercise 2.97

### Chapter 3: Modularity, Objects, and State #

• Exercise 3.1
• Exercise 3.2
• Exercise 3.3
• Exercise 3.4
• Exercise 3.5
• Exercise 3.6
• Exercise 3.7
• Exercise 3.8

#### 3.2 The Environment Model of Evaluation #

##### 3.2.3 Frames as the Repository of Local State #
• Exercise 3.9
• Exercise 3.10
##### 3.2.4 Internal Definitions #
• Exercise 3.11

#### 3.3 Modeling with Mutable Data #

##### 3.3.1 Mutable List Structure #
• Exercise 3.12
• Exercise 3.13
• Exercise 3.14
• Exercise 3.15
• Exercise 3.16
• Exercise 3.17
• Exercise 3.18
• Exercise 3.19
• Exercise 3.20
##### 3.3.2 Representing Queues #
• Exercise 3.21
• Exercise 3.22
• Exercise 3.23
##### 3.3.3 Representing Tables #
• Exercise 3.24
• Exercise 3.25
• Exercise 3.26
• Exercise 3.27
##### 3.3.4 A Simulator for Digital Circuits #
• Exercise 3.28
• Exercise 3.29
• Exercise 3.30
• Exercise 3.31
• Exercise 3.32
##### 3.3.5 Propagation of Constraints #
• Exercise 3.33
• Exercise 3.34
• Exercise 3.35
• Exercise 3.36
• Exercise 3.37

#### 3.4 Concurrency: Time Is of the Essence #

##### 3.4.1 The Nature of Time in Concurrent Systems #
• Exercise 3.38
##### 3.4.2 Mechanisms for Controlling Concurrency #
• Exercise 3.39
• Exercise 3.40
• Exercise 3.41
• Exercise 3.42
• Exercise 3.43
• Exercise 3.44
• Exercise 3.45
• Exercise 3.46
• Exercise 3.47
• Exercise 3.48
• Exercise 3.49

#### 3.5 Streams #

##### 3.5.1 Streams Are Delayed Lists #
• Exercise 3.50
• Exercise 3.51
• Exercise 3.52
##### 3.5.2 Infinite Streams #
• Exercise 3.53
• Exercise 3.54
• Exercise 3.55
• Exercise 3.56
• Exercise 3.57
• Exercise 3.58
• Exercise 3.59
• Exercise 3.60
• Exercise 3.61
• Exercise 3.62
##### 3.5.3 Exploiting the Stream Paradigm #
• Exercise 3.63
• Exercise 3.64
• Exercise 3.65
• Exercise 3.66
• Exercise 3.67
• Exercise 3.68
• Exercise 3.69
• Exercise 3.70
• Exercise 3.71
• Exercise 3.72
• Exercise 3.73
• Exercise 3.74
• Exercise 3.75
• Exercise 3.76
##### 3.5.4 Streams and Delayed Evaluation #
• Exercise 3.77
• Exercise 3.78
• Exercise 3.79
• Exercise 3.80
• Exercise 3.81
• Exercise 3.82

### Chapter 4: Metalinguistic Abstraction #

#### 4.1 The Metacircular Evaluator #

• Exercise 4.1
##### 4.1.2 Representing Expressions #
• Exercise 4.2
• Exercise 4.3
• Exercise 4.4
• Exercise 4.5
• Exercise 4.6
• Exercise 4.7
• Exercise 4.8
• Exercise 4.9
• Exercise 4.10
##### 4.1.3 Evaluator Data Structures #
• Exercise 4.11
• Exercise 4.12
• Exercise 4.13
##### 4.1.4 Running the Evaluator as a Program #
• Exercise 4.14
##### 4.1.5 Data as Programs #
• Exercise 4.15
##### 4.1.6 Internal Definitions #
• Exercise 4.16
• Exercise 4.17
• Exercise 4.18
• Exercise 4.19
• Exercise 4.20
• Exercise 4.21
##### 4.1.7 Separating Syntactic Analysis from Execution #
• Exercise 4.22
• Exercise 4.23
• Exercise 4.24

#### 4.2 Variations on a Scheme-Lazy Evaluation #

##### 4.2.1 Normal Order and Applicative Order #
• Exercise 4.25
• Exercise 4.26
##### 4.2.2 An Interpreter with Lazy Evaluation #
• Exercise 4.27
• Exercise 4.28
• Exercise 4.29
• Exercise 4.30
• Exercise 4.31
##### 4.2.3 Streams as Lazy Lists #
• Exercise 4.32
• Exercise 4.33
• Exercise 4.34

#### 4.3 Variations on a Scheme-Nondeterministic Computing #

• Exercise 4.35
• Exercise 4.36
• Exercise 4.37
##### 4.3.2 Examples of Nondeterministic Programs #
• Exercise 4.38
• Exercise 4.39
• Exercise 4.40
• Exercise 4.41
• Exercise 4.42
• Exercise 4.43
• Exercise 4.44
• Exercise 4.45
• Exercise 4.46
• Exercise 4.47
• Exercise 4.48
• Exercise 4.49
##### 4.3.3 Implementing the Amb Evaluator #
• Exercise 4.50
• Exercise 4.51
• Exercise 4.52
• Exercise 4.53
• Exercise 4.54

#### 4.4 Logic Programming #

##### 4.4.1 Deductive Information Retrieval #
• Exercise 4.55
• Exercise 4.56
• Exercise 4.57
• Exercise 4.58
• Exercise 4.59
• Exercise 4.60
• Exercise 4.61
• Exercise 4.62
• Exercise 4.63
##### 4.4.3 Is Logic Programming Mathematical Logic? #
• Exercise 4.64
• Exercise 4.65
• Exercise 4.66
• Exercise 4.67
• Exercise 4.68
• Exercise 4.69
##### 4.4.4 Implementing the Query System #
• Exercise 4.70
• Exercise 4.71
• Exercise 4.72
• Exercise 4.73
• Exercise 4.74
• Exercise 4.75
• Exercise 4.76
• Exercise 4.77
• Exercise 4.78
• Exercise 4.79

### Chapter 5: Computing with Register Machines #

• Exercise 5.1
• Exercise 5.2
• Exercise 5.3
• Exercise 5.4
• Exercise 5.5
• Exercise 5.6

#### 5.2 A Register-Machine Simulator #

• Exercise 5.7
• Exercise 5.8
##### 5.2.3 Generating Execution Procedures for Instructions #
• Exercise 5.9
• Exercise 5.10
• Exercise 5.11
• Exercise 5.12
• Exercise 5.13
##### 5.2.4 Monitoring Machine Performance #
• Exercise 5.14
• Exercise 5.15
• Exercise 5.16
• Exercise 5.17
• Exercise 5.18
• Exercise 5.19

#### 5.3 Storage Allocation and Garbage Collection #

##### 5.3.1 Memory as Vectors #
• Exercise 5.20
• Exercise 5.21
• Exercise 5.22

#### 5.4 The Explicit-Control Evaluator #

##### 5.4.3 Conditionals, Assignments, and Definitions #
• Exercise 5.23
• Exercise 5.24
• Exercise 5.25
##### 5.4.4 Running the Evaluator #
• Exercise 5.26
• Exercise 5.27
• Exercise 5.28
• Exercise 5.29
• Exercise 5.30

#### 5.5 Compilation #

##### 5.5.1 Structure of the Compiler #
• Exercise 5.31
• Exercise 5.32
##### 5.5.5 An Example of Compiled Code #
• Exercise 5.33
• Exercise 5.34
• Exercise 5.35
• Exercise 5.36
• Exercise 5.37
• Exercise 5.38
• Exercise 5.39
• Exercise 5.40
• Exercise 5.41
• Exercise 5.42
• Exercise 5.43
• Exercise 5.44
##### 5.5.7 Interfacing Compiled Code to the Evaluator #
• Exercise 5.45
• Exercise 5.46
• Exercise 5.47
• Exercise 5.48
• Exercise 5.49
• Exercise 5.50
• Exercise 5.51
• Exercise 5.52

## Resources #

### Tools used #

• “It changed the way I look at the fundamental structure of programs. It is possible, and desirable, to write code without assignement statements as much as possible. To not mutate the states of variables. And it forces you to think about software in a very different way. […] I assign now variable less frequently.”
• “[functional programming] forces you to keep your data in much better order. There will always be times when you have to change the state of the system but you do so with a tremendous amount of discipline in this language. You treat the changing of data in the system the way you would treat a transaction on disk.”