I first knew about the Y-combinator while reading Paul Grahamβs paper The Roots of Lisp, there he said that Lispβs primitive labels was not technically necessary since you can implement recursive functions by means of the Y-combinator, and thatβs what we are going to try to derive here.
Let's make an anonymous function recurse!
Implementation
As an example we are going to use the so loved factorial function π, which is defined as:
Here is how I would write that function in JavaScript:
function factorial(n: number): number {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
Removing recursion
If JavaScript didn't allow us to call a function from its own definition, we would be in trouble since our code would not be able to recurse naturally:
function factorial(n: number): number {
if (n === 0) {
return 1;
}
// Pretending we can't call factorial from within itself
throw new Error("Can't recurse :(")
}
factorial(0) // => 0
factorial(1) // => Can't recurse :(
Factorial closure
We know the recursive call should happen at the point we raise the exception, so let's change our definition in order to create a lexical closure capturing the factorial binding we need.
type Factorial = (n: number) => number;
function factorialFactory(factorialBinding: Factorial): Factorial {
return function actualFactorial(n) {
if (n === 0) {
return 1;
}
// Now we are able to recurse since we have
// access to the factorial function
return n * factorialBinding(n - 1);
}
}
This is an interesting idea, we are creating sort of lazily computed chain of factorial functions. See:
const factorial = factorialFactory(
function actualFactorial(n: number): number {
if (n === 0) {
return 1;
}
throw new Error("Can't recurse :(")
}
)
console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => Can't recurse :(
But notice that if we keep stacking factory calls, each time we are able to calculate a bigger factorial.
const factorial = factorialFactory(
factorialFactory(
function actualFactorial(n: number): number {
if (n === 0) {
return 1;
}
throw new Error("Can't recurse :(")
}
)
)
console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => Can't recurse :(
const factorial = factorialFactory(
factorialFactory(
factorialFactory(
function actualFactorial(n: number): number {
if (n === 0) {
return 1;
}
throw new Error("Can't recurse :(")
}
)
)
)
console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => Can't recurse :(
Recursing with closures
And this my friends is the key idea, I lied when I mentioned we are creating recursion "out of thin air", we instead are taking it from another place: the closures.
Right now, the recursion is quite manual since we are stacking the factory calls ourselves, but we can automate that by letting our factory recurse too by receiving a factory binding itself.
type FactorialFactory = (factorialFactoryBinding: FactorialFactory) => Factorial;
function factorialFactory(factorialFactoryBinding: FactorialFactory): Factorial {
return factorialFactoryBinding(factorialFactoryBinding); // the recursive magic πͺ
}
Note the types, the factory now recurse by calling the factory binding with itself in order to be able to return the actual value it needs to return: the factorial function.
const factorial = factorialFactory(
function actualFactorialFactory(factorialFactoryBinding: FactorialFactory): Factorial {
return function actualFactorial(n: number): number {
if (n === 0) {
return 1;
}
const factorialBinding = factorialFactoryBinding(factorialFactoryBinding);
return n * factorialBinding(n - 1);
}
}
)
Look at it go!
console.log(factorial(0)) // => 1
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => 24
console.log(factorial(5)) // => 120
The applicative Y-Combinator
Pay attention, because this is the hard part. Right now we have achieved recursion, but our implementation is really tied to the factorial business. Our goal now is to generalise this closure-recursion technique to any function.
Let's change our types first to make them more agnostic:
// Any function from an input to an output
type Fn<I, O> = (input: I) => O
// Any factory function
type Factory<T> = (factoryBinding: Factory<T>) => T;
// The recursive implementation of our factory
function factory<I, O>(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
return factoryBinding(factoryBinding);
}
Now, our goal is to be able to use a "super factory" function, let's name it , that given any function Fn<I, O>
, is able to give us back a recursive version of the same function.
This is the API we are looking for:
type Factorial = Fn<number, number>;
const factorial = Y(function(factorialBinding: Factorial) {
return function actualFactorial(n: number): number {
if (n === 0) {
return 1;
}
return n * factorialBinding(n - 1);
}
})
Knowing this, implementing it is just a matter of making the types match:
function Y<I, O>(fnFactory: (binding: Fn<I, O>) => Fn<I, O>): Fn<I, O> {
return factory(
function actualFactory(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
const binding = factory(factoryBinding);
return fnFactory(binding);
}
)
}
Well, there's a problem with that implementation, its recursion is eager, so we need to make it lazy again if want it to be useful:
function Y<I, O>(fnFactory: (binding: Fn<I, O>) => Fn<I, O>): Fn<I, O> {
return factory(
function actualFactory(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
return function(input: I): O {
const binding = factory(factoryBinding);
const fn = fnFactory(binding);
return fn(input);
};
}
)
}
console.log(factorial(0)) // => 1
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => 24
console.log(factorial(5)) // => 120
And that, is the applicative Y-Combinator which we can use to make any function recurse, not just factorial.
const factorial = Y(factorial => n => {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
})
const fibonacci = Y(fibonacci => n => {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
})
You may wonder our insistence in using the applicative adjetive. The reason is that Lambda Calculus syntax for the Y-Combinator is:
Very diferent from our definition which looks like this in compact form:
const Y = f => (g => g(g))(g => n => f(g(g))(n));
The reason is the Y-Combinator just won't work in languages with applicative or strict order of evaluation (see Evaluation Orders)
This applicative property of the Y-Combinator is also known by the Z-Combinator.
Conclusion
The Y-Combinator is one those things in lambda calculus and computer science that epitomises how math can be both beautiful and surprising. It allows us to make functions that can call themselves in a neat, clever way. Moreover, any programming language with lexical-closures/function-closures can be used to implement the Y-Combinator. This fact shows us how closely linked math and modern computer languages can be.
References
- As with many constructs in mathematical logic and computer science, the origins of much can be found in combinatory logic Fixed-point combinator
- Splending talk by Jim Weirich (RIP): Y Not- Adventures in Functional Programming
- The Little Schemer
- Some background on Lambda Calculus