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.
_______________________________________________
BangPypers mailing list
BangPypers@python.org
http://mail.python.org/mailman/listinfo/bangpypers
