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∗(n−1)!n=0n>0
Here is how I would write that function in TypeScript:
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:
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.
This is an interesting idea, we are creating sort of lazily computed chain of factorial functions. See:
But notice that if we keep stacking factory calls, each time we are able to calculate a bigger factorial.
n=2
n=3
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.
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.
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:
Now, our goal is to be able to use a “super factory” function, let’s name it Y, 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:
Knowing this, implementing it is just a matter of making the types match:
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:
And that, is the applicative Y-Combinator which we can use to make any function recurse, not just factorial.
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