Title: Concepts Lite in Practice

Author: Martin Moene

Date: 02 June 2016 09:57:37 +01:00 or Thu, 02 June 2016 09:57:37 +01:00

Summary: Concepts should make templates easier to use and write. Roger Orr gives a practical example to show this.

Body: 

The Concepts TS has been published and it has been implemented in gcc 6.1, released April 2016. Using concepts with gcc is as simple as adding the -fconcepts flag.

What does using concepts look like in practice: do we get what we hoped for? To answer that question properly we need to ask how, and why, we got here.

C++ is a rich language and supports polymorphic behaviour both at run-time and at compile-time. At run-time C++ uses a class hierarchy and virtual function calls to support object oriented practices where the function called depends on the run-time type of the target; at compile time templates support generic programming where the function called depends on the compile-time static type of the template arguments.

One major difference between these two is that the first one is tightly constrained by the inheritance hierarchy of the objects involved but the second one can be applied to unrelated types.

Run-time polymorphism is a key component in object oriented design. The function signature to use is decided at compile time based on the static type of the target object; the implementation used is based on the run-time type of the object. The rules of C++ guarantee that any object satisfying the static type will provide an implementation for the target function. This has been a fundamental part of C++ for a very long time (about as long as it has been called C++) and has been very stable – it has been essentially unchanged for over 30 years

Compile time polymorphism has also been in the language for a very long time. The principle is to provide a ‘template’ which enables the compiler to generate code at compile time. One of the main motivations for this was for type-safe containers; but when coupled with non-type template arguments, overloading, and tag-dispatching the result in modern C++ is very expressive. There is, I know, a range of opinions over the utility of template meta-programming and a lot of this is because it can be very hard to debug.

The reason for this is that templated code is fragile – whether the code is valid depends on the template arguments provided by the user when the template is instantiated. While the writer of a template has (usually) tested at least one instantiation of their code, they may have made, possibly unconscious, assumptions about the template arguments that can be used with their template.

(Note that if there is no valid instantiation the program is ill-formed, but a diagnostic is not required – it is a ‘hard problem’ to solve in general so compilers are not required to identify this in every case.)

Library writers currently rely on documenting their assumptions about template parameters but it is hard to get this right. Additionally, compilers don't read documentation and so the diagnosis of a compilation failure can be painful (for the user).

For example, consider this simple piece of code:

  class X{};
  std::set<X> x;
  x.insert(X{});

I get 50–100 lines of error text from this, depending on which compiler I use.

The fundamental problem is that I’m missing the < operator for X so it does not satisfy the LessThanComparable requirement documented in the C++ standard:

Table 18 – LessThanComparable requirements [lessthancomparable]

(In a future version of C++ this simple example may become valid – generation of default comparison operators may make it into the language.)

Enter concepts

One of the early papers on Concepts was Bjarne’s paper ‘Concept Checking – A more abstract complement to type checking’ from Oct 2003 [N1510]. He points out that the fundamental problem that makes it hard to provide good checking for templates in C++ is that templates are not constrained, so by default any possible type may be used to instantiate a template.

As a later paper puts it ([N2081], Sep 2006) “Concepts introduce a type system for templates that makes templates easier to use and easier to write.”

Currently type checking occurs when some part of the instantiation fails, rather than when checking against the signature of the function being called. Concepts allow the programmer to provide constraints against the types of template arguments which become part of the function signature and hence should be easier to check and provide clearer diagnostics to the user.

The proposals went through a number of changes and enhancements during the development of C++11 (then known as C++0x) but it eventually became clear that the system being proposed was too complex and could not be nailed down in time for a delivery of C++11 in a realistic timeframe. The proposal at that time included, among other things, concept checking which ensured the implementation complied with the concepts.

After much discussion and a number of meetings agreement was reached to provide a simplified form of concepts, so-called ‘Concepts Lite’, and to deliver this as a free-standing Technical Specification rather than initially putting it into the C++ standard itself.

This would give a common standard for those implementing concepts and allow time for experimentation with the feature and feedback from this would allow refinement of the proposal before it was adopted into the C++ standard itself.

Building up an example

Let’s build up a simple example to see what can be done with the current language rules and then show what can be done with Concepts Lite.

Consider this simple function declaration:

  bool check(int lhs, int rhs);

The function takes two int values and the validity of calling code is decided without any need to see the implementation of the function.

  int main()
  {
    int i = 1;
    int j = 2;
    return check(i, j); // Valid!
  }

A possible function definition could be:

  bool check(int lhs, int rhs) 
  { return lhs == rhs; }

