Re: tail-call elimination

[Chris Gray]

Daniel Colascione <address@hidden> writes:
> On 12/10/2012 6:57 PM, Chris Gray wrote:
>> Hello,
>> 
>> I have attached a patch that implements tail-call elimination for a subset of
>> emacs lisp.  This will be helpful in allowing coding styles which emphasize 
>> tail
>> recursion, such as is usual in languages like Scheme. 
>
> Your patch eliminates tail calls only in byte compiled code. Until the
> interpreter also supports guaranteed tail call elimination or we byte-compile
> all forms before evaluating them, elisp developers cannot rely on the
> optimization and cannot write idiomatic tail recursive code. As a purely
> opportunistic optimization, not as a guaranteed language feature, I doubt tail
> call elimination is worth the complexity.

I agree that the fact that the code must be byte-compiled makes it
harder to do interactive programming.  In many cases, however, small
tests can be done interactively to verify that the function is correct
before compiling it.  These would likely not blow up the stack, and thus
tail-call elimination would not be needed.  When the function has been
shown to work, it can be byte-compiled fairly simply.

I do, however, think that it's a bit inaccurate to say that this is a
purely opportunistic optimization.  It is guaranteed in the case that
your code is byte-compiled and lexically bound.  I would love to widen
that subset of the language to include things that aren't byte-compiled
(or to byte-compile automatically), but I've gotta start somewhere.

Cheers,
Chris