Notes on Structure and Interpretation of Computer Programs.
I bought Structure and Interpretation of Computer Programs almost ten years ago. Folks reassured me it a great work, and I wanted to love it. Since then, I’ve started working through the book roughly a dozen times, but never got far. The early content was too familiar to hold my attention, and the later content was inscrutable because I hadn’t done the earlier content to learn [Scheme](https://en.wikipedia.org/wiki/Scheme_(programming_language).
Over the holidays, I finally worked through the book, and am glad I did. In some places the authors' appreciation for tangents leads them towards more complex teaching examples than strictly necessary, but I learned a bunch during my reading, despite having studied most of the topics to some extent previously.
There’s too much content to take notes on everything, but here I’ve written up some bits that I found particularly elegant or interesting.
I worked through the book used emacs with scheme-mode and mit-scheme, which Iinstalled via
brew install mit-scheme. Overall, that toolkit worked quite well for me, and left me nostalgic for writing Steel Bank Common Lisp using SLIME in college.
As someone who came into programming through object oriented languages (Java, Python), stateful functions are an odd idea. As the concept sunk in, it started to gel for me that stateful functions are a fundamental that can be extended to implement objects.
The canonical example is to create an accumulator function that tracks the sum of all
parameters every passed to it. Here is the Scheme implementation
make-accumulator, which creates an anonymous function using the
starting parameter is then bound in the lambda’s scope, and becomes its privatelocal state.
(define (make-accumulator starting) (lambda (incr) (begin (set! starting (+ starting incr)) starting)))
starting is shared by all invocations to a given anonymous function, but is not
shared across lambdas created by
make-accumulator. Each lambda has its own private state,
which enables this behavior:
(define a (make-accumulator 0)) (a 1) ;Value: 1 (a 100) ;Value: 101 (define b (make-accumulator 10)) (b 1) ;Value: 11 (b 1) ;Value: 12 (b 5) ;Value: 17
This was a particularly powerful example for me as I first learned to program in Python, and the obvious translation of this program into Python2 doesn’t work.
def make_accumulator(amt): def update(incr): amt = amt + incr return amt return update a = make_accumulator(0) print a(5) print a(10)
That seems like it ought to do the same thing, but instead it throws this error:
Traceback (most recent call last): File "tmp.py", line 9, in
print a(5) File "tmp.py", line 4, in update amt = amt + incr UnboundLocalError: local variable 'amt' referenced before assignment
Python3 introduces nonlocal which makes this possible!
def make_accumulator(amt): def update(incr): nonlocal amt amt = amt + incr return amt return update a = make_accumulator(0) b = make_accumulator(100) print(('a', a(5))) print(('b', b(1))) print(('a', a(10))) print(('b', b(1000)))
Which gives the expected output:
('a', 5) ('b', 101) ('a', 15) ('b', 1101)
It’s still quite awkward to use the
nonlocal statement, but it’s possible which is exciting,
particularly in the context of using Python as a teaching and learning language.
If we’re looking to build a simple implementation of an object oriented language and have stateful functions, then we’re only missing one other ingredient: message passing. Message passing is the idea of sending a message to an object and allowing the object to determine how to handle it.
Consider this Python code:
class Animal: def speak(self): return "generic-animal-noise" a = Animal() a.speak()
When we call
a.speak(), we’re sending a message–in this case
speak–to the object
a and then
asking it to respond in a reasonable way. How would we handle this if we only had stateful functions
instead of a fully developed object system?
Something like this:
(define (make-account balance) (lambda (msg amt) (cond ((eq? msg 'deposit) (begin (set! balance (+ balance amt)) balance)) ((eq? msg 'withdraw) (begin (set! balance (- balance amt)) balance))))) (define act (make-account 100)) ;Value: act (act 'deposit 10) ;Value: 110 (act 'deposit 10) ;Value: 120 (act 'withdraw 50) ;Value: 70
This is a contrived example, but shows a working example of a very simple dispatch mechanism that allows our humble functions to start to behave very similarly indeed to objects.
One awkward limitation here is that it requires all messages have the same number of paramaters, one work around would be returning functions in response to messages:
(define (make-account balance) (lambda (msg) (cond ((eq? msg 'deposit) (lambda (amt) (begin (set! balance (+ balance amt)) balance))) ((eq? msg 'withdraw) (lambda (amt) (begin (set! balance (- balance amt)) balance)))))) (define act (make-account 100)) ;Value: act ((act 'deposit) 10) ;Value: 110 ((act 'withdraw) 100) ;Value: 10
This gives us a great deal of flexibility to handle different messages however we want. It does, however, start getting a bit scary just how dynamic everything is getting here. A bit too open ended?
Thinking about atypical object systems made me want to find an excellent introduction to Smalltalk, and also reminded me a bit of the Common Lisp Object System, colloquially CLOS, which has some neat ideas, particularly around generic functions.
Code as data
One of the most interesting ideas in software is programs which write or modify other programs. These kinds of meta-programs are a defining feature for Lisp languages, typically in their macro implementation. (For more on macros specifically, it’s interesting to read a bit about how different Lisps approach them: Scheme macros, Clojure macros, Common Lisp macros.)
However, to get started with software-modifying software, you don’t need to go all the ways
into macros, all you need is quote,
indicated by a leading single quote or
quote, for example these are equivalent:
(quote (+ 5 10)) (define a '(+ 5 10))
Once you’ve quoted an expression, you can then modify it
as if it were any other piece of data, for example
replacing addition with subtraction, and can use
eval to run that quoted code (
eval requires an environment
to run the evaluation within, and the-environment
is one way to get the current environment):
(define x (quote (+ 5 10))) (eval x (the-environment)) ;Value: 15 (car x) ;Value: + (cdr x) ;Value 25: (5 10) (define y (cons - (cdr x))) (eval y (the-environment)) ;Value: -5
This is simple, but the implications are powerful. Earlier this year I wrote an article on refactoring programmatically in Ruby, but that worked by rewriting source files, whereas this works while the program is running.
Interestingly, when you do abstract-syntax-tree (AST) refactoring in other languages, like what’s described in Google’s Large-Scale Automated Refactoring Using ClangMR, underneath the hood things are operating on s-expressions, which are basically representing those languages syntax as Lisp!
Most languages support some kind of
eval, but typically those just operate on a string like in Python:
>>> eval("5 + 4") 9
Because Lisp is just lists and you can modify those lists, the Lisp version of eval is much more useful, because you have access to the full syntax, not just an unstructured string.
Writing an interpreter
One of the really neat things that book does is
work through writing a working Scheme interpreter
from in Scheme, which is greatly simplified thanks
quote and code-as-data behavior.
For example, we could start by writing our own version of the
function that initially only handles self-evaluating primitives and if expressions
(otherwise it hands off evaluation to Scheme’s
(define (if? exp) (eq? (car exp) (quote if)) (define (true? exp) (eq? #t exp)) (define (self-evaluating? exp) (cond ((number? exp) #t) ((string? exp) #t) (else #f))) (define (eval-if exp env) (let ((predicate (cadr x)) (true-branch (caddr x)) (false-branch (cadddr x))) (if (true? (eval2 predicate env)) (eval2 true-branch env) (eval2 false-branch env)))) (define (eval2 exp env) (cond ((self-evaluating? exp) exp) ((if? exp) (eval-if exp env)) (else (eval exp env))))
From there we would use our simple evaluator via:
(define x (quote (if (= 5 10) 5 10))) (eval2 x (the-environment)) ;Value: 10
This core is then extended over and over until it can handle the full Scheme
language without resorting to calling
eval. This incremental approach is powerful,
because it lets you test and learn along the way without having to have the entire
More than just handling Scheme, this section goes on to explore different ways this can be modified to support different properties like lazy evaluation.
Where some books would teach some assembly code to explain how higher-level languages
are translated into lower-level langauges, SICP instead goes with a language of assembly-like
Scheme functions such as
This leads to programs that look like:
(controller test-b (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done)
This is a fairly readable, reasonable approach, with the added benefit of then being able
to implement each of those functions like
op, which is time better learning than
struggling to install a weird MIPs simulator.
My closing though is to simply be amazed at how many interesting ideas they managed to cram into a fairly short six-hundred pages, and managed to do it without assuming much prerequisite knowledge for folks reading the book. A big part of their ability to do so much is Scheme itself, which is exceptionally unencumbered tool to extend.
Scheme’s brevity is also a significant asset. Despite covering so much ground, there isn’t a huge volume of code to read or write while working through the book. There was more thinking and less typing than I initially expected.
The trend towards more practical education is a good one, and teaching folks languages like Python and Java–languages they’re likely to use in the workplace–is generally a good trend. Developing proficiency there will be directly useful in a way that understanding the pieces under the hood simply isn’t for most modern software development. That said, I think it’s really helpful for folks, perhaps later in their career, to spend some time with books like SICP, which peel back the layers of magic into something that you can reasonable about.
After working through SICP, some topics I want to learn more about this year are (book suggestions are extremely welcome):
- Smalltalk - the origin, implementation and usage of Smalltalk
- Type systems - sounds like Practical Foundations for Programming Languages is a good starting place?
- Compilers - Engineering a Compiler is staring at me from my shelf, maybe this is to year to actually open it