tail recursion and debugging

[gyro@ukulele.reasoning.com (Scott Layson Burson)]

   Date: Mon, 23 Apr 90 15:10:24 PDT
   From: Warren Harris <harris@hplwhh.hpl.hp.com>

   There's a lot of talk about how tail-recursion affects resource utilization.
   What about how it affects the programming environment?  Certainly whether an
   implementation performs tail-recursion elimination or not is visible in the
   debugging process (e.g. in a backtrace).  It's presence may make debugging more
   difficult because intermediate stack frames may be eliminated.  I think this
   aspect is just as important as whether the machine runs out of stack space or
   not.  They're both properties of the implementation.

I have been using a tail-recursive Common Lisp recently (Coral Common Lisp on
the Macintosh), and have formed some opinions about the interaction of tail
recursion and debugging.  Specifically, I do sometimes miss those stack frames.
On the other hand, I also sometimes find it extremely handy to take advantage
of tail recursion.

Coral's implementation provides a global switch that one can use to turn off
the compiler's generation of tail-recursive code.  This is an awfully blunt
instrument.  Here is what I have proposed to them as an alternative arrangement
that I believe would satisfy me entirely:

 1) Most calls would *not* be tail-recursive, except:

 2) I could declare groups of functions such that calls from any one to any
    other function in the group would be tail-recursive;

 3) A top-level function and any functions declared inside it (i.e. with LABELS
    or FLET) would automatically constitute such a group;

 4) (optional) A declaration exists for overriding (3);

 5) TAIL-FUNCALL is provided to override the default in specific cases.

Several CL compilers I know of implement (3) but not, to my knowledge, (2); but
I consider (2) to be a very important property (it makes possible a most
natural and convenient implementation of finite-state automata, for instance).

I believe, based on my experience to date, that this arrangement would let me
do everything I want to do with tail-recursion while still leaving those handy
stack frames around in the cases where it's not important to me that it remove
them.

I don't offhand see any difficulting in adapting this to Scheme; does anyone
else?  -- Though I concede in advance the distastefulness of having something
like TAIL-FUNCALL (or perhaps just "TAIL-CALL" or maybe even "GOTO" (!!)) after
we've gone to such lengths to get rid of anything that looks like that.  Even
so, I believe I would prefer this watering-down over uncompromising tail-
recursive purism.

On the other hand, maybe the use of the stack as the primary source of
information about the history of the computation is actually an unfortunate
historical accident.  Maybe we should, as GLS hints, find other ways of
recording debugging information as it goes by.  A FIFO buffer showing some
number of the most recent procedure invocations with their arguments would
often be much more useful than a stack backtrace, because after all, in a stack
backtrace there is no information whatever about values computed by frames that
have been returned from.

Well, I think this message will be controversial enough to kick off another
flurry of replies... here goes!

-- Scott