Reconsider constexpr

[gnzlbg]

E.g.

constexpr auto rng = view::iota(0, 10);
constexpr auto rng2 = view::iota(0) | view::take(10);
constexpr auto rng3 = rng | view::transform(square) | view::remove_if(odd);

should probably work, but that means C++14 will be a requirement. FWIW if the purpose is to prepare a C++17 library, C++14 should be a requirement anyways even tho right now that means clang > 3.6 and gcc 5.0 for the "bug-free" experience.

[gnzlbg]

I've partially fixed this while retaining C++11 compatibility. I'll review the pull-request to carefully consider which functions should be C++14 constexpr and why before submitting it since right now I just stamped with relaxed constexpr anything that looked remotely-close to important.

In my solution, I have a RANGES_RELAXED_CONSTEXPR macro that is enabled only in C++>=14. That is:

• use constexpr for C++11-or-above-constexpr functions,
• use RANGES_RELAXED_CONSTEXPR for C++14-or-above-constexpr-only functions, and
• use something else for C++17-or-above-constexpr functions (e.g. RANGES_EVEN_MORE_RELAXED_CONSTEXPR)?
• ...

It works, but one has to think about "is this function C++11/14/17-or-above-constexpr". The main problems i've found are:

• if you are testing this in C++14/1z and you screw something up, it won't show up until you try to compile in C++11 mode.
• you have to conditionally test for different language versions.E.g. some constexpr test will be C++14 only and you cannot include those tests when compiling in C++11 mode.
• you really need to write constexpr tests. In C++14 you can stamp almost anything with constexpr but until those types are instantiated the compiler won't complain about anything non-constexpr that you try to do. And in particular for template classes and functions, these are all "conditionally"-constexpr.

[ericniebler]

When you say things like, "you really need to write constexpr tests," who is "you"? I would like your pull request to come with tests, as all pull requests should.

[gnzlbg]

(With you I meant whoever is marking a function constexpr, so in this case me)

What I tried to express is that if the feature is only tested at run-time, compilation-errors due to conditional constexpr don't show up, so one really needs to force the compiler in all the tests to evaluate things at compile-time by using e.g. constexpr auto rng = ...; or RANGES_RELAXED_CONSTEXPR auto rng = ...;.

[viboes]

My experience is that C++14 relaxed constexpr are most of the time a facility for the implementer. You can almost always implement them using C++11 constexpr (I could be wrong). Of course the implementation is harder and not so beutiful. That means that the test could be the same.

Your approach is a more pragmatic one. Instead of making the library more complex, you just don't provide constexpr when doing it in c++11 is too complex and so need to inhibit some test in C++11. compilers.

[gnzlbg]

Your approach is a more pragmatic one. Instead of making the library more complex, you just don't provide constexpr when doing it in c++11 is too complex and so need to inhibit some test in C++11. compilers.

I don't think it is possible to provide a good constexpr experience in C++11 (think of optional and tagged_variant). I do think is possible to provide a good C++14 experience support covering most of the functionality.

[ericniebler]

I don't see any reason why tagged_variant couldn't be mostly or all C++11 constexpr. Ditto for optional. I'm not yet convinced that this much constexpr is needed. I'd rather keep the code clean and simple. And I'm opposed to adding a config macro that makes the test matrix explode.

[gnzlbg]

I just want to work with iota views at compile time (filter them, transform them, zip them,...). C++14 constexpr was just the easiest solution to the problem. I'm open to consider others.

I agree that increasing the complexity of the testing matrix is an issue, and also that don't using C++14 constexpr solves the problem.

