Concept archetypes

Concepts in the form added in C++20 used to be called lite. This is because they do not provide one quite important functionality: having the compiler check if the author of a constrained template is only using operations and types allowed by the constraining concept. In other words, we can say that our template only requires operations A and B to be valid, but we can still use some other operations inside and this is fine with the compiler. In this post we will show how this is problematic, even for programmers aware of the issue, and how to address it with concept archetypes.

(Note: I have edited this post since it was originally published based on the feedback from the readers. The changes are indicated with the blueish color.)

This example is a bit artificial, but we have to make it small. We will use function sum() as an example of a generic algorithm. It implements the addition of two values, provided that they are addable:

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

We require that our Ts are regular and provide operators + and +=:

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>;
  }; 

With these constraints satisfied we can provide various implementations of addition. For instance this one:

template <typename T>
T sum_impl(T a, T b)
{
  assert (a >= b);
  a += b;
  return a;
}

template <Addable T>
T sum(T a, T b)
{
  if (b > a) 
    return sum_impl(b, a);
  else
    return sum_impl(a, b);
}

Let’s pretend that we have discovered that the most efficient implementation is when we use += rather than + and when the bigger number is on the left-hand side. The point is, when we have provided the interface, in form of a concept, it is our business how we want to implement the function, as long as we satisfy the contract. Another minor observation is that we can call an unconstrained template form a constrained template, and this is fine.

Now suppose we are implementing a generic library that other people are going to use. A function template is not a piece of code that can be executed. It will only become one when instantiated with user provided types. The fact that the template definition compiles does not mean that the body is correct: most of errors from templates show up when we try to instantiate them. So, in order to ship a decent library, we have to test if our template can be instantiated for addable types:

int main()
{
  int i = 1, j = 2;
  std::cout << sum(i, j) << std::endl;

  double x = 2.25, y = 5.25;
  std::cout << sum(x, y) << std::endl;
}

This compiles, runs and outputs:

3
7.5

So, the implementation works. But these are very basic types. What if the users will use their custom addable types with our function? This also needs to be tested. Let’s use Boost.Rational library:

#include <boost/rational.hpp>

// verify if the type can be used with the library
static_assert(Addable<boost::rational<int>>);

int main()
{
  boost::rational<int> q1{1, 2}; // 1/2
  boost::rational<int> q2{1, 3}; // 1/3
  std::cout << sum(q1, q2) << std::endl;
  std::cout << sum(q2, q1) << std::endl;
}

This outputs:

5/6
5/6

So it works! We can also check with Boost’s big int library:

#include <boost/multiprecision/cpp_int.hpp> 

static_assert(Addable<boost::multiprecision::cpp_int>);

int main()
{
  boost::multiprecision::cpp_int i{"770000"}, 
                                 j{"119999"};
  std::cout << sum(i, j);
}

Works and outputs:

889999

Now we can confidently ship our library to the customers.

Our customer intends to use the library with the standard library type: std::complex. As the first step, she verifies if her type satisfies our concept:

#include <complex> 
#include "addable_library.hpp"

static_assert(Addable<std::complex<double>>);

This compiles fine, so std::complex<double> does model Addable. Now, she can correctly use the library:

int main()
{
  std::complex<double> z1{1, 0}, z2{0, 1};
  std::cout << sum(z1, z2);
}

And this program fails to compile. We get an old-style template error message, exposing the internal implementation of code of our library function, which uses operator>. And std::complex<double> does not provide operator > or >=.

Now it turns out our implementation uses operations that we did not list in the concept. But because types that are Addable and don’t provide relational operations are so infrequent, this bug could have gone unnoticed for a long while. It is not easy to spot this even in a short, simple function. And the compiler doesn’t try to help us. (As a side note, there are good reasons why compilers had better not do it.)

In order to avoid this situation, we have to check ourselves if in the implementation of a template we are only using the interface that we require in the concept. In order to do this, we have to define an archetype for our concept; that is, a type that only provides the interface indicated in the concept and not a single operation more.

Let’s try to define one for our concept:

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>;
  }; 

We start with an empty class:

class A {};

But it is not really empty: its interface already provides constructors (default, copy, move), assignments (copy, move), destructor, and a couple of others, like operator& and operator,. In order for our type to really be empty we would have to declare these operations as deleted. But because our concept already requires the aforementioned constructors, assignment and destructor to exist, we will not delete them. More, in order to be explicit about our intentions we will mark them as defaulted:

class A
{
public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;
};

This type already satisfies concept std::semiregular, which is part of std::regular, which in turn is part of our concept Addable. It doesn’t do anything useful, but it is fine: its goal is only to satisfy the concept. We can test it:

static_assert(std::semiregular<A>);

Now, in order to satisfy std::regular, our type needs to provide equality and inequality operators. In C++20 we can do it with one declaration:

