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 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#93840

On 7/14/2015 10:02 AM, Antoon Pardon wrote:
> On 07/14/2015 03:43 PM, Chris Angelico wrote:
>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net> wrote:

>>> No, tail call optimization doesn't change the behavior of the program,
>>> for the worse anyway.
>> It does, because you lose traceback records. That's pretty significant
>> when you come to try to debug something.
>
> I doubt it would be really significant. Not compared to writing it iteratively.
> When you write it iteratively, you don't get to keep a traceback record per time
> you go throught the loop. So the traceback records you loose in tale call elimination
> would be the traceback records you wouldn't have anyway in the iterative version.

To repeat: loosing tracebacks is probably fine when the function has a 
single *recursive* tail call.  This are precise the cases when it is 
simple and perhaps preferable to use a loop.  But *recursive* tail calls 
are only a small fraction of all tail calls.  So most of the time, the 
loss *would* be significant.  Consider

In moda: def f(a): return modb.g(a-3)

In modb: def g(b): return modc.h(b*(b-1))

In modc: def h(c): return 1.0/c

from moda import f
... (500 lines later)
f(3)

and your traceback has been reduced to

   In modc: line 1
      return 1.0/c
ZeroDivisionError: ...

???

-- 
Terry Jan Reedy

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

#93855

On 07/15/2015 02:41 AM, Terry Reedy wrote:
> On 7/14/2015 10:02 AM, Antoon Pardon wrote:
>> On 07/14/2015 03:43 PM, Chris Angelico wrote:
>>> On Tue, Jul 14, 2015 at 11:38 PM, Marko Rauhamaa <marko@pacujo.net>
>>> wrote:
>
>>>> No, tail call optimization doesn't change the behavior of the program,
>>>> for the worse anyway.
>>> It does, because you lose traceback records. That's pretty significant
>>> when you come to try to debug something.
>>
>> I doubt it would be really significant. Not compared to writing it
>> iteratively.
>> When you write it iteratively, you don't get to keep a traceback
>> record per time
>> you go throught the loop. So the traceback records you loose in tale
>> call elimination
>> would be the traceback records you wouldn't have anyway in the
>> iterative version.
>
> To repeat: loosing tracebacks is probably fine when the function has a
> single *recursive* tail call.  This are precise the cases when it is
> simple and perhaps preferable to use a loop.  But *recursive* tail
> calls are only a small fraction of all tail calls.  So most of the
> time, the loss *would* be significant.  Consider

But it doesn't need to be all or nothing. How about the following possibility.
When the runtime detects a serie of tail calls, it will keep the bottom three
and the top three backtrace records of the serie. And when it needs to print
a stacktrace it writes an indication that some tracebacks are missing. I think
that would be a workable compromise between workable tail call recursion
and usefull stacktraces.

Now of course there are some other problems like what if the tail call is into
a C-function. I don't think you want to drop a stack frame in those circumstances.
So I guess implementing this and getting all corner cases right, will not be
trivial and I understand if the core developers don't consider this a high
priority. But one likes to dream sometimes.

-- 
Antoon Pardon 

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

#93886

Antoon Pardon wrote:
> But it doesn't need to be all or nothing. How about the following possibility.
> When the runtime detects a serie of tail calls, it will keep the bottom three
> and the top three backtrace records of the serie.

Whatever value you choose for N, keeping only the
first/last N traceback frames will lead to someone
tearing their hair out.

I recently had an experience with some Java code
running in an environment which believed that nobody
would want to see more than about 30 traceback levels,
and chopped the rest off. Of course, the information
I desperately wanted was buried deeper than that...

So, -1 on any arbitrarily chosen traceback cutoff.

-- 
Greg

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

#93912

On 07/16/2015 12:43 AM, Gregory Ewing wrote:

> Antoon Pardon wrote:
>> But it doesn't need to be all or nothing. How about the following possibility.
>> When the runtime detects a serie of tail calls, it will keep the bottom three
>> and the top three backtrace records of the serie.
> Whatever value you choose for N, keeping only the
> first/last N traceback frames will lead to someone
> tearing their hair out.

I would say, that someone should get over himself.
Traceback are not the only or even the most useful
tool for debugging code. The current stack trace
doesn't even contain the value's of the variables
on the stack. So in case of Terry Reedy's example
that stack trace would IMO have been next to useless.

