Explicit TCE

[Alex Rønne Petersen]

On 12-10-2012 19:29, Tyler Jameson Little wrote:
> I've read a few threads discussing tail call elimination, but they all
> wanted the spec to articulate specific circumstances where tail call
> elimination is required.  Has there been any thought to adding syntax to
> explicitly state tail call elimination?
>
> D could use something like Newsqueak's become keyword. If you're not
> familial with Newsqueak, become is just like a return, except it
> replaces the stack frame with the function that it calls. This was
> briefly mentioned years ago in this forum, but the become keyword was
> ignored:
>
> http://www.digitalmars.com/d/archives/digitalmars/D/Rob_Pike_s_Newsqueak_-_some_good_concepts_53511.html
>
>
> I think D could do something like this:
>
>      int fact(int n, int accum = 1) {
>          if (n == 0) {
>              return accum
>          }
>          // become means return, but guarantees TCE
>          become fact(n - 1, accum * n)
>      }
>
> DMD should optimize this already, but explicitly stating become is a key
> to the compiler that the user wants this call to be eliminated.  Then,
> more interesting things can be implemented more simply, like a state
> machine:
>
>      void stateA() {
>          become stateB();
>      }
>
>      void stateB() {
>          become stateC();
>      }
>
>      void stateC() {
>          return;
>      }
>
>      void main() {
>          become stateA();
>      }
>
> This would only take a single stack frame. If there were conditionals in
> there for branching, this could end up with a stack overflow because DMD
> does not support complicated TCE, only simple recursive TCE.
>
> The become keyword would probably have to have these properties:
>
>      * statement after become must only be a function call (can't do
> foo() + 3)
>      * scope() needs to be handled appropriately for functions with become
>
> There might be others. I'm not sure how D handles stack sizes, so this
> may be an issue as well if stack sizes are determined at runtime. A
> requirement could be that functions called with become need to have a
> static stack size, since this stack might never be collected (in the
> case of an infinite state machine).
>
> Adding this feature wouldn't cost much, but it would add a ton of
> functional power.

I'm a big fan of explicit, guaranteed TCE.

However, the primary problem with this approach is a really mundane one: 
The major compiler back ends (GCC and LLVM) don't have any means of 
guaranteeing TCE...

-- 
Alex Rønne Petersen
alex at lycus.org
http://lycus.org