Bob Felts <wrf3@stablecross.com> wrote:
+---------------
| Kent M Pitman <pitman@nhplace.com> wrote:
| > A recursive function can run out of stack since CL does not guarantee
| > tail call elimination. 
| 
| Any pointers to the rationale for this decision?
+---------------

In addition to what others have replied, there are many constructs
in CL for which it's either difficult to "do the right thing" with
a tail call or even know *what* "the right thing" would be if one
were trying to perform tail-call optimization, for example:

- Tail-calling out of blocks in which dynamic variables were rebound.

- Tail-calling out of blocks wrapped by UNWIND-PROTECT.

- Tail-calling out of blocks wrapped by HANDLER-CASE or HANDLER-BIND.
  [IGNORE-ERRORS is the same as HANDLER-CASE.]

- Non-local exits from exception handlers or restarts.

- Heck, non-local exits, period!

And even in the simple cases, it's a debatable question whether the
tail-call optimization has to be *completely* "safe-for-space" or
merely "safe-for-stack". The difference has to do with references
to dynamically "dead" data which might appear to still be lexically
"live" due to the way closure environments are constructed. See the
plentiful published Scheme & ML literature for more on this.[1]

Also see <http://groups.google.com/group/comp.lang.lisp/browse_thread/
thread/d62865297bde3c41/8f9dcf58a00aca27?hl=en&lnk=st&q=#8f9dcf58a00aca27>
"CL Implementations and Tail-Call Elimination", from September 2007,
in which I developed some simple CL macrology for allowing "cooperating
tail-call groups" of functions to share a loop/trampoline emulation of
true tail-call optimization. [But note that this is still not necessarily
completely "safe-for-space", depending on your implementation, nor does it
"do the right thing" in the exceptional cases mentioned above!!]


-Rob

[1] A couple of refs to get you started:

       http://flint.cs.yale.edu/flint/publications/escc.html
       "Efficient and Safe-for-Space Closure Conversion".
       Zhong Shao & Andrew Appel
       [In ACM Transactions on Programming Languages and
       Systems (TOPLAS), 22(1), pages 129-161, January 2000.]

       ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz
       "Proper tail recursion and space efficiency"
       William D. Clinger
       [In the Proceedings of the 1998 ACM Conference on Programming
       Language Design and Implementation, June 1998, pages 174-185.]

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607