Tail recursion to while iteration in 2 easy steps

[Duncan Booth]

Alain Ketterlin <alain at dpt-info.u-strasbg.fr> wrote:

> Terry Reedy <tjreedy at udel.edu> writes:
> 
>> Part of the reason that Python does not do tail call optimization is
>> that turning tail recursion into while iteration is almost trivial,
>> once you know the secret of the two easy steps. Here it is.
>>
>> Assume that you have already done the work of turning a body recursive
>> ('not tail recursive') form like
>>
>> def fact(n): return 1 if n <= 1 else n * fact(n-1)
>>
>> into a tail recursion like
> [...]
> 
> How do know that either "<=" or "*" didn't rebind the name "fact" to
> something else? I think that's the main reason why python cannot apply
> any procedural optimization (even things like inlining are impossible,
> or possible only under very conservative assumption, that make it
> worthless).
> 

That isn't actually sufficient reason.

It isn't hard to imagine adding a TAIL_CALL opcode to the interpreter that 
checks whether the function to be called is the same as the current 
function and if it is just updates the arguments and jumps to the start of 
the code block. If the function doesn't match it would simply fall through 
to doing the same as the current CALL_FUNCTION opcode.

There is an issue that you would lose stack frames in any traceback. Also 
it means code for this modified Python wouldn't run on other non-modified 
interpreters, but it is at least theoretically possible without breaking 
Python's assumptions.

-- 
Duncan Booth http://kupuguy.blogspot.com