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