Subject: Re: Was not making tail recursion elmination a mistake?
From: rpw3@rpw3.org (Rob Warnock)
Date: Fri, 11 Jun 2004 23:39:50 -0500
Newsgroups: comp.lang.lisp
Message-ID: <v5qdnacNM8mLFFfd4p2dnA@speakeasy.net>
Svein Ove Aas  <svein+usenet01@brage.info> wrote:
+---------------
| Pascal Costanza wrote:
| > John Thingstad wrote:
| >> I have recently been annoyeed by the fact that tail recursion
| >> elimination is not part of the standard. ...
| >> What is the historic reason for this omission?
| > 
| > There are situations in which it is better not to eliminate tail
| > recursions (better debuggability, more restart options), so it would
| > have been an optional feature. The ANSI standard generally doesn't cover
| > optional features (or so it seems to me).
|
| It seems to me that you could make it an obligatory feature that has an
| option to be turned off by the programmer.
| Tail-call elimination isn't exactly hard to do, is it?
+---------------

When you *can* do it, no. But compared to Scheme, in CL it's a lot harder
to specify exactly when you can and can't do it -- and there are a *lot*
more places in CL where you *can't* than in Scheme.

Take a look at R5RS Scheme's section "3.5 Proper tail recursion", and
look at how very particular they had to be to define "tail calls", "active
tail calls" and "tail contexts", especially the recursive/inductive
definition of the latter. You basically need a full code-walker to
decide whether a given form is is is not a tail call (or in a tail
context).

Now consider writing the same section for Common Lisp, being sure
to "do the right thing" with regard to dynamically-bound variables,
UNWIND-PROTECT contexts (and other exception contexts, both HANDLER-
CASE-style *and* HANDLER-BIND-style), ill-specified things such as
TRACE, and non-standard but universally-desired things such as ADVISE
and threads.[1] Be sure that your document specifies "the right thing"
in all of these cases, *and* that the Common Lisp community *agrees*
that it's "the right thing" in each case.

Isn't exactly easy to do, is it?


-Rob

[1] Oh, and FFIs: Is a tail call to a foreign function that then
    makes what looks like a tail call back into Lisp that then makes
    a tail call *really* a "tail call"? Or is there junk on the stack
    waiting to blow your never-terminating state-machine-implememnted-
    as-tail-calls out of the water, hmmm?

    List the answer for each of the possible FFI suites anybody might
    want to use, with each Common Lisp implememntation anybody might
    ever want to use.

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