Tail recursion to while iteration in 2 easy steps

[Neil Cerutti]

On 2013-10-03, Duncan Booth <duncan.booth at invalid.invalid> wrote:
>> 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.

Tail call optimization doesn't involve verification that the
function is calling itself; you just have to verfify that the
call is in tail position.

The current frame would be removed from the stack frame and
replaced with the one that results from calling the function.

> There is an issue that you would lose stack frames in any
> traceback.

I don't think that's a major issue. Frames that got replaced
would quite uninteresting. 

> 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.

In any case it's so easy to implement yourself I'm not sure
there's any point.

-- 
Neil Cerutti