Tail Recursion

["Scott B. Layson" <gyro@KESTREL.ARPA>]

   Date: Wed, 22 Feb 89 17:51 EST
   From: Reti@RIVERSIDE.SCRC.SYMBOLICS.COM

       Date: Wed, 22 Feb 89 11:52 EST
       From: Stever@YUKON.SCRC.Symbolics.COM (Stephen Robbins)

       I've asked for years for some way to allow tail-recursion.  DCP sent me
       an excellent discussion of tail-recursion issues (which I've long since
       deleted), which boiled down to two points:

   I suspect there must have been more points which you've forgotten.  One problem
   is that there is a fair amount of state associated with a stack frame that pertains
   to cleanup now that would have to be stored elsewhere if multiple invocations of
   a function shared a stack frame.  Two that come to mind immediately are unwind-protects
   and stack-consed-presentation cleanups.

Frames with unwind-protects, dynamic bindings, stack consing, etc.
don't get removed from the stack on a tail-call.  That's true even in
Scheme implementations.

   Also, how do you set the trap-on-exit flag on one (but not several) of these tail-recursively
   called frames?

The problem is not when a frame has been *called* tail-recursively,
but rather when it goes to call something else tail-recursively.
(Think about it.)  Either you trap before the tail-call, or the
trap-on-exit bit, like the frame-has-special-bindings bit, keeps a
frame from being deleted from the stack.  I think both of those
options are useful in different situations.

Um, let me put that slightly differently.  There should be a bit
settable on a function that specifies that its frames should not be
deleted even if they otherwise would be (because it has no special
bindings etc.).  Trap-on-exits on frames that are doing a
CALL-n-RETURN that will be done tail-recursively should be done before
the call.

This approach requires no compiler modifications, though we still have
not heard word from Symbolics on whether the architecture(s) can
support it efficiently.

-- Scott