[Python-ideas] Tail recursion elimination

[Ned Batchelder]

On 1/19/14 6:54 AM, Joao S. O. Bueno wrote:
> On 19 January 2014 08:52, Mark Lawrence <breamoreboy at yahoo.co.uk> wrote:
>> On 19/01/2014 07:39, musicdenotation at gmail.com wrote:
>>> I propose tail-call optimization to be added into CPython.
>>
>> Then implement it so everybody else can use it.
> On a second though,  it actually could be done, at the VM level.
> I am not a proponent, but after my second though I am from "-1" to "+0".
>
> I believe that anytime one have the sequence:
>
>               20 CALL_FUNCTION            1
>               23 RETURN_VALUE
>
> in byte code, the current stack frame could be discarded prior
> to making the function call. Looking from 10000 meters, it feels
> like it would not impact any other aspect of the language but for
> enabling automatically tail recursion calls.
A big confusion here is between "tail recursion calls" and "tail 
calls".  This change would eliminate all tail calls, so that if f() 
ended by calling g(), then g would reuse the stack frame of f.  If g 
raises an exception, the stack trace would have no evidence of f in it.  
This is what people mean about unusable stack traces.  And don't forget 
that the stack is inspectable at runtime, so we aren't only talking 
about the visible stack trace produced on error, but the result of 
inspect.stack() etc, also.

Sure, if you eliminate only *recursive* tail calls, then the resulting 
stack traces aren't so bad, because you can do bookkeeping so that the 
1000 recursive calls to the same function are represented by one frame 
with an annotation of 1000 on it somewhere.  But how do you make it work 
your above code work only for recursive calls? And what about mutually 
recursive calls? Aren't those important too?

So we have two choices: the relatively easy job of eliminating all tail 
calls, which will throw away information we value, or the unsolved 
problem of how to eliminate recursive tail calls.

--Ned.
>
>     js
>   -><-
>
>>
>> --
>> My fellow Pythonistas, ask not what our language can do for you, ask what
>> you can do for our language.
>>
>> Mark Lawrence
>>
>> _______________________________________________
>> Python-ideas mailing list
>> Python-ideas at python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/