Re: What happened to TCO?

[Andrea Corallo via "Emacs development discussions." <emacs-devel@gnu.org>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I see two different patches from 2012
>> https://lists.gnu.org/archive/html/emacs-devel/2012-12/msg00283.html
>> https://lists.gnu.org/archive/html/emacs-devel/2012-09/msg00477.html
>> Neither was merged but I don't see any reason presented in the mailing
>> list. Why were these changes not accepted?
>
> I think the lukewarm reception discouraged them.
>
> Also, the benefits were not made very clear: as Daniel pointed out back
> then, if the TCO is only applied when byte-compiled, then you can't
> always rely on it (while you can argue that interpreted code doesn't
> matter to some extent, we still rely crucially on interpreted code
> during the bootstrap and during Edebug sessions.  We could fairly easily
> circumvent the bootstrap problem, but for Edebug it requires a lot more
> work).  Also reliance on TCO means use of recursive calls, which may be
> undesirable even with TCO if recursive calls are more expensive than
> equivalent `while` loops.
>
> So, I think TCO with the current ELisp implementation should be seen
> first and foremost as an "opportunistic optimization" rather than a new
> semantic feature on which code can rely.  Which begs for
> benchmarks showing how it affects existing code.
> But we haven't seen any, AFAICT.
>
> There are of course also potential other side-effects (e.g. impacts on
> backtraces).  I think these are hard to judge without actually using
> such a patch for a while, so we'd probably want it to be conditional
> at first.
>
> BTW, in the meant time (i.e. quite recently), I implemented another form
> of TCO (much more limited than Chris Gray's patch, since it only applies
> to self recursion and only for functions defined with `cl-labels`), but
> one that works both for bytecode and for interpreted code (because the
> optimization is done during macroexpansion).

For completeness I just wanted to add that Tail Recursion Elimination is
already present in the native-comp branch when compiling at speed 3.

  Andrea