What happened to TCO?

What happened to TCO?

[Troy Hinckley]

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?

Re: What happened to TCO?

[Stefan Monnier]

> 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).


        Stefan

Re: What happened to TCO?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Wed, 17 Mar 2021 22:30:13 -0400
> Cc: emacs-devel@gnu.org
> 
> > 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.

Maybe.  This is for them to tell (and I hope that's not the case).

From where I stand, these two didn't go in because the discussion
wasn't followed-up to get to that "LGTM" point where we can land the
feature.  Valid questions and considerations were brought up in each
of the two cases, but some of them were left unresolved.  Stefan
mentioned some of them.  In addition, I would like to remind us that
meanwhile we got the native-compilation feature, which is very close
to land on master, and one new question is how would these proposals
interact with it.

Feel free to respin one of those proposals based on current code, or
make some hybrid patch out of them.  If and when the issues discussed
then are resolved, I think this optimization will be a welcome
addition to Emacs.

Re: What happened to TCO?

[Andrea Corallo via Emacs development discussions.]

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