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

i-9d452e257a158497c740337ba6fa7d4d-bcl.gif

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.

More like this

Todays tasty treat: a variable-free nearly-pure functional programming language: Unlambda. Unlambda is based on the SKI combinator calculus. The [SKI calculus][ski] is a way of writing lambda calculus without variables, and without lambda. It's based on three combinators: S, K, and I: 1. S = λ x y…
For todays dose of pathological programming, we're going to hit the worlds simplest language. A Turing-complete programming language with exactly *two* characters, no variables, and no numbers. It's called [Iota][iota]. And rather than bothering with the rather annoying Iota compiler, we'll just…
Lambda calculus started off with the simple, untyped lambda calculus that we've been talking about so far. But one of the great open questions about lambda calculus was: was it sound? Did it have a valid model? Church found that it was easy to produce some strange and non-sensical expressions using…
I'm on vacation this week, so I'm recycling some posts that I thought were particularly interesting to give you something to read. ------------ In computer science, especially in the field of programming languages, we tend to use one particular calculus a lot: the Lambda calculus. Lambda calculus…

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

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.

Xanthir:

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