What is Y-combinator

In the functional programming field, the famous Y-combinator is expressed in lambda calculus like Y := lambda f.(lambda x.(f (x x)) lambda x.(f (x x))). Y-combinator can enable us to implement recursion without defining functions explicitly. In this article, we’ll discuss how to implement it in Python.

How to implement Y-combinator

Let’s break it into small pieces.

First, we take a look on the outer side. It’s actullay accepting an argument f and return the function lambda x.(f (x x)) invoking (or “applying” as a FP jargon) with the argument lambda x.(f (x x))’s result.

Inside lambda

If you have Lisp experience, you may be familiar with something like (f (x x)). It is also called “S-expression”. For something like (f a), it means that we are calling a function f, and it takes an argument a, and the a can also be another S-expression like (x x).

So in Python, it’s quite straight:

lambda x: f(x(x))

And the latter lambda x.(f (x x)) is definitely the same:

lambda x: f(x(x))

Outside lambda

So, how do we put them together? Actually, lambda x: f(x(x)) returns a function, so we’ll call this function whose argument is itself. I know it sounds strange, but for now we just do it:

( lambda x: f(x(x)) )  ( lambda x: f(x(x)) )
#     function                argument

And back to outside, we’ll get

Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

How to use Y-combinator

You may want to ask, how should we use this weird thing to implement recursions without defining any function? Let’s start from the factorial calculation.

First trying

In normal way, you will write it like:

def fac(n):
    return 1 if n <= 1 else n * fac(n - 1)

print(fac(5))  # 120

But what if you cannot define or name a function? In lambda calculus, we cannot define variable or name a function as usual. And then here comes Y-combinator.

First, let’s convert the factorial function into lambda:

fac = lambda f: lambda n: 1 if n <= 1 else n * f(n - 1)

And then, we use Y-combinator:

print(Y(fac)(5))

And we get:

RecursionError: maximum recursion depth exceeded

The evaluation problem we get

Wait, what is this? I’m sorry I forgot to mention this. This has something to do with the way how we calculate arguments when passing them into the function.

Let’s say you call function like:

def add1(x):
    return x + 1

def mul(x, y):
    return x * y

print(mul(add1(0), add1(1))) # 2

Let’s think about: When Python is calling mul(), how does python calculate it’s arguments? Some of you may raise your hand: it’ll calculate add1(0) and add1(1) first, and then mul(1, 2).

Yes, that’s almost right. Let’s think a little deeper. What if we call function like:

(lambda y: (lambda x: x)(y))(1)

As mentioned above, Python will calculate argument first, so it will become (lambda 1: (lambda x: x)(1), then (lambda x: x)(1).

But there is another way. So how about we call the inner function first? Let’s keep the 1 outside: (lambda y: (lambda y: y)())(1) then (lambda y: y)(1).

By this way, we simplify the function before we actually do any calculation. In fact, some functional languages do like this.

The way to delay evaluation

So if we want to delay the evaluation of an argument, what should we do? Say we don’t want it to calculate 3+3 right now, we can put them into a function:

another_f = lambda : 3 + 3

And the 3+3 will only be evaluated when we call it like another_f().

It is called “eta conversion” in lambda calculus.

Z-Combinator

Back to the Y-combinator we wrote, the problem happened when Python evaluate our argument too early, so we need to delay the argument to the latter lambda inside:

Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))
print(Y(fac)(5))  # 120

By this way, until the argument is passed into the latter lambda, x(x) will not be evaluated.

Eta-converted Y-combinator is called Z-combinator。

Final version without variables

Remember we cannot define variables in lambda calculus? So we just remove the variable name and get the final version:

print(
  (lambda f: (lambda x: x(x))
    (lambda x: f(lambda *args: x(x)(*args))))
  (lambda f: lambda n: 1 if n <= 1 else n * f(n - 1))(5))  # 120

A simpler version

However, if we are not that strict, we can define Y-combinator in a simpler way like:

Y = lambda f: f(Y(f))  # By definition
Z = lambda f: lambda *args: f(Z(f))(*args)  # eta converted
print(Z(lambda f: lambda n: 1 if n <= 1 else n * f(n - 1))(5))  # 120