Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93760 > unrolled thread

Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 00:05 +1000
    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-14 13:20 +1000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 09:26 +0200
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 02:34 -0600
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Grant Edwards <invalid@invalid.invalid> - 2015-07-14 14:03 +0000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 12:43 +0200
    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-13 22:15 -0700
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 15:25 +1000
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-13 22:41 -0700
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 21:43 +1000
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 15:28 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 22:55 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 16:38 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 23:43 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:29 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 03:48 +1000
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 10:28 +0200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-14 16:02 +0200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 00:07 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:31 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 20:41 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 11:10 +0200
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:43 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 09:31 +0200
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-17 10:41 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-16 21:45 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 15:56 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 00:00 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-16 16:32 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 02:43 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 19:50 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 03:03 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 10:04 -0700
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 20:34 +0300
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-17 04:58 +1000
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 22:14 +0300
                            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-17 11:41 +1200
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ethan Furman <ethan@stoneleaf.us> - 2015-07-16 12:52 -0700
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 03:49 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Joonas Liik <liik.joonas@gmail.com> - 2015-07-16 21:23 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 04:29 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-16 16:19 -0400
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 12:48 +0200
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-19 10:57 +1200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 21:05 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 13:43 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 21:49 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-17 14:54 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-17 23:12 +1000
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-17 16:27 -0400
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-15 21:13 +1200
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 12:55 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-15 12:22 +0100
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:34 +1200
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-16 00:34 +0100
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) MRAB <python@mrabarnett.plus.com> - 2015-07-15 13:00 +0100
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 22:13 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-16 10:34 +1200
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 22:22 +1000
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 08:41 +0300
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 21:33 +1000
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 15:08 +0300
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-14 15:31 +1000
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-13 23:46 -0600
        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 08:57 +0300
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-14 18:29 +1200
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 10:05 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-07-15 17:52 +1200
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 09:44 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ned Batchelder <ned@nedbatchelder.com> - 2015-07-15 03:45 -0700
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 13:55 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2015-07-15 13:04 +0200
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ned Batchelder <ned@nedbatchelder.com> - 2015-07-15 04:12 -0700
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 14:24 +0300
                          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Rustom Mody <rustompmody@gmail.com> - 2015-07-16 21:28 -0700
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-07-14 08:47 +0100
          Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 02:13 -0600
            Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 11:33 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-14 07:15 -0600
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:27 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ian Kelly <ian.g.kelly@gmail.com> - 2015-07-15 08:28 -0600
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-15 17:55 +0300
              Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 03:34 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 20:43 +0300
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 03:52 +1000
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Steven D'Aprano <steve@pearwood.info> - 2015-07-15 04:06 +1000
                    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 21:37 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 04:55 +1000
                        Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-14 22:12 +0300
                      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 21:36 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 21:01 -0400
                  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Chris Angelico <rosuav@gmail.com> - 2015-07-15 13:05 +1000
                Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Paul Rubin <no.email@nospam.invalid> - 2015-07-14 10:54 -0700
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-14 20:23 -0400

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

#93873

