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

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.