The Y-Combinator

Sep 17, 2017
lambda-calculus
recursion
typescript

Or how to implement recursion out of thing air.

Image of a recursive architectural structure.

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 “beloved” factorial function, which is defined as:

n!={1n=0n(n1)!n>0\begin{equation} n! = \begin{cases} 1 & \quad n = 0 \\ n*(n-1)! & \quad n > 0 \end{cases} \end{equation}

Here is how I would write that function in TypeScript:

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 makeFactorial(factorialBinding: Factorial): Factorial {
return function factorialWithoutRecursion(n) {
if (n === 0) {
return 1;
}
// Now we are able to recurse since we have
// access to the factorial binding
try {
return n * factorialBinding(n - 1);
} catch (e) {
throw new Error(`Cannot recurse at ${n}`);
}
}
}

This is an interesting idea, we are creating sort of lazily computed chain of factorial functions. See:

const factorial = makeFactorial(
function factorialWithoutRecursion(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 at 2

But notice that if we keep stacking factory calls, each time we are able to calculate a bigger factorial.

n=2n = 2

const factorial = makeFactorial(
makeFactorial(
function factorialWithoutRecursion(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 at 3

n=3n = 3

const factorial = makeFactorial(
makeFactorial(
makeFactorial(
function factorialWithoutRecursion(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 at 4

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 = (makeFactorialBinding: FactorialFactory) => Factorial;
function makeFactorial(makeFactorialBinding: FactorialFactory): Factorial {
return makeFactorialBinding(makeFactorialBinding); // 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 = makeFactorial(
function makeNonRecursiveFactorial(makeFactorialBinding: FactorialFactory): Factorial {
return function factorialWithoutRecursion(n: number): number {
if (n === 0) {
return 1;
}
const factorialBinding = makeFactorialBinding(makeFactorialBinding);
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 YY, 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 factorialWithoutRecursion(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); // [!code highlight:2]
return fnFactory(binding);
}
)
}

But wait, there’s a problem with this implementation, its recursion is eager, and we need to make it lazy again if we want to be able to use it in JavaScript:

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 { // [!code highlight:6]
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);
})

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

  1. As with many constructs in mathematical logic and computer science, the origins of much can be found in combinatory logic Fixed-point combinator
  2. Splending talk by Jim Weirich (RIP): Y Not- Adventures in Functional Programming
  3. The Little Schemer
  4. Some background on Lambda Calculus