C++17 static template lazy evaluation

Question

Considering the following example:

#include<iostream>

template<int n>
struct fibonacci {
    static const int value = n < 0 ? 0 : fibonacci<n-1>::value + fibonacci<n-2>::value;
};

template<>
struct fibonacci<1> {
    static const int value = 1;
};

template<>
struct fibonacci<0> {
    static const int value = 0;
};

int main() {
    
    std::cout << fibonacci<-1>::value << std::endl;

    return 0;
}

I am familiar with lazy evaluation in C++, and would expect that the second branch of the if statement the generic fibonacci template would not be evaluated, when an argument < 0 is passed. However, compiling the code still results in an infinite loop from that branch:

Fibonacci.cpp: In instantiation of ‘const int fibonacci<-900>::value’:
Fibonacci.cpp:5:58:   recursively required from ‘const int fibonacci<-2>::value’
Fibonacci.cpp:5:58:   required from ‘const int fibonacci<-1>::value’
Fibonacci.cpp:20:33:   required from here
Fibonacci.cpp:5:58: fatal error: template instantiation depth exceeds maximum of 900 (use ‘-ftemplate-depth=’ to increase the maximum)
    5 |     static const int value = n < 0 ? 0 : fibonacci<n-1>::value + fibonacci<n-2>::value;
      |                                                          ^~~~~

Why is this the case? Is it specific to something related to templated structs?

Answer 1

I am familiar with lazy evaluation in C++, and would expect that the second branch of the if statement the generic fibonacci template would not be evaluated, when an argument < 0 is passed.

It doesn't need to be evaluated. But we aren't dealing with evaluation here. We are dealing with template instantiation. You used fibonacci<n-1>::value, and that requires the complete object type fibonacci<n-1> to be instantiated. The type has to be checked, to see if it has a member value that can be used in such an expression.

Instantiating a class template causes the declarations of its members to be instantiated. The declaration of the static data member contains an initializer, which must therefore be instantiated as well. So we hit the need to instantiate the template recursively.

Simply naming fibonacci<n-1> won't cause it to be instantiated (think forward declarations). If you want to delay the instantiation, you must delay using those types in a way that requires their definition (such as accessing a member).

The old meta-programming trick for this (that is very in line with functional programming) involves helper templates.

template<class L, class R>
struct add {
    static constexpr auto value = L::value + R::value;
};

template<int n>
struct fibonacci {
    static const int value = std::conditional_t<(n < 0), fibonacci<0>, add<fibonacci<n-1>, fibonacci<n-2>>>::value;
};

std::conditional_t will choose a type based on the condition. Then, the ::value of that type (and only that type) is accessed. So nothing is fully instantiated until actually needed.

Answer 2

You can use if constexpr:

template<int n>
struct fibonacci {
    static const int value = []() {
        if constexpr (n < 0) {
            return 0;
        } else {
            return fibonacci<n-1>::value + fibonacci<n-2>::value;
        }
    }();
};