# [BangPypers] Introducing the Y Combinator(Not the company)

Sidharth Kuruvila sidharth.kuruvila at gmail.com
Thu Oct 15 17:58:04 CEST 2009

```AKA The Y Combinator in python. This is in response to Roshan Mathews'
post that he got stuck with the Y Combinator.

Aha a challenge, I shall undertake this as a test of my communication
skillz. :-)

The question is how do we implement a recursive function in a language
in which names can only be bound using a lambda expression eg. Python
without assignment operators and def.

We can solve this problem fairly easily, we pass the function itself
as a parameter. So now any recursive call must include the function as
a parameter too.

fact = lambda _fact, x: 1 if x == 1 else x * _fact(_fact, x-1)

print fact(fact, 5)

Or course lambda expressions in python are famously hard to read. So
we'll allow `def` with some restrictions. The code block of a function
definition cannot contain a call to the function itself. This is
because the function name isn't bound at the time the function itself
is defined.

We can rewrite the lambda code as

def fact(_fact, x):
if x == 1:
return 1
else:
return x*_fact(_fact, x-1)

print fact(fact, 5)

There, thats a lot more readable. Having to type `_fact(_fact, x-1)`
is quite irritating especially if the recursive call is made in more
than one place. So we can extract it into a function `f`.

def fact(_fact, x):
def f(x):
return _fact(_fact, x)

if x == 1:
return 1
else:
return x * f(x-1)

print fact(fact, 5)

But we still need to define `f` at the top of all our functions. It
makes sense to generalize this pattern so that `f` itself can be
passed as a parameter to fact. This is where the y combinator comes
in.

Ok, now things start to get a bit weird so hang in there.

Here's a definition of y combinator using lambdas, it's not
particularly readable so we'll just ignore it.

def y(f):
return ((lambda g: lambda a: f(g(g), a))
(lambda g: lambda a: f(g(g), a)))

Let's implement the y combinator using `def` instead.

def y(f):
def _y(g):
def _f(a):
return f(g(g), a)
return _f
return _y(_y)

`_f` accepts parameter `a` and then calls `f` with the parameters
`g(g)` and `a`.  `_y(_y)` bootstraps the whole operation by passing
`_y` to itself to be bound to `g`. `g` is now `_y`, so a call to `g`
will return `_f`.

So now we can implement fact to use the y combinator.

def fact(f, x):
if x == 1:
return 1
else:
return x * f(x-1)

fact = y(fact)

print fact(5)

ps. I wrote a lisp interpreter using lambda and the bootstrapping
concept some time ago. It's a bit of a brain damaged ugly sister of
the the y combinator.

http://kuruvila.net/2008/02/29/a-one-line-lisp-interpreter/

--
I am but a man.
```