Pathological Programming: The Worlds Smallest Programming Language

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…
[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…
[lazyk]: http://esoteric.sange.fi/essie2/download/lazy-k/
[Iota]: http://ling.ucsd.edu/~barker/Iota/

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 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-…
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…
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 think that the mere existence of this article is more than enough to demonstrate that I am quite clearly the geekiest blogger at SB.

It is probably enough to demonstrate you're the geekiest blogger, period. :-D

The catch with iota as a primitive is that it is not a supercombinator. A reduction step will, in general, leave lambda terms which are not expressed in terms of iota. Reducing S or K does not introduce any more lambda terms, which makes it actually practical for implementing lambda calculus without name capture.

By Pseudonym (not verified) on 08 Sep 2006 #permalink

Daniel:

My unlambda to iota translator was written in DrScheme.

Dear Mark C. Chu-Carroll,

Yours is one of a few dozen blogs that I look at several times a week. Keep up the great work! I hesitate to reduce myself to mere geek, although my wife is a Physics professor and my seventeen-year-old son about to receive his double B.S. in Applied Math and Computer Science.

When I was earning my double B.S. at Caltech 1968-1973
I was a protege of Feynman, and thus am the only person alive to have coauthored or coedited with Richard Feynman, Isaac Asimov, Ray Bradbury, and Sir Arthur C. Clarke.

Although Feynman's guidance to me in two areas he pioneered
-- Nanotechnology and Quantum Computing -- were
historical enough for me to have described them in
context in refereed papers, I am also delighted to
have done art projects with him, and to have
coauthored a poem with him.

"Footnote to Feynman", Jonathan V. Post and Richard
Feynman, [Engineering & Science, Caltech, Pasadena,
CA, Vol.XLVI, No.5, p.28, ISSN: 0013-7812, May 1983;
reprinted in Songs from Unsung Worlds, ed. Bonnie
Bilyeu Gordon, intro by Alan Lightman (award winning
author of Einstein's Dreams), Birkhauser Boston/AAAS,
hardcover ISBN: 0-8176-3296-4, paperback ISBN:
3-7643-3296-4, 1985.

I have so much to say about him, beyond our years of
friendship and our correspondence (inadvertantly
omitted from his recent selected letters due to an
error by the permissions editor). But I know that you
are busy. Rather than clutter your blog, I'll point to mine:
http://magicdragon2.livejournal.com/
and to an (out-of-date) static web page:
Ï: MATH Pages of Jonathan Vos Post
http://www.magicdragon.com/math.html

I have published other Math, Computer Science, and Physics-related poetry, such as may be found at
http://www.magicdragon.com/EmeraldCity/Poetry/

I want to say again how much I love your blog.

Like uber-geek Greg Egan, I am also a professional science
fiction author. But he's more impressive at novel
length than I; and I am more social.
http://www.magicdragon.com/UltimateSF/authorsP.html#JonPost

I still live in Altadena, where my most famous
neighbor was once Feynman, and then declined
precipitously to Rodney King.

Thank you again for innumerable inspirations,

Best,

Jonathan Vos Post
ex-Adjunct Profesor of Mathematics, Woodbury
University
ex-Adjunct Profesor of Astronomy, Cypress College
co-webmaster
http://magicdragon.com
Over 15,000,000 hits/year

Wow, Mr. Post, I think your comment wins for longest, most egotistical, and all around most useless comment of all time. Congrats!

Andy D: You've just won the "You're my hero" award.

Congrats to Mark for taking second place with this blog post that enabled Andy to win 1st.

I think "Markov normal algorithms" are even simpler, because semantics of all that lambda-iota stuff is based on substitution, and Markov algorithms are nothing more than plain string substitution.

As an additional bonus, one can use them to write non-trivial programs, that can even be read afterwards!