About variant/optional. IIRC (don't have the laptop here right now) there are a couple of branches that would have to be rewritten with the ternary operator for it to be C++11 constexpr. Otherwise, anything that loops (algorithms, actions, views) would have to be written recursively in C++11.

On Tuesday, March 31, 2015, Eric Niebler notifications@github.com wrote:

I don't see any reason why tagged_variant couldn't be mostly or all C++11 constexpr. Ditto for optional. I'm not yet convinced that this much constexpr is needed. I'd rather keep the code clean and simple. And I'm opposed to adding a config macro that makes the test matrix explode.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/range-v3/issues/125#issuecomment-88185288 .

[pfultz2]

I just want to work with iota views at compile time

Its better to use heterogeneous sequences with dependent typing instead, since constexpr-only is failry limited. First, you can't use lambdas with constexpr. Secondly, you can't use the parameters to constexpr functions statically(like in static_assert or to allocate an array). However, you can do all these things with dependent typing.

Right now, the ranges library has a fairly limited form of iteration that doesn't allow for ranges with different types in them. However, being able to extend the range concepts to support that would be a research project of its own(a very interesting one though).

In the meantime, you might want to look at something like Boost.Hana.

[gnzlbg]

just want to work with iota views at compile time

Its better to use heterogeneous sequences with dependent typing instead, since constexpr-only is failry limited. First, you can't use lambdas with constexpr.

You can't use them with Boost.Hana either, right?

Think of:

constexpr auto rng  = view::iota(0, 10) 
                    | view::filter([](int i) { return i % 2 == 0; })
                    | view::transform([](int i) { return i * 2; });

With range-v3 you can (and AFAIK in Hana you would need to do something similar):

constexpr auto is_even(int i) { return i % 2 == 0; }
constexpr auto times_two(int i) { return i * 2; }
constexpr auto rng  = view::iota(0, 10) 
                    | view::filter(is_even) 
                    | view::transform(times_two);

If we ever get constexpr lambdas, then the previous example using range-v3 and lambdas would work for free (and so would the equivalent example in Hana). And since constexpr is only going to get more powerful with time, any STL replacement should play well with constexpr from the start (which means it cannot be done in a quick and dirty way, it deserves a lot of thought).

Secondly, you can't use the parameters to constexpr functions statically(like in static_assert or to allocate an array).

Yes that's true (you can work around this but the solutions are just that, work arounds).

However, you can do all these things with dependent typing. Right now, the ranges library has a fairly limited form of iteration that doesn't allow for ranges with different types in them. However, being able to extend the range concepts to support that would be a research project of its own(a very interesting one though).

Let's go briefly back to my statement, I want to work with homogeneous sequences at compile-time. For me Hana is overkill. I can see why you disagree, dependent typing is much more powerful, but range-v3 with constexpr is very ergonomic (see examples above).

Dealing with run-time heterogeneous sequences in range-v3 is a completely different topic, and you should open a different issue if you want to discuss that. My two cents are that:

• type-erasure and zip are already there and work,
• run-time heterogeneous sequences involve too many trade-offs, I don't think that there is a single right solution that always works best, and
• Hana can already deal with run-time homogeneous sequences so time might be better spent pursing that line of research in Hana.

It is still not yet clear tho if Hana can handle run-time homogeneous sequences efficiently since its main use case right now are immutable sequences, so it might be better to start by figuring out if range-v3 could be used in Hana as a back-end for these first.

[pfultz2]

You can't use them with Boost.Hana either, right?

I believe you can, but would need to ask @ldionne.

With range-v3 you can (and AFAIK in Hana you would need to do something similar):

No, you can't do that in C++11/14. However, a library that supported heterogeneous sequences and dependent typing, you would be able to write something like this in C++14:

auto rng  = view::iota(int_<0>, int_<10>) 
                    | view::filter([](auto i) { return i % 2 == 0; })
                    | view::transform([](auto i) { return i * 2; });

And the filtering and transforming would happen at compile-time.

And since constexpr is only going to get more powerful with time

It still won't be as powerful as dependent typing, since it still has to support being called at runtime.

I want to work with homogeneous sequences at compile-time.

And I am saying that is better to encode your values as types and use heterogeneous sequences instead.

For me Hana is overkill.

Using ranges for compile-time computation is overkill. Hana is designed for fast compile-time computation, and ranges are designed for fast run-time computation.

It is still not yet clear tho if Hana can handle run-time homogeneous sequences efficiently since its main use case right now are immutable sequences

And this is an area that would need some research.

[gnzlbg]

No, you can't do that in C++11/14.

@pfultz2 I've spiced range-v3 with C++14 constexpr and that code works as is.

[ldionne]

Hey, I heard my name around here! This is an interesting discussion.

First, like you already know, anything that contains a lambda can't be marked constexpr; that's a limitation of the language. BTW, there is some work going on to change this. As you remarked, it would therefore be impossible to write

constexpr auto rng  = view::iota(0, 10) 
                    | view::filter([](int i) { return i % 2 == 0; })
                    | view::transform([](int i) { return i * 2; });

By using non-lambdas like @gnzlbg showed, it is (modulo a proper implementation) possible to write:

constexpr auto is_even(int i) { return i % 2 == 0; }
constexpr auto times_two(int i) { return i * 2; }
constexpr auto rng  = view::iota(0, 10) 
                    | view::filter(is_even) 
                    | view::transform(times_two);

This is useful if you want to do homogeneous computations at compile-time. It should also be pretty compile-time efficient, since constexpr is more compile-time efficient than type-based computations. However, this is mostly useless if you need the type of a computation to depend on one of these homogeneous constexpr computations. For this, you would need to go in Hana-world and make iota a range of IntegralConstants (an heterogeneous range). This is exactly what hana::range does. It has several benefits but also many drawbacks.

Like @pfultz2 remarked, it would be possible to write (with Hana)

auto rng  = hana::transform(
                hana::filter(
                    hana::make_range(hana::int_<0>, hana::int_<10>),
                    [](auto i) { return i % hana::int_<2> == hana::int_<0>; }
                ),
                [](auto i) { return i * hana::int_<2>; }
            );

Notice how rng is not constexpr anymore, and how we can now use lambdas inside the computation. Also, notice how I'm using IntegralConstants to do all the computations inside the lambdas, and I must use generic lambdas because their argument will be an IntegralConstant too. That computation is not performed at compile-time, although the difference is subtle. Instead, what happens is that decltype(rng) is the answer, i.e. the "value" of the resulting range. That way, you can pass the result to other compile-time computations, be they metafunctions or Hana-style functions manipulating heterogeneous sequences. However, had I written

auto rng  = hana::transform(
                hana::filter(
                    hana::make_range(hana::int_<0>, hana::int_<10>),
                    [](auto i) { 
                        std::cout << "WOOHOOO";
                        return i % hana::int_<2> == hana::int_<0>; 
                    }
                ),
                [](auto i) { return i * hana::int_<2>; }
            );

then the result is the same, but it becomes clear why the computation itself can not possibly be done at compile-time. What would happen at run-time is that the inner lambda would be executed and the stuff would be std::couted, but the "result" of the filtering/transforming would still be known at compile-time, because it is encoded in decltype(rng).

So strictly speaking, and if we only look at compile-time computations, heterogeneous sequences as in Hana are more powerful than homogeneous constexpr sequences as is being discussed here. However, they come with a lot of caveats too, like a more twisted implementation, worse compile-time performance and so on. To mitigate this last point, Hana provides efficient representations for some homogeneous compile-time structures, like a tuple containing IntegralConstants, a tuple containing Types only, and so on. However, because those structures are only optimizations, they must still work with heterogeneous objects as-if they were a real heterogeneous sequence that happened to contain homogeneous objects. Hence, we can't do miracles and it turns out to be necessarily less compile-time efficient than pure constexpr-based homogeneous code. One could argue that it is also less user-friendly because one has to use IntegralConstants and similar constructs, although Hana makes this minimally painful. When you need Fusion/MPL-like capabilities, you require this full power. When you only need to do homogeneous computations at compile-time, then you would be better served by a constexpr-enabled standard library (or range library, or whatever else). You might want to take a look at Sprout.

Regarding runtime sequences, while Hana could in theory handle sequences whose size is not known at compile-time, the current concepts would have to be slightly adjusted to do it properly. Whether those could be handled efficiently is a good question; I think so, but it would add some complexity to Hana. This area truly needs more research. Since I am focusing on compile-time for now (hoping to make it into Boost), I prefer to restrain Hana's scope and say that runtime sequences (homogeneous or heterogeneous (via type-erasure)) are not officially handled by Hana (for now).

All that being said, I am curious to know what is the use-case requiring compile-time homogeneous sequences so badly. Or is it just a wish to be constexpr-friendly by principle (which is understandable)?

Btw, apologies for the long comment; I'm a text machine gun this morning.

[gnzlbg]

If something like range-v3 gets standardized people are going to write the following all the time (by people I mean me, and others like me):

for(auto&& i : view::iota(0, N)) { ... }
// or
for(auto&& i : view::iota(0, N) | view::transform(...)) { ... }
// or 
for(auto&& i : view::iota(0, N) | view::filter(...)) { ... }

How important is it for those expressions to be constexpr?

From an usability point-of-view, if they are not constexpr you cannot use those inside a constexpr function. I think this is undesired.

From a compiler-optimization point-of-view, I don't know (and don't think anyone really does), but it wouldn't definitely hurt for these to be constexpr.

