Compile time recursion and conditionals

Question

I was reading the responses to "Printing 1 to 1000 without loop or conditionals" and I am wondering why it is necessary to have the special case for NumberGeneration<1> in the top answer.

If I remove that and add a check for N == 1 in the template (code below), the code fails compilation with "template instantiation depth exceeds maximum" but I'm not sure why. Are conditionals handled differently in compile-time?

#include <iostream>

template<int N>
struct NumberGeneration
{
    static void out(std::ostream& os)
    {
        if (N == 1)
        {
            os << 1 << std::endl;
        }
        else
        {
            NumberGeneration<N-1>::out(os);
            os << N << std::endl;
        }
    }
};

int main()
{
    NumberGeneration<1000>::out(std::cout);
}

score 12 · Accepted Answer · answered Jan 06 '12 at 15:10

12

Code generation and compilation doesn't branch depending on conditionals! Consider this:

// don't declare bar()!

void foo()
{
     if (false) { bar(); }
}

If you never declare bar(), this is a compilation error even though the inner scope can never be reached. For the same reason, NumberGeneration<N-1> is always instantiated, no matter whether that branch can be reached or not, and you have infinite recursion.

Indeed, the static analogue of conditionals is precisely template specialization:

template <> struct NumberGeneration<0> { /* no more recursion here */ };

answered Jan 06 '12 at 15:10

Kerrek SB

464,522
92
875
1,084

Thank you, this makes sense, I wasn't really thinking of compile-time instantiation and was expecting it to only be done when the code is reached. – baris.m Jan 06 '12 at 15:14
2

@baris.m: But there's a crucial subtlety of what you mean by "the code is reached": It's reached once during compilation by the compiler, always, and then again *conditionally* at runtime during program execution. – Kerrek SB Jan 06 '12 at 15:16
In my comment I was talking about being reached at runtime. Your answer makes perfect sense. – baris.m Jan 06 '12 at 15:21

score 4 · Answer 2 · answered Jan 06 '12 at 15:11

4

The conditional if will not be handled at compile time. It will be handled at runtime.

Thus, even for N=1, the compiler will generate NumberGenerator<0>, then NumberGenerator<-1> ... endlessly, until reaching template instantiation depth.

answered Jan 06 '12 at 15:11

Didier Trosset

36,376
13
83
122

score 3 · Answer 3 · answered Jan 06 '12 at 15:17

3

Templates are instantiated at compile time, the template special case prevents the compiler from recursing below 1 when compiling.

if-clauses are evaluated at runtime, so the compiler has already failed at compiling your code when it would have any effect.

answered Jan 06 '12 at 15:17

Joachim Isaksson

176,943
25
281
294

score 1 · Answer 4 · answered Jan 06 '12 at 15:09

1

I am wondering why it is necessary to have the special case for NumberGeneration<1> in the top answer.

Because that's the end condition for recursive ! Without that how could the recursive end ?

answered Jan 06 '12 at 15:09

RoundPi

5,819
7
49
75

What about the if N == 1 conditional I added to the template? In that case, we don't instantiate a new one with N-1, so that's how I expect the recursion to stop. – baris.m Jan 06 '12 at 15:12
@baris.m : You shouldn't remove the Template Specialization for condition 1 as that's the ending condition for the compile to end the calcaution/compilation. – RoundPi Jan 06 '12 at 15:15
1

@baris.m : The condtion you add is not helping as compile won't care about that and end the compilation during compile time. The check you added is only useful during run time, NOT compile time. – RoundPi Jan 06 '12 at 15:16
1

@baris.m: Please read this if you still having any doubt: http://en.wikipedia.org/wiki/Template_metaprogramming – RoundPi Jan 06 '12 at 15:17

score 1 · Answer 5 · answered Jan 06 '12 at 15:12

In general the condition N == 1 in your code is evaluated at run time (although compiler may optimize this away), not at compile time. Therefore template instantiation recursion in the else clause is never terminated. NumberGeneration<1> on the other hand is evaluated at compile time and therefore acts as a termination case of this recursive template.

Mike Seymour · Answer 6 · 2012-01-06T15:27:46.693

I'm fairly sure this is compiler-specific; some compilers may try to generate both branches of the if/else whatever the value of N, in which case compilation will fail in any event. Other compilers may evaluate the condition at compile time, and only generate code for the branch that's executed, in which case compilation will succeed.

UPDATE: Or as Luc says in the comments, it may be that the compiler must generate both branches, so that the code will always fail. I'm not quite sure which is the case, but either way it's a bad idea to rely on run-time conditions to control compile-time code generation.

It would be better to use specialisation:

template <int N>
struct NumberGeneration
{
    static void out(std::ostream & os)
    {
        NumberGeneration<N-1>::out(os);
        os << N << std::endl;
    }
};

template <>
void NumberGeneration<1>::out(std::ostream & os)
{
    os << 1 << std::endl;
}

(or you could shorten this slightly by instead specialising for N=0, with an out function that does nothing).

Also, be aware that some compilers may not support deeply resursive templates; C++03 suggests a minimum supported depth of only 17, which C++11 increases to 1024. You should check what your compiler's limit is.

Hum, I think the compiler *must* instantiate the template even though it could detect that the code will never be reached at runtime, so I don't think this code could ever finish compiling, whatever compiler you use. — Luc Touraille, Jan 06 '12 at 15:22
You don't need to specialize the entire struct, you can do it for just the function. — Paul Manta, Jan 06 '12 at 15:23

score 0 · Answer 7 · answered Jan 06 '12 at 15:08

It's because integers can be negative and runtime code (the if check) won't stop the compiler instantiating the template with 0, -1, -2, etc. A compiler might be able to get away with what you propose, but what if instantiating the other templates (0, -1, ...) has side effects that you depend on? The compiler can't fail to instantiate them for you in that case.

In short, just like all recursion you have to provide your own base case.

score 0 · Answer 8 · answered Jan 06 '12 at 15:18

Here's the correct way to do it:

template<int N>
struct NumberGeneration
{
    static void out(std::ostream& os);
};

template<int N>
void NumberGeneration<N>::out(std::ostream& os)
{
    NumberGeneration<N-1>::out(os);
    os << N << std::endl;
}

template<>
void NumberGeneration<1>::out(std::ostream& os)
{
    os << 1 << std::endl;
}

int main()
{
    NumberGeneration<20>::out(std::cout);
}

That's called template specialization: you, the programmer, provide an alternative definition for a particular instantiation of a template. You can specialize the entire template, or only a portion of it, as I did here (I only specialized the function, not the entire struct).

Compile time recursion and conditionals

8 Answers8

Linked