[Python-Dev] Re: Proper tail recursion (original) (raw)

Josiah Carlson jcarlson at uci.edu
Fri Jul 16 19:45:38 CEST 2004

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 "", line 1, in ? File "", line 3, in g File "", line 3, in h recursive tail call frames removed as requested File "", line 3, in i ...

More information about the Python-Dev mailing list