Explicit TCE

[Tyler Jameson Little]

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.