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 use an even more twisted language called [Lazy-K][lazyk], which can run Iota programs, Unlambda programs, as well as its own syntax.
[unlambda]: http://scienceblogs.com/goodmath/2006/08/friday_pathological_programmin_3.php
[lazyk]: http://esoteric.sange.fi/essie2/download/lazy-k/
[Iota]: http://ling.ucsd.edu/~barker/Iota/

A few weeks ago, I showed you [Unlambda][unlambda], a programming language based on the SKI combinator calculus. The SKI combinator calculus is a nifty little thing that defines two canonical operators, S and K, called combinators. It’s easy to show that *any* lambda calculus function *and thus any program* can be written using nothing but two basic combinators: S, and K. Literally, nothing but those two combinators: no variables, no numbers, nothing. To make things easier to write, they also add I, but you can actually write I in terms of S and K:
1. S is the function “*λ x y z . x z (y z)*”.
2. K is the function “*λ x y . x*”
3. I is the fuction “*λ x . x*”; it can also be written “SKK”
Well, you can do better than SKI. You can define *one* combinator, ι: using iota, and *only* iota, you can write *any* lambda calculus function. What’s it look like? ι=*λx.xSK*; or stretched out, *λ x . (λ a b c . a c (b c) (λ d e . d)*.
If you’ve got ι, then you can define S, K, and I combinators in terms of iota as follows:
1. S = ι(ι(ι(ιι)))
2. K = ι(ι(ιι)
3. I = ιι
The *programming language* [Iota][iota] is based on the ι combinator. We write the combinator as “i”; and we use “*” for function application. Like the “‘” in Unlambda, we can think of “*” as an open-paren, and the close-paren isn’t needed, since all functions take only one parameter.
So to repeat the combinators in Iota syntax:
1. S=*i*i*i*ii
2. K=*i*i*ii
3. I=*ii
Of course, there is one problem with Iota as a programming language. It doesn’t have any input or output statements. But that’s no problem: the *program itself* is both its input and its output. When a program stops, you look at what it’s turned into, and that’s its output – just like in lambda calculus: apply a function, do all of the betas, and the program transforms itself into its result. (And actually, the Lazy-K interpreter, which accepts Iota syntax, will generate output, based on an idea of lists of input and output…)
As I said before, only “*” and “i” are part of Iota syntax. So to do numbers, we need to use church numerals. And we can’t write them in lambda syntax! So we need to work out how to construct them using Iota expressions.
The church numeral for one in lambda syntax is “λ s z . s z”. Translated to iota, that’s pretty simple: “*ii”. Easy, right? So how bad could two be? Heh… In lambda calculus, it’s “*λ s z . s (s z)*”. In SKI, it’s “(S(S(KS(KI))))” In Iota? “***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii”.
It only gets worse with bigger numbers. Three is “***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii”. We’ll stop with that.
To program conditionals, we need to define true, false, and if. The “true” value in lambda calculus is written “*λ x y . x*”, and “false” is written “*λ x y . y*”. And finally, “if(cond,true,false)” is “*λ c t f . (c t f)*”. So what do they look like in Lazy-K?
* True = “*i*i*ii”
* False = “**i*i*ii*ii”
* If = “*ii”
There now, That’s not so bad, is it?
To give you an idea, here’s an Iota program which generates prime numbers. It uses the Lazy-K mechanism for output.
*i*i*ii
**i*i*i*ii*ii*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii
**i*i*i*ii*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii
**i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii
**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii*i*i*i*ii**i*i*i*ii**i*i*i
*ii**i*i*ii*i*i*i*ii*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii
**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii*i
*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii
*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii
*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii**i
*i*i*ii*ii**i*i*ii*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii
**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii**i
*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i
*i*ii*i*i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i
*ii*ii**i*i*i*ii**i*i*i*ii*ii*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii
*i*i*i*ii*i*i*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii
**i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*i*ii**i*i*ii*i*i*ii*i*i*ii
**i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*
ii**i*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*i*ii*i*i*i*ii*i*i
*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i
*i*ii*i*i*i*ii*i*i*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i
*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii**i*i*i*ii**i*i
*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii*i*i*ii**i*i*ii*i*i*ii
**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii
**i*i*ii**i*i*i*ii*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii
**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii**i*i*i*ii*ii**i*i*ii*i
*i*ii**i*i*ii**i*i*ii**i*i*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii
**i*i*i*ii**i*i*ii**i*i*i*ii*ii**i*i*i*ii*i*i*i*ii**i*i*i*ii*ii**i*i
*ii*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i
*i*ii**i*i*ii*i*i*i*ii*i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*ii
**i*i*ii**i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*i*ii*ii**i*i*ii*i*i*ii
**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i
*i*ii*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii
*i*i*ii*ii**i*i*i*ii**i*i*i*ii*ii*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i
*i*ii*i*i*ii*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i
*ii**i*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii
*ii**i*i*i*ii*ii*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i
*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii*i*i*ii
**i*i*ii*ii**i*i*i*ii*i*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*
i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i
*i*ii*ii*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii
**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i
*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i
*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i
*ii*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i
*ii**i*i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii*i*i*ii**i*i*ii*ii**i*i*i
*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii*ii**i*i*i*ii**i*i*ii
**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i
*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii
**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii*i*i*ii
**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i
*ii*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii**i*i*ii*i*i*ii**i*i*i*ii
*ii**i*i*ii*i*i*ii**i*i*ii**i*i*i*ii*ii**i*i*ii*i*i*ii**i*i*i*ii
**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii*i
*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i
*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii
**i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*ii**i*i*ii**i*i*i*ii*ii**i*i*ii
**i*i*ii*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii*ii**i*i*i*ii**i*i*ii**i*i
*i*ii**i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii**i*i*i*ii**i*i*i*ii**i*i
*ii*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*i*ii
**i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii*i*i*ii**i*i*ii
**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii*i*i*ii**i*i*i*ii**i
*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii**i*i*i*ii*ii**i*i*ii**i*i*ii*ii
**i*i*i*ii**i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii**i*i*i*ii*ii*ii
**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*ii
**i*i*ii*ii*i*i*ii**i*i*i*ii*ii*ii
Doesn’t get more pathological than that, now does it?
Actually, it *does*.
There’s a companion to Iota, called *Jot*. Jot is a purely binary representation that is not just a two character programming language, but also a complete Godel numbering of Iota programs.
Here’s the combinators in Jot:
1. S = 11111000
2. K = 11100
3. I = 1111110001110011100
Basically, “0” is ι, and “1” is “*”. (It’s actually a tad more complex than that, but we won’t bother ourselves with the details.)
So, here’s out fibonacci generator written in Jot:
111100111111111100011111111100000111111111000001111111000111100
111111000111111100011110011111000111001111111000111100111111000
11110011111100011110011111110001111001111110001111111000
11111111100000111100111111100011110011111110001111111000111100
111110001110011111111100000111111100011111110001111001111100011100
11111111000111111111000001111111110000011111110001111111000111100
111110001110011111111100000111001111111000111111100011110011111000
1111111000111100111001111111000111100111110001111111000
111111111000001111111110000011110011111110001111001111100011100
111111111000001111111000111100111111000111111100011111111100000
1111001111111000111100111111100011111110001111001111100011100
1111111110000011111111100011111110001111001111100011100
11111111000111111111000001111111110000011111110001111111000
1111001111100011100111111111000001111110001111111000111100
11111000111001111111100011111110001111111110000011111111100000
1111111110000011111110001111111000111100111110001110011111111100000
11100
Incidentally, as I’ve mentioned, there’s currently a “geek-off” competition going on at ScienceBlogs to prove who’s the biggest geek. I think that the mere *existence* of this article is more than enough to demonstrate that I am quite clearly the geekiest blogger at SB. But just to put the icing on the cake, I generated the fibonacci program above by writing a little micro-compiler from Unlambda to Iota; and then translated from Iota to Jot *by hand*. (What’s a bit scary about that is that the compiler from Unlambda to Iota is longer than the entire Iota compiler.)
[unlambda]: http://scienceblogs.com/goodmath/2006/08/friday_pathological_programmin_3.php
[lazyk]: http://esoteric.sange.fi/essie2/download/lazy-k/
[Iota]: http://ling.ucsd.edu/~barker/Iota/