Recently at the Lambda Lounge, we spun up a study group for the classic text Structure and Interpretation of Computer Programs (aka SICP) – thanks to Ken Sipe for the push! For many years this text was used for the introductory course at MIT (and other institutions).
I read SICP in my first CS class at University of Illinois in 1992. At the time, I remember it being shockingly, weirdly different than everything I expected. Prior to college, I’d had several years of Logo, several years of Basic, and 4-5 years of Turbo Pascal, mostly self-taught. I thought I kind of knew what programming was but I had never been “taught” programming in any meaningful way. Being introduced to Scheme and starting from such a basic level was so different than everything I’d done up till then that I actually wondered (for probably the first time since I’d seen a computer) whether this was my calling.
That shock faded of course as the semester went on, and I found other friends to work through things with, and as I took further classes (mostly using C and C++). I still have great fondness for those sometimes hard hours puzzling through the harder parts of SICP (often using Scheme on NeXT machines till the labs closed at 3 am).
As I re-read SICP now I see how valuable and basic the concepts are and how important they still are to me every day as a programmer. Chapter 1 alone covers: how languages are built from primitives, combination, and abstraction; recursion vs iteration; black box abstraction; time and space complexity of a running process; functions as first-class objects; naming and scopes. Oh, and also teaches you all the basics of Lisp, sufficient to do most numeric computing. That’s chapter 1!
Take this section for example:
One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.
This was published 26 years ago, but we are still today talking about tail recursion and tail call optimization (TCO) as a feature of importance in the JVM for functional programming. What tail recursion is, how it affects the time and space complexity of programs, how it is implemented (and whether it’s implemented) are all critical things for programmers in any modern language to understand. Languages like Java, Clojure, Scala, Ruby, etc all make different and sometimes subtle choices about how these issues and they are important, far more important than whether you need a “;” at the end of a line or whatever other syntax.
I was particularly struck during watching the first video from the Abelson and Sussman lectures as he talked about the three big themes of the course:
- Techniques for controlling complexity
- Black box abstraction
- Meta-linguistic abstraction
If you were going to pick any 3 big themes, those seem like pretty good ones to me. Our languages and tools today have come awfully far but we’re still trying to figure out the best way to do those. If you’re interested in programming and you haven’t read SICP, I really recommend it – it’s worth your time if you are serious about programming as a craft and an art.