Programs with no variables
Ordinary code leans on names. You declare a variable, give it a value and refer to it later. Combinator calculus asks what happens if you remove names entirely. The answer is that a handful of fixed functions, called combinators, plus the operation of applying one thing to another, are enough to express every computable function.
This is not a recent curiosity. The idea dates back to early twentieth-century work in logic, where the goal was to understand the foundations of mathematics. It reappears in esoteric programming languages because a language with only two or three primitives is both compact and extremely hard to read.
The three classic combinators
The usual starting set has three members, written S, K and I.
- K takes two arguments and keeps the first. Written as a rule: K x y becomes x.
- I takes one argument and returns it. I x becomes x.
- S takes three arguments and distributes the third into the first two. S x y z becomes x z (y z).
Application is written by juxtaposition and groups to the left, so K x y means (K x) y. Computation is just repeated reduction: find a combinator with enough arguments and replace it using its rule, until no more rules apply.
Interestingly, I is not strictly needed. The expression S K K behaves like I. Applied to any x: S K K x becomes K x (K x), and then K picks its first argument, leaving x. This is the sort of tiny proof that makes the system satisfying. S and K alone are enough to build everything.
How Unlambda looks
Unlambda is an esoteric language built on this idea, created by David Madore in the late 1990s. Its application operator is written as a backtick placed before two expressions, and its basic functions are single letters, including s, k and i. The identity function built above would be written with backticks as skk , and applying it to some value x gives ```skkx ``, which reduces to x.
Unlambda also adds practical pieces so that programs can actually do something. A function written as a period followed by a character, such as .a, prints that character when applied and then returns its argument unchanged. So `.ai prints the letter a. There is a function for a newline, and further primitives for delaying evaluation and for capturing and resuming control flow, in the style of continuations. These extras are not needed for pure computation, but they let the language interact with the outside world.
The result is a language where a program is a long string of backticks and single letters. Writing it by hand is a bit like assembling a circuit with tweezers. Even simple tasks need careful planning of how arguments get routed to the right place.
Why no variables is harder than it sounds
In a normal language, you pass a value around by name. With combinators, there are no names, so to get an argument where you need it you must build a combinator expression that does the routing. S duplicates and distributes, K discards, and everything else is composition.
There is a general procedure, called bracket abstraction, that converts a function written with variables into a combinator expression. Doing it by hand quickly produces large expressions, which is one reason that hand-written combinator code is rare outside puzzles. Tools can do the conversion, and compilers for some functional languages have used combinator-like internal forms, though the details vary by implementation.
Relation to lambda calculus
Combinator calculus and lambda calculus are two views of the same territory. Lambda calculus uses variables and abstraction; combinators trade those for fixed primitives. Each can express the other, which is part of why they are discussed together in discussions of the Church-Turing thesis and computability theory generally. Combinators are in a sense the compiled form, with the names already boiled away.
Other combinator-style languages
Unlambda is the best-known esoteric example, but not the only one. Some designs push minimality further and reduce everything to a single primitive combinator, so that a program is just a tree of one repeated symbol. Others encode combinator terms as strings of bits, which makes them natural targets for studies of the smallest universal programs. Details differ between projects, and it is worth reading a language’s own documentation rather than assuming it follows the conventions above.
What to take away
Three small facts are worth keeping.
- A very small set of rules, S and K, suffices for universal computation.
- Programs with no variables are possible, but the cost is readability.
- Reduction, the repeated application of rewrite-like rules, is a form of computation that does not need a program counter.
That last point is why combinator languages are often grouped with rewriting systems. A reduction step is a pattern replacement, and the whole program is just the sequence of such steps. If this style appeals, try reducing a few small expressions on paper before touching an interpreter. Following S K K x to x once by hand explains more than any definition.