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.

For today’s installation of programming insanity, I decided to go with a relative of Thue, which is one of my favorite languages insane languages that I wrote about before. Thue is a language based on a rewriting system specified by a semi-Thue grammar. Todays language is called Thutu (pronounced tutu); it’s a string rewriting system like Thue, only it’s based on regular expressions instead of grammars, and it’s even got regular expression-based control flow mechanisms, making it a sort of hybrid language.

The scary thing about Thutu is that it’s not all that different from a language I’ve wanted to find some time to write myself – except that the one I want to write isn’t intended to be pathological. I’ve never stopped missing Teco for writing text processing programs; and since
my TECO programs tended to be roughly of the form: “Find something matching this pattern, and then take this action”, a regular-expression based language would make a lot of sense.

But anyway, today we’re looking at Thutu, which is a deliberately obscure version of this idea.

Continue reading →