but the calling code does not need access to the implementation at compile time and the implementation can be changed without invalidating the call site.

Unfortunately using a single function means the following code compiles (possibly with a warning, but the code is valid C++) but is probably not doing what is expected:

  int main()
  {
    double root10 = sqrt(10.0); // approx 3.162278
    double pi = 3.14159;        // near enough
    return check(root10, pi);   // implicit
  }                             // conversion to int

If we want to check the original double values rather than the (truncated) int values, we need to generalise the code. One way is to add an overload:

  bool check(int lhs, int rhs);
  bool check(double lhs, double rhs);
  {
    bool b1 = check(1, 2);  // works with int
    bool b2 = check(e, pi); // works with double
  }

We have generalised our function to a predefined set of types – but we need to duplicate the implementation.

Another approach is to use a template:

  template <typename T>
  bool check(T lhs, T rhs);

We now have only one function definition:

  template <typename T>
  bool check(T lhs, T rhs) { return lhs == rhs; }

and we have produced a template for a set of functions for an unbounded number of types.

  {
    bool b1 = check(1, 2);       // works with int
    bool b2 = check(root10, pi); // works with
  }                              // double

We can easily generalise further to take two different types:

  template <typename T, typename U>
  bool check(T lhs, U rhs);

Now, without any further changes to the implementation, the function can deal with any two types for which equality is defined.

As we mentioned earlier though, compilation errors are reported during the instantiation of the function template; for example, if we pass an int and the address of an int we see Listing 1.

Basic_Template_Failure.cpp: In instantiation of 
 'bool check(T&&, U&&) [with T = int&; U = int*]':
... comparison between pointer and integer [-fpermissive]
 bool check(T && lhs, U && rhs) { return lhs == rhs; }
                                         ~~~~^~~~~

We could do better ...

‘SFINAE’

When substituting possible values for template arguments the result can be invalid – in this case the program itself is not invalid, but the troublesome substitution is simply removed from the overload set. This is known as ‘substitution failure is not an error’ which abbreviates to SFINAE.

Use of this rule can be used for enable_if and other similar techniques. Listing 2 is a simple example.

template <typename T>
void f(T t, typename T::value_type u);

template <typename T>
void f(T t, T u);

int main()
{
   f(1, 2);  // first f() non-viable when substituting int
   std::vector<int> v;
   f(v, 2);  // second f() not a match as types differ
}

In the first call to f() the compiler tries to substitute int into the first template, which involves trying to form the type int::value_type. This is not valid, so the first template is skipped and the second one is used.

We can use SFINAE in our check() function to ensure that the equality check will be valid:

  template <
    typename T, typename U, 
    typename = std::enable_if_t< is_equality_comparable <T, U>::value>
  >
  bool check(T && lhs, U && rhs);

This has the desired effect of removing the function from the overload set if the two types are not equality comparable (see Listing 3).

Basic_Enable_Failure.cpp:40:21: error: no matching function for call to 
 'check(int&, int*)'
return check(i, &j);
                  ^
Basic_Enable_Failure.cpp:34:6: note: candidate: 
 template<class T, class U, class> bool check(T&&, U&&)
bool check(T && lhs, U && rhs) { return lhs == rhs; }
     ^~~~~
Basic_Enable_Failure.cpp:34:6: note: 
  template argument deduction/substitution failed:

Notice what we do here, which is very common with this sort of technique. We have added a third template argument to the template, which doesn’t have a name as it is not used anywhere, and given it a default value specified in terms of the arguments that we wish to constrain.

We do of course need to provide is_equality_comparable; Listing 4 is one possible implementation.

#include <type_traits>

template<typename T, typename U, typename = void>
struct is_equality_comparable : std::false_type{ };

template<typename T, typename U>
struct is_equality_comparable<T,U,
  typename std::enable_if<
    true,
    decltype(std::declval<T&>() == std::declval<U&>(), (void)0)
    >::type
  > : std::true_type
{
};

While writing this is not for the faint hearted – and nor is reading it – this is the sort of construct that can be written once and provided in a common header. It can therefore be used without needing to investigate the implementation. Note however that, even apart from the complexity, there is a problem with the disjoint between the check and the expression being checked

  decltype(std::declval<T&>() == std::declval<U&>())

The expression we want to detect is lhs == rhs but we have to write a more complicated expression, subject to the various rules for SFINAE, which acts as a proxy for the check we actually wanted.

For some expressions it can be rather challenging to find an equivalent SFINAE check, and sometimes there can be subtle differences.

