Tail call elimination

[bearophile]

Walter Bright:

>I know how to do tail call optimization (it's a very old optimization), but there are some technical problems with it in the back end. In any case, tail call optimization is not necessary to do D-style functional programming, because loops with mutable indices are practical with pure functions.<

- I think GCC is able to perform tail call optimization in some situations, but not in all of them, I think it has some limits. So I presume that even if you know how to perform such optimization, you may not know how to make the compiler perform it in every situation.
- I know it's not necessary, just as closures aren't necessary in an OO language, because you can create a class every time you may want a closure. But functional programmers are used to use certain idioms, such idioms they are part of the functional style of mind (and they are useful because you can build over them. Functional programming is all about building functions using other functions). If you want to push some functional-style in D (and I think it's a good thing) then several things are necessary (quite useful) to allow such style of mind (even if some of them may look redundant to nonfunctional programmer, like closures). This is why I think things tail call elimination and a little may be useful if D wants to become more functional.
- I was mostly talking about D as a language, about its specs, not about DMD. So even if DMD isn't able to perform a tail call optimization, it may become part of its specs anyway. Putting it into the specs (for example like this: "every conformant D implementation must optimize tail calls in this and that situation") seems the only way to make people write code that uses such optimization: GCC has it, but very few C programs I see around rely on it because it's not part of the official C specs.
- I don't know if the LDC compiler is able to perform such optimization, or if can learn such trick. I think LDC can become an important part of the future of the D language.
- I have shown two documents (an HTML page and a pdf) that talk about two possible ways to implement forms of tail call elimination. One of similar ways can be used by DMD to perform some forms of tail call optimization so it can respect the D specs :-)

Bye,
bearophile