Why no tailcall-optimization?

[process]

Why doesn't Python optimize tailcalls? Are there plans for it?

I know GvR dislikes some of the functional additions like reduce and
Python is supposedly about "one preferrable way of doing things" but
not being able to use recursion properly is just a big pain in the
a**.

[Aaron \Castironpi\ Brady]

Re: Why no tailcall-optimization?

On Sep 22, 8:13 pm, process <circularf...@g mail.comwrote:

Why doesn't Python optimize tailcalls? Are there plans for it?
>
I know GvR dislikes some of the functional additions like reduce and
Python is supposedly about "one preferrable way of doing things" but
not being able to use recursion properly is just a big pain in the
a**.

I didn't think this through completely-- is it incompatible with
closures and local function definitions?

def f( m ):
def g( n ):
return m+ n
stuff( )
return g( 0 )

In this case, the stack, growing up:

g
f
main

is not equivalent to:

g
main

in the last step, due to the local definition of 'm' in 'f'.

[Michael Palmer]

Re: Why no tailcall-optimization?

On Sep 22, 9:13 pm, process <circularf...@g mail.comwrote:

Why doesn't Python optimize tailcalls? Are there plans for it?
>
I know GvR dislikes some of the functional additions like reduce and
Python is supposedly about "one preferrable way of doing things" but
not being able to use recursion properly is just a big pain in the
a**.

There are some attempts, see for example

http://code.activestate.com/recipes/496691/

[Terry Reedy]

Re: Why no tailcall-optimization?

process wrote:

Why doesn't Python optimize tailcalls? Are there plans for it?

I started to write an article on this but it disappeared....
So short answer:
1. Unless down very carefully, in a way that would slow things down, it
would change the semantics of Python.
2. It is usually trivial to convert to a while loop, which amounts to
in-frame recursion. If using tail-recursion requires a nested inner
function to avoid repeating one-time initialization or exposing the
cumulation variable, writing the loop is easier since no nested function
is needed.
3. In Python, for loops are usually better for processing iterables,
which covers most uses of induction (recursion/iteration).

Terry Jan Reedy

[Carl Banks]

Re: Why no tailcall-optimization?

On Sep 22, 9:13 pm, process <circularf...@g mail.comwrote:

Why doesn't Python optimize tailcalls? Are there plans for it?

The main technical difficulty is that the compiler has to know whether
the function returns a tail call or not at compile time.

But because Python is fully dynamic with regard to type, the compiler
never(**) knows anything about any object other than "it's an
object". The compiler doesn't even know if the object is callable.

Probably it would be possible to achieve this optimization without
involving the compiler, but it'd be at cost of great complexity and
probably would negatively affect ordinary function calls (which are
already slow enough).

(BTW, if you're just talking about converting simple tail-recursive
functions, and not about general tail-call optimization, then I'd
suggest a third-party package would be better for that, since it would
be a pretty complex thing that would benefit only a tiny fraction of
users.)


Carl Banks


(**) Actually the compiler can do some compile-time constant
expression folding, but that's about it. Otherwise it's object
agnostic.

[sturlamolden]

Re: Why no tailcall-optimization?

On Sep 23, 3:13 am, process <circularf...@g mail.comwrote:

Why doesn't Python optimize tailcalls? Are there plans for it?

Because Python is a dynamic language. While a function is executing,
its name may be bound to another object. It may happen as a side
effect of what the function is doing, or even from another thread. The
compiler has no way of knowing that.

Recursion can always be expressed as iteration, possibly with a Python
list as stack.

[Rhamphoryncus]

Re: Why no tailcall-optimization?

On Sep 22, 7:13 pm, process <circularf...@g mail.comwrote:

Why doesn't Python optimize tailcalls? Are there plans for it?
>
I know GvR dislikes some of the functional additions like reduce and
Python is supposedly about "one preferrable way of doing things" but
not being able to use recursion properly is just a big pain in the
a**.

Eliminating tail calls affects the semantics of your program (by
changing memory complexity). As an optimization, it's a side-effect
of the implementation, which is a particularly nasty kind of side-
effect.

Even if guaranteed it's fairly subtle. "return x()" would be
optimized while "return x() + 1" would not. Or maybe you're calling a
function that uses a wrapper and the wrapper isn't tweaked right to be
optimized.

Recursion in general can be very useful, but not tail-recursion. The
only time it's not trivial to convert tail-recursion into a loop is
when it involves multiple functions, but even that can be done if you
know how.