I had started with SICP (Structure and Interpretation of Computer Programs) some time early last year. I had read through one and a half chapters and then stopped because it felt too mathematical and I didn’t know what I was getting from it. Then later that year, I attended Lambda Retreat, conducted by Anand, who is my colleague and has found SICP to be quite profound himself.
It changed the way I think about programs, added new perspective, and got me interested in the design and implementation of programming languages. I have heard varied opinions from people who have read this SICP. Some feel that it is overrated and for some it changes how they think about programs.
To some extent, it was the latter for me. This post highlights what I had to take away from the book that was positive for me.
Controlling complexity with abstractions
This, and the following point, were the biggest take aways for me. It started with the
exercise problem on Ackermann function.
First I tried simplifying it the dumb way by expanding all the values. I noticed a pattern building up but it took a while to see what it
was doing. The expansions were getting harder and harder for higher values of the first argument. Then I abstracted out A(m-1, n) as a
function f(n) and it was straightforward after that.
Abstractions play a big role in the cognitive complexity of something. It would have taken a very long time for me to see the pattern if I had not created this abstraction. We encounter this all the time in programming. If we don’t keep two simple chunks separate from one another, they form one big complex thing. Next time we want to make a change to this monstrosity, we have to wade through the details and redo all the thinking that we did the first time.
Building composable software with layers of abstraction
Any non-trivial software will have layers to it. For example, a database system could have a file system layer, an engine layer, and a user interface layer. If we want to add a new operation to the engine, we shouldn’t have to implement something at the file system layer. It is much better if we can re-use some part of the existing file system operations in our new operation. This way we don’t have to switch contexts between the engine logic and the details of file system manipulation. It is easier to focus only on one.
+--------------+
| interface |
+--------------+
| engine |
+--------------+
| filesystem |
+--------------+
This is only possible if our software doesn’t have circular dependencies between layers. An explicit choice has to be made so that our file system layer logic is limited in scope only to file system level manipulations. It shouldn’t implement procedures that are specially meant to perform everything that engine operation X will do. It should rather be the responsibility of the engine level code to pick the right tools from the file system layer and build its logic.
For example, an insert operation in the engine might need to 1) find the right place to write the new contents, 2) serialize data into
that format, 3) write it there. The file system part should provide an API to do 1 and 3 separately, rather than combining the logic of
all three into one single procedure.
That way, each procedure has one responsibility and the dependency is well-defined. The same file system primitives can also be re-used to implement other operations. We don’t think of the specific logic in the engine layer when writing logic in the file system layer. We build primitives that any engine-level operation could use.
SICP looks at this in a more programming languages oriented manner. In any programming language, there are three parts: primitives, means of abstraction, and means of combination. Each layer of abstraction should, in a way, provide these things to the next layer of abstraction.
Eval-Apply: the wizardry of the wizard book
The cover image of SICP shows a wizard holding the eval-apply globe. It is how programming is done. Evaluation happens as a combination of applications, and applications happens as a combination of evaluations. Application refers to the application of functions, and evaluation refers to the evaluation of primitive statements. Combination happens through application of functions. That the core of programming can be described with only two procedures is mind-blowing.
Function application is a two step process: evaluate the parameters, and then evaluate the body with the obtained values as arguments. Evaluation is a series of applications.
By the end of the book, when I had implemented the evaluator, it felt very simple. A whole programming languages implemented with only some functions. I think the implementation seemed simple because we were guided through building good abstractions and layers of abstractions in a bottom-up manner. Doing the same thing without that context would have been much more complicated. It shows the power of breaking down the problem in terms of primitives, the means of combination, and the layers of abstractions.