[Python-Dev] Re: Proper tail recursion

[Josiah Carlson]

On Fri, 16 Jul 2004 09:23:15 -0400, Chris King <colanderman at gmail.com> wrote:

> On Fri, 16 Jul 2004 00:52:07 -0700, Josiah Carlson <jcarlson at uci.edu> wrote:
> 
> > If unlimited recursion were allowed, perhaps limited tracebacks (first
> > and last 500 stack frame traces), RLE tracebacks (though a clever
> > programmer could easily destroy the generator with fewer than 64
> > functions, but we probably shouldn't do that), or combined limited and
> > RLE tracebacks would be sufficient. What do I mean by an RLE traceback?
> 
> I thought of doing RLE tracebacks, but compression fails in the case
> of cooperative recursive calls.  I think perhaps along with the
> sys.setrecursionlimit(None) option you suggest, developers should be
> allowed to turn recursive tracebacks off entirely in the case of
> cooperative recursive calls.

They already can by writing your own sys.excepthook callable. I think
the following would be sufficient for removing tracebacks...

def myexcepthook(type, value, traceback):
    print >>sys.stderr, "Exception:", type.__name__, ":", value


> The other problem with RLE tracebacks is that a traceback object also
> keeps a reference to each function's locals (by virtue of keeping a
> reference to its frame obejct).  Throwing this info out makes RLE
> tracebacks no more useful to debuggers than having no traceback at
> all.

Which is precisely why (in general) frames should not be tossed.  Even a
partial traceback is better than no traceback.


> Keeping the first and last X frames in a traceback seems reasonable,
> but this would similarly cripple debuggers (what happens if the bug is
> in the (X+1)th frame?).  Implementation would also be complicated.

Impementation is 99% done in the traceback module.

As for bugs appearing in frame X+1, I'm not concerned.  20, 30, 40
levels of traceback, yeah, I (and others I'm sure) have gone through
those.  But as soon as you start hitting 500 levels of traceback, all
but the first and last few dozen are noise.

Honestly, I'd like to see a real application that has a bug only in
recursion level 501.  However, I'm not sure one would ever come to exist
if the programmer used any sort of reasonable modern development methods
(test-driven, design by contract, etc.), and were remotely competant.

To me, the point of limiting tracebacks to 1000 calls was to reduce
and/or remove the liklihood of someone getting a multi-meg email via
logging.SMTPHandler, or filling up their filesystem with a
logging.FileHandler.


> IMHO it should be an all-or-nothing deal: either the programmer turns
> tail-call optimizations on to nullify memory uses, or turns them off
> to facilitate debugging.

IMO it shouldn't be only about tail-call optimizations.  Andrew Koenig
suggested that frames be allocated from the heap, which if it is
possible (is there anything that gets executed directly by the processor
so we have to worry about processors supporting NX?), seems to remove
the C stack limit.

In the case of tail-calls, more optimizations could be done (optionally),
to remove the overhead on tail calls (also removing information
containing tracebacks), but the user should be warned that while it
would reduce memory usage, all they get from the traceback are lines are
like so:
***recursive tail call frames removed as requested***

Now, because it seems as though one could easily mix regular and tail
calls, the following traceback seems reasonable (if optional tail call
optimizations were done)...

Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 3, in g
  File "<stdin>", line 3, in h
***recursive tail call frames removed as requested***
  File "<stdin>", line 3, in i
...


 - Josiah