All that being said, I am curious to know what is the use-case requiring compile-time homogeneous sequences so badly.

A basic application I have in mind is linear algebra libraries that use view::iota and view::stride to implement iteration on stack allocated matrices at compile-time.

Discussing my own application in detail here is very off-topic so I keep it as brief as possible.

Implementing an edge-based n-dimensional binary tree with 2^n children (for n = 2 it is a quad-tree, for n = 3 it is an octree). The positions of the children and neighbors of a node are represented using view::iota(0, n). For example finding the n - m-dimensional neighbor of a node where n = 3 and m = 2 means to "find the edge neighbors of a 3D node". This operation can be performed by finding some face neighbor of a face neighbor of a node (~ transforming view::iotas when you talk about whole neighbor subsets). To return neighbor sub-sets, e.g., all edge neighbors, using stack allocated std::arrays, the sizes of these ranges has to be computed at compile-time (size(...) should be constexpr). This can, and also is, implemented with dependent types, but that doesn't mean they should be exposed to users. If I give a user a view::iota(0, 10) and he wants to compute its size using size(view::iota(0, 10)) to allocate a std::array that should just work. And I'll stop here. If anyone is interested in knowing more we should move the discussion somewhere else (e.g. email).

[ldionne]

[Sorry for the long silence]

That seems like a pretty cool application. It should be pretty easy to make iota constexpr (if it isn't already). However, the more difficult question is what exactly do you want to make constexpr and what is OK not being constexpr? It would be useful to have a criterion for saying "this utility should be made constexpr", but one that's stricter than "this is constexpr because the current implementation allows it". In other words, I think it would be useful to develop guidelines for making functions constexpr. Otherwise, you might just as well stick constexpr before every possible function that is not obviously runtime (e.g. has new or throw in it).

[gnzlbg]

but one that's stricter than "this is constexpr because the current implementation allows it".

I think customization points should be constexpr if possible. I'll try to make all the views, algorithms, and actions constexpr. I haven't found one that cannot be made constexpr yet. I think this is important for avoiding "shadow worlds" in the language. You do not want separate STLs for run-time only functions and for maybe runtime/maybe compile-time constexpr functions.

Coming back to the instantiation of constexpr functions in unevaluated constexts, I learned something last week that I wanted to share:

• In C++11: do not use -> decltype(...) for SFINAE, use e.g. enable_if instead.

Basically, you should be able to, in C++14, omit all trailing "auto-deduced" return types in your code without altering behavior (that is, remove all -> decltype(...) in C++14).

This is important when you want to mark functions constexpr in C++14. If you use decltype for SFINAE functions that were not previously instantiated will be, and different compile-time branches will be taken. Constraining explicitly on types using e.g. enable_if does not have this problem as far as i could tell.

[ericniebler]

In C++11: do not use -> decltype(...) for SFINAE, use e.g. enable_if instead.

This is a pretty serious inconvenience. All the places that use RANGES_DECLTYPE_AUTO_RETURN are changed to use ... what? Do I need to go back to the C++03 way of defining a separate trait for every expression I want to SFINAE on?

[gnzlbg]

Pretty serious is an understatement. It is a huge inconvenience. I am very very very lucky that in range-v3 most "branches" happen to have the same result when marking functions with C++14 constexpr. This is mostly because most of the code is constrained multiple times anyways with concepts.

[ldionne]

This is important when you want to mark functions constexpr in C++14. If you use decltype for SFINAE functions that were not previously instantiated will be, and different compile-time branches will be taken.

I don't understand. constexpr functions are instantiated earlier than non-constexpr functions? Can you please throw an example?

[gnzlbg]

Ai Azuma's example:

template<typename T>
int f(T x) {  return x.get(); }

template<typename T>
constexpr int g(T x) { return x.get(); }

int main() {
  decltype(f(0)) a;  // OK
  decltype(g(0)) b;  // FAILS: constexpr functions are instantiated in unevaluated contexts
  return 0;
}

If you are using decltype to perform expression SFINAE, marking any of the functions involved in the expression constexpr might change the behavior of your program or make it invalid (in both C++11 and C++14).

[ldionne]

That's fucked up. Why on earth would you instantiate a function's body when you only require its signature, even if it's constexpr? It is obvious to me how decltype(f(x)) must instantiate f when it is using a deduced return type (regardless of f's constexpr-ness), but not this! I never encountered this because I'm using deduced return types everywhere in Hana (because they're dependent types), but I find this awful at first sight. Do you have a link to the rationale?

