Hi,
I would like to share some of my recent attempts concerning recursivity in
python, more precisely recursivity with lambda functions.
I know that the title of my thread with the "tail-recursion" words may wake up
some long and old war; please don't take it as such. I am not claiming anything
about what programming languages should be or not; I enjoy using python for
many purposes and I perfectly know how to handle loops for achieving some tasks,
but sometimes I like rather think with recursivity because I have been using
various dialects of Lisp for a long time. I had a very great time studying the
Y-combinator; then I wrote various pieces of code for remapping recursive calls
to loop iterations.
The following functions are fully usable; I hope someone will enjoy using them.
If you are not interested by the explanations, just jump to the end of the
message and take my functions for using them.
Here is a recursive function:
fac = lambda f: lambda n: 1 if n==0 else n*f(n-1)
The Y-combinator is well known:
Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
Now, you can use the recursive function:
rf = Y(fac)
rf(5)
Now we write fac as a tail-recursive function:
fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b)
rf = Y(fac)
rf(5,1)
but of course, the recursivity is handled like previously.
In fact, it is very easy to build some effcient wrapper; for instance:
(lambda f: f(lambda *args: ("callback",args)))
will act in the following way:
(lambda f: f(lambda *args: ("callback",args)))(fac)(5,1)
--> ('callback', (4, 5))
(lambda f: f(lambda *args: ("callback",args)))(fac)(4,5)
--> ('callback', (3, 20))
(lambda f: f(lambda *args: ("callback",args)))(fac)(3,20))
--> ('callback', (2, 60))
(lambda f: f(lambda *args: ("callback",args)))(fac)(2,60)
--> ('callback', (1, 120))
(lambda f: f(lambda *args: ("callback",args)))(fac)(1,120)
--> ('callback', (0, 120))
(lambda f: f(lambda *args: ("callback",args)))(fac)(0,120)
--> 120
Here, the "callback" string is arbitrary chosen in order to make the loop know
that a next call is needed.
Now, the recursivity is handled as successive calls, which is what I was looking
for. A first proposal could be:
def with_tail_recursion(func):
x = (lambda f: f(lambda *args: ("callback",args)))(func)
def wrapper(*args):
out = ("callback",args)
while type(out)==tuple and out[0]=="callback":
out = x(*out[1])
return out
return wrapper
Now, the very same function can be used as recursive or inside a loop:
fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b)
rf = Y(fac)
tr = with_tail_recursion(fac)
rf(5,1)
--> 120
tr(5,1)
--> 120
Of course, if most of your job relies on writing functions returning tuples
with the string "callback" being the first argument, you should use another
keyword in the previous code ;-)
You can inspect the stack by raising an exception:
f2 = lambda f: lambda n: 1/n if n==0 else f(n-1)
and see the differences between Y(f2)(5) and with_tail_recursion(f2)(5)
But I was not fully happy with the use of a tuple, efficient but a little too
tricky to my eyes. For that reason, I took the Y combinator again and slightly
modified it:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
Now, the function doesn't call itself, but returns a function calling itself
with the relevant arguments.
I like this new function better than the previous one, but it is now more
difficult for the wrapper to detect when it is time to leave the loop.
Right now, I use the following test: checking for the __call__ string in
the dir() list. This means ONE IMPORTANT THING: this second wrapper can't
handle tail-recursive functions returning functions, (which is actually more
likely to happen than tail-recursive functions returning tuples with the
string "callback" being the first argument ;-) ). But I like it that way:
def B(func):
x = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = x(*args)
while '__call__' in dir(out):
out = out()
return out
return wrapper
tr2 = B(fac)
tr2(5,1)
--> 120
Now, you can write functions with a huge depth of recusivity with no
problem :
B(lambda f: lambda n: "ok" if n==0 else f(n-1))(5000)
(don't try with the Y combinator instead...)
Best regards,
--
Thomas Baruchel
--
http://mail.python.org/mailman/listinfo/python-list
