"Benji Smith" <Benji_member@pathlink.com> wrote in message news:b5a1tn$2pcd$1@digitaldaemon.com...
> So....will the DMD compiler do tail-call optimizations? It that a compiler feature that's on the drawing board, or is it not a priority?

It can do it, it's just not a priority.

DDevil wrote:
> OK, after looking at the assembly, it looks like D is not doing tail-call
> optimizing at all.  GCC and MSVC optimize it very nicely and that's why
> they run so fast.  They completely remove the recursive calls by using
> jmp. This effectively turns it into a for-loop. 
> 
> It's interesting because I was comparing the Fibonacci Numbers benchmark
> which runs about the same in C and D.  After looking at the assembly, I
> see that GCC is not able do tail-call optimizing for that benchmark (in
> theory it _should_ be able to, but it might be more difficult).

Show me the code for that fibonacci. If it's the most naive recursive one, it *can't* be optimised by tail recursion elimination.

To understand it, you have to turn to the definition of tail recursion. Why is it called "tail"? It is in the cases, when a recursive function calls itself, but does not process a result it gets back in any way, simply returning it. This results in the interesting stack behaviour: after the stack has been built up by sucessive recursive calls, there is a computation result on top of it, of which you know it would get passed to the bottom without change. So you don't need to return n times to get to the bottom: simply decrease the stack pointer and put the result there. Furthermore, that actually means, that all those stack values were not requiered to be saved in the first place. So the tail recursion elimination kicks in and transforms the function - or a mutually recursive set of functions - into a loop. Cuts off the tail, so to say.

In our first days of OCaml we were taught, that we have to change our recursion to behave like that - so that result is created unchanged in a topmost function call. This usually involves passing more arguments to the recursive function. The optimisation is very important for functional programming - where you don't want to or can't use the loops explicitly - but for a usual programmer with imperative background it does little. Like, this style doesn't even make your code terser, it just requeres you to spend time picking up names for all these tiny functions. :>

Mind that when comparing C and D it's not fair to campare DMD against GCC, unless you have also compared DMC with GCC. A compiler can't be better than its underlying backend.

> I can't remember when GCC does the tail-call optimizing so I don't know if
> using it as a back-end would help.

It should in those cases "to whom it may apply". :>
Besides, we would get a debugger and i could finally install D on a sparc at the university!

-i.

On Tue, 25 Mar 2003 19:36:07 +0100, Ilya Minkov wrote:

> DDevil wrote:
> Show me the code for that fibonacci. If it's the most naive recursive
> one, it *can't* be optimised by tail recursion elimination.

It's listed with the rest of the D Language Shootout programs I've ported. http://www.functionalfuture.com/d

And yes, it is a naive recursive version, and it must be implemented that way (or close to it) for the shootout.

> To understand it, you have to turn to the definition of tail recursion.

Trust me, I know.  I have spent many an hour in Erlang and OCaml.  I probably should have worded my post differently.  In theory _any_ recursive function can be optimized into a loop given a smart enough back-end or compiler.  Note that I'm not only talking about tail-call elimination at this point, but recursion optimization in general.

> Mind that when comparing C and D it's not fair to campare DMD against GCC, unless you have also compared DMC with GCC. A compiler can't be better than its underlying backend.

True, but in the benchmark I was specifically testing Walter's default back-end against GCC and MSVC's.

--
// DDevil

"Ilya Minkov" <midiclub@8ung.at> wrote in message news:b5q744$22cp$1@digitaldaemon.com...
> Mind that when comparing C and D it's not fair to campare DMD against GCC, unless you have also compared DMC with GCC. A compiler can't be better than its underlying backend.

You're right. Any speed/size comparison of D vs C/C++ should be done with DMC/C++, since then the languages are being compared rather than the back ends.