On Tue, Jul 14, 2015 at 11:27 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> On Tue, Jul 14, 2015 at 2:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>> The programmer shouldn't be controlling tail call optimizations.
>>
>> The programmer controls it regardless.
>>
>>     return foo()  # TCO
>>
>>     result = foo()  # No TCO
>>     return result  # No TCO
>
> Not necessarily. Compile this function with gcc ("gcc -S -O2 atoi.c"):
>
> ========================================================================
> int atoi(const char *str, int n)
> {
>     if (str && *str)
>         n = atoi(str + 1, n * 10 + *str - '0');
>     return n;
> }
> ========================================================================
> (Example modified from <URL: http://stackoverflow.com/questions/34125/wh
> ich-if-any-c-compilers-do-tail-recursion-optimization#220660>.)
>
> You'll see that the generated code is tail-call-optimized.

This can't be done generally, though. What if, instead of a local
variable, the assignment were to a dict item? Even if the dict itself
is a local variable, the assignment can't be optimized away.

[toc] | [prev] | [next] | [standalone]

#93874

Ian Kelly <ian.g.kelly@gmail.com>:

> On Tue, Jul 14, 2015 at 11:27 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> You'll see that the generated code is tail-call-optimized.
>
> This can't be done generally, though. What if, instead of a local
> variable, the assignment were to a dict item? Even if the dict itself
> is a local variable, the assignment can't be optimized away.

Of course, you can only do correct optimizations. My point is that tail
call optimizations should not be micromanaged by the programmer.


Marko

[toc] | [prev] | [next] | [standalone]

#93822

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

> Ian Kelly <ian.g.kelly@gmail.com>:
> 
>> On Mon, Jul 13, 2015 at 11:57 PM, Marko Rauhamaa <marko@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

[toc] | [prev] | [next] | [standalone]

#93824

Steven D'Aprano <steve@pearwood.info>:

> 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."

The problem there is in the C standard, not the compiler that complies
with the standard.

I don't like the way integer overflows are explicitly undefined in
modern C.

Similarly, I don't like the way tail call behavior is undefined in
Python.

Neither blemish gives me much trouble in practice.


Marko

[toc] | [prev] | [next] | [standalone]

#93826

On Wed, Jul 15, 2015 at 3:43 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> I don't like the way integer overflows are explicitly undefined in
> modern C.
>
> Similarly, I don't like the way tail call behavior is undefined in
> Python.

Where in the Python spec is it stated that tail call behaviour is
undefined? The behaviour of the 'return' statement is well defined: it
evaluates its expression (or None), *then* removes the top of the call
stack and passes control back to the caller:

https://docs.python.org/3/reference/simple_stmts.html#the-return-statement

This implies that during the evaluation of its expression, the current
function's call stack entry is still present. Tail call behaviour is
therefore well defined: it is identical to any other expression
evaluation, and then the final result is passed back to the caller.

ChrisA

[toc] | [prev] | [next] | [standalone]

#93828

On Wed, 15 Jul 2015 03:43 am, Marko Rauhamaa wrote:

> The problem there is in the C standard, not the compiler that complies
> with the standard.
> 
> I don't like the way integer overflows are explicitly undefined in
> modern C.
> 
> Similarly, I don't like the way tail call behavior is undefined in
> Python.

Tail call behaviour is not undefined in Python. There is a strong convention
(followed by all implementations I know of) to follow the reference
implementation's (CPython) behaviour, which is not to optimize tail calls.
But even if an implementation chooses to not follow that, it's not
*undefined behaviour*. It's just implementation-dependent behaviour.

No Python compiler is permitted to format your hard drive because you
perform a tail call.


> Neither blemish gives me much trouble in practice.

Given how even the best, cleverest, and most security conscious C
programmers get repeatedly bitten by C undefined behaviour, I'm confident
that if you've written any non-trivial C code, it almost certainly has bugs
because of undefined behaviour, you've just never noticed them yet. Perhaps
the specific version of the compiler you use doesn't optimize that case, or
you've never tried it with data that exposes the introduced bugs.


"Making the landmine a much much worse place to be is the fact that there is
no good way to determine whether a large scale application is free of
undefined behavior, and thus not susceptible to breaking in the future.
There are many useful tools that can help find some of the bugs, but
nothing that gives full confidence that your code won't break in the
future."

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html


So, if you make it a habit to religiously compile your C applications with
all warnings turned on, and you actually read *and fix* them all, AND you
scan the applications with Valgrind, the Clang static analyser, and
whatever other tools you can find, then you *might* have good reason to be
reasonably confident that your code is *mostly* free of C undefined
behaviour bugs.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#93830

Steven D'Aprano <steve@pearwood.info>:

> Tail call behaviour is not undefined in Python. There is a strong
> convention (followed by all implementations I know of) to follow the
> reference implementation's (CPython) behaviour, which is not to
> optimize tail calls. But even if an implementation chooses to not
> follow that, it's not *undefined behaviour*. It's just
> implementation-dependent behaviour.

But in Scheme, tail call elimination is mandatory and thus can be relied
on. Unless that promise is made, you can't write code that depends on
it.


Marko

[toc] | [prev] | [next] | [standalone]

#93831

On Wed, Jul 15, 2015 at 4:37 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Steven D'Aprano <steve@pearwood.info>:
>
>> Tail call behaviour is not undefined in Python. There is a strong
>> convention (followed by all implementations I know of) to follow the
>> reference implementation's (CPython) behaviour, which is not to
>> optimize tail calls. But even if an implementation chooses to not
>> follow that, it's not *undefined behaviour*. It's just
>> implementation-dependent behaviour.
>
> But in Scheme, tail call elimination is mandatory and thus can be relied
> on. Unless that promise is made, you can't write code that depends on

I think I'm beginning to understand. Tail call elimination is
necessary to cope with a system of programming that has deliberately
excluded certain other options (eg mutables, in pure functional
languages), but is not as important in a more fully-featured language.
Constant folding would be the same way; it's not absolutely critical,
and if Python doesn't support it for some particular expression then
it's not going to kill you, but in SPL [1] it would be a vital
efficiency improvement. Scheme needs TCE because of the way you have
to write code for Scheme to be even capable of executing it; Python
doesn't, because you can write your code to not need TCE.

[1] https://en.wikipedia.org/wiki/Shakespeare_(programming_language)#Constants_and_Assignment_of_Values

ChrisA

[toc] | [prev] | [next] | [standalone]

#93833

Chris Angelico <rosuav@gmail.com>:

> Tail call elimination is necessary to cope with a system of
> programming that has deliberately excluded certain other options (eg
> mutables, in pure functional languages),

Tail call elimination is necessary for the functional programming style.
While Scheme strongly promotes it, functional programming style crops up
in virtually all programming languages nowadays.

> but is not as important in a more fully-featured language.

It is not all that important in Python for idiomatic reasons, not for
some "full-featuredness".

> Scheme needs TCE because of the way you have to write code for Scheme
> to be even capable of executing it; Python doesn't, because you can
> write your code to not need TCE.

You can write Sheme perfectly procedurally, but why would you do that
when you have Python to satisfy your procedural urges?


Marko

[toc] | [prev] | [next] | [standalone]

#93842

> I think I'm beginning to understand. Tail call elimination is
> necessary to cope with a system of programming that has deliberately
> excluded certain other options (eg mutables, in pure functional
> languages),

Tail recursion is the functional way to write a while loop.  To put is 
another way, a while loop is within stackframe recursion.  Ditto for for 
loops, which are specialized while loops.

Recursion, first (or car), rest (or cdr), and linked lists 
(non-mutational stacks with the top at the front) work together as a 
tightly coordinated system.  (rest ll) is equivalent to ll[1:] except 
that rest does not mutate anything. When Python's ll.pop(0) (or ll.pop() 
removes and returns (first ll), it does mutate ll.  Since ll becomes 
what was previously (rest ll), there is no need for a separate list.rest 
method.

Python's next(it) is also does the job of both first + rest. As with 
pop(0), it removes the first item of it, mutates it so it represents the 
rest of the items in the collection it represents, and then returns the 
initial item. Again, there is no need for a separate rest(it) funciton. 
  The fundamental computational idea in both systems, beneath the 
differing syntax and religious wars, is that we can process a collection 
by processing one item at a time.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#93841

On 7/14/2015 1:52 PM, Chris Angelico wrote:
> On Wed, Jul 15, 2015 at 3:43 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> I don't like the way integer overflows are explicitly undefined in
>> modern C.
>>
>> Similarly, I don't like the way tail call behavior is undefined in
>> Python.
>
> Where in the Python spec is it stated that tail call behaviour is
> undefined? The behaviour of the 'return' statement is well defined: it
> evaluates its expression (or None), *then* removes the top of the call
> stack and passes control back to the caller:
>
> https://docs.python.org/3/reference/simple_stmts.html#the-return-statement

I do not see anything there explicitly about call stacks.

> This implies that during the evaluation of its expression, the current
> function's call stack entry is still present. Tail call behaviour is
> therefore well defined: it is identical to any other expression
> evaluation, and then the final result is passed back to the caller.

In the blog post
http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
that everyone discussing this issue should read, Guido said that if a 
tail call is not within a try statement, tco would be fine except for 
the implementation issue of helpful tracebacks, which he cares greatly 
about.  However, as both he and the linked doc say, a tail call within a 
try: statement is not a tail call, in that more python code within the 
function may yet be executed.

It is not hard to construct an example in which tco would mess up a 
traceback message that is displayed.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#93844

On Wed, Jul 15, 2015 at 11:01 AM, Terry Reedy <tjreedy@udel.edu> wrote:
> On 7/14/2015 1:52 PM, Chris Angelico wrote:
>>
>> On Wed, Jul 15, 2015 at 3:43 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>
>>> I don't like the way integer overflows are explicitly undefined in
>>> modern C.
>>>
>>> Similarly, I don't like the way tail call behavior is undefined in
>>> Python.
>>
>>
>> Where in the Python spec is it stated that tail call behaviour is
>> undefined? The behaviour of the 'return' statement is well defined: it
>> evaluates its expression (or None), *then* removes the top of the call
>> stack and passes control back to the caller:
>>
>> https://docs.python.org/3/reference/simple_stmts.html#the-return-statement
>
>
> I do not see anything there explicitly about call stacks.

There isn't anything explicitly about call stacks, but it clearly
states that the expression is evaluated, and *then* processing of the
return statement occurs. Unlike C, Python doesn't have "undefined
behaviour"; there are some things which are "implementation-defined",
but that's a different concept. But the spec is reasonably clear by
implication, in my opinion; if tail calls are allowed to remove stack
entries, that definition will need to be edited. (That's not to say it
can't be, of course. But it would be a change.)

ChrisA

[toc] | [prev] | [next] | [standalone]

#93827

Steven D'Aprano <steve@pearwood.info> writes:
> 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

In that particular example, the refactored code simply looks wrong.

[toc] | [prev] | [next] | [standalone]

#93838

On 7/14/2015 1:15 AM, Paul Rubin wrote:

>    def quicksort(array, start, end):
>       midp = partition(array, start, end)
>       if midp <= (start+end)//2:
>          quicksort(array, start, midp)
>          quicksort(array, midp+1, end)
>       else:
>          quicksort(array, midp+1, end)
>          quicksort(array, start, midp)
>
> I assume you know how quicksort and its partition step work.  The idea
> is you partition the array around the pivot element (midp is the index
> of that element), then recursively sort the two partitions, doing the
> smaller partition as a recursive call and the larger one as a tail call,
> so that you use O(log n) stack depth instead of potentially O(n).

Thank you for the example.  It I have ever seen how to minimize the max 
stack needed for first calls, I have forgotten.  First some comment:
1. There is no terminal condition, so the above will loop forever. The 
body should start with 'if not terminal(start, end):' where terminal is 
the actual expression.  I did not write it because it depends on whether 
'end' is the highest index or one past it.
2. There are no tail calls (call followed by return), so a tail-call 
optimizer will not optimize this.  A recur() function might be able to.
3. Mutation is anathema to functional programming, so a functional 
programmer would never write and version of this, at least not without 
holding his nose.

The tail-like calls in each branch can be avoided with assignment and 
gobacks.  In Python, we go-back with while loops. (IE, 'while' = 'label' 
+ 'if' + 'goto'.)  With minimal change to the above, we get (untested)

def quicksort(array, start, end):
     while not terminal(start, end):
         midp = partition(array, start, end)
         if midp <= (start+end) // 2:
             quicksort(array, start, midp)
             start = midp+1
         else:
             quicksort(array, midp+1, end)
             end = midp

I can understand that someone might prefer to break the symmetry of the 
paired calls by wrapping the second with recur() (assuming that such a 
function is sensibly feasible on *all* implementations).  In the other 
hand, I prefer the reduced-noise explicit assignment that highlights the 
one parameter that gets rebound.

-- 
Terry Jan Reedy

[toc] | [prev] | [standalone]

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

Back to top | Article view | comp.lang.python

csiph-web