Concepts to the rescue

There are several ways we can constrain our check function with concepts. The first, and most basic way, is by adding a requires clause:

  template <typename T, typename U>
  requires requires(T t, U u) { t == u; }
  bool check(T && lhs, U && rhs);

The function declaration shows the constraint using normal C++ syntax (that matches the code used in the definition.) Calling check() with int and char* gives this error:

  Basic_Requires.cpp:19:6: note: constraints not satisfied
  bool check(T && lhs, U && rhs) { return lhs ==  rhs; }

(I’m using the gcc 6.1 release for these examples; there are some additional changes from Andrew Sutton still to come in gcc that should further improve the error messages.)

Alternatively, we could define a named concept and use that:

  template<typename T, typename U>
  concept bool Equality_comparable() {
    return requires(T t, U u) {
      { t == u } -> bool;
    };
  }

Naming a concept has two main benefits.

• The concept can be shared by multiple template declarations
• Naming allows us to express some of the semantic constraints on the type.

We use it like this by supplying it with appropriate arguments in the declaration:

  template <typename T, typename U>
  requires Equality_comparable<T, U>()
  bool check(T && lhs, U && rhs);

Calling check() with int and char* now gives us Listing 5.

Basic_Concept.cpp:33:29: error: 
  cannot call function 'bool check(T&&, U&&) [with T = int&; U = char*&]'
  return check(argc, argv[0]);

Basic_Concept.cpp:29:6: note: 
   concept 'Equality_comparable<int&, char*&>()' was not satisfied

As another alternative the concepts TS allows us to write a concept using a variable-like syntax instead of the function-like syntax used above:

  template<typename T, typename U>
  concept bool Equality_comparable = 
    requires(T t, U u) {
      { t == u } -> bool;
    };

  template <typename T, typename U>
  requires Equality_comparable<T, U>
  bool check(T && lhs, U && rhs);

The syntax is quite similar to the function template form, except for the reduction in the number of brackets. One restriction though is that you cannot overload variable concepts. The error handling is pretty much the same:

Basic_Variable_Concept.cpp:29:6: note: 
  concept 'Equality_comparable<int&, char*&>' was not satisfied

Making consistent concepts

The Equality_comparable concept I introduced above is asymmetric as it only checks that the expression t == u is valid. This matches our (only!) use case, but is not suitable for use as a general equality concept.

The ranges TS defines something like this:

  template<typename T, typename U>
  concept bool EqualityComparable() {
    return requires(T t, U u) {
      { t == u } -> bool;
      { u == t } -> bool;
      { t != u } -> bool;
      { u != t } -> bool;
    };
  }

However, if we use this concept in our example we now have the reverse problem: you can argue our template is now over-constrained. Consider this simple example of trying to use check() with a simple user-defined class (Listing 6).

struct Test{
  bool operator==(Test);
};

bool foo(Test v, Test v2)
{
  return check(v, v2);
}

Basic_Concept_Failure.cpp: In function 'int main()'
Basic_Concept_Failure.cpp:39:20: error: 
  cannot call function 'bool check(T&&, U&&)' 
  return check(v, v2);
... concept 'Equality_comparable<Test&, Test&>()'

In order to call our check() function we have to declare, but not necessarily define, an extra operator.

  struct Test{
    bool operator==(Test);
    bool operator!=(Test);
  };

or

  bool operator!=(Test, Test);
  
  bool foo(Test v, Test v2)
  {
    return check(v, v2); // Now Ok
  }

This was a simple example as we were instantiating the template with the same type for both T and U. If the arguments to check() differ in type we have a little more work to do (Listing 7).

struct Test{
  bool operator==(int);
};

bool foo(Test v)
{
  return check(v, 0);
}

Basic_Concept_Failure2.cpp: In function 'int main()'
Basic_Concept_Failure2.cpp:39:20: error: 
  cannot call function 'bool check(T&&, U&&)' 
  return check(v, 0);
... concept 'Equality_comparable<Test&, int>()'

In order to call our check() function we now have to declare three extra functions (see Listing 8).

struct Test{
  bool operator==(int);
  bool operator!=(int);
};

// These two cannot be defined in-class
bool operator==(int, Test);
bool operator!=(int, Test);

bool foo(Test v)
{
  return check(v, 0); // Ok
}

Is this good or bad? It’s both, unfortunately.