class A
{
public:
  // ...
  friend bool operator==(A const&, A const&) = default;
};
// test it:
static_assert(std::regular<A>);

Now, our two addition operators. We could do it like this:

class A
{
public:
  A& operator+=(A const&) { return *this; }
  friend A operator+(A const&, A const&) { return {}; }
  
  // ...
};

But that would not be the minimum satisfaction of our concept. Recall:

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>;
  }; 

The requirement for operator+ is that its result be convertible to T but not necessarily T. If we miss that, we are risking the same problem as we observed with operator>: an algorithm constrained by Addable may rely on the result of addition being exactly T. Most of the types satisfy it, so it would go unnoticed, but a library user may later be using a type where the result of addition is not T, but something convertible to it. So, we have to take this into account. A minimal implementation could look like this:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  // ...
};

The full class definition:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;

  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  friend bool operator==(A const&, A const&) = default;
};

We can now give it a better name and test if the archetype actually satisfies the concept:

using AddableArchetype = A;
static_assert(Addable<AddableArchetype>);

Now we have proved that our archetype models the concept, and we are convinced (although this cannot be statically proven) that it is a minimum interface that models the concept. In other words, now we are convinced we have an archetype. But is it really the the minimum interface that models the concept? See the next post to find out.

As a next step, we can use it to test the implementation of our algorithm. We simply define a non-template function that instantiates the algorithm sum with our archetype:

inline void test_concept_usage(AddableArchetype a,
                               AddableArchetype b)
{
  sum(a, b);
}

This function is never called; parameters a and b are never initialized. Only the existence of the function body is enough to guarantee that the entire implementation of sum is instantiated and therewith tested for using only the declared operations.

And it is tested. The program fails to compile. The error message is an old-style one, exposing the implementation details: type AddableArchetype does not provide operator> or operator>=. This is the same error that we have seen before. But this time it is the library author that sees the error before the library is shipped, rather than the library user when it is too late. Our test has discovered a bug. The bug is either in the implementation of function sum(), or in concept Addable — it is not clear yet. But because we are warned ahead of time, we can make a conscious choice.

We have a couple of options. First, we can decide that the implementation of our algorithm went too far. Such implementation is illegal and has to be changed so that it only uses operations required by the concept. Second, we can draw an opposite conclusion: the experience from implementing the algorithm the way we did shows that our initial idea about what the concept should require was incorrect, and it now has to be refined. The decision to modify a concept does not come easily, but may be necessary when we have learned something new about our domain while implementing algorithms. Finally, it is possible to provide two overloads of sum(): one that requires less of its arguments, and the other that offers optimizations:

template <Addable T>
T sum(T a, T b);
 
template <Addable T>
  requires std::totally_ordered<T>
T sum(T a, T b);

Suppose we make the call: concept Addable will also require the type to provide relational operators; this will make it close to the algebraic structure ordered group. (This is not necessarily the best decision, but I want to illustrate how the process of altering a concept works.) We have to change the definition of the concept:

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

Now our archetype no longer models the concept. The static check that we added will remind us of this:

static_assert(Addable<AddableArchetype>);
//            ^--- this now fails

We can fix our archetype by replacing the defaulted equality operator with defaulted spaceship operator:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;

  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  friend auto operator<=>(A const&, A const&) = default;
};

Now the archetype models the updated concept again, and the static test test_concept_usage passes which gives us the confidence that our algorithm uses only operations defined in the concept. Users of the library will still not be able to use it with std::complex<double>, but this time, they will get a clear message up front: your type does not model concept Addable.

And that’s it. For a final note, in this example we have seen an archetype with trivial implementation. It is possible to make the archetype actually do something useful, like counting the number of invocations of individual functions from the interface, or throwing exceptions from functions for the purpose of testing exception safety.

This entry was posted in programming and tagged , , . Bookmark the permalink.

