march 2017

The Programmer’s Ring

Stumbling upon the ritual of the calling of an engineer, and the associated engineer’s ring, I figured we programmers should have something similar. There’s already an oath, which I endorse, though I’d like more poetry.

I don’t know of any ring however, so I designed one. The material or exact shape aren’t too important, but I needed some kind of logo or formula that would represent programming or computers. I ended up choosing the iota combinator, a small Turing Complete function. The notation is derived from the lambda calculus, modified for conciseness and clarity:

[0 [[[2 0 (1 0)]]] [[1]] ]

Here’s the result on my ring:

It’s stainless steel, laser engraved, custom made by a machinist. I wear it on the middle finger of my dominant hand.

Why not the famous Y combinator?

The Y combinator is the obvious candidate. It’s small, famous, and even used for tattoos. I could have just used this:

Y = λf. (λx. f (x x)) λx. f (x x)

This wasn’t ideal, though.

First, the Y combinator is strongly associated with recursion, functional programming, and Lisp. We need a formula that embodies everything.

Second, the notation itself is a bit noisy. For instance, the symmetry of the Y combinator, the repetition of λx. f (x x), is hard to spot at a glance. We need a notation that can be read at a glance (at least for small formulas).

The iota combinator

The formula I wanted came from the SKI combinator calculus. It’s a Turing complete system that works with only two functions (only S and K are really needed):

S = λxyz. x z (y z)
K = λxy. x
I = λx. x

We could just put S an K side by side, but that would make two formulas, and I’d rather have “one formula to program them all”. Fortunately, there is such a formula: the iota combinator. It’s Turing complete by itself, and used as the sole operation in some esoteric languages. Here:

i = λx. x S K
i = λx. x (λxyz. x z (y z)) λxy. x

Now there’s still this noisy notation.

De Bruijn indices

The lambda calculus lets us name variables however we like:

i = λx. x (λxyz. x z (y z)) λxy. x
i = λa. a (λabc. a c (b c)) λab. a

This redundancy make formulas more verbose than they has to be, and precludes canonical representations: even after being fully evaluated down to their normal form, expressions still have several representations.

So I tried de Bruijn indices. With them, variables are not referenced by name, but by stack offset: the last variable is accessed with the number 0, the second last with the number 1, and so on (the Wikipedia page starts at one, but we programmers count from zero).

  |      De Bruijn indices      |        Lambda calculus         |
--+-----------------------------+--------------------------------+
S | λλλ. 2 0 (1 0)              | λxyz. x z (y z)                |
K | λλ. 1                       | λxy. x                         |
I | λ. 0                        | λx. x                          |
Y | λ. (λ. 1 (0 0)) λ. 1 (0 0)  | λf. (λx. f (x x)) λx. f (x x)  |
i | λ. 0 (λλλ. 2 0 (1 0)) λλ. 1 | λx. x (λxyz. x z (y z)) λxy. x |

Now expressions have only one normal form, and the notation is more concise. Still, this lacks symmetry, and the overall structure is hard to assess at a glance. So I figured, how about using delimiters instead of “λ”? I settled with the square bracket:

S = [[[2 0 (1 0)]]]
K = [[1]]
I = [0]
Y = [ [1 (0 0)] [1 (0 0)] ]
i = [0 [[[2 0 (1 0)]]] [[1]] ]

Your mileage may vary, but this is by far my preferred notation:

• The symmetry of the Y combinator is now obvious.
• We can easily see where functions end.
• How the S and K combinator form the iota combinator is now obvious.
• We can group brackets together for readability.

Why

This is not just about having a cool trinket I can brag about in parties. There’s a deeper meaning.

First, understanding the formula and the notation requires a bit of fundamental knowledge —functions, and call stack. This could serve as a filter: if you can’t understand functions or the call stack, you probably can’t program.

Second, simplicity is hard. We often reach for the obvious solution instead of the simple one. This ring can remind us that we can do much with little: if something feels too complex, it probably is.