Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Steven D'Aprano]

On Tue, 14 Jul 2015 06:33 pm, Marko Rauhamaa wrote:

> Ian Kelly <ian.g.kelly at gmail.com>:
> 
>> On Mon, Jul 13, 2015 at 11:57 PM, Marko Rauhamaa <marko at pacujo.net>
>> wrote:
>>> How about "return"?
>>
>> I think you miss my point entirely. "return" doesn't mean tail-call
>> optimize;
> 
> Why not?

Because then you lose most of your debugging information when an exception
occurs and a stack trace is printed.


>> it just means to return the result.
> 
> Same difference.

If "return" was the same as "return and TCO", we wouldn't be having this
discussion, because Python would have had TCO for over 20 years. So the two
must clearly be different.

And I think that's the solution. If we had two key words, let's say "return"
and "treturn" ("tail-return"), where treturn performed TCO when possible,
then the programmer could TCO some functions and not others, according to
whether they feared bugs in the function more or less than hitting the
recursion limit.

That's better than a global setting or switch, and better than a TCO
decorator, since it would even allow you to TCO some paths through a
function but not others.

I'm undecided about what should happen if you use treturn in a non-tail call
situation. Should it simply fall back to regular return? Or should it raise
an exception? (Preferably at compile time, if not possible, at runtime.)

The downside is that this would put responsibility on the programmer to
decide whether to TCO or not. Well, potential downside. Using a TCO
decorator or switch to enable it also puts responsibility on the
programmer, but that's usually considered a good thing.


>> This is what led to the confusion responsible for the bug that Chris
>> pointed out in the first place. With a keyword that explicitly means
>> "perform tail-call optimization *and* return",
> 
> That could well be the explicit definition of the "return" statement in
> Python without changing the behavior of any working Python program
> today.

Really? If it doesn't change the behaviour, why bother making the change?

It would change the behaviour of code. Code which currently breaks for
sufficiently large data may no longer break. That's a plus. Code which
currently generates tracebacks -- which may actually be *intended*
behaviour and not a bug, e.g. in test suites -- will change their behaviour
and be significantly less useful. That's a minus.


>> the association of the keyword with the optimization is much clearer,
>> and the programmer is much less likely to mistakenly omit it.
> 
> The programmer shouldn't be controlling tail call optimizations.

Why not? The programmer should control ALL optimizations that have a
semantic effect. I think constant folding is okay[1], everything else is
dubious and should be under the control of the programmer, not the compiler
writer.

I find it rather unnerving to think that I've written code to do something
in a certain way, and somebody else (the compiler writer) decides to
silently change that to something which may or may not have the same
effect. The *intent* is that it should have the same effect, but in
practice that's often not the case. Compiler optimizations often break
floating point algorithms (e.g. inappropriately deciding that x + y - x
must equal y) or introduce security bugs.

Here's an example where an overzealous but standards-conforming optimization
introduced a security bug:

http://code.google.com/p/nativeclient/issues/detail?id=245

According to the compiler writer, the code before and after the optimization
had precisely the same meaning. According to the developers. who should
know because they wrote it, the optimized code was missing a rather large
function: sanitising untrusted data.

C, in my opinion, is the poster child for how a programming language should
NOT be designed, and I don't want Python to go down the same path. John
Regehr writes:

"... there are compilers (like GCC) where integer overflow behaved a certain
way for many years and then at some point the optimizer got just a little
bit smarter and integer overflows suddenly and silently stopped working as
expected. This is perfectly OK as far as the standard goes. While it may be
unfriendly to developers, it would be considered a win by the compiler team
because it will increase benchmark scores."

http://blog.regehr.org/archives/213

So, no, I don't want the compiler making optimizations I can't control. 




[1] Only because Python gives us no standard way to control the floating
point rounding mode.

-- 
Steven