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.
\n[unlambda]: http:\/\/scienceblogs.com\/goodmath\/2006\/08\/friday_pathological_programmin_3.php
\n[lazyk]: http:\/\/esoteric.sange.fi\/essie2\/download\/lazy-k\/
\n[Iota]: http:\/\/ling.ucsd.edu\/~barker\/Iota\/<\/p>\n
\nA 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:
\n1. S is the function “*λ x y z . x z (y z)*”.
\n2. K is the function “*λ x y . x*”
\n3. I is the fuction “*λ x . x*”; it can also be written “SKK”
\nWell, 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)*.
\nIf you’ve got ι, then you can define S, K, and I combinators in terms of iota as follows:
\n1. S = ι(ι(ι(ιι)))
\n2. K = ι(ι(ιι)
\n3. I = ιι
\nThe *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.
\nSo to repeat the combinators in Iota syntax:
\n1. S=*i*i*i*ii
\n2. K=*i*i*ii
\n3. I=*ii
\nOf 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…)
\nAs 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.
\nThe 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”.
\nIt 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.
\nTo 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?
\n* True = “*i*i*ii”
\n* False = “**i*i*ii*ii”
\n* If = “*ii”
\nThere now, That’s not so bad, is it?
\nTo give you an idea, here’s an Iota program which generates prime numbers. It uses the Lazy-K mechanism for output.
\n*i*i*ii
\n**i*i*i*ii*ii*ii**i*i*i*ii**i*i*ii**i*i*i*ii**i*i*i*ii**i*i*ii
\n**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
\n**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
\n**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
\n*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
\n**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
\n*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
\n*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
\n*i*i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii*ii*ii**i*i*ii**i
\n*i*i*ii*ii**i*i*ii*i*i*ii**i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii
\n**i*i*i*ii**i*i*ii*i*i*i*ii**i*i*i*ii**i*i*ii**i*i*i*ii*ii**i
\n*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
\n*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
\n*ii*ii**i*i*i*ii**i*i*i*ii*ii*ii*ii**i*i*i*ii**i*i*i*ii**i*i*ii
\n*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
\n**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
\n**i*i*ii**i*i*i*ii**i*i*ii*i*i*ii**i*i*i*ii**i*i*i*ii*ii**i*i*
\nii**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
\n*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
\n*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
\n*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
\n*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
\n**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
\n**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
\n**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
\n*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
\n**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
\n*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
\n*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
\n**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
\n**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
\n*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
\n*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
\n*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
\n*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
\n*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
\n*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
\n**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*
\ni*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
\n*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
\n**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
\n*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
\n*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
\n*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
\n*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
\n*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
\n**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
\n*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
\n**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
\n**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
\n*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
\n*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
\n**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
\n*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
\n*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
\n**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
\n**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
\n*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
\n*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
\n**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
\n**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
\n*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
\n**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
\n**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
\n**i*i*ii*ii*i*i*ii**i*i*i*ii*ii*ii
\nDoesn’t get more pathological than that, now does it?
\nActually, it *does*.
\nThere’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.
\nHere’s the combinators in Jot:
\n1. S = 11111000
\n2. K = 11100
\n3. I = 1111110001110011100
\nBasically, “0” is ι, and “1” is “*”. (It’s actually a tad more complex than that, but we won’t bother ourselves with the details.)
\nSo, here’s out fibonacci generator written in Jot:
\n111100111111111100011111111100000111111111000001111111000111100
\n111111000111111100011110011111000111001111111000111100111111000
\n11110011111100011110011111110001111001111110001111111000
\n11111111100000111100111111100011110011111110001111111000111100
\n111110001110011111111100000111111100011111110001111001111100011100
\n11111111000111111111000001111111110000011111110001111111000111100
\n111110001110011111111100000111001111111000111111100011110011111000
\n1111111000111100111001111111000111100111110001111111000
\n111111111000001111111110000011110011111110001111001111100011100
\n111111111000001111111000111100111111000111111100011111111100000
\n1111001111111000111100111111100011111110001111001111100011100
\n1111111110000011111111100011111110001111001111100011100
\n11111111000111111111000001111111110000011111110001111111000
\n1111001111100011100111111111000001111110001111111000111100
\n11111000111001111111100011111110001111111110000011111111100000
\n1111111110000011111110001111111000111100111110001110011111111100000
\n11100
\nIncidentally, 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.)
\n[unlambda]: http:\/\/scienceblogs.com\/goodmath\/2006\/08\/friday_pathological_programmin_3.php
\n[lazyk]: http:\/\/esoteric.sange.fi\/essie2\/download\/lazy-k\/
\n[Iota]: http:\/\/ling.ucsd.edu\/~barker\/Iota\/<\/p>\n","protected":false},"excerpt":{"rendered":"
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, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-147","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-2n","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/147","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=147"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/147\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=147"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}