> I recently had an experience with some Java code
> running in an environment which believed that nobody
> would want to see more than about 30 traceback levels,
> and chopped the rest off. Of course, the information
> I desperately wanted was buried deeper than that...

So? My experience is, that if you need to dig that deep
in a stack trace, to find the information you need, you
get it easier and faster by turning debug level logging
on and going through the logs. YMMV.

I also have to wonder, In my suggestion you would only start
to loose traceback records after six consecutive tail calls.
That IMO strongly suggest a loop. Most people suggest such
a loop should be written iteratively. So my example would
allow to keep 6 trace back records through such a loop
while the iterative version would only keep one trace back
record. But no one seems to be tearing their hair out
for not having trace back records of the previous run
through a loop. Yet you protest when trace back records
disappear when such a loop is written recursively.
 

> So, -1 on any arbitrarily chosen traceback cutoff.

Noted. It just doesn't carry much weight with me.

-- 
Antoon Pardon

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

#93968

Antoon Pardon wrote:
> On 07/16/2015 12:43 AM, Gregory Ewing wrote:
> 
>>Whatever value you choose for N, keeping only the
>>first/last N traceback frames will lead to someone
>>tearing their hair out.
> 
> I would say, that someone should get over himself.
> Traceback are not the only or even the most useful
> tool for debugging code.

They're the one thing I miss the most whenever I have
to debug something in an environment that doesn't provide
them, though,

 > My experience is, that if you need to dig that deep
> in a stack trace, to find the information you need, you
> get it easier and faster by turning debug level logging
> on and going through the logs. YMMV.

That only helps if the code logs the information you need
or can be easily modified to do so. In my case, it didn't
and couldn't.

> I also have to wonder, In my suggestion you would only start
> to loose traceback records after six consecutive tail calls.
> That IMO strongly suggest a loop.

Not necessarily. Chains of calls very often go more than 6
levels deep. It's less likely that they would all happen to
be tail calls, but it could happen without there being any
looping or recursion involved. And the source of the problem
you're trying to debug could be in *any* of the intermediate
calls, not necessarily the first or last 3.

-- 
Greg

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

#93925

On Thu, Jul 16, 2015 at 5:31 PM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/16/2015 12:43 AM, Gregory Ewing wrote:
>
>> Antoon Pardon wrote:
>>> But it doesn't need to be all or nothing. How about the following possibility.
>>> When the runtime detects a serie of tail calls, it will keep the bottom three
>>> and the top three backtrace records of the serie.
>> Whatever value you choose for N, keeping only the
>> first/last N traceback frames will lead to someone
>> tearing their hair out.
>
> I would say, that someone should get over himself.
> Traceback are not the only or even the most useful
> tool for debugging code. The current stack trace
> doesn't even contain the value's of the variables
> on the stack. So in case of Terry Reedy's example
> that stack trace would IMO have been next to useless.

