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:



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.

0 thoughts on “Simple Programming in Binary: Binary Combinatory Logic

  1. KeithB

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

  2. Mark C. Chu-Carroll

    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.

  3. Markk

    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.

  4. Mark C. Chu-Carroll

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


Leave a Reply