Understanding the Y combinator

Lambda calculus (λ-calculus) is a mathematical system for computation based on function abstraction and application, using variable binding and substitution.¹

Structure and Interpretation of Computer Programs is an amazing book by Harold Abelson and Gerald Jay Sussman. The book teaches the fundamental principles of computer programming, including recursion, abstraction, modularity, and much more. I recommend the book to anyone who is interested in programming, I am sure they will learn something.

This book has two editions. The first one uses Scheme (a dialect of Lisp), for its examples and explanations, while the second uses JavaScript. I have not programmed much in JavaScript at the time of writing this, but I will try to provide all examples in both lambda notation, Scheme and JavaScript.

At one point, in section 1.3.3, they talk about finding fixed points of functions. This was the first time I heard about this, and it’s what mainly motivated me to write this article. If you are interested on the general Lisp approach, and not on the Y combinator itself, I recommend you check it out.

One of the most valuable things that SICP has taught me is that sometimes it’s extremely useful to treat functions as black boxes that are able to transform some inputs into some outputs. They call this wishful thinking, and it has been useful not only when using functions, but also when designing them.

This is the function for calculating the factorial of a number \(n\), using the lambda calculus notation:

\[ \text{fact} = \lambda n. \Big(\Big(\text{iszero}\ n\Big) 1 \Big(\text{mult}\ n \ \big(\text{fact}\ (\text{prec}\ n)\big)\Big)\Big) \]

In Scheme:

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (mult n (fact (prec n))))))

Or in JavaScript:

var fact = (n) => (n == 0)
    ? 1
    : mult(n, (fact(prec(n))));

We are defining fact as a function that takes a parameter n. This function returns 1 if n is zero, and otherwise multiplies n by the factorial of the number preceding n.

In this case, we can simply ignore how iszero, mult, prec and even fact work internally, we just have to trust that they do what we expect. Another useful way of thinking about lambda calculus and Lisp in general is as a language for expressing processes.

In any case, we don’t have those name-defining commodities in lambda calculus. A function can’t call itself by name, so we will have to find an alternative way.

Before trying to understand the Y combinator, let’s have a look at an example of how an anonymous function might call itself without the need for symbols.

\[ (\lambda x. x\ x)(\lambda x. x\ x) \]

Or in Scheme:

((lambda (x) (x x))
 (lambda (x) (x x)))

Note: Depending on the Lisp, you might need to use (funcall x x) instead of (x x), since variables and functions don’t share the same namespace. You can search about the differences between Lisp-1 and Lisp-2.

Or in JavaScript:

((x) => x(x))((x) => x(x))

We can see that the two parenthesized expressions are identical, and that the first is applied to the second one. Let’s try to simplify it by β-reduction. The first parenthesized expression, is applied to the second one. We replace each occurrence of \(x\) in the body of the first expression with the whole second parenthesized expression.

We are right back where we started. This function would call itself indefinitely, and a similar form will be used for the Y combinator below.

Before getting into the fixed-point combinators, we need to define what a fixed point is.

A fixed point of function \(f\) is a value that is mapped to itself by the function.³ In other words, \(x\) is a fixed point of \(f\) if \(f(x) = x\). For this to be possible, \(x\) has to belong to both the domain of \(f\) (set of values that it can take), and the codomain of \(f\) (set of values that it can return).

For example, if \(f(x) = x!\), 1 and 2 are fixed points, since \(f(1) = 1\) and \(f(2) = 2\).

The image shows the graph of a function \(f\), with 3 fixed points. When plotting with \(y = f(x)\), these 3 points were also on the line \(x = y\).

For example, for some functions \(f\), we can locate a fixed point by beginning with an initial guess and applying \(f\) repeatedly.

\[ f(x),\quad f(f(x)),\quad f(f(f(x))),\quad \dots, \]

We would do that until the value doesn’t change very much, and we are satisfied with the result.

A fixed-point combinator is a higher-order function (i.e. a function that takes a function as argument) that returns some fixed point of its argument function.⁴

So, if a function fix is a fixed-point combinator, a function f has one or more fixed points, then fix(f) is one of these fixed points:

\[ f(\text{fix}\ f) = \text{fix}\ f \]

In lambda calculus, every function has a fixed point.

An example of a fixed-point combinator is the Y combinator. This is the definition of \(Y\).

\[ Y = \lambda f. \big(\lambda x. f (x\ x)\big) \big(\lambda x. f (x\ x)\big) \]

Or in Scheme:

(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (f (x x))))))

Note: This version is not accurate, see Implementation in Scheme below.

Or in JavaScript:

var Y = (f) =>
    ((x) => f(x(x)))(
     (x) => f(x(x)));

Since it’s a fixed-point combinator, calling \(Y\) with a function as its argument would be reduced to \(Y\ f = f(Y\ f)\). This is a very interesting and useful concept, and it’s where this image comes from.

Let’s try to understand what it does, and why it’s a fixed-point combinator. We are saying that \(Y\) is a function that takes one parameter \(f\). The body consists of the same lambda term applied to itself: \((\lambda x. f(x\ x))\). You may realize why we explained how to do recursion with anonymous functions earlier. A similar principle applies here, but we are also calling the \(f\) function.

Let’s simplify it with β-reduction step by step:

Note how the reduction on the third step is applying \(g\) to the same expression in the second step, which we know is equal to \(Y\ g\). That’s how we can verify that \(Y\ g = g(Y\ g)\).

An alternative (and slightly simpler) version of the Y combinator is the following:

\[ X = \lambda f. (\lambda x. x\ x) (\lambda x. f(x\ x)) \]

Notice how the first call to \(f\) was not necessary, since this expression also β-evaluates to the Y combinator.

You might be wondering what makes the Y combinator so special. As we said, lambda calculus doesn’t have any kind of “global symbols”, therefore a function can’t reference itself by name. Let’s go back to the factorial example in Scheme.

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (fact (- n 1))))))

This recursive form is possible because the fact function can reference itself by name. More specifically, because a lambda body is evaluated whenever a call is made, and by that time the fact symbol is already bound to the lambda, and therefore the body can reference it. In OCaml, for example, the rec keyword is needed when defining a recursive function to denote that it will reference itself, and not an external function with the same name.

The Y combinator allows us to call a function recursively in a language that doesn’t implement recursion. Let’s have a look at an alternative form of fact.

(define fact-generator
  (lambda (self)        ; Outer lambda (fact-generator)
    (lambda (n)         ; Inner lambda (returned by fact-generator)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

Let’s carefully look at what we just defined. We are defining fact-generator as the outer lambda, a function with one argument self. This function does not return the factorial of a number, but instead returns another another lambda function that will receive a number n, and return its factorial.

This inner lambda, the one that will be returned when calling fact-generator, is essentially the same as our previous fact function, but this time it’s able to use recursion without referencing itself by name by accessing the self parameter of the outer lambda.

The important detail is that fact-generator is supposed to return a factorial function, but also expects to receive a factorial function as its self parameter, which will be used whenever the inner lambda wants to make a “recursive” call. How could we accomplish this? At first sight, we could try something like this.

;; Wrong.
(define fact
  (fact-generator fact))

The code above is incorrect because of how Scheme evaluates the arguments. When evaluating the define expression, it will first try to evaluate the call to fact-generator, but before that it must evaluate its argument, the fact symbol. Since at this point fact isn’t defined (we are trying to do just that), Scheme will show an “Unbound variable” error.

Since the fact-generator function expects a function for calculating the factorial, but also returns one, we are looking for something like:

(define fact
  (fact-generator (fact-generator (fact-generator ...))))

Does that look familiar? Indeed, this is just what the Y combinator allows us to do.

Our Scheme version of the Y combinator was not really correct. Evaluation in Scheme (and most Lisps) is strict, meaning that each argument is evaluated before applying the function. This is not a problem in lambda calculus.

If you reached this far, I hope you have learned something. Everything in this article is based on what I found while trying to learn about the Y combinator, so if you feel like some explanations could be improved, feel free to contribute.