Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Antoon Pardon]

On 07/15/2015 02:41 AM, Terry Reedy wrote:
> On 7/14/2015 10:02 AM, Antoon Pardon wrote:
>> On 07/14/2015 03:43 PM, Chris Angelico wrote:
>>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko at pacujo.net>
>>> wrote:
>
>>>> No, tail call optimization doesn't change the behavior of the program,
>>>> for the worse anyway.
>>> It does, because you lose traceback records. That's pretty significant
>>> when you come to try to debug something.
>>
>> I doubt it would be really significant. Not compared to writing it
>> iteratively.
>> When you write it iteratively, you don't get to keep a traceback
>> record per time
>> you go throught the loop. So the traceback records you loose in tale
>> call elimination
>> would be the traceback records you wouldn't have anyway in the
>> iterative version.
>
> To repeat: loosing tracebacks is probably fine when the function has a
> single *recursive* tail call.  This are precise the cases when it is
> simple and perhaps preferable to use a loop.  But *recursive* tail
> calls are only a small fraction of all tail calls.  So most of the
> time, the loss *would* be significant.  Consider

But it doesn't need to be all or nothing. How about the following possibility.
When the runtime detects a serie of tail calls, it will keep the bottom three
and the top three backtrace records of the serie. And when it needs to print
a stacktrace it writes an indication that some tracebacks are missing. I think
that would be a workable compromise between workable tail call recursion
and usefull stacktraces.

Now of course there are some other problems like what if the tail call is into
a C-function. I don't think you want to drop a stack frame in those circumstances.
So I guess implementing this and getting all corner cases right, will not be
trivial and I understand if the core developers don't consider this a high
priority. But one likes to dream sometimes.

-- 
Antoon Pardon