An Introduction to Function Fixed Points with the Y-Combinator
Searching for the essence of recursion
The Y-combinator is a function that lets us do something neat: it allows us to encapsulate recursion in functions. This article shows how this is done, and how this encapsulation is related to the mathematical concept of fixed points. The focus here is on recursion rather than on combinatorial logic, so we won’t cover more advanced, non-recursive implementations of the Y-combinator. If you are trying to use the Y-combinator as a method for introducing recursion into a language, this article will likely be more useful to you.
The Y-combinator
In this article, the Y-combinator does not refer to an orange website, but to the original, a function in Alonzo Church’s lambda calculus. A combinator, for those unfamiliar with the term, is a way of combining functions into a new function. Specifically, it is a function which takes one or more pure functions as inputs, and returns a new function as output, which calls no other functions besides those provided as input to the combinator. Church’s lambda calculus is a way to express any program as a series of combinators, and “Y” is the name he chose for the combinator which provides recursion.
Let’s see what the Y-combinator is good for by looking at an example which is commonly used when explaining recursion: the function to return the nth fibonacci number. A naive implementation of it looks something like this:
function fibonacci(n : number) : number {
if (n < 3) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}(Since we’re interested in recursion, not in the nature of fibonacci numbers, this post will ignore the matrix form of computing fibonacci numbers using linear algebra.)
The challenge we’ll take here, in order to achieve our stated objective of “capturing the essence of recursion in a function”, is to write this fibonacci function without referring to the function in its own body. To put this another way, we’re going to look for an implementation which would let us write fibonacci as an anonymous function, like this:
n => {
if (n < 3) return 1;// Problem: we have no name for ourselves that we can use here
return ???(n - 1) + ???(n - 2);
}
We want this function to be able to call itself, without giving it a name in the scope in which it’s declared. We can’t perform recursion ourselves, but we need a function which will compute the next steps of the fibonacci algorithm. So let’s pretend that this function exists, call it fib, and have another function provide it to us:
function fibonacciFactory(fib : number => number) : number => number {
return (n : number) => {
if (n < 3) return 1;
return fib(n - 1) + fib(n - 2);
}
}The innermost body of this function is the same as that of the normal, recursive fibonacci function that we started with. This means that if we call fibonacciFactory with a fibonacci function, that we’ll get the fibonacci function that we want out of it. But this is a problem. The way we get the fibonacci function is by calling fibonacci factory with some argument:
const fibonacci = fibonacciFactory(?)But the missing argument fib is the fibonacci function itself, which we can only get as the output of fibonacciFactory:
const fibonacci = fibonacciFactory(fibonacciFactory(?));Which makes us need to write:
fibonacciFactory(fibonacciFactory(fibonacciFactory(?))etc. We’re trapped in an infinite chain here; we need some way to “close the loop.”
The y-combinator does this loop-closing. This is how we’ll call it:
const fibonacci = y(fibonacciFactory);fibonacci(7); // returns 13
And this is how we’ll implement it:
function y<A, B>(fn: (A => B) => (A => B)) : A => B {
function result (arg : A) : B {
const completeFunction : A => B = fn(result);
return completeFunction(arg);
}; return result;
}
Let’s break down how this works.
When we call fibonacci, we’re calling the result function returned by y. This function has access to fn, our fibonacciFactory function. The first thing the result function does is create a new function, by passing itself to fibonacciFactory. We know already that the output of fibonacciFactory is fibonacci, and completeFunction is the output of fibonacciFactory, so completeFunction is also fibonacci. And since result just passes its argument through to completeFunction, result is also fibonacci.
Effectively, we’ve extracted the recursive step out of our first fibonacci's calling of itself, and replaced it with result's self-reference. In doing so, the function y encapsulates the general notion of recursion. Using y, any function which performs recursion by calling itself can be rewritten as a function which performs one step of a recursive algorithm, and is given a function which it uses to perform the remaining steps.
We’ll see more things we can do with y later, but first it’s time to look at fixed points.
(Note: the code shown in this section is not the only way to implement the y-combinator. In fact, the y-combinator can be defined in a way such that nothing inside of it refers to itself at all, as demonstrated in JavaScript here. A non-self-referential implementation of y is actually traditional, because the lambda calculus in which y was introduced had only anonymous functions, meaning that explicit recursion/self-reference was impossible. Thus, y was a way of introducing recursion into that language. A recursive implementation of y is used here because it is easier to understand, and our focus is on fixed points, not on combinators.)
Fixed points of functions
Having y allows us to explain the title of this post, “fixed points.” Fixed points come from math, where a fixed point of a function f is a value for which f(x) = x. For example, the squareRoot function has two fixed points, 0 and 1, because squareRoot(0) = 0 and squareRoot(1) = 1. The function x => (x — 3) * 2 has one fixed point, 6, (because (6 — 3) * 2 = 6) and the function x => x + 1 has no fixed points, because there is no value x for which x = x + 1. The identity function, x => x, has an infinite number of fixed points, because identity(x) = x for all values of x.
Let’s look back at the problem we had which made us create our y combinator. We were stuck in a position like this:
const fibonacci = fibonacciFactory(fibonacciFactory(?));We wanted to call fibonacciFactory, but it needed to be called with fibonacci, which we could only get by calling fibonacciFactory. Now we have y, and we can get fibonacci. But we didn’t change fibonacciFactory at all; it will still give us a fibonacci function if we give it a fibonacci function. So we can do this:
// Quick-and-dirty test function to verify that things
// are working the way we expect
function testFib(fib : number => number) {
console.log([1, 2, 3, 4, 5, 6, 7].map(fib));
}testFib(fibonacci); // prints [ 1, 1, 2, 3, 5, 8, 13 ]const fibonacci2 = fibonacciFactory(fibonacci);
testFib(fibonacci2); // prints [ 1, 1, 2, 3, 5, 8, 13 ]const fibonacci3 = fibonacciFactory(fibonacciFactory(fibonacci));
testFib(fibonacci3); // prints [ 1, 1, 2, 3, 5, 8, 13 ]// etc.
The output of fibonacciFactory(fibonacci) is fibonacci. This is exactly f(x) = x, our definition of a fixed point. So just like 0 and 1 are the fixed points of squareRoot, fibonacci is the fixed point of fibonacciFactory. This is the true nature of y: the y-combinator is a function which, given a higher-order function in a certain form, finds that function’s fixed point.
The connection between recursion and fixed points
We saw how to implement a recursive function without explicit self-reference. First, we changed it into a higher-order function, which took another function as an argument. The argument function was tasked with performing the next step of the recursive computation, so when our originally-recursive function would have called itself, it could call the argument function instead. However, this left us with a problem. When we tried to use our new self-referential function, we ended up having to pass it its own output, which we could only get by calling it, which we could only get by passing it its own output… etc. This trapped us in an infinite chain of nested function calls: fibonacciFactory(fibonacciFactory(fibonacciFactory(...))).
We solved this with the Y-combinator: y encapsulated recursion, allowing us to collapse our infinite chain of nested calls into a single function. Examining y further, we found out that it’s related to the mathematical concept of fixed points. The fixed points of some function f are the values of x which satisfy the equation x = f(x), and we saw that when f is a higher order function, x can be a function.
Fixed points aren’t just a cool diversion; they’re actually the mechanism by which y freed us from our infinite chain of calls. x = f(x) implies that x = f(f(x)), which implies that x = f(f(f(x))), etc. Our problem was that we had an infinite chain of nested calls, and wanted a single function; the definition of a fixed point is an equation showing that a single value is equivalent to a potentially infinite chain of nested calls wrapped around that value. Coming from high-level languages with support for self-reference, this may seem alien, but it actually shows us the fundamental nature of recursion.
Understanding the Y-combinator can help us understand the nature of recursion in general. But it’s not just an intellectual curiosity: It can help us build tools for working with recursive functions in general. In part two of this post, we’ll see how we can define different versions of y which provide us with practical benefits.
The source code for all of the examples in this post may be found here.
This post is part of my series on recursion schemes, higher-order recursive functions which have a close connection to the Y-combinator.
Thanks to Lizz Katsnelson for editing this post.
