Concept archetypes — update

An observant reader indicated that in the previous post where I was trying to implement a concept archetype — a type with minimal interface that models a given concept — I actually failed. This deserves a closer examination.

Let’s recall. We have the following 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>;
  }; 

and we have the following type that we believe to be an archetype for the concept:

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

The thing to note is the usage of intermediate type A::Rslt that attempts to reflect that the result of adding two A's does not have to be another A but just something convertible to it.

Now imagine that our generic function sum() that uses our concept as a constraint is implemented slightly different than in the previous post:

template <typename T>
auto sum_impl(T a, T b)
{
  assert (a >= b);
  auto r = a + b;
  return r;
}
 
template <Addable T>
T sum(T a, T b)
{
  if (b > a) 
    return sum_impl(b, a);
  else
    return sum_impl(a, b);
}

The difference now is that rather than immediately converting the result of operator+ to T, we return exactly the type produced. Testing it against the archetype reveals no problem. The following compiles fine:

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

But now imagine the following user defined type which uses expression-template-style signature for operator+:

struct Num
{
  int i;
  friend auto operator<=>(Num, Num) = default;

  Num& operator+=(Num const& n) { 
    i += n.i; 
    return *this; 
  }
};

struct NumAddExpr
{
  Num const& lhs;
  Num const& rhs;

  operator Num() { 
    return Num{lhs} += rhs; 
  }
    
  NumAddExpr(Num const& x, Num const& y)
   : lhs{x}, rhs{y} {}

  NumAddExpr(NumAddExpr&&) = delete;
};

NumAddExpr operator+(Num const& x, Num const& y)
{
  return {x, y}; 
}

static_assert(Addable<Num>);

Declaring move constructor as deleted also declares all special member constructors and assignments as deleted, so the only use that can be made of NumAddExpr is to convert it to Num. The static assertion in the last line demonstrates that type Num satisfies the concept.

So, let’s use it:

int main()
{
  sum(Num{1}, Num{2});  
}

And now we get the ugly error message resulting from template instantiation: function template sum_impl() which was supposed to be an implementation detail.

Why did our archetype not detect it? Because the concept only required that the result of the addition is convertible to T, whereas the archetype additionally makes this type std::semiregular by providing implicitly declared constructors and assignments. A more decent archetype should look like this:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
    Rslt(Rslt&&) = delete;
    void operator&() const = delete;
    friend void operator,(Rslt, Rslt) = delete;
  };
    
  static Rslt make() { throw 0; }
 
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, A) { return make(); }
   
  friend auto operator<=>(A const&, A const&) = default;
};

The observation here — as indicated by the reader who reported this — is that associated types that we model (like Rslt) in our archetype are subject to the same rule as the archetype itself: declare all special member functions as deleted.

Now, is this refined version a really minimum interface that models the concept? After this exercise, I would not dare to answer this question with certainty. For instance, our concept only requires that expression a + b for operands of type T is well defined (possibly including conversions) but does not require that in the signature of the operator the types are exactly T; whereas our archetype has exactly T. It is possible to imagine a contrived implementation of an algorithm that works with our archetype but not with sufficiently contorted user-defined type.

My observation here is that making sure that the archetype has really the minimum interface is a manual job, and it is difficult. But even if the archetype is not 100% minimum, it can still help us detect many bugs early in the development cycle.

I would like to thank Marcel Krüger for pointing out this issue in the previous post.

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

