## Y-combinator in Python

A simple introdution to Y-combinator in Python

## 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
```