Things you can almost, mostly, do with Concepts

David Sankel, in a CppCon 2016 lightning talk, gives as an example the first concept he tried to write:

Personally, the first concept I wrote was true. Your mileage may vary. This concept — a type that you can invoke with any {type that is itself invocable with int and yielding an int}— is, as David pointed out, completely unimplementable* in the Concepts TS. This is because all the expressions that are checked for validity and type must be instances of concrete types. Func is a concrete type, int is a concrete type. But IntFunction isn’t a type, it’s a concept.

What does it mean to specify that a type must be invocable with some other type that satisfies a concept? And how do we check that? We can’t simply try to call Func with the universe of types that satisfy IntFunction. There are an infinite amount of such types, so that’s never going to work. We need to reduce down this infinity to just one representative type of IntFunction. A representative type of a concept is usually called an archetype. Choosing the right archetype is decidedly nontrivial. Let’s go through the process. The standard library comes with a type that models IntFunction, let’s just try it:

This is a start. std::function<int(int)> is certainly an IntFunction, but is this a good archetype of IntFunction? To answer that question, we have to be more explicit about our goal. We want a say that a type T models concept CallableWithIntFunction if, and only if, for every type M that itself is a model of IntFunction, you can invoke T with an M. The correlating negated definition would be if we can find a type M which models IntFunction, and you cannot invoke T with an M, then T must not model CallableWithIntFunction.

Given that goal, does our implementation succeed? Consider this type:

evil1::Cdoes model CallableWithIntFunction1, but it doesn’t actually meet our expectations. There are many, many types which would model IntFunction that I couldn’t pass into evil1::C. Just about all of them in fact. So std::function is a bad choice for archetype, we can’t use a well-known class like this. We need our own class type that won’t clash.

Let’s try another implementation, this time with our own private type:

This is better, our evil1::C from before doesn’t model CallableWithIntFunction2, which is good. But this still isn’t quite right. Consider the following counterexample:

Both of those assertions pass. evil2::F does model IntFunction and evil2::C does model CallableWithIntFunction2. But… we can’t actually invoke C with an F. Where did we go wrong this time? Again, bad archetype.

Our archetypes::IntFunction is indeed callable with an int, but despite having a body consisting only of a single declaration, it has a lot of other functionality due to the implicit compiler-generated operations. Namely, it’s default constructible, copyable, movable, destructible. None of those operations were things that we checked in IntFunction! So when we use a function that more narrowly meets the definition, like evil2::F, which is not copyable, our archetype failed us. We have to be far more specific:

With this more restrictive archetype, both evil1::C and evil2::C fail, since both classes require more functionality than IntFunction alone is able to provide. Is this restrictive enough? Still no!

Here, we have a different problem. evil3::F models IntFunction, but that’s probably not what we were expecting. We wanted a function to be callable with an int, but what we actually specified was a function callable with an lvalue of type int. This formulation allows types like evil3::F, which we cannot provide to C.

Let’s try again:

Here now is perhaps the most interesting of cases. evil4::F does model IntFunction: you can invoke it with an int and it does yield a result that is convertible to int. But it doesn’t yield int, so the usage in C isn’t quite valid — passing an evil4::F into an evil4::C will result in a hard error due to the deduction failure for std::min. It may be immediately tempting to restrict IntFunction to specifically yield an int, but that’s far too restrictive to be practically useful. Functions returning something like bool should be acceptable candidates for IntFunction, we don’t want to remove those from consideration. So where did we go wrong?

We did two things wrong. Our archetype is still insufficient, and the user of our concept is misbehaving.

First, our archetype needs to allow for the fact that the call operator can return a type other than int. We’ll just introduce another private type to satisfy that requirement:

Secondly, our evil4::C is misusing the concept IntFunction. All that concept provides for us is that the type is invocable with an int and yields a type that is convertible to int. It does not tell us that the result type is int. Using std::min() in the body makes our function under-constrained. Now, we could go in two directions: either (a) use a more refined concept than IntFunction that stipulates that the return type of the call operator must be precisely int or (b) restrict ourselves to just the functionality that IntFunction provides us. The latter gives us type more opportunities for use, so it’s the better choice here:

And here now is a type that can be invoked with any type that models IntFunction, guaranteed. And we’ve ended up with a concept that precisely allows and disallows all candidates appropriately. Probably. Maybe. Coming up with the right archetype is hard, and we ended up with one that’s 15 lines long for a concept that’s pretty simple. And I’m not even completely sure that there isn’t some pair of types evil6::F and evil6::C that breaks this anyway (probably need to delete the arithmetic operators too?).

While it is possible in Concepts TS to write the concept that David Sankel wanted, it’s quite a lot of work! In order to be able to write such a concept directly, the compiler would be need to be able to construct archetypes for all concepts on the fly. Such archetype construction is not part of Concepts TS, but we can do it on our own. Carefully.

Bonus Slide. Since you’ve made it this far, here’s a bonus slide. Another thing you can sort of do with concepts. Let’s say I want to write fmap for optional. That’s pretty straightforward in C++17 (ignoring references of all kinds for simplicity):

std::invoke_result_t serves two purposes here. First, for SFINAE. If a function isn’t invocable with T, this function template will be removed from the overload set. Second, for the actual result type. We need that R in order to implement this function.

How would we write this with concepts?

(We technically don’t need Regular, but I want to avoid references in this example, so I need F to be copyable). Okay so… this looks basically the same. Concepts doesn’t give us a way to get R (that result type is referred to as an associated type of the Invocable concept), so we have to use the same C++11/4/7 metaprogramming tricks to get at it that we’ve always used. Indeed, the use of the concept doesn’t actually give us much here. We’re not going to overload on other function types that aren’t invocable, or on more refined function types. What we had before is really all we need.

Which is fine. This is basically just an example where Concepts didn’t solve a problem that we didn’t have. But it is an interesting case where we (or, at least, I) will continue to use C++17 SFINAE even with Concepts TS.