• Reiner Pope (64/64) Aug 13 2006 What are the rules about template recursion, and compile time evaluation...
• Walter Bright (7/26) Aug 14 2006 This happens when the compiler itself runs out of stack space. This

Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:

What are the rules about template recursion, and compile time evaluation 
in general? For example, the following code produces an error on my 
computer:

import std.stdio;

template count(uint n)
{
     static if (n == 0) const uint count = 0;
     else const uint count = 1 + count!(n-1);
}

int main(char[][] args)
{
     writefln("%d", count!(3008));
     return 0;
}

factorial.d(6): template instance factorial.count!(1u) recursive expansion

So it recurses too deeply. But if I sidestep the recursion, then it's 
OK. A double-instantiation works:

int main(char[][] args)
{
     writefln("%d", count!(3002)); // Doesn't recurse as deep
     writefln("%d", count!(3008)); // Can stop recursing when 3002 is 
reached
     return 0;
}

But when I use the same process to get much bigger, I get problems again:

int main(char[][] args)
{
     writefln("%d", count!(3007));
     writefln("%d", count!(4000));
     writefln("%d", count!(5000));
     return 0;
}

When attempting to compile, this gives me:

c:\reiner\d\tools\dmd\bin\..\..\dm\bin\link.exe 
factorial,,,user32+kernel32/noi;

--- errorlevel 1

as well as a messagebox entitled 'Unexpected OPTLINK Termination at 
EIP=0044C37B' with a dump of the registers.

And the compiler is crashed by user code. Not a good thing, in my opinion.

What is the deal with compile-time recursion? Is doing heavy stuff with 
it supposed to be avoided? If so, why is that sort of thing discussed in 
the spec (the factorial example on the templates page)?

What template recursion depth must a compiler guarantee? If there are no 
guarantees, then what does one do about the fact that code may compile 
on one computer but not another?



However, trying this out on runtime code, the recursion limit is much 
higher (on my computer, it easily reaches 50000), and it executes much 
faster. However, the real point is that it produces a *catchable* error:

uint countDynamic(uint n)
{
	if (n == 0) return 0;
	return 1 + countDynamic(n-1);
}

int main(char[][] args)
{
	writefln("%d", countDynamic(100000)); // This throws a Stack Overflow 
which can be caught with try/catch
	return 0;
}


Since there is such a big difference in speed between runtime evaluation 
and template-based evaluation of effectively the same code, then perhaps 
using templates for compile-time evaluation is the wrong approach?

Cheers,

Reiner

Walter Bright <newshound digitalmars.com> writes:

Reiner Pope wrote:
 What are the rules about template recursion, and compile time evaluation 
 in general? For example, the following code produces an error on my 
 computer:
 
 import std.stdio;
 
 template count(uint n)
 {
     static if (n == 0) const uint count = 0;
     else const uint count = 1 + count!(n-1);
 }
 
 int main(char[][] args)
 {
     writefln("%d", count!(3008));
     return 0;
 }
 
 factorial.d(6): template instance factorial.count!(1u) recursive expansion

This happens when the compiler itself runs out of stack space. This 
amount will vary from machine to machine, operating system to operating 
system.

While the compiler is expected to do its best to accommodate recursion 
as much as possible, I recommend that for practical reasons one should 
think of a different algorithm if recursion levels more than 100 are used.