6 Responses to Concept archetypes — update

  1. David Hunter says:

    Thanks for an interesting post. What’s you view on the possibility of compiler/tool generated archetypes. I suspect for any non trivial concept doing them by hand is beyond most of us mere mortals!

    • It needs to be noted that concept support that was almost added for C++11 did have this capability. One of the design controversies at that time was whether declarations in concepts should indicate valid expressions (much like what we have today) or pseudo declarations of functions that were required. This would today look something like:

      template <typename T>
      concept Addable = requires
      {
        T& T::operator+=(T const&);
        T operator+(T const&, T const&);
      };
      

      And it was the latter model that was chosen at that time, because for that model the implementers knew how to build archetypes. You can see that in the above declaration I had to modify operator+ so that now returns exactly T. Note that the built in operator+ for type short has the return type int. In C++11 concepts it would work though because that proposal also had concept maps that are missing from C++20 concepts lite mostly for performance reasons.

      Maybe it is technically possible to have the compiler generate archetypes for C++20 concepts lite, but for sure it is more difficult. What would have to be emitted for:

      template <typename T>
      concept C = requires(T x, T y, T z) 
      {
        { x * x + y * y + z * z } -> std::convertible_to<T>;
      };
      

      Also, I have oversimplified the matter in this post. One archetype that is produced from a concept: it can be more when the concept has more than one template parameter:

      template <typename Matrix, typename Vector>
      concept LinearAlgebra = requires(Matrix m, Vector v) 
      {
        { m * v } -> std::convertible_to<Vector>;
        { m * m } -> std::convertible_to<Matrix>;
      };
      

      Here a concept has to produce two archetypes: one for a matrix and one for a vector.

      But since the only usage for an archetype is to check whether a given constrained template uses only the operations indicated in constraints, what we really want is the definition checking for constrained templates.

  2. Does everybody here have some previous foundational knowledge that I do not know about?

    How are contracts logically interacting with requirements? Is contract not a requirement?
    And is it that requirement can have one or more concepts or is it the opposite or is it both?
    And is “archetype” not a “meta class”?

    What I am missing in your series it episode one.

    • Yeah. I can see the problem. I am starting with an assumption that the reader is already familiar, at least superficially, with C++20’s feature known as “Concepts Lite”, and that they have used it at least in toy examples.

      There is a plenty of materials on the topic out there on the subject, of better or worse quality. Like:

      Rather than repeating what has already been told, I focus on things other people teaching concepts omit. I guess I have never made that clear.

      To try to address your specific questions. A “function contract” is the most general way of expressing everything that a function requires of its users. (It also specifies what a function provides, but this is off topic now.). Word “requirement” in this general sense of a function contract can be categorized into groups based on how much the compiler can help you enforcing them statically. For instance, when you say a function requires a string of characters to be passed, you can use a type like std::string_view and now a C++ compiler can statically enforce that anywhere the function is used it is passed a std::string_view or something convertible, or else a hard compiler error is emitted. On the other side of the spectrum, you have a requirement that two dynamically-sized strings passed to the function must have equal lengths. There is no way to detect it statically, so we have a different “kind” of requirement.

      Concepts and requires keyword is a tool for managing a yet different kind of requirement that is somewhere in the middle: constraints on template parameters. A template – by definition – is not code but something that can produce code when passed parameters. Unless these parameter are passed it cannot be fully checked for correctness. Concepts help manage this, and turn as many function template requirements into compiler errors, as soon as possible, with as good error messages as possible.

      So a concept is like a function evaluated at compile time. It takes a set of types as input and returns a true/false answer to the question whether these types provide a certain set of operations.

      One could say that a concept is a means for statically enforcing certain parts of the contract.

      An archetype is a concrete type: it is a perfect model of a given concept: a concept (as a metafunction) would return answer “true” fr its archetype. An archetype is used for statically verifying certain contracts expressed with concepts.

      Does this help, or does it complicate things even further?

  3. Cameron says:

    Another issue is the (perhaps rare) case of concepts containing unions of predicates, A || B. Now there simply is no ‘minimal’ archetype and you need to synthesize multiple different types and test them all. To me it seems the problem of creating correct archetypes quickly becomes intractable, and so really it’s just a question of how much effort you want to go to in order to get better-but-still-not-perfect coverage.

    • Thanks. This is an important observation.

      If I were to put a practical limit on where I go with my archetype, I guess it would boil down to observation, “a class with no member declarations inside already provides a rich and maybe unintended interface, so get rid of this interface.”

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.