Defining a smallish set of well-defined and ‘complete’ concepts is arguably a good idea as it encourages/enforces more consistent operator declarations for types. Stepanov’s original design for the STL was based on his work in Elements of Programming and he defined various type attributes such as Regular and Constructible. This type of classification is a natural fit for this sort of use of concepts.

However, it can increase the work needed to adapt a class to comply with a concept. C++ programmers are used to providing the minimal set of methods to use a template and have a reluctance to provide more than this. Whether this is something to be encouraged is arguable.

The ‘requires requires’ use is less affected by this issue as each function template has its own clause – but it raises the complexity of reading each function declaration, and breaks DRY.

Behaviour under change

When using run-time polymorphism, the derived type must implement all the pure virtual methods in the base class. If a new method is added, or a signature is changed, errors are reported when the derived class is compiled and/or instantiated (depending on exactly what’s changed).

When the constraints for a function change, the type provided may now silently fail to satisfy the constraints. This may result in a compile time failure, or may result in a different overload of the function being selected.

More complex constraints

If we look at an example with a more complicated constraint we see some additional benefits of using concepts over the existing technology that uses enable_if or other SFINAE techniques.

While enable_if and similar techniques do provide ways to constrain function templates it can get quite complicated. One recurring problem is the ambiguity of template argument types solely constrained by enable_if – for example, see Listing 9.

struct V {
  enum { int_t, float_t } m_type;

  // Constructor from 'Int' values
  template <
    typename Int, 
    typename = std::enable_if_t< std::is_integral<Int>::value>
  >
  V(Int) : m_type(int_t) { /* ... */ }
 
  // Constructor from 'Float' values
  template <
    typename Float, 
    typename = std::enable_if_t< std::is_floating_point<Float>::value>
  >
  V(Float) : m_type(float_t) { /* ... */ }
};

Unfortunately this example does not compile – as we have two overloads of the same constructor with the same type (that of the first template argument) – see Listing 10.

ambiguity_with_enable_if.cpp:25:5: error: 
  'template<class Float, class> V::V(Float)' cannot be overloaded
  V(Float) : m_type(float_t) {}
  ^
ambiguity_with_enable_if.cpp:20:5: error: 
  with 'template<class Int, class> V::V(Int)'
  V(Int) : m_type(int_t) {}
  ^

The compiler never gets to try overload resolution as declaring the two overloads is a syntax error. If we add a second argument we can resolve the ambiguity and allow overload resolution to take place; SFINAE will then remove the case(s) we do not want.

We can give the extra argument a default value to avoid the caller needing to be concerned with it. (Listing 11)

enum { int_t, float_t } m_type;

template <int> struct dummy { dummy(int) {} };

// Constructor from 'Int' values
template <
  typename Int, 
  typename = std::enable_if_t< std::is_integral<Int>::value>
>
V(Int, dummy<0> = 0) : m_type(int_t) {/* ... */}

// Constructor from 'Float' values
template <
  typename Float, 
  typename = std::enable_if_t< std::is_floating_point<Float>::value>
>
V(Float, dummy<1> = 0) : m_type(float_t) {/*...*/}

The additional dummy arguments are of two different types, dummy<0> and dummy<1>, and so we no longer have ambiguity and both functions participate in overload resolution.

However, this addition of dummy arguments that take no other part in the function call adds needless complexity for both the compiler and for the readers and writer of the template. We are also relying on the optimiser removing the dummy arguments.

Concepts are a language feature and so the solution using them is much clearer, as can be seen in Listing 12.

struct T {
  enum { int_t, float_t } m_type;

  // Constructor from 'Int' values
  template <typename Int>
    requires std::is_integral<Int>::value
  V(Int) : m_type(int_t) { /* ... */ }
 
  // Constructor from 'Float' values
  template <typename Float>
    requires std::is_floating_point<Float>::value
  V(Float) : m_type(float_t) { /* ... */ }
};

There is no ambiguity here as the constraints are part of the overload resolution rules themselves and so there is no need for dummy arguments.

Concept introducer syntax

The concepts TS supports a ‘concept introducer’ syntax and an abbreviated syntax which I have not yet demonstrated, so let’s modify the example to do so.

A lot of the complexity in the wording of the Concepts TS is to ensure that the specification of a constrained function using this additional syntax is equivalent to the requires form (Listing 13).

template <typename T>
concept bool Int = std::is_integral_v<T>;

template <typename T>
concept bool Float = std::is_floating_point_v<T>;

struct V {
  enum { int_t, float_t } m_type;

  // Constructor from 'Int' values
  template <Int T>
  V(T) : m_type(int_t) { /* ... */ }
 
