On 10/2/2013 4:17 AM, Alain Ketterlin 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)
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
--
https://mail.python.org/mailman/listinfo/python-list