Btw, thanks for sharing.

[gnzlbg]

http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1581

To me it was unexpected, and I was very angry at first. I just read this by Richard Smith on noexcept(auto) (link below):

[...]
While I understand why some people may want to use that feature, I'd say that
they shouldn't. That's a circular definition: if this function fails to
compile, don't try to compile it.

Functions should exist or not based on the concepts. If that fails to compile,
either the concept or the function body is bad or under-constrained.

That all applies equally to the 'decltype(<returned expression>)' case, which was my point. 
If you would use concepts later, you should be using enable_if now, not ad-hoc SFINAE tricks.

https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/ICtSsQxnPAw

[pfultz2]

That all applies equally to the 'decltype()' case, which was my point.

Trailing decltype is what is used to constrain a function. If we change the function to this:

template<typename T>
auto f(T x) -> decltype(x.get()) {  return x.get(); }

int f(int x) { return x; }

template<typename T>
constexpr auto g(T x) -> decltype(x.get()) { return x.get(); }

int g(int x) { return x; }

int main() {
  decltype(f(0)) a;  // OK
  decltype(g(0)) b;  // OK
  return 0;
}

Then it compiles. So trailing decltype can be used but it must be turtles all the way down.

If you would use concepts later, you should be using enable_if now, not ad-hoc SFINAE tricks.