Actually, they do contain all of that (at least, they do in Py3 - not
sure about Py2 as I haven't checked). You can poke around with the
locals at every point on the stack:

def f(x):
    if x < 10: g(x+10)
    return 5

def g(x):
    if x % 3: h(x + 2)
    return 7

def h(x):
    return 1/x

try:
    x = -12
    print(f(x))
except ZeroDivisionError as e:
    tb = e.__traceback__
    while tb:
        fr = tb.tb_frame
        print("In function %s (%s:%d), x = %r" % (
            fr.f_code.co_name,
            fr.f_code.co_filename,
            fr.f_lineno,
            fr.f_locals["x"],
        ))
        tb = tb.tb_next


It's all there. And it's immensely helpful.

ChrisA

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

#93928

On 07/16/2015 01:45 PM, Chris Angelico wrote:
> On Thu, Jul 16, 2015 at 5:31 PM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>>
>> I would say, that someone should get over himself.
>> Traceback are not the only or even the most useful
>> tool for debugging code. The current stack trace
>> doesn't even contain the value's of the variables
>> on the stack. So in case of Terry Reedy's example
>> that stack trace would IMO have been next to useless.
> Actually, they do contain all of that (at least, they do in Py3 - not
> sure about Py2 as I haven't checked). You can poke around with the
> locals at every point on the stack:

Fine, I should have been more clear.

The stack trace as it is generally produced on stderr after an uncought
exception, doesn't contain the values of the variables on the stack.

-- 
Antoon Pardon

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

#93929

On Thu, Jul 16, 2015 at 11:56 PM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/16/2015 01:45 PM, Chris Angelico wrote:
>> On Thu, Jul 16, 2015 at 5:31 PM, Antoon Pardon
>> <antoon.pardon@rece.vub.ac.be> wrote:
>>>
>>> I would say, that someone should get over himself.
>>> Traceback are not the only or even the most useful
>>> tool for debugging code. The current stack trace
>>> doesn't even contain the value's of the variables
>>> on the stack. So in case of Terry Reedy's example
>>> that stack trace would IMO have been next to useless.
>> Actually, they do contain all of that (at least, they do in Py3 - not
>> sure about Py2 as I haven't checked). You can poke around with the
>> locals at every point on the stack:
>
> Fine, I should have been more clear.
>
> The stack trace as it is generally produced on stderr after an uncought
> exception, doesn't contain the values of the variables on the stack.

Sure. So you catch it at top level and grab whatever info you need. In
some frameworks, this is already done for you - an uncaught exception
from application code drops you into a debugger that lets you explore
and even execute code at any level in the stack.

This would be destroyed by automated tail call optimization.

ChrisA

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

#93932

On 07/16/2015 04:00 PM, Chris Angelico wrote:
> On Thu, Jul 16, 2015 at 11:56 PM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>> Fine, I should have been more clear.
>>
>> The stack trace as it is generally produced on stderr after an uncought
>> exception, doesn't contain the values of the variables on the stack.
> Sure. So you catch it at top level and grab whatever info you need. In
> some frameworks, this is already done for you - an uncaught exception
> from application code drops you into a debugger that lets you explore
> and even execute code at any level in the stack.

What is unclear about "as it is generally produced on stderr"? That you
can do a whole lot of stuff, doesn't mean that this whole lot of stuff is
part of what generally happens. When people on this list ask a person
to include the stacktrace with the description of the problem, they
don't mean something that includes the values of the variables.

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

#93935

On Fri, Jul 17, 2015 at 12:32 AM, Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
> On 07/16/2015 04:00 PM, Chris Angelico wrote:
>> On Thu, Jul 16, 2015 at 11:56 PM, Antoon Pardon
>> <antoon.pardon@rece.vub.ac.be> wrote:
>>> Fine, I should have been more clear.
>>>
>>> The stack trace as it is generally produced on stderr after an uncought
>>> exception, doesn't contain the values of the variables on the stack.
>> Sure. So you catch it at top level and grab whatever info you need. In
>> some frameworks, this is already done for you - an uncaught exception
>> from application code drops you into a debugger that lets you explore
>> and even execute code at any level in the stack.
>
> What is unclear about "as it is generally produced on stderr"? That you
> can do a whole lot of stuff, doesn't mean that this whole lot of stuff is
> part of what generally happens. When people on this list ask a person
> to include the stacktrace with the description of the problem, they
> don't mean something that includes the values of the variables.

True. That said, though, it's not a justification for dropping stack
frames; even in the form that's printed to stderr, there is immense
value in them. It may be possible to explicitly drop frames that a
programmer believes won't be useful, but a general and automated
dropping of tail-call information will do more harm than good. The
fact that some frameworks can show _even more_ helpful information out
of a traceback only makes this stronger.

ChrisA

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

#93936

Wouldn't it be possible to have like a dynamically
sized stack so that you can grow it endlessly
with some acceptable overhead..

That would pretty much take care of the stack-overflow
argument without many painful side effects on
the semantics at least..

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

#93937

On Fri, Jul 17, 2015 at 2:50 AM, Joonas Liik <liik.joonas@gmail.com> wrote:
> Wouldn't it be possible to have like a dynamically
> sized stack so that you can grow it endlessly
> with some acceptable overhead..
>
> That would pretty much take care of the stack-overflow
> argument without many painful side effects on
> the semantics at least..

The trouble with that is that it can quickly run you out memory when
you accidentally trigger infinite recursion. A classic example is a
simple wrapper function...

def print(msg):
    print(ctime()+" "+msg)

With the recursion limit at its default of 1000, this can't do more
than 1000 iterations before the system detects that it's stuck. With
an infinite stack, this could destroy your system memory and then
finally terminate with MemoryError... if you're lucky. If you're not,
the whole system could get wedged before this gets killed. (Imagine,
for instance, a computer with a large hard disk devoted to virtual
memory. Long before that's exhausted, the system will be practically
unusable, because every little operation will require going back to
the disk.)

ChrisA

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

#93938

On 07/16/2015 09:43 AM, Chris Angelico wrote:

> True. That said, though, it's not a justification for dropping stack
> frames; even in the form that's printed to stderr, there is immense
> value in them. It may be possible to explicitly drop frames that a
> programmer believes won't be useful, but a general and automated
> dropping of tail-call information will do more harm than good. The
> fact that some frameworks can show _even more_ helpful information out
> of a traceback only makes this stronger.

If we had a general mechanism then we would also need to have a setting somewhere so we could adjust which frames to keep when debugging.

I must say I don't see much value in a stack trace that says a called b called c called a called b called c called a called ... -- particularly when the line quoted has only the variable names, not 
their values, so you can't see what's changing.

Of this whole thread, though, I like the 'recurse' keyword proposal best -- I have no issues with the programmer specifying when to ditch the stack frame, but maybe that's my assembly roots showing. ;)

--
~Ethan~

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

#93940

On 16 July 2015 at 20:03, Chris Angelico <rosuav@gmail.com> wrote:
>
> The trouble with that is that it can quickly run you out memory when
> you accidentally trigger infinite recursion. A classic example is a
> simple wrapper function...
>
> def print(msg):
>     print(ctime()+" "+msg)
>
> With the recursion limit at its default of 1000, this can't do more
> than 1000 iterations before the system detects that it's stuck. With
> an infinite stack, this could destroy your system memory and then
> finally terminate with MemoryError... if you're lucky. If you're not,
> the whole system could get wedged before this gets killed. (Imagine,
> for instance, a computer with a large hard disk devoted to virtual
> memory. Long before that's exhausted, the system will be practically
> unusable, because every little operation will require going back to
> the disk.)
>

That all sounds reasonable. However that can be looked another way.
Soppose you have some code that traverses some tree, a strange
imbalanced tree (say from some xml)

It is, semantically at least, a reasonable aproach to process such a
structure with some recursive function.
Lets say we have a function that counts all <li> elements in a
document for example. and recursively traverses the element tree.
Because most xml is relatively flat (let's assume its rare to find
more than 100 levels of nesting say) this function would perform
perfectly well for most cases.
however if some guy sent you an xml document with 1000 levels of
nesting your program would crash.

Now suddenly you have perfectly good functioning code that randomly
crashes. because of some arbitrary limit.
it most distinctly reminds me of a certain programming language that
kills your thread after 30000 operations because you are
obviously-in-an-infinite-loop.
it leaves a very bad taste in my mouth.

That 30k limit (much less lines of source code ofc) is the reason you
need nasty hacks to do stuff like implement BigInteger.
That 1k stack limit is the limit you cant use perfectly good code
just because your input data has some weird quirk.

This puts python on par with jass2 and this deeply saddens me.

Now i admit that it is possible to have infinite recursion but it is
also possiblew to have infinite loops. and we don't kill your code
after 1000 iterations of a while loop so why should we treat recursion
any differently?

Having a user defined maximum stack limit might be a good idea, eg if
my stack takes up 100MB its prolly broke, but it should be my duty as
a programmer to specify such a limit, not have it inflicted upon me
(worse, in a manner that cannot be changed!).

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

#93951

On Fri, 17 Jul 2015 03:34 am, Joonas Liik wrote:

> Now i admit that it is possible to have infinite recursion but it is
> also possiblew to have infinite loops. and we don't kill your code
> after 1000 iterations of a while loop so why should we treat recursion
> any differently?

Because a while loop which repeats to many times is annoying but harmless,
but a function that recurses too many times will blow up the stack and
cause a seg fault, possibly executing arbitrary memory as code. You want
malware and viruses to take over your system? That's how you get malware
and viruses to take over your system.


> Having a user defined maximum stack limit might be a good idea, eg if
> my stack takes up 100MB its prolly broke, but it should be my duty as
> a programmer to specify such a limit, not have it inflicted upon me
> (worse, in a manner that cannot be changed!).

You mean sys.getrecursionlimit() and sys.setrecursionlimit()?



-- 
Steven

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

#93953

On 16 July 2015 at 21:58, Steven D'Aprano <steve@pearwood.info> wrote:
> On Fri, 17 Jul 2015 03:34 am, Joonas Liik wrote:
>
>> Now i admit that it is possible to have infinite recursion but it is
>> also possiblew to have infinite loops. and we don't kill your code
>> after 1000 iterations of a while loop so why should we treat recursion
>> any differently?
>
> Because a while loop which repeats to many times is annoying but harmless,
> but a function that recurses too many times will blow up the stack and
> cause a seg fault, possibly executing arbitrary memory as code. You want
> malware and viruses to take over your system? That's how you get malware
> and viruses to take over your system.

That's just a buggy implementation, there are ways to extend the stack
that nears its capacity, safely.

>
>> Having a user defined maximum stack limit might be a good idea, eg if
>> my stack takes up 100MB its prolly broke, but it should be my duty as
>> a programmer to specify such a limit, not have it inflicted upon me
>> (worse, in a manner that cannot be changed!).
>
> You mean sys.getrecursionlimit() and sys.setrecursionlimit()?
>
... and that buggy implementation means that when you
sys.setrecursionlimit() you will overflow the stack and crash because
the recursion limit is an aritificial safeguard and the underlying c
buffer is not adjusted accordingly or at least so it would seem.

https://docs.python.org/2/library/sys.html#sys.setrecursionlimit
so as per the docs the programmer has no real control over how much
stack his program can have. all you can say is "let me ignore the
safeguard a little longer, i hope i wont crash the program" that is
not the same as "can i please have a stack depth of 20000..

You are giving the programmer a choice between "run out of stack and
crash" and "mutilate interpreter internals and crash or zero out the
hard drive" this is not a real choice..

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

#93971

Joonas Liik wrote:
> https://docs.python.org/2/library/sys.html#sys.setrecursionlimit
> so as per the docs the programmer has no real control over how much
> stack his program can have. all you can say is "let me ignore the
> safeguard a little longer, i hope i wont crash the program" that is
> not the same as "can i please have a stack depth of 20000..

I don't think there's much that can be done about that.

If CPython doesn't impose an artificial limit, then it's at
the mercy of the C compiler and runtime system as to the
handling of stack overflows.

The only way for CPython to take total control of the stack
situation would be to get the C stack out of the picture
altogether, using techniques such as the original Stackless
Python employed. But the BDFL has ruled out CPython ever
going that way, because it would massively warp the C API.

-- 
Greg

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

#93958

On 07/16/2015 12:14 PM, Joonas Liik wrote:

> You are giving the programmer a choice between "run out of stack and
> crash" and "mutilate interpreter internals and crash or zero out the
> hard drive" this is not a real choice..

+1

--
~Ethan~

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

#93942

On Fri, Jul 17, 2015 at 3:34 AM, Joonas Liik <liik.joonas@gmail.com> wrote:
> That all sounds reasonable. However that can be looked another way.
> Soppose you have some code that traverses some tree, a strange
> imbalanced tree (say from some xml)
>
> It is, semantically at least, a reasonable aproach to process such a
> structure with some recursive function.
> Lets say we have a function that counts all <li> elements in a
> document for example. and recursively traverses the element tree.
> Because most xml is relatively flat (let's assume its rare to find
> more than 100 levels of nesting say) this function would perform
> perfectly well for most cases.
> however if some guy sent you an xml document with 1000 levels of
> nesting your program would crash.

This sounds like a denial-of-service attack. If you can state that no
reasonable document will ever have more than 100 levels of nesting,
then you can equally state that cutting the parser off with a tidy
exception if it exceeds 100 levels is safe.

> Now i admit that it is possible to have infinite recursion but it is
> also possiblew to have infinite loops. and we don't kill your code
> after 1000 iterations of a while loop so why should we treat recursion
> any differently?

Partly because infinite recursion requires infinite storage too. If it
truly is tail calls, then you can turn it into a while loop and not
have the limit; otherwise, you run the risk of blowing out your RAM.

> Having a user defined maximum stack limit might be a good idea, eg if
> my stack takes up 100MB its prolly broke, but it should be my duty as
> a programmer to specify such a limit, not have it inflicted upon me
> (worse, in a manner that cannot be changed!).

Actually, it is up to you. There's a default, but you can change it.

>>> def recurse(n): return n and recurse(n-1)
...
>>> recurse(998)
0
>>> recurse(999)
(throws RuntimeError)
>>> sys.getrecursionlimit()
1000
>>> sys.setrecursionlimit(5)
>>> recurse(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in recurse
  File "<stdin>", line 1, in recurse
  File "<stdin>", line 1, in recurse
  File "<stdin>", line 1, in recurse
RuntimeError: maximum recursion depth exceeded
>>> sys.setrecursionlimit(5000)
>>> recurse(5000)
(throws RuntimeError with a gigantic traceback)
>>> sys.setrecursionlimit(50000)
>>> recurse(50000)
Segmentation fault

Though as you can see, CPython does have other issues. If you crank
the recursion limit up far enough, you *will* blow out your C stack.
Other Pythons may behave differently, and different builds of CPython
may crash at different points. But within reason, you can expand this
limit, and you can certainly shrink it (eg to reduce the effect of a
tree-parser DOS attack).

ChrisA

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

#93946

On 16 July 2015 at 20:49, Chris Angelico <rosuav@gmail.com> wrote:
>
> This sounds like a denial-of-service attack. If you can state that no
> reasonable document will ever have more than 100 levels of nesting,
> then you can equally state that cutting the parser off with a tidy
> exception if it exceeds 100 levels is safe.
>
This particular example does have that kind of smell.. my bad for
being careless with examples.

what if its not a ddos tho, maybe its just strange data?

how about you run some genetic algorithm to optimise something, and
you store a log of your progress as a tree structure.
then you have a script to traverse that tree for some reason, maybe to
analyse the history and optimise the parameters of the search in the
future.
when the problem is complex it might well require thousands of steps
to get to the desired outcome..

but over time the log grows longer and longer.

at first as the script is written it's probably tested on some rather
small logs, but they grow over time so eventually your program will
implode on completely reasonable input.

notice that the tree grows at a constant rate with generations rather
than ~log(n) so it will not reach a natural limit other than finding a
satisfying solution.

whether that limit be 1k or 8k there is no single limit that is
reasonable for all use cases and the range you can vary it is rather
restricted..


(notice: this example has the issue with the genetic algorithm being
potentially expensive to run so it might not reach the 1k limit, but
that does not mean there are not other problems that share this
property. what I want to convey here is that not all tree traversal
has a natural depth limit and there are cases where it will be hit
even with completely natural inputs)

>
> Partly because infinite recursion requires infinite storage too. If it
> truly is tail calls, then you can turn it into a while loop and not
> have the limit; otherwise, you run the risk of blowing out your RAM.

A valid argument. tho 100MB stack space vs infinite stack space is
still very much distinct.

For a long running program it might not even be a big issue if some of
the stack (the very bottom) is swapped to disk as the top will be nice
and warm in the cache. and yes such a program is not exactly common
but just because it uses a lot of memory does not mean it has
"frozen". it is the job of the programmer to say how much heap his
program can use and it is also his job to say how much stack space is
acceptable.

also:

def much_memory_1(str):
    return munch_memory_1(str+"munch much memory!")

much_memory_1(str)

--vs--
def much_memory_2(str):
    tmp = str[:]
    while True:
        tmp +="munch much memory!"
    return tmp  # will never reach this

much_memory_2(str)


>> Having a user defined maximum stack limit might be a good idea, eg if
>> my stack takes up 100MB its prolly broke, but it should be my duty as
>> a programmer to specify such a limit, not have it inflicted upon me
>> (worse, in a manner that cannot be changed!).
>
> Actually, it is up to you. There's a default, but you can change it.
>
>>>> def recurse(n): return n and recurse(n-1)
> ...
>>>> recurse(998)
> 0
>>>> recurse(999)
> (throws RuntimeError)
>>>> sys.getrecursionlimit()
> 1000
>>>> sys.setrecursionlimit(5)
>>>> recurse(5)
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "<stdin>", line 1, in recurse
>   File "<stdin>", line 1, in recurse
>   File "<stdin>", line 1, in recurse
>   File "<stdin>", line 1, in recurse
> RuntimeError: maximum recursion depth exceeded
>>>> sys.setrecursionlimit(5000)
>>>> recurse(5000)
> (throws RuntimeError with a gigantic traceback)
>>>> sys.setrecursionlimit(50000)
>>>> recurse(50000)
> Segmentation fault

..as i recall reading from a certain stackoverflow post the limit was
about 8000 and possibly varying..

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

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

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

csiph-web