Easier C++: An Introduction to Concepts

very C++ programmer has had one of those days: A simple use of a template library turns into a nightmare, with pages upon pages of error messages streaming out of the compiler. Somewhere in that proverbial haystack are the clues you will need to determine exactly what went wrong?an error about a missing + operator here, an incompatible type assignment there?but you know you are in for a long search through the grisly internals of the template library, or a visit from your local C++ template guru.

This article is not about C++ template error messages, but they are indicative of a far more general problem with the C++ template system. Most errors in the use of templates come from a misunderstanding between the author of the template and the user of the template. The author of the template expects the user’s type to provide some specific set of operations, say, a + operator for addition and a copy assignment operator, which I’ll refer to as the template requirements. When the user provides a type with the appropriate operations, i.e., the type satisfies the template requirements, everything works. However, when the user’s type is missing some operations, the compiler reports the error as soon as the template tries to use that operation, which is often deep in the implementation of the template library. Thus, the template requirements are effectively a contract between the template author and user, and debugging a template error message is the act of trying to determine who broke the contract?and how.

Enter: Concepts
Concepts is a language feature planned for C++0x that allows programmers to express the template requirements as part of the template’s source code. Placing requirements on a template formalizes the contract between template author and user, allowing the compiler to ensure that both parties uphold their end of the bargain. The template author is permitted to use only operations that he has required the user to provide, while the template user is allowed to supply only types that provide all of the operations that the template requires. When both parties uphold the terms of the contract, the program works; but when one party makes a mistake, the compiler produces an error message that describes the error in terms of the contract, isolating the template author from the template user and, therefore, producing shorter, simpler error messages that do not expose library internals to the user.

This article introduces the core ideas behind concepts, showing how they can be used to express the template requirements to provide correct and easy-to-use template libraries. The end of the article will illustrate some of the advanced features of concepts that make template libraries more powerful and more flexible. The intrepid reader may want to follow along using ConceptGCC, a prototype compiler implementing the concepts language feature. Template metaprogramming gurus: Please check your template tricks at the door?you won’t need them here.

A Min(imal) Example
Your journey into concepts starts with the simplest of function templates, min():

templateconst T& min(const T& x, const T& y) {  return x < y? x : y;}

Despite being simple, the min() function does place some requirements on its template type parameter T. The user must provide a type that has a less-than operator (<) to compare two values of type T, the result of which must be convertible to a Boolean value. Supply a type that has such a less-than operator (like int or std::string) and min() will work; supply a type without a less-than operator (such as std::complex), and min() will fail to instantiate.

Listing 1 shows how to introduce concepts into the min() function template. The min() function template has been augmented with a requires clause, which states the template requirements in terms of concepts, which I'll describe in a moment. In this case, the requirement is LessThanComparable, meaning, "T must meet the LessThanComparable concept's requirements." Other than the addition of the requires clause, the definition of min() is unchanged. However, because min() now has requirements (a.k.a. constraints), it's called a constrained template.

Concepts are entities that describe the operations that a type is expected to have. The beginning of Listing 1 declares the LessThanComparable concept with a single type parameter, T. The body of the concept describes what it means for T to be LessThanComparable. In this case, it means that there is a less-than operator taking two values of type T and returning something that is convertible to bool. You could certainly express other operations in the body of the concept?other operators, member functions, non-member functions, constructors, etc.?but few other operations make sense for LessThanComparable.

Constrained templates, through their use of concepts, describe the contract between the template user and author so that the compiler can verify that both parties abide by the terms of the contract. Next, you'll see how the compiler verifies both sides of the contract.

User's Side of the Contract
To call the min() function, the user must provide a type for T that meets the LessThanComparable concept's requirements. Because C++ integers provide a less-than operator, the call min(17, 42) is a reasonable test. However, this call will fail with an error at the call site (not in the implementation of min()) stating that int is not LessThanComparable. The problem, in this case, is that the compiler does not know what the less-than operator in LessThanComparable actually means, and therefore cannot determine whether the built-in less-than provided for integers agrees with that meaning. Therefore, the user states explicitly that int meets the LessThanComparable concept's requirements through the use of a concept map:

