www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Tail call optimization?

reply =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
Does D to tail call optimization of any kind?

-- 
- Alex
Mar 18 2012
parent reply bearophile <bearophileHUGS lycos.com> writes:
Alex Rønne Petersen Wrote:


 Does D to tail call optimization of any kind?


The D standard doesn't require the D compiler to perform that optimization
(unlike Scheme).
Currently both DMD and LDC are able to perform tail call optimization in some
normal cases. And I presume GDC is able to do the same.

Bye,
bearophile
Mar 18 2012
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
On 18/03/2012 21:28, bearophile wrote:

 Alex Rønne Petersen Wrote:


 Does D to tail call optimization of any kind?


 The D standard doesn't require the D compiler to perform that optimization
(unlike Scheme).
 Currently both DMD and LDC are able to perform tail call optimization in some
normal
 cases. And I presume GDC is able to do the same.


What are "normal cases"?

- where the function directly tail-calls itself?
- where two functions mutually tail-call each other?
- where a function tail-calls another non-recursively?

And in the last case, I can see that it depends on being able to replace the
caller's 
stack frame with the callee's.  But what does this depend on - just the
relative sizes of 
the functions' stack frames, or is it more subtle than that?

Stewart.
Mar 19 2012
parent reply bearophile <bearophileHUGS lycos.com> writes:
Stewart Gordon:


 What are "normal cases"?


It means "very simple cases". Things like fibonacci / factorial functions that
call themselves at the tail.

Generally it's a fragile optimization, it's easy for it to not work/stop
working. LLVM used to perform this optimization, then it stopped working for
months an no one noticed. I have written a bug report and they have made it
work again. And then they have put it in their demo :-)
http://llvm.org/demo/

Bye,
bearophile
Mar 19 2012
parent =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
On 19-03-2012 13:07, bearophile wrote:

 Stewart Gordon:


 What are "normal cases"?


 It means "very simple cases". Things like fibonacci / factorial functions that
call themselves at the tail.

 Generally it's a fragile optimization, it's easy for it to not work/stop
working. LLVM used to perform this optimization, then it stopped working for
months an no one noticed. I have written a bug report and they have made it
work again. And then they have put it in their demo :-)
 http://llvm.org/demo/

 Bye,
 bearophile


I still don't understand why compilers don't just provide *guaranteed, 
well-defined* tail calls when the emitted IR demands it... this whole 
"it may or may not be TCO'd" business is ridiculous.

-- 
- Alex
Mar 19 2012