Simple Programming in Binary: Binary Combinatory Logic

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.

1. S=λx y z.x z (y z)
2. K=λx.(λy.x)
3. 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:

1. "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).
2. "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.