Decent concepts

Last year I published two posts on writing concepts:

1. Concept Archetypes,
2. Semantic requirements in concepts.

Having had some time to reflect upon these posts, I now realize that the model presented in them is not complete. In this post I want to give a more coherent view of concepts.

In this post we will see that:

1. Duck-typing property cannot be relied upon for the majority of concepts;
2. “Additional requirements” when specializing algorithms have to be reflected through concept refinement;

Algorithm specializations

Let’s get back to the declarations from one of the previous posts (Semantic requirements in concepts):

template <typename T>
concept Addable = 
  std::regular<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
    /* axiom */ (x + y) == (y + x);
    /* axiom */ (x + y) == (x += y);
  }; 
 
template <Addable T>
  T sum(T a, T b);
 
template <Addable T>
  requires std::totally_ordered<T>
  T sum(T a, T b);

We have a primary algorithm sum() that works for any type that models concept Addable, and a specialized implementation that works for types which additionally model concept std::totally_ordered. In the same post we said that a concept, apart from syntactic requirements, also has semantic requirements. In fact, if your concept doesn’t have semantic requirements, it is probably not a concept. We have also seen that we may not be fully aware of all semantic requirements that we are relying upon. It is only an ideal that one can first design the interface and then just use it. In reality, it is an iterative process, where we discover the interface as we develop the algorithms and use the library.

For this reason, it is likely that we rely on more semantic requirements than we are aware of, in case of the second overload. Concept Addable requires operator+ along with its semantic properties. Concept std::totally_ordered requires operator< and its friends along with their semantic properties. But for a type that already is a group in the mathematical sense, which is also totally ordered, it is almost sure that we additionally make an assumption about how operators + and < interact. For instance, we would be really surprised if the following didn’t hold:

assert((a < b) == (a + c < b + c)); 

However, this semantic property does not belong to concept Addable, because Addable is not aware of operator<. Similarly, it does not belong to concept std::totally_ordered because std::totally_ordered is not aware of operator operator+. So, where does it belong? Given that semantic requirements can only be reflected with a concept, the only solution to this problem is to introduce a new concept:

template <typename T>
concept OrderedAddable = 
  Addable<T> &&
  std::totally_ordered<T> &&
  requires(T x, T y, T z) {
    /* axiom */ (x < y) == (x + z < y + z);
  }; 

There may even be more subtle assumptions that you make, that may not be expressible. With this new concept in mind, our algorithm overloads become:

template <Addable T>
  T sum(T a, T b);
 
template <OrderedAddable T>
  T sum(T a, T b);

Now that we have two concepts, another deficiency of the solution I showed in “Concept Archetypes” becomes exposed. We wrote an archetype only for one concept, and tested only one overload for concept compliance:

using AddableArchetype = /* archetype for Addable */;

inline auto test_sum(AddableArchetype a,
                     AddableArchetype b)
                  -> AddableArchetype 
{
  return sum(a, b);
}

This only tests the first overload, but gives no guarantee that the other overload only uses the interface from concept OrderedAddable. We have to provide an archetype and a similar test for the other concept:

using OrdredAddableArchetype = 
  /* archetype for OrderedAddable */;

inline auto test_sum(OrderedAddableArchetype a,
                     OrderedAddableArchetype b)
                  -> OrderedAddableArchetype 
{
  return sum(a, b);
}

Thus, when we provide a specialized version of our algorithms we have to use a concept refinement — in order to reflect the additional semantic requirements — just putting a conjunction of smaller concepts will not suffice.

Runtime-checking the axioms

In the concept definitions above I used name axiom to describe semantic properties. Axioms (briefly described in this post) are capable of describing a subset of semantic requirements; namely, those that say that a pair of expressions is equivalent and can be used interchangeably. Or in other words, what expression transformations the implementations of the algorithms are allowed to perform.

We could try to at least partially check in the implementations of our algorithms if the values passed satisfy the axioms.

typename <Addable T>
bool is_commutative(T const& a, T const& b)
{
  return (a + b) == (b + a);
}

template <OrderedAddable T>
void is_ordered_group(T a, T b, T c)
{
  return (a < b) == (a + c < b + c); 
}


// generic version of the algorithm:
 
template <Addable T>
T sum(T a, T b)
{
  assert(is_commutative(a, b));
  return a + b;
}
 
// specialized version of the algorithm:
 
template <typename T>
T sum_impl(T a, T b)
{
  assert (a >= b);
  a += b;          
  return a;
}
 
template <OrderedAddable T>
T sum(T a, T b)
{
  assert(is_commutative(a, b));
  assert(is_ordered_group(a, b, b));
  assert(is_ordered_group(a, b, a));

  if (b > a) return sum_impl(b, a);
  else       return sum_impl(a, b);
} 

This gives us a chance to detect some buggy usages of the library sooner.

Duck-typing vs concepts

Concepts have both syntactic and semantic requirements. Therefore we cannot safely say, “if this type satisfies the syntactic requirements of our concept, then it must model our concept”. We have seen how this reasoning could go wrong. Such assumptions can only work for very small and very well established concepts. For instance, std::regular: it is safe to assume that if a type has a copy constructor, then this constructor performs a copy of the original; and this assumption is made so many times. The same goes for std::totally_ordered: we can reasonably assume that if someone has defined the six relational operators, they will satisfy the axioms of strict weak order for the values passed to the algorithms. But any bigger concept cannot safely rely on this duck-typing property. For instance the iterator concept. Even in the C++03 STL a type is never recognized as an iterator only because it has operators like ++, == and *. There is no way to make your type an iterator without declaring at least one line of code that contains both these sequences of letters: std and iterator.

The design for concepts planned for C++11 did address this: unless you annotated a concept as a duck-typing one (it was called an “auto concept”), it required an additional declaration to say that a given type models your concept: it was called a “concept map”. Concept maps also addressed another problem that we face today: the need for customization points. But that is another story to be told another time.

I would like to thank my colleague Mateusz Drewienkowski for pointing out the easy way to runtime-test concept axioms.