[Python-ideas] Tail recursion elimination

[Haoyi Li]

> Having to fork the entire compiler just to write a few functions in
> their most idiomatic, natural (recursive) form seems a bit extreme,
> wouldn't you say?

You don't need to.

MacroPy's @tco decorator is about as easy as you could ask for. 'pip
install macropy', 'from macropy.experimental.tco import macros, tco' is
about as easy as you could ask for. Works for arbitrary tail-calls too,
not just tail recursion.

If you haven't tried it out, complaining about the difficulty of
implementing tail-call-optimization yourself seems silly.
From: Andrew Barnert
Sent: 1/19/2014 12:04 PM
To: Steven D'Aprano; python-ideas at python.org
Subject: Re: [Python-ideas] Tail recursion elimination
From: Steven D'Aprano <steve at pearwood.info>

Sent: Saturday, January 18, 2014 4:45 PM


> On Sat, Jan 18, 2014 at 10:29:46AM -0800, Andrew Barnert wrote:
>
>>  Whether or not you really need it, adding it to Python is a fun
>>  challenge that's worth trying.
>
> "Need" is a funny thing.

Which I why I made that point. It's not a completely objective
question, and it may be hard for the OP (or you, or anyone else) to
convince anyone that he "needs" it even though he does (or, more
importantly, convince people that _they_ need it). If so, he doesn't
have to let that stop him from writing and sharing an implementation.
It may turn out that, once people have a chance to play with it, that
will convince everyone better than any abstract argument he could
make. If not, at least he's had fun, learned about CPython internals,
and, most importantly, produced a fork that he can maintain as long as
he thinks he needs it. Depending on your time and resources, that may
not be worth doing, but that's the same decision as any other
development project; there's nothing actually stopping anyone from
doing it if it's worth their while, so anyone who wants this should
consider whether it's worth their while to do it.

> You can go a long way without recursion, or only shallow recursion. In
> 15 years + of writing Python code, I've never been in a position that I
> couldn't solve a problem because of the lack of tail recursion. But
> every time I manually convert a recursive algorithm to an iterative one,
> I feel that I'm doing make-work, manually doing something which the
> compiler is much better at than I am, and the result is often less
> natural, or even awkward. (Trampolines? Ewww.)


But the same is true for converting a naive recursive algorithm to
tail-recursive. It's unpleasant make-work, just like converting it to
iteration. In a language like Common Lisp, it's about the same amount
of work, but the tail-recursive version often ends up looking more
natural. In a language like Python, where we typically deal in
iterables rather than recursive data structures, I believe it would
often be _more_ work rather than the same amount, and end up looking a
lot less natural rather than more. I'm sure there would be exceptions,
but I suspect they would be rare.

>>  Third, eliminating tail calls means the aren't on the stack at
>>  runtime, which means there's no obvious way to display useful
>>  tracebacks. I don't think too many Python users would accept the
>>  tradeoff of giving up good tracebacks to enable certain kinds of
>>  non-pythonic code,
>
> What makes you say that it is "non-pythonic"? You seem to be assuming
> that *by definition* anything written recursively is non-pythonic.

Not at all. There's plenty of code that's naturally recursive even in
Python—and much of that code is written recursively today. For a good
example, see os.walk.

However, the main driver for TCE is the ability to write looping
constructs recursively, which is not possible without it (unless the
thing you're looping over is guaranteed not to be too big). Look at
any tutorial on tail recursion; it's always recursing over a cons list
or something similar. And looping that way in Python will almost
always be non-pythonic, because you will have to drive the iterable
manually. Again, there are surely exceptions, but I doubt they'd be
very common.

> In fact, in some cases, I *would* willingly give up *non-useful*

> tracebacks for the ability to write more idiomatic code. Have you seen
> the typical recursive traceback?

But if you eliminate tail calls, you're not just eliminating recursive
tracebacks; you're eliminating every stack frame that ends in a tail
call. Which includes a huge number of useful frames.

If you restrict it to _only_ eliminating recursive tail calls, then it
goes from something that can be done at compile time (as I showed in
my previous email) to something that has to be done at runtime, making
every function call slower. And it doesn't work with mutual or
indirect recursion (unless you want to walk the whole stack to see if
the function being called exists higher up—which makes it even slower,
and also gets us back to eliminating useful tracebacks).

> py> a(7)
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 9, in c
>     return 1/n
> ZeroDivisionError: division by zero
>
> The only thing that I care about is the very last line, that function c
> tries to divide by zero. The rest of the traceback is just noise, I
> don't even look at it.

Your example is not actually tail-recursive.

I'm guessing you know this, and decided that having something that
blows up fast just to have an example of a recursive traceback was
more important than having an example that also fits into the rest of
the discussion—which is perfectly reasonable.

But it's still worth calling that out, because at least half the blog
posts out there that say "Python sucks because it doesn't have TCE"
prove Python's suckiness by showing a non-tail-recursive algorithm
that would blow up exactly the same way in Scheme as in Python.

> Now, it's okay if you disagree, or if you can see something useful in

> the traceback other than the last entry.

Sure. Unless that line in b is the only place in your code that ever
calls c, I think it would be useful to know how we got to c and why n
is 0. If that isn't useful, than _no_ tracebacks are ever useful, not
just recursive ones.

> I'm not suggesting that TCE
> should be compulsary. I would be happy with a commandline switch to
> turn it on, or better still, a decorator to apply it to certain
> functions and not others. I expect that I'd have TCE turned off for
> debugging.

But the primary reason people want TCE is to be able to write
functions that otherwise wouldn't run. Nobody asks for TCE because
they're concerned about 2KB wasted on stack traces in their shallow
algorithm; they ask for it because their deep algorithm fails with a
recursion error. So, turning it off to debug it means turning off the
ability to reproduce the error you're trying to debug.

>>  but even if you don't solve this, you can always

>>  maintain a fork the same way that Stackless has been doing.
>
> Having to fork the entire compiler just to write a few functions in
> their most idiomatic, natural (recursive) form seems a bit extreme,
> wouldn't you say?


Not necessarily.

The whole reason Stackless exists is to be able to write some
algorithms in a natural way that wasn't possible with mainline
CPython. At least early on, it looked at least plausible that
Stackless would eventually be merged into the main core, although that
turned out not to happen. There are some core language changes that
were inspired by Stackless. Someone (Ralf Schmidt, I think?) was able
to extract some of Stackless's functionality into a module that works
with CPython, which is very cool. But even without any of that, people
were able to use Stackless when they wanted to write code that
required its features. That's surely better than not being able to
write it, period.

And a TCE fork could go the same way. It might get merged into the
core one day, or it might inspire some changes in the core, or it
might turn out to be possible to extract the key functionality into a
module for CPython—but even if none of that happens, you, and others,
can still use your fork when you want to.

If you prefer to call it a patch or a branch or something else instead
of a fork, that's fine, but it's basically the same amount of work
either way, and there's nothing stopping anyone who wants it from
doing it.
_______________________________________________
Python-ideas mailing list
Python-ideas at python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/