Notes on Structure and Interpretation of Computer Programs.

programming (1), review (14), book (19)

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.

Stateful functions

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 of make-accumulator, which creates an anonymous function using the lambda function. 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)))

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

Message passing

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 to Scheme’s quote and code-as-data behavior.

For example, we could start by writing our own version of the eval function that initially only handles self-evaluating primitives and if expressions (otherwise it hands off evaluation to Scheme’s eval):

(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 intrepreter complete.

More than just handling Scheme, this section goes on to explore different ways this can be modified to support different properties like lazy evaluation.

Register machines

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 test, branch and goto.

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 reg and 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):