Skip to content

Instantly share code, notes, and snippets.


orf/ Secret

Created Oct 15, 2013
What would you like to do?
import functools
def tail_call(tuple_return=False):
def __wrapper(func):
def _optimize_partial(*args, **kwargs):
I replace the reference to the wrapped function with a functools.partial object
so that it doesn't actually call itself upon returning, allowing us to do it instead.
Advantages: Theoretically needs no code changes and is more understandable
Disadvantages: Its startup overhead is higher and its a bit slower. Also can only call
recursively when returning, so return func(1) + func(2) will not work.
old_reference = func.func_globals[func.func_name]
func.func_globals[func.func_name] = functools.partial(functools.partial, func)
to_execute = functools.partial(func, *args, **kwargs)
while isinstance(to_execute, functools.partial):
to_execute = to_execute()
func.func_globals[func.func_name] = old_reference
return to_execute
def _optimize_tuple(*args, **kwargs):
This way requires the function to return a tuple of arguments to be passed to the next
Advantages: Very little overhead, faster than plain recursion
Disadvantages: Needs code changes, not as readable, no support for keyword arguments (yet)
while args.__class__ is tuple: # Faster than isinstance()!
#while isinstance(args, tuple):
args = func(*args)
return args
if tuple_return:
functools.update_wrapper(_optimize_tuple, func)
return _optimize_tuple
functools.update_wrapper(_optimize_partial, func)
return _optimize_partial
return __wrapper
def test_fib_optimize(i, current=0, next=1):
if i == 0:
return current
return test_fib_optimize(i - 1, next, current + next)
def test_fib_tuple_optimized(i, current=0, next=1):
if i == 0:
return current
return i - 1, next, current + next,
def test_fib_no_optimize(i, current=0, next=1):
if i == 0:
return current
return test_fib_no_optimize(i - 1, next, current + next)
import timeit
import sys
for func in (test_fib_optimize, test_fib_tuple_optimized, test_fib_no_optimize):
print func.func_name, timeit.timeit(functools.partial(func, 1700), number=1000)
Copy link

schinckel commented Oct 17, 2013

Shouldn't you use the same 'isinstance' optimisation in both functions, to ensure that isn't why the tuple version is faster?

Copy link

orf commented Oct 22, 2013

I did, I must have not uploaded that version :/
If I remember correctly it didn't significantly decrease the overhead, which is a shame.

Copy link

baruchel commented Oct 8, 2016

Your idea of using a partial for calling later the returned function is a nice idea; I was also working on the same topics at the same time than you (!!!) and I achieved the same purpose a little differently by using lambda calculus: see but it works exactly the same way as you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment