Possibly Pythonic Tail Call Optimization (TCO/TRE)

Terry Reedy tjreedy at udel.edu
Wed Jul 15 03:01:21 CEST 2015


On 7/14/2015 1:52 PM, Chris Angelico wrote:
> On Wed, Jul 15, 2015 at 3:43 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> I don't like the way integer overflows are explicitly undefined in
>> modern C.
>>
>> Similarly, I don't like the way tail call behavior is undefined in
>> Python.
>
> Where in the Python spec is it stated that tail call behaviour is
> undefined? The behaviour of the 'return' statement is well defined: it
> evaluates its expression (or None), *then* removes the top of the call
> stack and passes control back to the caller:
>
> https://docs.python.org/3/reference/simple_stmts.html#the-return-statement

I do not see anything there explicitly about call stacks.

> This implies that during the evaluation of its expression, the current
> function's call stack entry is still present. Tail call behaviour is
> therefore well defined: it is identical to any other expression
> evaluation, and then the final result is passed back to the caller.

In the blog post
http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
that everyone discussing this issue should read, Guido said that if a 
tail call is not within a try statement, tco would be fine except for 
the implementation issue of helpful tracebacks, which he cares greatly 
about.  However, as both he and the linked doc say, a tail call within a 
try: statement is not a tail call, in that more python code within the 
function may yet be executed.

It is not hard to construct an example in which tco would mess up a 
traceback message that is displayed.

-- 
Terry Jan Reedy



More information about the Python-list mailing list