[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.


More information about the BangPypers mailing list