Why is for-loop not a compile-time expression?

Question

If I want to do something like iterate through a tuple, I have to resort to crazy template metaprogramming and specialized template helpers. For example, the following program will not work:

#include <iostream> #include <tuple> #include <utility> constexpr auto multiple_return_values() { return std::make_tuple(3, 3.14, "pi"); } template <typename T> constexpr void foo(T t) { for (auto i = 0u; i < std::tuple_size<T>::value; ++i) { std::get<i>(t); } } int main() { constexpr auto ret = multiple_return_values(); foo(ret); } 

Because i cannot be const or we cannot implement it. But for loops, there is a compilation time construct that can be evaluated statically. Compilers can freely delete, convert, fold, expand, or do whatever they want, thanks to the as-if rule. But then why not use outlines in constexpr? Nothing should be done in runtime in this code. This is confirmed by compiler optimization.

I know that you could change i inside the loop body, but the compiler can still detect it. Example:

 // ...snip... template <typename T> constexpr int foo(T t) { /* Dead code */ for (auto i = 0u; i < std::tuple_size<T>::value; ++i) { } return 42; } int main() { constexpr auto ret = multiple_return_values(); /* No error */ std::array<int, foo(ret)> arr; } 

Since std::get<>() is a compile-time construct, unlike std::cout.operator<< , I cannot understand why this is forbidden.

Answer 1

πάντα ῥεῖ gave a good and useful answer, I would like to mention one more question, but with constexpr for .

In C ++, at the most fundamental level, all expressions have a type that can be defined statically (at compile time). Of course, there are things like RTTI and boost::any , but they are built on top of this structure, and the static type of an expression is an important concept for understanding some rules in the standard.

Suppose you can iterate over a heterogeneous container using syntax for syntax, for example:

 std::tuple<int, float, std::string> my_tuple; for (const auto & x : my_tuple) { f(x); } 

Here f is some overloaded function. It is clear that the intended value of this method is to call different overloads f for each of the types in the tuple. This really means that in the expression f(x) , overload resolution must be performed three times. If we play according to the current C ++ rules, the only way this might make sense is if we basically expand the loop into three different loop bodies before we try to figure out what types of expressions are.

What if the code is actually

 for (const auto & x : my_tuple) { auto y = f(x); } 

auto not magic, it does not mean "no type information", it means "type deduction, please, compiler". But it is clear that in the general case there really should be three different types of y .

On the other hand, there are complex problems with such a thing - in C ++, the parser must know which names are types and which names are templates in order to parse the language correctly. Is it possible to modify the parser to loop constexpr for loops before all types are resolved? I do not know, but I think it can be nontrivial. Maybe there is a better way ...

To avoid this problem, in current versions of C ++ people use the visitor pattern. The idea is that you will have an overloaded function or function object, and it will be applied to each element of the sequence. Then each overload has its own "body", so there is no ambiguity regarding the types or values ​​of variables in them. There are libraries like boost::fusion or boost::hana that allow you to iterate over heterogeneous sequences using the given vistior - you should use your mechanism instead of the for loop.

If you can do constexpr for only using ints like

 for (constexpr i = 0; i < 10; ++i) { ... } 

there is the same complexity as heterogeneous for the cycle. If you can use i as a template parameter inside the body, then you can create variables that are of different types in different runs of the loop body, and then it is not clear what the static types of expressions should be.

So, I'm not sure, but I think there might be some non-trivial technical problems associated with actually adding the constexpr for function to the language. Visitor pattern / planned reflection features may turn out to be less of a headache IMO ... who knows.

---

Let me give you another example that I just thought about that which shows difficulty.

In regular C ++, the compiler knows the static type of each variable on the stack and therefore can calculate the layout of the stack frame for this function.

You can be sure that the address of the local variable will not change during the execution of the function. For example,

 std::array<int, 3> a{{1,2,3}}; for (int i = 0; i < 3; ++i) { auto x = a[i]; int y = 15; std::cout << &y << std::endl; } 

In this code, y is a local variable in the body of the for loop. It has a clearly defined address in all this function, and the address printed by the compiler will be the same every time.

What should be the behavior of similar code with constexpr for?

 std::tuple<int, long double, std::string> a{}; for (int i = 0; i < 3; ++i) { auto x = std::get<i>(a); int y = 15; std::cout << &y << std::endl; } 

The fact is that type x is displayed differently in each pass through the loop - since it has a different type, it can have a different size and alignment on the stack. Since y appears after it on the stack, this means that y can change its address on different runs of the loop - right?

What should be the behavior if the pointer to y taken in one pass through the loop and then dereferenced in a later pass? Should there be undefined behavior, although it would probably be legal in similar "no-constexpr for" code with std::array shown above?

Is it possible to change the address y ? Should the compiler populate the address y so that the largest of the types in the tuple can be placed before y ? Does this mean that the compiler cannot just expand the loops and start generating the code, but must expand each instance of the loop to the side, and then collect all the type information from each of the N instances, and then find a satisfactory layout?

I think you better just use the package extension, it’s much more clear how it should be implemented by the compiler, and how effective it is at compilation and runtime.

Answer 2

Here's a way to do it that doesn't require too many templates, inspired by fooobar.com/questions/311809 / ... :

 template<std::size_t N> struct num { static const constexpr auto value = N; }; template <class F, std::size_t... Is> void for_(F func, std::index_sequence<Is...>) { using expander = int[]; (void)expander{0, ((void)func(num<Is>{}), 0)...}; } template <std::size_t N, typename F> void for_(F func) { for_(func, std::make_index_sequence<N>()); } 

Then you can do:

 for_<N>([&] (auto i) { std::get<i.value>(t); // do stuff }); 

If you have a C ++ 17 compiler available, it can be simplified to

 template <class F, std::size_t... Is> void for_(F func, std::index_sequence<Is...>) { (func(num<Is>{}), ...); } 

Answer 3

Why is the for-loop expression not a loop?

Because the for() loop is used to define a C ++ runtime control flow .

In general, variable templates cannot be unpacked in runtime control flow operations in C ++.

  std::get<i>(t); 

cannot be displayed at compile time, since i is a run-time variable.

Instead, use the option of unpacking the parameters of the variation template .

---

You may also find this post helpful (if it doesn't even notice a duplicate answering your question):

go through a tuple

Answer 4

In C ++ 20, most std::algorithm functions will be constexpr . For example, using std::transform , many operations that require a loop can be performed at compile time. Consider this example of calculating the factorial of each number in an array at compile time (adapted from the Boost.Hana documentation ):

 #include <array> #include <algorithm> constexpr int factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); } template <typename T, std::size_t N, typename F> constexpr std::array<std::result_of_t<F(T)>, N> transform_array(std::array<T, N> array, F f) { auto array_f = std::array<std::result_of_t<F(T)>, N>{}; // This is a constexpr "loop": std::transform(array.begin(), array.end(), array_f.begin(), [&f](auto el){return f(el);}); return array_f; } int main() { constexpr std::array<int, 4> ints{{1, 2, 3, 4}}; // This can be done at compile time! constexpr std::array<int, 4> facts = transform_array(ints, factorial); static_assert(facts == std::array<int, 4>{{1, 2, 6, 24}}, ""); } 

See how the facts array can be compiled at compile time using the "loop", that is, std::algorithm . At the time of this writing, you need an experimental version of the latest release of clang or gcc, which you can try on godbolt.org . But soon, C ++ 20 will be fully implemented by all major compilers in release versions.