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)
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:
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.