13 Responses to Concept archetypes

  1. Aaron says:

    Just one remark: Bjarne Stroustrup says that concepts like “has an addition” are suspect (at CppCon 2018, https://www.youtube.com/watch?v=HddFGPTAmtU&t=45m16s). Not relevant to the topic you’re discussing here, but I thought it’s good to mention in case somebody decides to copy this. Otherwise a really good post, the idea to test instantiation with archetypes seems very useful.

  2. dmz1978 says:

    While I find the archetype idea good, I do not know what to do with the information provided by the botched attempt at compilation of test_concept_usage. Your way is to change the concept and then the archetype it should model, but:

    1. Concept is part of interface.
    2. The “bigger left hand side is better” is an implementation detail on some hypothetical platform.

    As a result, the last version of Addable concept exposes implementation detail in the interface. What happens, when you port it to another platform? Will you change the Addable as well? Will the code, which compiled on platform A stop compiling on platform B, because the types, which used to be modeled by the concept, are no longer modeled?

    • dmz1978 says:

      “What happens, when you port it to another platform?” — there is an idea here, which I did not articulate, that the new platform has some other “best” approach at implementation…

    • Thank you for bringing up this topic. I would like to address your comment, but let me first ask a clarifying question.
      Are you reporting an issue with having to make a decision which one to fix (concept or generic algorithm)?
      Or are you reporting an issue with my choice to alter the concept?

      • dmz1978 says:

        Bit of both — not a fan of exposing what seems like an implementation detail to the interface — but more the first, why choose interface “contamination” over the generic algorithm using only what it is “allowed to”?

        I do understand this might not have a good solution.

        If you hide the detail, that the arguments need to be totally ordered (which might be surprising for a function not doing ordering, judging from the name and hypothetical documentation), then you can neither use greater than, nor greater equal and since this is the most efficient way of doing this particular job here, the efficiency will suffer.

        If you decide to leave the consequence of implementation in the interface, then you either one, probably cannot change the implementation in the future or two, the interface would need to be updated and would not be past-proof (old client code stops compiling).

        (I tak źle, i tak niedobrze.)

        • > Let’s pretend that we have discovered that the most efficient implementation is when we use += rather than + and when the bigger number is on the left-hand side.

          This is the same story as for iterators. You have the fallback, generic algorithm that uses `+`, and when the type additionally satisfies `totally_ordered`, you can use the more efficient `+=`.

    • Here is how I see it.
      An interface is a result of a trade-off between what the users can or are willing to provide, and what the implementers need in order to provide satisfactory implementation(s). In this sense an interface always reflects some aspects of implementations. So the sole fact that some aspects of implementation are “exposed” is not the problem, I think. The problem is when *too much* of implementation details are exposed or that too much unrelated requirements are now imposed on the users.
      Can I implement algorithm `find()` without default-constructing iterators in the implementation? Yes. So why does it require in the interface that iterators be default-constructible? Answer: in case someone may want to implement it in a different way that would need it. But is requiring default-constructibility here an exposure of implementation details? I wouldn’t say so.
      Second point is that in my experience, designing a good interface is an iterative process. You start with what you think is a good interface design, then you try to use it (both as a user and as an implementer) and discover that the interface has flaws. You change it, try to use it, then you discover that t sort of works, but there is much more that an implementation could do if you modified the interface a bit. THen someone else tells you that they have a different use case that you did not anticipate, and the interface cannot handle it…
      If you are lucky, all these iterations happen before you ship your library/product. But if you discover after shipping that your library could be aso used on a different platform, but on this platform the current interface will not work, and you cannot change the interface because you have already made a commitment, then this is time to release version 2 of your library.
      It looks like you perceive Addable with total order as something artificial and exposing an implementation detail, but it does not look so strange to me. A lot of types have this property that if they support addition then they also support ordering. It has a name in mathematics: Ordered Group, I think. Although I am not sure I would call a concept like that. Maybe if the name of the concept was changed this would look less artificial.
      Finally, the conflict between requiring less and providing more can  be solved by providing two overloads:

      template <Addable T>
        T sum(T a, T b);
      
      template <Addable T>
        requires std::totally_ordered<T>
        T sum(T a, T b);
      
  3. Marcel Krüger says:

    > Now we have proved that our archetype models the concept, and we are convinced (although this cannot be statically proven) that it is a minimum interface that models the concept. In other words, now we are convinced we have an archetype.

    It’s not yet minimal because `Rslt` provides a much richer interface than required by the concept, especially it’s regular. E.g. if `sum_impl` were implemented as
    “`
    template
    auto sum_impl(T a, T b)
    {
    assert (a >= b);
    auto c = a + b;
    return c;
    }
    “`
    it would compile with `A`, but not with
    “`
    class B
    {
    struct Marker { explicit Marker() = default; };
    struct Rslt {
    Rslt(Marker) {}
    Rslt() = delete;
    Rslt(const Rslt&) = delete;
    Rslt(Rslt&&) = delete;
    B& operator=(const Rslt&) = delete;
    B& operator=(Rslt&&) = delete;
    operator B() { return {}; }
    };

    public:
    B() = default;
    B(B&&) = default;
    B(B const&) = default;
    B& operator=(B &&) = default;
    B& operator=(B const&) = default;
    ~B() = default;

    void operator&() const = delete;
    friend void operator,(B const&, B const&) = delete;

    B& operator+=(B const&) { return *this; }
    friend Rslt operator+(B const&, B const&) { return Marker{}; }

    friend bool operator==(B const&, B const&) = default;

    friend auto operator(B const&, B const&) = default;
    };
    “`
    which still satisfies `Addable`. This probably indicates a more general point: If a class should be an archtype, related classes (like Rslt) also have to be archtypes.

  4. Pingback: Recent ISO C++ News and Articles – David I's Software Development Cornucopia

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.