Structure and Interpretation of Computer Programs

So, as I said in the previous post, I followed Teach Youserlf Computer Science recommendation and started with SICP. I got mind blown while reading this book.

During our academic life, we read many books, read several other sources, and solve countless exercises, but you always find something that outshines the others and that you will always remember, maybe because you’ve had a great teacher or maybe because the book was great. As I read the book on my own (fair enough, I had a huge help watching Professor Brian Harvey’s lectures), I think it’s mainly the second option.

First of all, the book passed the test of time: the first edition is from 1984, and the second edition was released in 1996. This is an increasingly convincing point to me lately. Things that have true value without needing buzzwords or financial appeal (“read this book/take this course and increase your salary by up to 100% this year”).

The second point, the book is on a topic one step before algorithms, that is, programming languages in general. I got particularly convinced after reading this part of “Why Structure and Interpretation of Computer Programs matters”:

Why? Because SICP is unique in its ability — at least potentially — to alter your fundamental beliefs about computers and programming. Not everybody will experience this. Some will hate the book, others won’t get past the first few pages. But the potential reward makes it worth trying.

It was really worth it.

To be really honest with the book and fully explain what is so impressive about it, I would need to copy and paste it here, which would give me a Copyright Infringement. I follow with my words, definitely not up to those of the authors of SICP.

I will leave some of the greatest ideas found in the book, followed by an explanation and sometimes an aspect not found in the book:

1. Abstraction, abstraction, abstraction: you don’t need too much experience to notice that computer programs grow fast. We always use abstractions to model the problem we are trying to solve, instead of modeling the problem in terms of how our computer works.
2. First-class procedures: procedures can be seen as data, that is, they can be passed as arguments to other procedures, returned from procedures, assigned to variables, or stored in data structures (like being aggregated in pairs)
3. On the other hand, data can be treated as procedures: we use a lot of pairs in the book (cons, car, cdr), but it’s shown that we can actually implement pairs with (you guessed it) procedures! In the book, there’s actually a real implementation of cons, car, and cdr with nothing but lambdas.
4. From 2 and 3 we have that code is data, data is code. Depending on how we face it, there’s no division between them.
5. Recursion: this is a concept that appears several times throughout the whole book, sometimes hidden, sometimes really apparent. It gets in fact really interesting when we are studying interpreters and compilers in chapters 4 and 5. There’s a cool footnote that shows the famous Y-Combinator (not the startup accelerator) and how one can implement recursion in a language with no support for recursion, using only first-class procedures and lambda calculus. It’s fantastic
6. Lambda calculus: the book is definitely not about this topic, nonetheless it was my first time seeing it, and implementing the Y-Combinator on paper was really cool.
7. Normal order, applicative order, and environment model of evaluation.
8. Programming paradigms: functional programming, object-oriented programming, and declarative programming are three paradigms seen in the book. The coolest thing is that you naturally start using functional programming in chapters 1 and 2, then the book presents some problems that would be better modeled if one could set a state to a variable in chapter 3. Enter the concept of environments, local state, and procedures like “set!” (we studied two whole chapters without ever mentioning mutable state!). Then, when you least expect it you start to implement an Object-Oriented Language (the book still doesn’t use this name because it wasn’t in widespread use yet).
9. Functional programming: just like in a mathematical function, every time you give the same value as an argument to a procedure, it should always return the same output.
10. Object-oriented programming: only in the third chapter will we have enough tools to implement an object-oriented language. Those tools are message passing, local state, and inheritance. It will give you miles of a head start when you study an object-oriented language like Python, Java, or C++ because there are dozens of exercises where you draw environment diagrams with procedures, variables, inheritances, etc.
11. Parallelism: introduces several problems that arise when we have multiple processors sharing the same resources, or several inputs/outputs in an operating system, and some of the mechanisms used to get around the problems: atomic operations, which execute a query AND change the state of a variable without interruptions; the mutex, which defines the critical sections of the code, that is, the ones that cannot be interrupted otherwise they would generate errors in the state of variables, and these errors are very difficult to detect and debug; and serializers, a mechanism that guarantees that two procedures using the same resources will not have their instructions interleaved, generating errors.
12. Deadlock: imagine two processes that share the same resources, for example in banking. Process 1 will be a wire transfer from account A to B will be and process 2 a wire transfer from account B to A. The execution may never terminate (it will be in a deadlock) because process 1 acquired the balance of account A and process 2 acquired the balance of account B. When process 1 tries to acquire the balance of account B, it will be protected by process 2. At the same time, when process 2 tries to acquire the balance of account A, it will be protected by process 1. There are several techniques to avoid deadlocks (for example using the underlying hardware and/or operational system).
13. Streams: introduced as a new data structure, with an advantage over variables with mutable state: they can represent infinite sequences (it was here that my mind was blown for the first time in the book). In a normal pair, we have the first element, the car, and the second element, the cdr. In a stream, we also have the car, but the cdr is a promise to compute the remaining elements. There’s literally a delay on the cdr, and that element is only computed if we force it to be computed. Streams are useful because you can implement a procedure that is easier to read and still computationally efficient.
14. Memoization: also seen when I studied Data Structures and Algorithms, memoization is a technique used to avoid computing the same term over and over again when facing some recursions (a classical example is Fibonacci). It’s said that Dynamic Programming is the Divide and Conquer method plus a table to store values.
15. Interpreters: in chapters 4 and 5 we start to learn about evaluators, how the code that we write is interpreted by the machine, “who” does it, and “how” it’s done. There’s a big idea here, that “The evaluator, which determines the meaning of expressions in a programming language, is just another program.”, and that we can write an evaluator for a certain language using that same language (I learned that this is called bootstrapping when studying compilers). We use all these concepts to create new languages, with ideas and goals very different from the original language we were using, suitable for the problems we want to solve.
16. Compilers: while on interpreters the machine language is “elevated” to the level of the language we are using to write our code, the strategy with compilers is the other way around, that is, it “lowers” our code to the level of machine language. This way several optimizations in the code can be done, typically increasing the speed of the final product. But I need to study compilers to fully understand this.

I think the main idea is that programming languages are meant to make the programs we write reflect the problem we are dealing with, not how computers work.

Thank you for reading!

Three reviews on SICP that I like:

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 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.

Brian Harvey: Why Structure and Interpretation of Computer Programs matters

https://www.quora.com/Whats-so-great-about-SICP

Uncle Bob: https://www.youtube.com/watch?v=Z0VpFmp_q4A