My attempts in playing with tail-recursion in python

[Thomas Baruchel]

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]

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.

Despite the very short size of my function, I made a module of it as a
convenience for my own use. I share here my "recursion.py" file in which
I also added some docstrings.

----------------- module "recursion.py" -------------------------------

"""
The recursion module provides convenient functions for handling
recursion with lambda functions.

The famous Y-combinator is provided as a convenience, but the most
distinctive function of the module is the B function for handling
tail-recursion.

Written by Thomas Baruchel
"""

Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

def B(func):
"""
B(lambda) -> lambda

Return a usable function from a lambda expression written with a
tail-recursion style. The new function will be evaluated inside
a loop with no recursive calls, allowing high depths of recursion.

Since the internal loop evaluates the return of the function as long
as it is callable, the function does not work with functions returning
functions (at the end of the recursive calls); there is no restriction
otherwise.

E.g.:
fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b)
func = B(fac)
func(5,1)
--> 120
or more shortly:
B(lambda f: lambda a,b: b if a==0 else f(a-1,a*b))(5,1)
--> 120
"""
x = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = x(*args)
while callable(out):
out = out()
return out
return wrapper