Alain Ketterlin <al...@dpt-info.u-strasbg.fr> wrote:
> Terry Reedy <tjre...@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
--
https://mail.python.org/mailman/listinfo/python-list