Later when we have concepts, I would expect trailing decltype to transport the concept constraints:

// F has the concepts of x.get()
template<class T>
auto f(T x) -> decltype(x.get()) { return x.get(); }

[gnzlbg]

I never encountered this because I'm using deduced return types everywhere in Hana

@ldionne And I guess you were also using C++14 constexpr from the start, right? I think this makes a big difference.

[ldionne]

Yes, everything is constexpr and deduced return type (almost since the beginning). Also, because of tag dispatching, Hana has its own "concept" framework that makes sure that when a function is called, then it should successfully compile (basically like what Richard says). Otherwise, you get a hard error when the compiler is trying to instantiate the invalid body of a function to deduce its return type.

[ldionne]

But even upon reading (part) of the discussion you linked, I don't really get the rationale for the instantiation of constexpr functions in unevaluated contexts.

[pfultz2]

Otherwise, you get a hard error

Does that mean the functions are not constrained? Can I do something like this in Hana:

template<class Sequence>
auto sum(const Sequence& s) -> decltype(fold(s, _ + _))
{
    return fold(s, _ + _);
}

template<class Range>
auto sum(const Range& r) -> decltype(std::accumulate(r.begin(), r.end()))
{
    return std::accumulate(r.begin(), r.end());
}

[ldionne]

No; you will get a hard error while trying to instantiate fold if s is not a hana::Foldable. Instead, you should write

template<class Sequence, class = std::enable_if_t<
    hana::models<hana::Foldable, Sequence>()
