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:

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.

Keith:
True. Wonder if I can find an SKI version of DeCSS code. Then I could translate it into BCL, and incorporate the “illegal” bitmap into the sidebar.

Its funny, but this BCL make more sense to me somehow than SKI itself. I always feel like the notation gets in the way with all of the stuff that has descended from Church. It just doesn’t click for me – I keep thinking it looks ugly, so it becomes hard for me to try to uhm… internalize it. Even ugly things like regular expressions I eventually get in some subtle way, but I always have to work step by step though these kinds of things.

KeithBAnd, if you convert the DVD descrambling code into BCL and make a picture, you have an illegal picture.

Mark C. Chu-CarrollKeith:

True. Wonder if I can find an SKI version of DeCSS code. Then I could translate it into BCL, and incorporate the “illegal” bitmap into the sidebar.

Xanthir, FCDhttp://www.cs.cmu.edu/~dst/DeCSS/Gallery/

They have the code in Scheme, Brainfuck, and pure lambda calculus.

MarkkIts funny, but this BCL make more sense to me somehow than SKI itself. I always feel like the notation gets in the way with all of the stuff that has descended from Church. It just doesn’t click for me – I keep thinking it looks ugly, so it becomes hard for me to try to uhm… internalize it. Even ugly things like regular expressions I eventually get in some subtle way, but I always have to work step by step though these kinds of things.

Mark C. Chu-CarrollXanthir:

I actually already found that, and I’m in the process of writing a lambda->SKI translator. 🙂