Tail recursion to while iteration in 2 easy steps

[Terry Reedy]

On 10/2/2013 4:17 AM, Alain Ketterlin 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)

As I said in response to randomxxx, even this 0th step (recursion to 
recursion transformation) requires assumptions or carefully reasoning 
about the properties of the operations.

>> 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).
>
> -- Alain.
>
> P/S: don't take me wrong; your explanation is excellent (and very useful
> to python programmers). What I say is that it relies on assumptions that
> do not apply to python.

Program transformations (usually intended to be optimizations), whether 
automatic or manual, are infamous for being buggy in not always being 
correct because of hidden assumptions that are not always true.

CPython core developers have be very conservative about what 
tranformations they put into the compiler. (1,2,3) can always be 
compiled as a constant, and so it is. [1,2,3] might or might not be a 
constant, depending on the context, and no attempt is made to analyze that.

-- 
Terry Jan Reedy