Skip to content

Instantly share code, notes, and snippets.


orf/ Secret

Created October 15, 2013 14:54
  • Star 22 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
Star You must be signed in to star a gist
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

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