Associated types are extremely important for expressing the capabilities of intermediate types within concepts. For instance, the reference type of an Input Iterator is the return type of the iterator’s operator*; all we know about the reference type is that it is Copy Constructible and can be implicitly converted to the value_type of the iterator (another associated type). Whenever a concept map is defined for a particular concept, definitions need to be given for every associated type of that concept. For instance, consider this Callable2 concept:
auto concept Callable2<typename F, typename X, typename Y> {
typename result_type;
result_type operator()(F&, X, Y);
};
This concept is marked auto, meaning that the compiler should be able to implicitly generate concept maps when needed. For instance, it should be able to implicitly generate Callable2<int(*)(int, int)>. However, this does not work, because no definition of the associated type result_type is provided! In truth, this is only an annoyance: one can write a concept map that handles every case for binary function pointers:
template<typename R, typename P1, typename P2, typename A1, typename A2>
where Convertible<A1, P1> && Convertible<A2, P2>
concept_map Callable2<R (*)(P1, P1), A1, A2> {
typedef R result_type;
};
This concept map solves the problem (it has been in ConceptGCC for several months). However, the need to specify result_type defeats the purpose of auto. What about user-defined function objects? They will also need their own concept maps, so this problem represents a barrier to adoption, because there are many function objects out in the Real World that will need concept maps.
The solution, which is implemented in ConceptGCC as of today (although it is currently “lightly tested”), is to require that the compiler implicitly generate associated types from the return types of model operations. For instance, when the compiler is attempted to match the type int (*)(int, int) to the Callable2 concept, it needs to determine if it can compile this function:
Callable2<int (*)(int, int)>::result_type
Callable2<int (*)(int, int)>::operator()(int (*&f)(int x, int y) {
return f(x, y);
}
As part of type-checking that function, the compiler computes the type of f(x, y) to determine if it is convertible to the result_type. When result_type has not already been defined by the user, the compiler will implicitly define result_type to the type of f(x, y). Now we can implicitly match Callable2<int (*)(int, int)>: no concept map necessary!
Applying this change throughout the concept descriptions in the ConceptC++ Standard Library allows for greater simplification. For instance, ConceptGCC currently has a Callable2 concept that looks like the above, but a completely separate BinaryPredicate concept that looks like this:
auto concept BinaryPredicate<typename F, typename X, typename Y> {
bool operator()(F&, X, Y);
};
However, what is a BinaryPredicate other than a Callable2 whose result_type is convertible to bool? We can now directly express this relationship through refinement, without worry that users will have to write concept maps for these trivial, structural concepts.
auto concept BinaryPredicate<typename F, typename X, typename Y>
: Callable2<F, X, Y> {
where Convertible<result_type, bool>;
};
In truth, the ability to determine the values of associated types from return types is not necessarily new to ConceptC++. One could use a default value for the associated type that redirects to decltype:
auto concept Callable2<typename F, typename X, typename Y> {
typename result_type = decltype((F())(X(), Y()));
result_type operator()(F&, X, Y);
};
Aside from the avoidable problems that F, X, and Y now need default constructors, this formulation is sufficiently confusing: if the user does provide a concept map that overrides the syntax of operator(), which operator() does that decltype expression refer to? One found through Argument Dependent Lookup or the one given in the concept map?
In summary, associated type deduction should simplify the use of concepts by allowed the implicit generation of associated type definitions. This means writing fewer and shorter concept maps, better backward compatibility, and more expressive concepts… as soon as I finish testing the ConceptGCC implementation.
Thanks to Rolf Bonderer, whose examples and request for associated type deduction pushed me to get this implemented in ConceptGCC.
