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
[email protected]
http://lycus.org
