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