  // Constructor from 'Float' values
  template <Float F>
  V(F) : m_type(float_t) { /* ... */ }
};

This is syntactic sugar to avoid needing to use typename:

  template <Int T>
  bool check(T value);

is equivalent to:

  template <typename T>
  requires Int<T>
  bool check(T value);

The translation between the introducer syntax and that using requires is fairly simple and unlikely to cause confusion. Note though that, as they are equivalent, both forms can occur in the same translation unit – and that the name T could be different.

It does save characters: in this case 37 vs 58. How much of a benefit this is seems to depend who you ask.

You can further abbreviate the syntax:

  struct V {
    enum { int_t, float_t } m_type;
	
    // Constructor from 'Int' values
    V(Int) : m_type(int_t) { /* ... */ }

    // Constructor from 'Float' values
    V(Float) : m_type(float_t) { /* ... */ }
  };

This syntax allows the declaration of templates without needing to use <>.

Is this a good thing? There seem to be three main answers:

• Yes
• No
• Maybe

One reason why it might be troublesome is the difference that a function being a template or not makes to the lookup and argument matching rules (see Listing 14).

bool check(Int value);

void test(Float f)
{
  if (check(f))
  {
    // do something
  }
}

Will check() get called? If Int is a type we look for conversions on argument types that we will not look for if Int is a concept.

Additionally, whether we need access to the definition of check() depends on whether it is a template or not.

Equivalent or functionally equivalent?

What does it all mean, anyway?

  bool check(Int value);

This is equivalent to:

  template <Int A>
  bool check(A value);

which is itself equivalent to:

  template <typename C>
  requires Int<C>
  bool check(C value);

and all of these are functionally equivalent to:

  template <typename D>
  requires std::is_integral_v<D>
  bool check(D value);

The difference is that a program can contain two declarations of a function template that are equivalent – but it is not valid to contain two declarations of a function template that are only functionally equivalent. There are additional rules defining the finer details of equivalence in the concepts TS (or [N4335]).

Restrictions on the concept introducer syntax

  bool check(Int value, Int other);

This is equivalent to:

  bool check(T value, T other);

Note that the two variables will always have the same type – we cannot use the short form syntax (there were some very tentative proposals, but nothing was accepted) to replace:

  template <Int T, Int U>
  bool check(T value, U other);

auto templates

The concepts TS also allows using auto to introduce an unconstrained template parameter (Listing 15).

bool check(auto value);

void test(Float f)
{
  if (check(f))
  {
    // do something
  }
}

I see this as less problematic than the constrained case – it mirrors the existing use of auto for declaring a polymorphic lambda. There is no ambiguity in the mind of the reader about whether or not the function so declared is a template, the use of auto means it must be a template and so no further context is needed.

While ‘Concepts Lite’ is not part of C++17 (see, for example, [Honermann] for more on this...) this part of the TS does stand a little apart from the rest and I for one would have been happy to accept this into C++17 as a separate proposal; sadly this hasn’t been proposed yet and the departure gate for C++17 is probably closed for that option.

Summary

Concepts do seem to be significantly simpler to read and write than the current alternatives.

It does seem to me that it delivers better compiler errors for users; while I’m sure it is possible to find counter-examples I expect them to be rarer.

It is easier to constrain functions, for writers, without requiring complex and sometimes fragile meta-programming trickery. Concepts also express intent in code rather than by inference, in documentation, or in comments.

Using concepts does have the potential of under or over constraining. If we under-constrain types that match, the concepts fail when the template is instantiated, and if we over-constrain, we restrict the set of allowable types further than we needed.

The syntax is slightly awkward – this is my biggest issue with the current wording in the TS.

• template <typename T> requires requires(T t) {…}

  ‘requires requires’ – can we be serious?

• concept bool x = requires(...) {}

  the type must be specified and must be bool

• supporting the variable form, in addition to the function form, seems to be unnecessary

I am not persuaded that we need the concept introducer syntax. While it reduces the number of symbols in the code I am not sure that this actually simplifies things or merely hides away complexity that we do need to know about.

Now is the time for C++ programmers to use concepts and to provide feedback to the standards body. With the recent release of gcc 6.1 doing this has become easier.

References

[Honermann] http://honermann.net/blog/?p=3 (‘Why concepts didn’t make it into C++17’)

[N1510] http://www.stroustrup.com/n1510-concept-checking.pdf

[N2018] http://open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2081.pdf

[N4335] http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4335.html (pre-publication concepts working paper)

Notes: 

More fields may be available via dynamicdata ..