>>
auto sum(const Sequence& s) {
    return hana::fold(s, hana::_ + hana::_);
}

When you think of it, it's basically impossible to be sfinae-friendly for Hana. The reason is that Hana can be used to carry compile-time computations, and hence the validity of the fold call above could depend on performing the actual computation. Hence, the sfinae-friendliness of the call to fold would also depend on the contents of the sequence you pass; if the sequence happens to contain elements that cause a hard error when they are added together, then it is just not possible for Hana to avoid the trap. Trying to be sfinae-friendly would also bring a lot of issues, like the need to make all functions single expressions (so you can put them in the trailing decltype). This is not really feasible in practice.

[ldionne]

And by the way, even with the enable_if I posted above, you would still get a hard failure if you passed a hana::Foldable that contains types that can't be added. Again, when you think of it, it's hard to do better because the validity of the expression depends on the computation itself.

[gnzlbg]

@ldionne AFAIK the core language issue is not resolved yet. IIRC the standard says they can be potentially-evaluated in unevaluated contexts. The simplest thing then is to always evaluate them, which turns out fixes some problems and introduces others.

[ericniebler]

So trailing decltype can be used but it must be turtles all the way down.

Interesting.

As an aside, I've found that C++14's automatically-deduced function return type feature leads to very bad error messages. It makes code nice to read, but not so nice to write. Until we get concepts, I expect that a library that uses of automatically-deduced function return types internally would be a nightmare to use.

[ldionne]

@ericniebler In my experience, it isn't worse than anything else. Regardless, I see two other possibilities for computing return types:

1. Use trailing decltype, in which case a subtle error in a function down the chain will cause the outer function call to SFINAE-out. I think this could potentially lead to some headbanging trying to figure out where exactly the error is happening, but I could be wrong.
2. Use metafunctions to compute the return type of functions (as done in Fusion and basically all other C++03 libraries). Then, when you get an error, things are not necessarily pretty either.

One way to reduce programmer pain when using auto-deduced return type is to static_assert early in the chain of function calls, so that you still get a reasonable error message. Do you have an example of very bad error messages because of deduced return types?

[ericniebler]

Do you have an example of very bad error messages because of deduced return types?

Not offhand. I ran into my share of mystifying errors while developing the calendar example in example\calendar.cpp.

[pfultz2]

As an aside, I've found that C++14's automatically-deduced function return type feature leads to very bad error messages

Interesting, since usually its usually the errors from the trailing decltype that people usually complain about, since most compilers have poor reporting for sfinae, currently.

Until we get concepts, I expect that a library that uses of automatically-deduced function return types internally would be a nightmare to use.

How would native support for concepts help?

[pfultz2]

Use trailing decltype, in which case a subtle error in a function down the chain will cause the outer function call to SFINAE-out. I think this could potentially lead to some headbanging trying to figure out where exactly the error is happening, but I could be wrong.

Well this is really a quality of implementation issue really. One way a library can help with reporting is to use template aliases to transport the substitution failures(which I describe in detail here). The Fit library uses this technique.

I also have a patch(D8309) for clang that moves in the right direction to improve the error reporting, but there is disagreement whether this is the better approach. Of course, compilers can be doing a whole lot more for error reporting in this area, and I'll be discussing this more next week.

Use metafunctions to compute the return type of functions (as done in Fusion and basically all other C++03 libraries). Then, when you get an error, things are not necessarily pretty either.

In the C++11 days before C++14, I used to have a set of sophisticated macros that would build the additional metafunction to compute the return type. This was used so I could get automatic return type deduction without constraining the function(like in C++14).

One way to reduce programmer pain when using auto-deduced return type is to static_assert

I feel like that is a move in the wrong direction as is apparent with type deduction of constexpr functions.

[ericniebler]

way a library can help with reporting is to use template aliases to transport the substitution failures(which I describe in detail here).

I haven't grokked your approach in detail, but I achieved a similar end in my proto-0x library (see substitution_failre here and try_call). I described the technique in a BoostCon talk once (see here for the part where I discuss it).