Sunday, January 18, 2015

Using tail-recursion on plain Python (hack)

Ok, just to note, I don't think this should be actually used anywhere, but I thought it was a nice hack to share :)

The idea is using the Python debug utilities to go back to the start of the frame... it probably won't win any speed competition and will break your debugger (so, really, don't use it).

The idea is setting "frame.f_lineno" to set the next line to be executed (but that can only be done inside a tracing function, so, we do have to set the tracing just for that and remove it right afterwards).

As a note, setting the next line to execute is  available in the PyDev debugger, so, you could jump back to some place backward in the code through Ctrl+Alt+R to see how some code behaved -- with the possibility of changing local vars, this is usually pretty handy.

So, now on to the code -- I think it's pretty straightforward:

import sys
from functools import partial

def trisum(n, csum):
    f = sys._getframe()
    if n == 0:
        return csum
        n -= 1
        csum += 1
        print(n, csum)
        f.f_trace = retrace_to_trisum
        raise AssertionError('Never gets here!')
        # Originally the 3 lines above would be the recursion call
        # It's possible to see that commenting the above lines
        # and executing the code will make Python throw a
        # RuntimeError: maximum recursion depth exceeded.
        trisum(n, csum)

def reuse_frame(line, frame, *args):
    # Reusing a frame means setting the lineno and stopping the trace.
    frame.f_lineno = line + 2 # +2 to Skip the f = sys._getframe()
    frame.f_trace = None
    return None

retrace_to_trisum = partial(reuse_frame, trisum.__code__.co_firstlineno)
print(trisum(1000, 0))

No comments: