From Anonymous Functions to the Y Combinator

Can a function recurse if it has no name? At RubyConf 2012, Jim Weirich answers by separating the particular rules for factorial from the mechanism of recursion, eventually constructing a fixed-point combinator from anonymous functions. He warns at the outset that this is not Ruby style he recommends for everyday production code; it is an exercise in understanding the foundations of computation.

Weirich begins with the Turing machine: a readable and writable tape, a read/write head, and simple state-transition rules can describe complex computation. He shows an animation counting in binary: on reading a one it erases it and carries, until it finds a position where it can write. Turing's approach puts the question of what an algorithm can compute into a deliberately simple model. Watch at 03:31

Alonzo Church's lambda calculus provides another model of computation, built from functions and function application. λx.x is the identity function: it takes a value and returns it unchanged. The process of substituting an argument into a function body is called beta reduction; substitution must avoid accidentally capturing variable names. Watch at 06:50

07:10View full image

Numbers can be represented without built-in numbers. A Church numeral encodes a number as the number of times a function f is applied to x: zero applies it zero times, one once, and two twice. Booleans can also be functions: true takes two arguments and returns the first, while false returns the second. Apply true to one and zero, substitute the arguments in turn, and the result is one.

09:00View full image

The talk notes that lambda calculus, Turing machines and general recursion have equivalent computational power. That raises the question: if functions in lambda calculus have no names, how can a function call itself in its own definition?

Before returning to recursion, Weirich asks a volunteer to start at zero and press a calculator's cosine key repeatedly. The value approaches approximately 0.739085: applying cosine again returns the same value within the calculator's precision. A value x satisfying f(x) = x is a fixed point of f. Watch at 13:29

14:10View full image

A function need not have exactly one fixed point. Square root has two, zero and one; every input is a fixed point of the identity function; and some functions have none. The cosine example illustrates convergence, not a guarantee that repetition finds a fixed point for every function.

Factorial is a simple recursive example: 0! = 1, and for n > 0, n! = n × (n - 1)!. Thus 5! = 120. An ordinary definition can use the name fact to call itself inside its body, but that name is not automatically available when the function is called directly as an anonymous expression. Watch at 16:18

That does not make anonymous recursion impossible. It means finding a way to bring “the function to call next” into the current function. Weirich introduces higher-order functions and several refactorings before returning to that problem.

A higher-order function treats functions as values: it can take a function, return one, or do both. In the talk, make_adder takes a number and returns a new function that adds that number to its input. compose takes two functions and returns a function that applies them in sequence. Watch at 17:52

For example, adding one to ten and then multiplying by three gives thirty-three. Passing “add one” and “multiply by three” as values to a composition function produces a new function that performs the same steps. The later derivation relies on the same idea: a function can receive another piece of computation and produce a more complete one.

The talk demonstrates four transformations that reshape expressions for the next step. In actual use, scope and evaluation timing still matter. Watch at 21:19

1. 1Tennent's correspondence principle: wrapping an expression in a zero-argument function and immediately calling it can preserve the result under the appropriate conditions.
2. 2Introduce a binding: add an unused parameter and pass a value. The new name must not accidentally shadow a free variable in the expression; in a strict language, the supplied expression is also evaluated first.
3. 3Wrap a function: put a function call inside another function. The inner call runs only when the outer function is called, providing a way to delay evaluation later.
4. 4Inline a definition: replace a use of a name with the function definition it denotes. Weirich uses this to remove intermediate names and return to anonymous expressions.

Weirich first imagines a “factorial improver”: it takes a partial factorial function and returns a new one. The new function returns one for zero; otherwise it uses the supplied partial function to compute n - 1 and multiplies the result by n. Watch at 28:47

improve = ->(partial) {
  ->(n) { n.zero? ? 1 : n * partial.(n - 1) }
}

Give the improver a function that always raises an error and the result can at least compute 0!. Improve that result once more and it can compute 1!; continue and each layer handles one more case. A finite number of hand-written nests is not general recursion, but it exposes the key structure: each layer only needs to know how to call the next.

33:40View full image

The next step is to let a function receive itself. Passing the original improver to itself fails: the improver expects a function but receives a number at the next step. Weirich changes the inner call so a generator uses itself again through gen.(gen).(n - 1); gen is now a function that generates the next layer, not the original partial factorial function. The resulting expression no longer depends on an external recursive function called fact; in the demonstration it computes large factorials until Ruby's call stack is exhausted. Watch at 33:42

Moving self-application directly into an argument position causes trouble, however: Ruby evaluates arguments before the call. If evaluating gen.(gen) immediately requires another gen.(gen), expansion continues before the program can check factorial's base case, eventually overflowing the stack. Wrap the call in ->(v) { gen.(gen).(v) } instead: the function is passed first and expansion occurs only when the next input is needed.

By introducing bindings, substituting and inlining, Weirich separates the improver that knows the factorial rule from the part responsible for self-application and delayed evaluation. The latter need not know anything about factorial. Another improver written in the same style could describe a different recursive definition, such as Fibonacci. Watch at 38:15

44:30View full image

The following equivalent Ruby form makes fix take an improver and return a recursive function:

fix = ->(f) {
  ->(x) { f.(->(v) { x.(x).(v) }) }.
    (->(x) { f.(->(v) { x.(x).(v) }) })
}

factorial = fix.(improve)
factorial.(5) # => 120

Here f is the improver; the two x functions form the self-application structure; and the inner ->(v) delays the next expansion. The example retains ordinary integers, conditionals and multiplication for clarity. It demonstrates the mechanism in Ruby rather than expressing the whole program in pure lambda calculus.

Give the factorial improver an already complete factorial function and the improved function still computes the same factorial: its behavior is unchanged. In that behavioral sense, factorial is a fixed point of the improver. The fixed-point combinator constructs the corresponding recursive function from an improver in this form. Watch at 45:04

49:20View full image

Weirich calls his construction an applicative-order Y combinator and notes that it is also commonly called the Z combinator. The classical normal-order form does not require the same wrapper; Ruby evaluates arguments first, so using that form directly would expand too early. Names and formulations vary across references; the key is to check the evaluation strategy.

At the end, Weirich is explicit: if a language already has named functions, there is no need to use a Y combinator for everyday recursion. What he values is the derivation—from fixed points, higher-order functions and small transformations to an expression whose parts can each be inspected. Watch at 50:34

He also recommends Tom Stuart's “Programming with Nothing” for further exploration of programs built with lambda functions. The lesson is not to memorize the combinator, but to understand how self-application and the right evaluation timing can establish recursion without a function name.