For reasons that I’ll explain in another post, I don’t have a lot of time for writing a long pathological programming post, so I’m going to hit you with something short, sweet, and beautiful: binary combinatory logic.

I’ve written in the past about lambda calculus, and it’s equivalent variable-free form, the SKI combinator calculus. I’ve ever written about other combinator calculus based languages, like Unlambda and Iota.

Binary combinatory logic, aka BCL, is a language based on SKI calculus – except that it encodes the entire thing into binary. Two characters, plus two rewrite rules, and that’s it – a complete

combinator calculus based programming language.

SKI combinator calculus is a simple variable-free calculus with three constructs: S, K, and I; and I isn’t really primitive, but can be defined in terms of S and K.

- S=λx y z.x z (y z)
- K=λx.(λy.x)
- I=λx.x=SKK

So, in BCL, S is written “01”; K is written “00”. And there are two rewrite rules, which basically define “1” without a zero prefix as a a paren-like grouping construct:

- “1100xy”, where “x” and “y” are valid BCL terms (that is, complete syntactic units),

gets rewritten to be “x”. If you follow that through, that means that it reduces to ((Kx)y).
- “11101xzy” gets rewritten to “11xz1yz”. Again, following it through, and that

reduces out to “(((Sx)y)z)”.

So, following on unlambda’s method of handling IO, “hello world” in BCL is:

010001101000010000010110000000000101101111
000010110111110011111111011110000010011010

And here’s the really neat thing. Write an interpreter for BCL in BCL. Take the bit string that results, and convert it to a bitmap. That’s what’s over the right here. So, for example, the first line is “1111100000111001”; keep going, and you’ll find the entire BCL interpreter.

### Like this:

Like Loading...