David Madore is responsible for one of the best-known and most-confounding esolangs of all time: Unlambda. The language is based on the SKI combinator calculus, a super-minimalist computational system used in the mathematical analysis of algorithms, but considered impractical for coding. In Unlambda everything is a function that takes a single variable, so there are no indicators like ()s to take parameters. Like the SKI calculus, it entirely eschews variables and the lambda indicator, and so is described as lambda-without-the-lambda. If this is entirely new to you, the second half of this post is a nice introduction. Madore, an accomplished mathematician, is also responsible for languages that play at the edges of infinity. His main web presence is his webpage from his undergrad days thirty years ago, which remains a fascinating portrait of the sincerity, optimism, and banalities of the early Web. He is also on Twitter with a handle derived from his engagement with The Hackers' Zen.
In response to a flurry of questions about creating Unlambda, Madore gives us some notes:
- I think I came up with Unlambda in 1999. I knew very little about other esolangs at the time (and I still don't know much about them), that is to say, I knew a bunch of names but didn't try programming in any of them.
- I was reading a book on logic that mentioned the Hilbert-style axioms (S: (A⇒B⇒C)⇒(A⇒B)⇒A⇒C; K: A⇒B⇒A; and I: A⇒A) and I was simultaneously thinking about the Curry-Howard correspondence between proof systems and typing systems, so I thought about what these axioms meant in terms of functional programming and how we could use them to re-explain the lambda-calculus without lambdas: this is how I came up with Unlambda. The 'c' function is because I was also fascinated by call/cc at the time (and still am, I guess), especially as it also has a nice interpretation in the Curry-Howard correspondence as Peirce's law (((A⇒B)⇒A)⇒A). The 'd' is clearly an error of mine, I should never have included it, it's unnecessary (I thought it might be, but it was a misunderstanding on my part of how normalization proceeds) and it makes the language far less elegant (on the other hand, it makes the interpreter's job a bit more complex, which is maybe fair for an obfuscated programming language).
- At the time, I was thinking about proposing another obfuscated programming language in a somewhat similar flavor, where everything would be written in continuation-passing-style (no function ever returns), but never got around to it.
- I think Unlambda got some attention from various teams writing compilers with multiple front-ends or stuff like that, or in compilation courses, because it can be an interesting test case, toy example or illustration.
- I once had a page in Wikipedia because of Unlambda, but it was later decided that I wasn't notable enough. :-(
[Ed note: while Madore's page is gone, Unlambda's lives on]
» Thanks, this is a great intro to what you were thinking when you created the language! Does your work as a mathematician since then build on these ideas or relate to them in any specific way?
Not really. I'm ("officially") in Algebraic Geometry, which is rather disconnected from such things as the lambda-calculus. But I do dabble in all sorts of domains of mathematics, including a lot of logic (and, for some reason, recently, a lot of epidemiology...).
» Has anyone written programs in Unlambda that surprised you (in terms of the strange direction they took or perhaps in what they were able to accomplish with it)?
After I wrote the language, I ran a mini-competition (on an internal newsgroup system at the ENS where I was a student) to write a quine in Unlambda (I offered a copy of the Abelson & Sussman "wizard book" to whomever would write the first). I knew it was doable because I had written one myself, but mine was unwieldy, and I was amazed by how fast other people were able to write quines, and how small they could get them (the record, as far as I know, is 491 bytes, at ftp.madore.org/pub/madore/unlambda/CUAN/quine/quine06.unl, or how efficient (in terms of data representation).
Later on, someone was able to write an Unlambda interpreter in Unlambda, which also surprised me, and a couple of other fun programs. Of course, it's a bit of a cheat because what he actually did was write a translator for a subset of Scheme into Unlambda, and then used this translator to translate an Unlambda interpreter written in that subset of Scheme (as well as the translator itself) into Unlambda.
» Unlambda has been described as "easy to write, impossible to read"—does that jibe with your experience with it?
Yes, quite. Once you have a translator as described in the previous paragraph, it becomes fairly easy to write lots of things in Unlambda, and not so impressive after all. But I would be very impressed if anyone were able to read non-trivial Unlambda programs without actually running them.
One particularly difficult program which rose to a certain degree of fame is this one: ``r`ci`.*`ci, which prints an endless list of rows of asterisks, each with one more than the previous (i.e., it counts in unary using asterisks): the output isn't particularly impressive, but understanding how it works is definitely tricky! I stumbled upon this program by more or less randomly trying various stuff with call/cc, and I had a hard time figuring out how it did what it did. See https://stackoverflow.com/questions/30409800/any-history-background-about-the-yin-yang-puzzle-in-detail and the links therein for various comments and translations of this weird program.
» Considering the impact Unlambda has had on esoteric languages, I'm curious if you ever connected with other esolangers after creating the language.
Not really, no. I was aware of the existence of esolangs.org but that's about as far as it goes.
» Apart from Unlambda, you've created a few other esolangs, most notably Amicus, introduced (in 2015) in this post; how did this come about, and how would you describe hyperarithmetic functions to the less-mathy of us? What is the central idea of the language, if it can be described in a few sentences?
First of all, this definitely wasn't intended as an esolang... I wanted to give a formal definition of hyperarithmetic machines, it turned out to be a bit less workable than I had hoped for (I tried writing something non-trivial in it, and I realized it was quite tedious! see note #4½ in the blog post in question), and one of my blog readers decided it was interesting and gave it a name. Why not? In retrospect, it's true that it makes for a possibly interesting esolang, but its birth was entirely fortuitous.
A "hyperarithmetic machine" (note: the terminology is mine: the concept is standard in computability, but generally people speak of "hyperarithmetic[al] functions" for the functions they compute, and the devices doing the computation are left unnamed) is a model of higher computation, i.e., it is a kind of abstract computer that is strictly stronger than a Turing machine.
Basically, a hyperarithmetic machine can do everything that a Turing machine can do, with one additional capability: given a sequence of integers that is, itself, computed by a [program for a] hyperarithmetic machine, the machine can (in a single magical step, if you will) decide whether the sequence consists entirely of zeroes or whether there is a nonzero value somewhere down the line; note that the computation of every single one of these values has to terminate, but provided that this is the case, the machine has the ability to examine all of them and decide whether there is a nonzero value among them. The values in the examined sequence are themselves computed by hyperarithmetic machines (so they can themselves use the same ability): this makes it a bit subtle to define properly because you can't allow a program to examine its own behavior. But after it's properly defined, the machine in question is extremely powerful: it can not only solve the halting problem for ordinary Turing machines, but also the halting problem for Turing machines with access to a solution of the halting problem for ordinary Turing machines, "and so on".
So anyway, my blog post was about defining this properly and explaining a few equivalent definitions; and since the definition is a bit tricky, I tried to give a precise formalization, and to make sure my formalization did what I thought it did, I wanted to make sure that if we removed the extra magical ability of hyperarithmetic machines we got (something equivalent to) ordinary Turing machines, and this is how I accidentally invented an esolang.
(But hyperarithmetic machines are not, in and of themselves, connected to esolangs any more than Turing machines are. One could imagine all sorts of programming languages to run on them just as there are many Turing-equivalent programming languages.)
Writing all this reminds me of two things which might interest or amuse you:
One is that I invented a number of programming languages for transfinite computers (i.e., that are able to deal with and manipulate certain infinite ordinals). I didn't give them any specific names, and there are a few of them whose exact relation is, sadly, not entirely clear even theoretically, but they are defined here. At least some variants of the languages in question should be equivalent to the aforementioned "hyperarithmetic machines". The languages in question aren't supposed to be difficult to write, on the contrary, but they are definitely esoterical since they are meant for computers that (presumably!) cannot physically exist in this universe. (Also, I should make it clear that the theoretical concepts, like that of a hyperarithmetic machine/function, aren't new and aren't due to me: they are "well known" notions from higher computability that were developed in the 1950's to 1970's, but computability theorists never bothered to actually formulate them in the form of a programming language.)
Another thing that I am reminded of is that, in 2012, I accidentally (i.e., without participating!) won a prize in the IOCCC competition. How it happened is a bit embarrassing for everyone involved: I had written a program that was meant to be clear and readable and well-commented, and someone else (Aaron Grothe) reused my program, made it obfuscated and submitted it as an entry to the IOCCC (without telling me or telling the judges; which was legal because I had placed my program in the Public Domain, but perhaps a bit dishonest); the judges decided to award a prize to the program in question, and when he was asked to explain how it worked, he referred to my own work, so the judges (after consulting me) decided to make me co-winner. This is how I won the IOCCC without participating (I guess this makes me unique!), with a program that I thought was clear and well-written (which may or may not say something about my ability to write clear code :-).
So I guess I'm an accidental esolang designer and an accidental obfuscated programmer. :-\
Excerpt from Madore's post referenced above, on hyperarithmetic computing (original in French):
I said that it was not possible, in the base language (0), to write an interpreter for the language (0) itself; that is, there is no such thing as a "universal" function which takes two arguments, [the code of] a function e to execute and an argument z to pass to it, and which behaves like the execution of e ( z ); it is also not possible, all the more so, to write in language (0) an interpreter for extended languages (1), (2) and (3).
On the other hand, what is possible in language (0) is to write what I want to call an " essence interpreter ". It is about a function (recursive primitive, therefore) which takes three arguments: [the code of] a function e to execute, an argument z to pass to it, and a certain "quantity of essence" t which gives to the interpreter a time limit for the execution of e ( z ) before failing: basically, the interpreter starts the execution of e ( z ) for t execution steps (this twill therefore limit the main loop of the interpreter), and if the execution ends in the allotted time (less than t steps), the essence interpreter ends by returning the calculated value, otherwise, the essence interpreter ends with a special value "lack of gasoline" (in other words: I executed your program the time you told me, it did not finish in the allotted time, if you want, you can try again with more gasoline ). The gasoline interpreter, which is essentially Kleene's T predicate , even though it is tedious to write, is codable in my language (0), even if it is to interpret one of the more languages. rich (1), (2) or (3).
» Do you find (more mainstream) functional languages most appealing to work with? Do all of your esolangs build on the functional paradigm?
I don't program that much (and mostly in quite standard languages: C, Perl, Java, JavaScript, an occasional bit of Python), but I do enjoy the diversity of programming languages that exist, while simultaneously regretting that good ideas always end up being marred by bad decisions so the "one language to rule them all" is still completely elusive.
Functional programming is definitely something natural and appealing to mathematicians: first, because we're used to dealing with functions as first-class citizens (and defining functions which take functions as input or return functions as output, to an arbitrary degree of complexity), and second, concerning purely functional (i.e., side-effect-free) languages, because the mathematical world is, largely speaking, conceived as unchanging. So Haskell in particular is a language whose ideas I, and I think many mathematicians, find extremely satisfactory (and the typing system relies on many mathematical ideas). However, I have to say that when I actually tried to use Haskell for practical stuff, I was disappointed, because you often face the dilemma of either doing things in a mathematically elegant way or having to break the elegance for efficiency's sake (maybe experienced Haskell programmers know how to avoid the dilemma, but for a beginner like myself it was something of a letdown).
» Your site is a charming throwback to the '90s personal webpage (complete with ~). While it has some newer content mixed into your info from 30 years back, you've maintained both the look and the unguarded sensibility where everything is shared from the mundane to the very personal: favorite authors, the slightly different shade of blue in your eyes, to more personal writing like the "Petite autobiographie gaie" with descriptions of loneliness and connection as a young gay man and the long description of your personality. Is this a more open and honest Web that you seek out?
The state of my web site is mostly due to my lack of time and patience at keeping things up to date: I find that writing things once is easy but maintaining them afterwards requires a tremendous amount of work. This is why I now prefer to publish things in the form of (often very long) blog posts, which are clearly dated so there is clearly no promise that they will be updated later, in fact there is more of an assumption to the contrary. So pretty much everything else on my web site is in limbo (and in various different circles of limbo, since I changed my mind a number of times as to how to organize and style my web pages and never got around to uniformizing everything).
On the other hand, it's true that I also care greatly about things like URL longevity, and I try very hard not to break links once I've published them. When I re-read my past blog entries, I'm often upset by how many links have broken, often over a short span of time.
» Are there other esolangs of yours that I haven’t yet asked about?
I couldn't say. ;-) I mean, I had pretty much forgotten about "Amicus" which, as explained above, is something of an accident, so there may be others!