Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Chris Angelico]

On Tue, Jul 14, 2015 at 3:41 PM, Paul Rubin <no.email at nospam.invalid> wrote:
> Chris Angelico <rosuav at gmail.com> writes:
>> That's a prime example of recursion... but not of recursion that can
>> be tail-call optimized into iteration. It's an example of forking
>> recursion, where one call can result in multiple calls (same with tree
>> traversal); it calls itself to sort the first part and the last part,
>> and while you might be able to turn the second call into a goto, you
>> still need stack space to maintain the first call. The claim that TCO
>> means you don't need stack space for all those levels of recursion
>> doesn't work if you still need stack space for all those levels of
>> recursion *before* you get to the tail call.
>
> You partition the array into two parts, one of which has at most N/2
> elements.  You push that smaller one onto the stack and recurse, so at
> the next recursive level you push at most an N/4 part, then N/8 and so
> on.  In that way the total recursion depth is O(log N).  If N=1e6 you
> enter 20 levels of recursion which is no big deal.
>
> If you also push the larger part on the stack, it can have size as high
> as N-1, so you can end up pushing N-1, N-2, N-3, etc.  If N=1e6 you
> overflow the stack when you've barely gotten started.

Ah, good point. So this is a way of forcing the recursion to be capped
at log N, preventing the worst-case time from also carrying worst-case
stack usage. Fair enough. Okay! Great! We have one example where TCO
can be helpful, because it means your two calls look identical. Well,
nearly identical... since one of them has to be "return
quicksort(...)" but the other has to be just "quicksort(...)". So in
order to make sure it's a true optimizable tail call, they end up
having to look different. Plus there's the whole traceback problem.

I'm still interested in the explicit "replace current stack frame with
this call" operation. Calling it "goto" seems wrong, as most languages
with goto restrict it to _within_ a function, whereas this would be
_across_ functions:

int fail_and_bail_demo(int arg, char *whatever)
{
    int ret = 1; /* failure */

    if (arg < 0) goto failure;

    int stuff_done = do_stuff(whatever);
    if (stuff_done < arg) goto failure;

    if (do_more_stuff(arg, whatever)) goto failure;

    ret = 0; /* If we get here, success! */

    failure:
    clean_up();
    return ret;
}

Contrast this proposal:

def func():
    pass

def setup_and_call():
    setup()
    transfer func, (), {}

The transfer of control has to be to the beginning of some other
function. So I'd rather it _not_ be called goto, but rather something
more evoking the notion of "hand control over to that function over
there, pretending that I've already returned". It's very much like the
Unix exec* family of functions, but Python already uses the name
'exec' in a very different way.

Done explicitly like this, it avoids the problem of bad tracebacks,
because by definition you would use it only when you want the current
stack frame to be dropped. I wonder how hard it would be to hack this
into CPython... Anyone feel like tackling it?

ChrisA