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.

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.
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:
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.)

0 thoughts on “Pathological Programming: The Worlds Smallest Programming Language

  1. MiguelB

    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. 😀

  2. Pseudonym

    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.

  3. Jonathan Vos Post

    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:
    and to an (out-of-date) static web page:
    π: MATH Pages of Jonathan Vos Post
    I have published other Math, Computer Science, and Physics-related poetry, such as may be found at
    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.
    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,
    Jonathan Vos Post
    ex-Adjunct Profesor of Mathematics, Woodbury
    ex-Adjunct Profesor of Astronomy, Cypress College
    Over 15,000,000 hits/year

  4. Andy D

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

  5. nikita

    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!


Leave a Reply