Re: Tail Recursion in Common Lisp ???

[Bradley C. Kuszmaul <bradley@Think.COM>]

Perhaps this has been mentioned before, but one way to think about
tail recursion which allows the right thing to happen if the user
modifies the definition of the function in the middle of running it is
to do as follows: Do the tail recursion by "goto"'ing indirectly
through the symbol's function cell (rather than by "goto"'ing directly
to the location where the code happens to be).  (Of course, the "goto"
would reclaim the stack space of the current function call before allocating
the stack space for the recursive call.)

This allows the efficiency (mod one indirect pointer chase) of the
classical tail recursion (i.e. it does not eat up stack), with the program
illness of common-lisp (i.e. the semantics are preserved for dynamic 
redefinition of functions)

Such a mechanism does screw up some debuggers, but we could argue that
 * Implementors who want good debuggers should not do tail recursion, or
 * Implementors should only do tail recursion if some appropriate declaration
   is made.
Thus, there may be programming environment reasons (the debugger) for not
doing tail recursion, but it is possible to efficiently support tail recursion
even in the face of dynamic redefinition of function names.

In fact, this approach allows all of the "tail calls" to be optimized
by using the same "goto" mechanism, so mutually recursive functions
which are defined and compiled separately could win.

(One could even get rid of the extra pointer chase in the truly
recursive case by stating that if an INLINE declaration is made for
the function, then dynamic redefinition of the function is not allowed
and a direct goto could be used.)

 -Brad