concept_map LessThanComparable { }

Concept maps state that a particular type meets the concept's requirements. When one attempts to use a constrained template like min(17, 42), the compiler searches for a concept map LessThanComparable and will find the concept map defined above, so the call succeeds.

Concept maps play a second role in checking the user's side of the contract, because the concept maps themselves are verified against the body of the concept. In the concept map above, the compiler verifies that the int type has a suitable less-than operator (it happens to be a built-in operator), which returns a type that is convertible to bool. This checking can be seen when one attempts to write an incorrect concept map, for instance:

concept_map LessThanComparable> { } // error: no operator< for std::complex

Because std::complex does not provide a less-than operator, the compiler will produce an error message stating that this type does not meet the LessThanComparable concept's requirements. Because you can't even define the concept map to state that complex numbers are LessThanComparable, you can't attempt to use the min() function. Most importantly, you never have to look into the actual body of min() to determine that there was an error; the requirements have all of the information you need.

For trivial concepts such as LessThanComparable, the need to write a concept map for every type can become a bit onerous. For this reason, there is a special kind of concept, called an auto concept, for which the compiler will automatically provide concept maps whenever they are needed. If you change the definition of the LessThanComparable concept to the following, users will no longer have to write concept maps for LessThanComparable to call the min() function:

auto concept LessThanComparable {  bool operator<(const T& x, const T& y);}

Author's Side of the Contract
When the author of a template places requirements on that template, the author is also bound by the terms of the contract. In particular, the author cannot use an object of type T with any operations not specified in the contract. With the min() function, for example, the body of the function can use only the < operator on objects of type T, because only the < operator is specified by the LessThanComparable concept. Suppose you tried to implement a max() function with LessThanComparable as follows:

templaterequires LessThanComparableconst T& max(const T& x, const T& y) {  return x > y? x : y; // error: no operator>(T, T)}

In this example, the author specified in the contract that the type T would provide a '<' operator, but the template body uses '>'. The compiler will produce an error message when it processes the template stating that no such '>' operator exists. Therefore, the template author is bound by the same contract as the user, and there cannot be any surprises where the template author states one requirement in the contract but uses a slightly different operation in the implementation. This is exactly the kind of problem that occurs with template libraries today: Because most types that max() would be tested with will have both less-than and greater-than operations, the latent error?that the function requires less-than but uses greater-than?is unlikely to be detected by testing. With concepts, however, the compiler detects this form of error immediately.

Because both the template author and user are held to the same contract, the compiler can provide an extremely important guarantee: If both the template's implementation and the use of the template meet the contract's requirements, the instantiation of that template will not fail. There are two practical effects to this guarantee. First, concepts eliminate the spectacularly poor error messages produced by long instantiation backtraces, because the failures occur before template instantiation is even attempted. Second, both users and library authors can have a far greater level of confidence in template libraries using concepts than in the corresponding pre-concept libraries, because the compiler takes a more active role in verifying the correctness of templates.

The Perimeter of a Polygon
Listing 2 contains a simple algorithm that computes the perimeter of the polygon it is given, by summing the lengths of each of the sides of the polygon. Polygons are described by the Polygon concept, which provides functions that determine the number of sides and the length of a given side.

The Polygon concept's requirements can be satisfied by many different data types. For example, you can implement a simple triangle class that can be passed to the perimeter() function:

class triangle {public:  int sides[3];};int num_sides(const triangle& tri) { return 3; }int side_length(const triangle& tri, int index) {   return tri.sides[index]; }concept_map Polygon { }

The triangle class provides the operations required by the Polygon concept, num_sides() and side_length(). Note, however, that while the Polygon concept expects side_length() to return a double, triangle's version of side_length() returns an int. This is not an error. Concept maps provide one level of conversions, which will automatically convert the int returned by triangle's num_sides() into the double expected by users of the Polygon concept. This way, minor mismatches in the interface between the template user and the template author are resolved automatically in the concept map, making constrained templates more widely applicable.

Associated Types
The implementation of perimeter() works with the triangle class, but it is suboptimal; despite the fact that the sides of the triangle are specified in terms of integers, all of the computation in perimeter() is performed via floating-point arithmetic. To solve this problem, the algorithm should instead perform the computation using the same type that the polygon uses to express the lengths of its sides, which may vary from one type to another.

Concepts provide a way to express such types, which vary from one use of a concept to another: associated types. Associated types are declared within the body of a concept via the typename keyword (using the same syntax as template type parameters), and can be used to describe operations within the concept. You can now revise the Polygon concept to introduce an associated type named length_type, which is used to express the length of a single side in the polygon, and therefore is the return type of the side_length() operation:

concept Polygon {  typename length_type  int num_sides(const P&);  length_type side_length(const P&, int index);}

Because the types of concept operations are important wherever the concepts are used, you can refer to an associated type as a nested type within the concept. For example, an updated perimeter() algorithm should refer to the length_type of the Polygon concept explicitly, rather than using double:

templaterequires Polygon

Polygon

::length_type perimeter(const P& poly) { Polygon

::length_type sum = 0; // error! for (int i = 0; i < num_sides(poly); ++i) sum += side_length(poly, i); // error! return sum; // error!}

Here, the uses of double are replaced with Polygon

::length_type, which has made the algorithm capable of handling different length types, and therefore more reusable. However, this change has introduced some new errors that will be detected by the compiler. Previously, the algorithm was relying on the built-in operations provided by double: construction from an integer, addition via +=, and copy-construction of the return value. With an arbitrary length_type, you can no longer assume that all of these operations are available. They have to be specified as requirements on the length type, which the user's length type must satisfy.

Member-Function Requirements
To express the length type's requirements, we introduce another new concept, Numeric. The Numeric concept provides the essential operations required to sum a value:

auto concept Numeric {  T::T(const T&);              // copy construction  T::T(int);                   // construction from an int  T::~T();                     // destructor  T& operator+=(T&, const T&); // addition}

The first three operations in the Numeric concept require a copy constructor (which can be satisfied by a built-in initialization), the ability to construct a value of type T from an int, and the ability to destroy an object of type T. Each of these operations is stated using member function syntax with the T:: prefix, specifying that these operations apply to objects of type T. The same syntax can be used to describe specific member functions requirements (for example, T::clone()).

Armed with the Numeric concept, you can express the perimeter() algorithm's full requirements as:

templaterequires Polygon

&& Numeric::length_type>Polygon

::length_type perimeter(const P& poly);

The "&&" in the requires clause states that both requirements must be satisfied for the algorithm to be usable, that is, the type P must be a Polygon and its length_type must be Numeric. Any number of different requirements can be added to a template using "&&", including multiple requirements on the same types.

Associated Requirements
Adding the Numeric requirement to the perimeter() concept is correct, but it is not ideal. The requirement that the length_type of a Polygon be Numeric isn't solely a property of perimeter(): It's a more universal property that polygons only make sense if their length types are proper numeric types. To support this common usage, concepts support associated requirements, which specify extra requirements on the associated types of a concept within the concept body. Here is the final version of the Polygon concept, which makes use of associated requirements:

concept Polygon {  typename length_type;  requires Numeric;  int num_sides(const P&);  length_type side_length(const P&, int index);}

With this change, you can remove the explicit Numeric requirement from the perimeter() algorithm, because the length type of a Polygon is always numeric. For the final declaration of this perimeter() algorithm, I've also employed two syntactic shortcuts, which simplify the expression of template requirements and simplify access to associated types:

template P::length_type perimeter(const P& poly);

The first shortcut is the use of Polygon P, which states that P is a template type parameter whose requirement is Polygon

; it is identical to writing the same requirement within a requires clause. The second shortcut is the use of P::length_type, which searches for an associated type named length_type within the requirements placed on P, and is identical to Polygon

::length_type.

Syntax Remapping with Concept Maps
All the concept maps so far have had empty bodies within their curly braces, and have been used to state (and check) that a type meets the concept requirements. However, concept maps need not be empty: they can contain definitions that specify how a type meets the concept requirements, and can even contain new functions that allow one to map the syntax provided by a type to the syntax expected by the concept. For example, start with a simple rectangle structure:

 struct rectangle {  double left, top, right, bottom;};

You could add appropriate num_sides() and side_length() functions to this type to make it look like a Polygon. But, this expands the interface in a way that might not be desirable if the only purpose is to use the perimeter() function. Instead, you can write a concept map that makes the rectangle look like a polygon:

concept_map Polygon {  typedef double length_type;  int num_sides(const rectangle&) { return 4; }  double side_length(const rectangle& rect, int index) {    return index % 2? fabs(rect.right – rect.left)                     : fabs(rect.bottom – rect.top);  }}

In this concept map, the Polygon concept's requirements are satisfied by the body of the concept map itself. The functions provided by the concept map are visible only through the concept itself, and are not part of the public interface of the rectangle structure (which has not changed). Only those constrained templates that operate on Polygons will see this particular view of the rectangle structure.

Through this syntax-remapping mechanism, an existing type can be adapted to meet an existing concept's requirements without changing either the type or the concept, allowing far greater reuse of generic algorithms than is possible without concept maps.

Concept Refinement and Concept-Based Overloading
It is often the case when implementing a generic algorithm that there are several possible implementations, each of which involves different trade-offs. Some implementations may apply to a wide variety of data types (are very generic) while others operate more efficiently on a more narrow range of data types (are more specialized). For example, the generic perimeter() algorithm operates on any polygon in linear time, but there is a more efficient implementation: If you know that the polygon is an equilateral polygon (where all sides have the same length), you could compute the perimeter with a single multiplication. Like Polygon, EquilateralPolygon is a concept that describes types that behave like polygons.

You could implement an EquilateralPolygon separately from the Polygon concept, but doing so misses an important opportunity for reuse, because every equilateral polygon is also a polygon. You can therefore express EquilateralPolygon as a refinement of the Polygon concept:

concept EquilateralPolygon : Polygon

{ }

As the syntax implies, concept refinement is similar to concept "inheritance," because the refining concept (EquilateralPolygon) inherits all of the base concept's requirements (Polygon). Additionally, a type that is an EquilateralPolygon can be used in any algorithm that expects a Polygon, meaning that this square class could be used with the existing perimeter() algorithm:

class square {public:  int length;};concept_map EquilateralPolygon {  typedef int length_type;  int num_sides(const square&) { return 4; }  int side_length(const square& sq, int) {     return sq.length;   }}

Concept refinement describes a hierarchical "is-a" relationship that can also be used by concept-based overloading, which involves overloading constrained templates on their requirements. As noted before, you can write a constant-time algorithm for computing the perimeter of an equilateral polygon, assuming you've already added a suitable multiplication operator to the Numeric concept:

templateP::length_type perimeter(const P& poly) {  return num_sides(poly) * side_length(poly, 0);}

This implementation of perimeter() overloads the previous, Polygon-based implementation. For types that are non-equilateral Polygons, the previous (linear-time) implementation will be used, because this (constant-time) constrained template's requirements will not be satisfied. For equilateral polygons like square, both implementations are valid because every equilateral polygon is a polygon. In this case, concept-based overloading picks the overload corresponding to the more refined concept, automatically selecting the constant-time implementation of perimeter(). Concept-based overloading (and, related, concept-based partial specialization of class templates) allows the user to provide multiple, different variations of the same algorithm, which differ only by the properties of the types that they support, and the compiler will select the most appropriate algorithm variation for each call site.

Truly Easier C++
Concepts are a significant extension to the C++ template system. By allowing template authors to explicitly describe the template requirements, the compiler is able to verify both the template author’s and the template user's side of the (previously implicit) template contract. This additional type checking makes it easier to write templates (because they cannot violate the stated contract) and use templates (because contract violations result in far more readable error messages). The use of template requirements also enables advanced features that make templates more reusable, such as the ability to remap syntax within concept maps, and more expressive, through the use of concept-based overloading.

As of this writing, concepts are expected to be included in the C++0x language and standard library. However, concepts have not yet been voted into the working paper by the ISO C++ standards committee, and some small details may still change. Watch for more interesting developments in C++0x and the concepts mechanism.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Related Posts