[Python-Dev] Re: Proper tail recursion

[Chris King]

On Fri, 16 Jul 2004 10:45:38 -0700, Josiah Carlson <jcarlson at uci.edu> wrote:
> 
> On Fri, 16 Jul 2004 09:23:15 -0400, Chris King <colanderman at gmail.com> wrote:
> 
> > 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

I wasn't clear enough -- by "turn off" I meant "throw out"; redefining
sys.excepthook will still store them (and thus take up memory).

The problem isn't whether or not tracebacks should be cut -- it's
whether huge lists of recursively entered stack frames should be kept
around.  If they are kept (a necessity for a proper traceback),
optimizing tail calls is almost worthless; indeed, it would be
entirely worthless in Stackless, which already allocates frames from
the heap.

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

The stack limit isn't the problem (it's very large, as far as I can
tell).  The memory used by holding onto stack frames that have no use
other than in tracebacks is the problem.

> 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***

This is exactly what the current patch does (minus the warning
message): it removes the memory overhead by tossing out extraneous
stack frames, at the cost of the availability of proper traceback
information.  Adding a warning would be trivial.