In this article, we'll introduce a higher-order function called the Y combinator. It's immediately recognizable thanks to the famousstartup incubator of the same name, but what is this strange sounding term all about?

In most languages, recursion is supported directly for named functions. For example, the followingfactorial function written in JavaScript calls itself recursively:

constfactorial=n=>n>1?n*factorial(n-1):1factorial(5)// 120

Lambdas, i.e. anonymous functions, generally don't have built-in support for recursion, but since they should be used when the logic is simple (and extracted to a named function otherwise), it's unlikely one would want to make a recursive call in a lambda.

Therefore, making recursive calls as above is the way to go. However, let's pretend we can't use recursion directly. As long as our language has support for functions as first-class citizens (they can be assigned to variables, passed in as arguments, and returned like any other object), we can still implement recursion ourselves. One nice way to do so is with a higher-order function called the Y combinator. The name sounds intimidating, but it's just a higher-order function, a function that wraps around another function.

Instead of making a recursive call directly as we did earlier, we will modify ourfactorial function so that it calls a callback function. This callback function will be responsible for calling back into thefactorial function to complete a recursive call. Ourfactorial function will therefore now have an additional parameter,recurse:

constfactorial=>recurse=>n=>n>1?n*recurse(n-1):1;

In the above function, instead of callingfactorial directly, we call therecurse callback.

What should this callback look like? We can consider acallRecursively function that looks something like the following:

constcallRecursively=target=>args=>target(args2=>target(args3=>target(...)(args3))(args2))(args);

When we call our target (thefactorial function in our case), we need to pass a callback to it that accepts the next parameter that the target will be called with. However, we run into a problem of infinite regress. For each call, we have to to keep supplying a new callback.

It turns out there is a clever trick that helps us get around this limitation. We can create a function and then call that function with itself as its own argument! In JavaScript, we use anIIFE to do so. Below is an example of the mechanism we'll use:

(f=>f(f))(self=>console.log(self));

We supply the lambdaself => console.log(self) as an argument to the self-executing lambda(f => f(f)). When we run this code (e.g. in the browser console), we see that the variableself refers to the very function it is being passed into as a parameter:

>(f=>f(f))(self=>console.log(self));self=>console.log(self)

We will use this idea to solve our problem of infinite regress. We define a function we'll call Y (for Y combinator) that takes a target function (e.g.factorial) and the parameters for that target function as arguments. Our Y combinator function will then call the target function, supplying a callback for the target function to invoke when it wants to make a recursive call. The complete code is below:

constY=target=>args=>(f=>f(f))(self=>target(a=>self(self)(a)))(args);constfactorial=recurse=>n=>n>1?n*recurse(n-1):1;Y(factorial)(5);//120

In the above code, when the target, e.g.factorial, and its argument are passed into the Y combinator function, the Y combinator will executeself => target(a => self (self)(a)). When the target is executed, the callbacka => self(self)(a) is passed to thetarget so that it can initiate the next recursive call. Keep in mind thatself is a reference to the functionself => target(a => self(self)(a)).

When ourfactorial function receives the argument5 (note that our target iscurried in this example), it will execute the callback, passing in4 for the parametera. This will trigger a recursive call back into the target, and so on, until the terminating condition for the target function is reached. When our callback code executes, we need to pass a reference to to the handler as the first argument, hence theself(self) fragment in the above code.

The Y combinator function is not something we expect to see being used in modern programming languages, since they have built-in support for recursion (at least for named functions). However, higher-order functions are an important part of the functional programming paradigm, so working out the details of how such a function behaves can still be a useful exercise. The general idea of composing functions along these lines is commonly applied in functional programming across a wide range of use-cases.

We also gain insight intolambda calculus, a powerful mathematical framework for understanding computation. For example, We can completely inline the code we've written to show there are no free variables. While the code is not exactly readable when inlined this way, this gets us very close to the pure lambda calculus form for this logic:

(target=>args=>(f=>f(f))(self=>target(a=>self(self)(a)))(args))(recurse=>n=>n>1?n*recurse(n-1):1)(5);//120

References

• Y combinator
• Currying
• Lambda calculus
• IIFE