Why isn't a for-loop a compile-time expression?

Question

If I want to do something like iterate over a tuple, I have to resort to crazy template metaprogramming and template helper specializations. For example, the following program won't 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 can't be const or we wouldn't be able to implement it. But for loops are a compile-time construct that can be evaluated statically. Compilers are free to remove it, transform it, fold it, unroll it or do whatever they want with it thanks to the as-if rule. But then why can't loops be used in a constexpr manner? There's nothing in this code that needs to be done at "runtime". Compiler optimizations are proof of that.

I know that you could potentially modify i inside the body of the loop, but the compiler can still be able to detect that. 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 can't see why it's disallowed.

Answer 1

πάντα ῥεῖ gave a good and useful answer, I would like to mention another issue though with constexpr for.

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

Suppose that you can iterate over a heterogenous container using a fancy for syntax, like this maybe:

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

Here, f is some overloaded function. Clearly, the intended meaning of this is to call different overloads of f for each of the types in the tuple. What this really means is that in the expression f(x), overload resolution has to run three different times. If we play by the current rules of C++, the only way this can make sense is if we basically unroll the loop into three different loop bodies, before we try to figure out what the types of the expressions are.

What if the code is actually

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

auto is not magic, it doesn't mean "no type info", it means, "deduce the type, please, compiler". But clearly, there really need to be three different types of y in general.

On the other hand, there are tricky issues with this kind of thing -- in C++ the parser needs to be able to know what names are types and what names are templates in order to correctly parse the language. Can the parser be modified to do some loop unrolling of constexpr for loops before all the types are resolved? I don't know but I think it might be nontrivial. Maybe there is a better way...

To avoid this issue, 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's no ambiguity as to the types or meanings of the variables in them. There are libraries like boost::fusion or boost::hana that let you do iteration over heterogenous sequences using a given vistior -- you would use their mechanism instead of a for-loop.

If you could do constexpr for with just ints, e.g.

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

this raises the same difficulty as heterogenous for loop. If you can use i as a template parameter inside the body, then you can make variables that refer to different types in different runs of the loop body, and then it's not clear what the static types of the expressions should be.

So, I'm not sure, but I think there may be some nontrivial technical issues associated with actually adding a constexpr for feature to the language. The visitor pattern / the planned reflection features may end up being less of a headache IMO... who knows.

---

Let me give another example I just thought of that shows the difficulty involved.

In normal C++, the compiler knows the static type of every variable on the stack, and so it can compute the layout of the stack frame for that function.

You can be sure that the address of a local variable won't change while the function is executing. For instance,

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 a for loop. It has a well-defined address throughout this function, and the address printed by the compiler will be the same each 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 point is that the type of x is deduced differently in each pass through the loop -- since it has a different type, it may have different size and alignment on the stack. Since y comes after it on the stack, that means that y might change its address on different runs of the loop -- right?

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

Should the address of y not be allowed to change? Should the compiler have to pad the address of y so that the largest of the types in the tuple can be accommodated before y? Does that mean that the compiler can't simply unroll the loops and start generating code, but must unroll every instance of the loop before-hand, then collect all of the type information from each of the N instantiations and then find a satisfactory layout?

I think you are better off just using a pack expansion, it's a lot more clear how it is supposed to be implemented by the compiler, and how efficient it's going to be at compile and run time.

Answer 2

Here's a way to do it that does not need too much boilerplate, inspired from http://stackoverflow.com/a/26902803/1495627 :

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 accessible, 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

In C++20 most of the std::algorithm functions will be constexpr. For example using std::transform, many operations requiring a loop can be done at compile time. Consider this example calculating the factorial of every number in an array at compile time (adapted from 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 array facts can be computed at compile time using a "loop", i.e. an std::algorithm. At the time of writing this, you need an experimental version of the newest clang or gcc release which you can try out on godbolt.org. But soon C++20 will be fully implemented by all the major compilers in the release versions.