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.
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
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))
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.
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:
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(1) first, and then
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
3+3 will only be evaluated when we call it like
It is called “eta conversion” in lambda calculus.
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