RC24. Lisp Black Magic

Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023

I thought I’d regained my balance and overcome my recent bout of Lisp-induced vertigo, but after today’s meeting of Group SICP I’m about ready to puke.

Back to cons

Here’s where we left off, just this side of the abyss:

(define (cons a b)
  (lambda (pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))

(define (car x) (x 1))

(define (cdr x) (x 2))

There we were, losing touch with reality, teetering on the brink of madness, grasping desperately at parameters a and b which had vanished before our very eyes only to be replaced with an incantation. But at the last moment, vision blotting out and prepared to surrender to the abyss, we discovered that a and b hadn’t really disappeared at all but had become, like a lock of hair or personal memento, an ingredient from which a specter could be conjured.

That’s because when we define a pair of a and b using this new implementation of cons, what we in fact get is not some piece of paired data but a procedure with a single formal parameter, pick. If we then apply car to our pair, what we are doing is passing the argument 1 to the procedure that is the pair, which in turn spits out the value a which had been hard-coded into the procedure that is the pair. Same situation with cdr, except here we are passing 2 to the pair object/procedure thing, which returns the value b.

I can’t take it!

Ah, stability regained. Our worldview was briefly disturbed, but ultimately this bit of conjuring could be reconciled with our mental model.

Not for long. When reading through SICP, I skipped over this next part, happy to sustain the delusion that I was standing on solid ground. But in our group meeting it became the crushing subject of discussion:

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

So zero is a procedure . . . that returns a procedure that takes one argument ‘f’ . . . that returns a procedure that takes one argument ‘x’ and returns that argument. And add-1 is a procedure that takes one argument n . . . that returns a procedure taking an argument f . . . that returns a procedure taking argument x . . . that returns f applied to . . . . . . . . . . . . . ? ? ?

Meanwhile, Profs. Abelson and Sussman are asking us to go ahead and define one and two directly. Be warned, they say, this exercise is “mind-boggling,” but… I’ve already fallen headlong into the abyss.

This abyss, I learned from my SICP groupmates (two of whom, mercifully, are mathematicians), is what’s known as the \(\lambda \text{ Calculus}\). I won’t bother trying to explain here what I am in no position to explain to anyone. However, what I have come to understand about the Lambda Calculus is that is offers a way to circumvent numbers via procedures, or functions, alone. And indeed what is not mind-boggling but brain-exploding about the above procedures for one and add-1 is that, unlike the implemtation of cons above, numbers are nowhere to be found. They have evaporated like the apparitions it turns out they in fact are.

Groping for zero-ness

Things are a little weird here, but it’s possible to orient oneself.

First of all, this zero procedure:

(define zero (lambda (f) (lambda (x) x)))

I think my particular difficulty is with parsing anonymous lambda functions, which remain somewhat illegible to me. All the same, let’s try.

• zero is a procedure
• which returns another procedure (lambda (f))
• which returns another procedure (lambda (x))
• which returns its parameter x, as is

Let’s say we have a procedure f. Here’s how the expansion would look if we pass f to zero:

(zero f); => (lambda (x) x) => x

What’s interesting about zero, then, is that it takes a procedure f and returns a procedure lambda (x) x. In other words, it sort of just ignores the f procedure altogether and returns x.

Let’s make a few additional simple procedures to work with

(define (identity x) x)
(define (inc x) (+ 1 x))
(define (square x) (* x x))

and then expand some more concrete examples:

(zero identity) ; => (lambda (x) x)

(zero inc)      ; => (lambda (x) x)

(zero square)   ; => (lambda (x) x)

Regardless of what procedure we give to zero, it returns a “zeroed-out” identity procedure.

If we want to delude ourselves into thinking we’re standing on solid ground, we can pass some concrete numbers, as well, to see how things evaluate:

1 ]=> ((zero identity) 5)

;Value: 5

1 ]=> ((zero inc) 5)

;Value: 5

1 ]=> ((zero square) 5)

;Value: 5

What is being “zeroed out”, then – this will become clear in a moment – is the number of times f (here identity, inc, and square) is applied. Here, f is applied zero times to x.

Groping for one-ness

Okay, so let’s do what the profs suggest and expand (add-1 zero).

(add-1 zero)
; => (lambda (f) (lambda (x) (f ((zero f) x))))
; => (lambda (f) (lambda (x) (f x)))

Applying add-1 to zero returns

• a procedure that takes a single parameter f (another procedure)
• which returns a procedure that takes a single parameter x (a value)
• which returns something like f of zero of f of x

But what’s cool is that ((zero f) x), as we know, expands to x, which means that (add-1 zero) effectively returns f(x).

As such, we should be able to define one as follows:

(define one
  (lambda (f) (lambda (x) (f x))))

And, hey, isn’t that interesting? What’s one-ish about one is that we are now applying f to x one time.

Interesting. I think I can guess what may happen if we apply add-1 to one in that case:

(add-1 one)
; => (lambda (f) (lambda (x) (f ((one f) x))))
; => (lambda (f) (lambda (x) (f (f x))))

((one f) x) above will, according to our definition of one, return (lambda (x) (f x)), which is why we can expand it to (f x). And what do you know? We’ve added one to one and now we have something distinctly two-ish going on here – namely f is being applied twice, since what (add-1 one) returns is effectively (f (f x)) in scheme syntax, or \(f(f(x))\) if we want something more recognizably math-y.

If we wanted, we could go ahead and define two in a similar fashion:

(define two
  (lambda (f) (lambda (x) (f (f x)))))

Let’s do some examples now, passing procedures like identity, inc, and square to one and two along with some values so we can again delude ourselves into thinking we’re on solid ground and we can go about our lives as if nothing has changed.

1 ]=> ((zero identity) 5)

;Value: 5

1 ]=> ((one identity) 5)

;Value: 5

1 ]=> ((two identity) 5)

;Value: 5

1 ]=> (((add-1 two) identity) 5) 

;Value: 5

This isn’t particularly revealing, since the result in each case is 5 – as we would expect, since the identity function applied n times to x will still be x.

But let’s try it with inc, a procedure that increments its argument by one.

1 ]=> ((zero inc) 5)

;Value: 5

1 ]=> ((one inc) 5)

;Value: 6

1 ]=> ((two inc) 5)

;Value: 7

1 ]=> (((add-1 two) inc) 5)

;Value: 8

As we are beginning to see,

• what’s zero-ish about zero is that it applies inc to 5 zero times
• what’s one-ish about one is that it applies inc to 5 one time
• what’s two-ish about two is that it applies inc to 5 two times
• what’s three-ish about (add-1 two) is that it applies inc to 5 three times

It gets even more interesting with square:

1 ]=> ((zero square) 2)

;Value: 2

1 ]=> ((one square) 2)

;Value: 4

1 ]=> ((two square) 2)

;Value: 16

1 ]=> (((add-1 two) square) 2)

;Value: 256

See a pattern?

• zero applies square to 2 zero times => \(2\)
• one applies square to 2 one time => \(2^{2} = 4\)
• two applies square to 2 two times => \(2^{2^{2}} - 16\)
• (add-1 two) applies square to 2 three times => \(2^{2^{2^{2}}} = 256\)

All that is solid melts into air

What’s happened here (at the risk of being redundant – I’m still attempting to convince myself that this is true) is that numbers are no longer treated as concrete, stable things. Instead they are, if anything, something like the residue of a process, the byproduct of an action. Not a count of things but the very activity of counting. Zero-ness is doing something or applying it zero times, one-ness is doing something once, two-ness is doing it twice, three-ness is doing it three times. Adding, has always struck me as an action, but here adding operates not on numbers but on the act of counting. My groupmates hinted that subtraction and multiplication and division are possible. I suppose multiplication is intuitive enough, but division and subtraction seem a bit thornier.

There’s something, then, that is very in potentia about numbers conceived not as data but as procedures and functions. They are not objectively and concretely there, as it were, but they emerge and materialize through an activity. Which, my groupmates pointed out, is pretty much accurate. Since numbers, of course, aren’t concrete things at all, are they? They’re concepts that stand in for counting. And with that we return to the main crux of this phase of SICP, which is that data and procedures are ultimately somewhat indistinguishable from one another.

When Marx wrote that “All that is solid melts into air, all that is holy is profaned, and man is at last compelled to face with sober senses his real conditions of life,” what he meant was that the rise of the bourgeoisie had utterly upended a social order that had been unchanged through most of human history, and that moreover it did so in such a way as to make possible the conditions for an eventual revolution. What was “solid”, in other words, was that seemingly unchanging and universal order which, as the rise of the bourgeoisie made evident, was actually not so solid after all. Needless to say, invoking Marx in this context is hyperbolic, to say the least. But, in its own little way, SICP has risen amidst the order that has been my worldview, and suddenly the solid ground I took for granted is, well, it’s sublimating, damn it!

Other things

• motivating coffee chat in the AM with yet another recurser I hadn’t met yet
• SICP study group that rocked my world and led to this here blog entry
• Data Disco where I started parsing Twin Peaks screenplays while watching another Data Disco-er work on an image classifier project
• Went to Weekly presentations, great to see everyone’s progress
• Paired on K&R and made great progress there on another text processing problem
• started thinking more concretely about Implementing DNS in a weekend as a quick project idea