Stack Overflow Asked by gcalin on January 8, 2021
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?
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.
Correct answer by StoryTeller - Unslander Monica on January 8, 2021
Right answers has already been provided by Artefacto and Story Teller - Unslander Monica .
I am just trying to explain further with the help of cppinsights
For explanation purpose consider the original code with a little modification:
...
template<int n>
struct fibonacci {
static const int value = n > 0 ? 0 : fibonacci<n-1>::value + fibonacci<n-2>::value;
};
...
int main() {
std::cout << fibonacci<3>::value << std::endl; // modified parameter from -1 to 3 to avoid compilation failure by recursive instantiation
return 0;
}
Here is what the generated by compiler will look like
...
#ifdef INSIGHTS_USE_TEMPLATE
template<>
struct fibonacci<3>
{
static const int value = 3 > 0 ? 0 : fibonacci<2>::value + fibonacci<1>::value;
};
#endif
/* First instantiated from: insights.cpp:5 */
#ifdef INSIGHTS_USE_TEMPLATE
template<>
struct fibonacci<2>
{
static const int value = 2 > 0 ? 0 : fibonacci<1>::value + fibonacci<0>::value;
};
#endif
...
int main()
{
std::cout.operator<<(fibonacci<2>::value).operator<<(std::endl);
return 0;
}
It is clear from above generated code that even if the expression 3 > 0 is true still compiler instantiated the templates in false expression for n = 2 and n = 1
Now look at the code of if constexpr shared by Artefacto. i.e.
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;
}
}();
};
Considering template parameter as -1. Here is how compiler will interpret it
#ifdef INSIGHTS_USE_TEMPLATE
template<>
struct fibonacci<-1>
{
class __lambda_5_30
{
public:
inline /*constexpr */ int operator()() const
{
if constexpr(-1 < 0) {
return 0;
}
}
using retType_5_30 = int (*)();
inline /*constexpr */ operator retType_5_30 () const noexcept
{
return __invoke;
};
private:
static inline int __invoke()
{
if constexpr(-1 < 0) {
return 0;
}
}
} __lambda_5_30{};
static const int value = __lambda_5_30.operator()();
class __anon_5_30;
};
#endif
It's clear from above code that compiler didn't even considering the else part of if constexpr. That's why this code will work completely fine.
Answered by The Philomath on January 8, 2021
When fibonacci is instantiated with some value of n, all expressions used inside this instantiation must be compiled as well. This means that any templates that are used must also be instantiated. This is necessary even if the expression containing the template instantiation is never evaluated.
The only way to avoid instantiation of a template inside an expression is to not compile the expression at all. This allows you to avoid instantiating the templates with incorrect arguments.
You can do this by using if constexpr from C++17:
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;
}();
};
Here's a demo.
Answered by cigien on January 8, 2021
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;
}
}();
};
Answered by Artefacto on January 8, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP