SICP: The Closure in the Grass

I was working my way through SICP last night when I came across a passage that at first struck me as curious, then interesting, then deeply interesting, and finally a little mind-blowing. Out of this little passage I got a little slice of enlightenment about first-order data, how Lisp can be rewritten in Lisp, domain-specific languages, how duck typing works, message-passing, and, finally, the clearest explanation and demonstration of a closed procedure that I have ever seen.

The passage addresses the question of complex data representations. If one establishes a satisfactory contract between the necessary constructor and selectors for a data representation, and if an implementation of that data representation can be shown to uphold that contract, then the details of the implementation don’t matter a bit.

That is certainly not controversial in the least. But Lisp’s treatment of procedures as first-class data allows for some surprising implementations. The particular items being re-implemented caught my attention too. Here is the code from the book, section 2.1.3:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
            ((= m 1) y)
            (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

Yeah, that code re-implements cons, car, and cdr. And instead of returning a pair, this cons returns a procedure, named “dispatch” within the definition of cons. The name “dispatch” is just for our convenience. It could have just as easily been created as an anonymous procedure with (lambda ...).

A cons that doesn’t return a pair? How can that work? Well, what’s the contract that these procedures have to apply?

if (cons a b) => c
then (car c) => a
and (cdr c) => b

The re-implemented car and cdr take a procedure and apply it to a constant number, 0 or 1. If we define a variable c by passing a and b to cons, the procedure that has been labeled “dispatch” is what is returned for c. When we pass c to car and cdr, these call “dispatch” with a 0 or a 1, and that in turn returns a or b. The contract is upheld. It works.

What the book has to say about this:

This may seem a curiosity now, but procedural representations of data will play a central role in our programming repertoire. This style of programming is often called message passing, and we will be using it as a basic tool in chapter 3 when we address the issues of modeling and simulation.

— 2.1.3 What Is Meant by Data?

I have a few things to add.

  1. We can re-implement cons car and cdr in Scheme. Wow. It’s shocking to see a re-implementation of something so primitive to the language. But it drives home another point. As fundamental to Scheme as these procedures feel, they are still “only” abstractions.
  2. cons, car, and cdr are basic procedures that act on and build data. They are fundamental to Scheme’s recursive properties. If we can implement these easily in Scheme, it points to the possibility of creating all kinds of similar basic, fundamental abstractions and using them to construct all kinds of little languages. Here is the root of domain-specific languages.
  3. Talk about duck typing. The arguments passed to car and cdr don’t have to be lists or pairs. In fact, they could be any data type that upholds the contract. A lot has been written about design-by-contract. Here is an eloquent expression of it in a few lines of code. Scheme’s rules of rewriting make this possible. Scheme will substitute a process for a variable and evaluate it appropriately just as easily as it will substitute a list for the variable and proceed accordingly.
  4. “Message passing,” eh? That’s the basis of object-oriented programming, among other things, isn’t it?
  5. Finally, this is the best, clearest explanation and demonstration of a closure that I have ever seen! Where does the information passed to cons go? It essentially gets written into the dispatch procedure. And that procedure, first-class citizen of Scheme that it is, will wait until it is called, like a jack-in-the-box primed to pop up with our desired values. I really wasn’t expecting such an excellent example and explanation in one — I nearly tripped over it, like a snake in the grass.