Unlambda

Unlambda

Unlambda is a functional programming language built on combinatory logic — and its name is the first joke: it contains no lambda abstraction at all. Where the lambda calculus lets you write anonymous functions that bind variables, Unlambda abolishes variables entirely. There are no names, no data types, no statements — only functions applied to functions, in a parenthesis-free notation that produces programs resembling stray punctuation. David Madore released it in 1999 as a deliberate proof that functional programming could be made maximally unreadable while remaining fully Turing-complete.^[1]

The result is what the esolang community calls a Turing tarpit: everything is possible, nothing is easy. Unlambda's "Hello, World!" — .!.d.l.r.o.w. .,.o.l.l.e.Hi — works by applying a chain of print-one-character functions and ending on the identity combinator, and it is considered one of the friendlier sights in the entire language.^[2]

No variables, only functions

Unlambda's syntax has exactly one operator: the backquote ` `, which applies the function on its left to the argument on its right. If f and x are expressions, fx ` is the application of f to x`. Everything else is a combinator — a function that takes one argument and returns another, with currying doing the rest:

The s, k, and i trio is the important part: those three combinators form the SKI basis, which is provably equivalent to the entire lambda calculus — every lambda term, and therefore every computable function, can be written in them. Unlambda inherits Turing-completeness from pure algebra, which is precisely Madore's point: the language is a calculus wearing a joke costume.^[3]

The continuation that goes back in time

The genuinely startling inclusion is c — call-with-current-continuation. When c is applied, it captures the program's entire future execution as a first-class object — a "continuation" — and passes it to its argument. If that captured continuation is ever invoked, execution travels back in time: the whole program state rewinds to the moment c ran, but with the new argument in hand. Continuations can express loops, escapes, coroutines, and control structures the language pointedly refuses to provide — which means the hardest primitive in functional programming is here doing the work of GOTO.^{c's continuation semantics and the time-travel metaphor from the reference documentation">[4]}

The d combinator adds a second cruelty: it delays evaluation of its first argument until its second is computed — inverting the order of side effects so that expressions print in reverse of their written order. Between d scrambling sequence and c scrambling time, an Unlambda program resists reading on two axes at once.

Where it sits in the wing

The early esolang canon attacked one assumption each: INTERCAL attacked seriousness, Brainfuck attacked size, Malbolge attacked the programmer, Whitespace attacked visibility, and Befunge attacked dimensionality. Unlambda attacked variables — the deepest assumption of all, the one even the other esolangs kept. That it did so with more mathematical sophistication than most real languages is the joke's final layer: the hardest language to read in this catalogue is also the closest to pure logic.

Check your understanding

• Why is "Unlambda" an ironic name for a language based on the lambda calculus?
• What do s, k, and i form — and why does that make Unlambda Turing-complete?
• What does the backquote operator do?
• What does c capture, and what happens if you invoke what it captures?