Concepts (C++)

In July 2009, the C++ standards committee decided to remove concepts from C++0x. This article documents concepts as they last appeared in a published working paper.

In the pending C++0x revision of the C++ programming language, concepts and the related notion of axioms were a proposed extension to C++'s template system, designed to improve compiler diagnostics and to allow programmers to codify in the program some formal properties of templates that they write. Incorporating these limited formal specifications into the program (in addition to improving code clarity) can guide some compiler optimizations, and can potentially help improve program reliability through the use of formal verification tools to check that the implementation and specification actually match.

In July 2009, the C++0x committee decided to remove concepts from the draft standard, as they are considered "not ready" for C++0x. There are unofficial plans to have the concepts back in the standard in some form, however no official decision has been made yet. A preliminary version of concepts for C++ has been implemented as ConceptGCC.

Motivation

C++ template classes and functions necessarily impose restrictions on the types that they take. For instance, the standard library containers require that the contained types be assignable. Unlike the dynamic polymorphism that class inheritance hierarchies exhibit, where a function that accepts an object of type Foo& can be passed any subtype of Foo, any class can be supplied as a template parameter so long as it supports all of the operations that users of actual instantiations upon that type use. In the case of the function, the requirement an argument must meet is clear (being a subtype of Foo), but in the case of a template the interface an object must meet is implicit in the implementation of that template. Concepts provide a mechanism for codifying the interface that a template parameter must meet. (See also: type class).

The primary motivation of the introduction of concepts is to improve the quality of compiler error messages. If a programmer attempts to use a type that does not provide the interface a template requires, the compiler will generate an error. However, such errors are often difficult to understand, especially for novices. There are two main reasons for this. First, error messages are often displayed with template parameters spelled out in full; this leads to extremely large error messages. On some compilers, simple errors can generate several kilobytes of error messages. Second, they often do not immediately refer to the actual location of the error. For example, if the programmer tries to construct a vector of objects that do not have a copy constructor, the first error almost always refers to the code within the vector class itself that attempts to copy construct its contents; the programmer must be skilled enough to understand that the real error was that the type doesn't support everything the vector class requires.

In an attempt to resolve this issue, C++0x adds the language feature of concepts. Similar to how OOP uses a base-class to define restrictions on what a type can do, a concept is a named construct that specifies what a type must provide. Unlike OOP, however, the concept definition itself is not always associated explicitly with the type being passed into the template, but with the template definition itself:

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

Rather than using an arbitrary class or typename for the template type parameter, it uses LessThanComparable, which is a concept that was previously defined. If a type passed into the min template function does not satisfy the requirements of the LessThanComparable concept, then a compile error will result, telling the user that the type used to instantiate the template does not fit the LessThanComparable concept.

A more generalized form of the concept is as follows:

template< typename T> requires LessThanComparable<T>
  const T& min(const T &x, const T &y)
  {
    return y < x ? y : x;
  }

The keyword requires begins a list of requirements, which are specified by concept(s). In the requirement list, multiple concepts can be combined with boolean operation negative(!) and logical-and(&&) to form template constraint. Using the syntax of requires !LessThanComparable<T> if the user wishes to prevent the use of one particular template if the type matches the concept. This mechanism can be used in a way similar to template specialization. A general template would handle types with fewer features, explicitly disallowing the use of other, more feature-rich, concepts. And those concepts would have their own specializations that use those particular features to achieve greater performance or some other functionality. Another operation logical-and is also easy to use in the requirement list. For the type used in the template requires both assignment and copy-construct, just add requires Assignable<T>&&CopyConstructible<T>.

Concept definition

Concepts are defined as follows:

auto concept LessThanComparable< typename T>
{
  bool operator<(T, T);
}

The keyword auto, in this instance, means that any type that supports the operations specified in the concept will be considered to support the concept. Without the use of the auto keyword, the type must use a concept map in order to declare itself as supporting the concept.

This concept says that any type that has an operator < that takes two objects of that type and returns a bool will be considered LessThanComparable. The operator need not be a free-function; it could be a member function of the type T.

Concepts can involve multiple objects as well. For example, concepts can express that a type is convertible from one type to another:

auto concept Convertible< typename T, typename U>
{
  operator U(const T&);
}

In order to use this in a template, it must use a generalized form of concept usage:

template< typename U, typename T> requires Convertible<T, U>
  U convert(const T& t)
  {
    return t;
  }

Concepts may be composed. For example, given a concept named Regular:

concept InputIterator< typename Iter, typename Value>
{
  requires Regular<Iter>;
  Value operator*(const Iter&);
  Iter& operator++(Iter&);
  Iter operator++(Iter&, int);
}

The first template parameter to the InputIterator concept must conform to the Regular concept.

Concepts can also be derived from one another, like inheritance. Like in class inheritance, types that meet the requirements of the derived concept also meet the requirements of the base concept. It is defined as per class derivation:

concept ForwardIterator< typename Iter, typename Value> : InputIterator<Iter, Value>
{
  //Add other requirements here.
}

Typenames can also be associated with a concept. These impose the requirement that, in templates that use those concepts, these typenames are available:

concept InputIterator< typename Iter>
{
  typename value_type;
  typename reference;
  typename pointer;
  typename difference_type;
  requires Regular<Iter>;
  requires Convertible<reference, value_type>;
  reference operator*(const Iter&); // dereference
  Iter& operator++(Iter&); // pre-increment
  Iter operator++(Iter&, int); // post-increment
  // ...
}

Concept maps

Concept maps allow types to be explicitly bound to a concept. They also allow types to, where possible, adopt the syntax of a concept without changing the definition of the type. As an example:

concept_map InputIterator<char*>
{
  typedef char value_type;
  typedef char& reference;
  typedef char* pointer;
  typedef std::ptrdiff_t difference_type;
};

This map fills in the required typenames for the InputIterator concept when applied to char* types.

As an added degree of flexibility, concept maps themselves can be templated. The above example can be extended to all pointer types:

template< typename T> concept_map InputIterator<T*>
{
  typedef T value_type;
  typedef T& reference;
  typedef T* pointer;
  typedef std::ptrdiff_t difference_type;
};

Further, concept maps can act as mini-types, with function definitions and other constructs commonly associated with classes:

concept Stack< typename X>
{
  typename value_type;
  void push(X&, const value_type&);
  void pop(X&);
  value_type top(const X&);
  bool empty(const X&);
};

template< typename T> concept_map Stack<std::vector<T> >
{
  typedef T value_type;
  void push(std::vector<T>& v, const T& x) { v.push_back(x); }
  void pop(std::vector<T>& v) { v.pop_back(); }
  T top(const std::vector<T>& v) { return v.back(); }
  bool empty(const std::vector<T>& v) { return v.empty(); }
};

This concept map allows templates that take types that implement the concept Stack to take a std::vector, remapping the function calls directly to the std::vector calls. Ultimately, this allows a pre-existing object to be converted, without touching the definition of the object, into an interface that a template function can utilize.

Finally, it should be noted that some requirements can be checked using static assertions. These can verify some requirements that templates need, but are really aimed at a different problem.

Axioms

Axioms are a facility pertaining to concepts supplied by C++0x to express the semantic properties of concepts. For example, the concept Semigroup can be defined with an axiom Associativity as

concept Semigroup< typename Op, typename T> : CopyConstructible<T>
{
  T operator()(Op, T, T);

  axiom Associativity(Op op, T x, T y, T z)
  {
    op(x, op(y, z)) == op(op(x, y), z);
  }
}

Compilers are allowed, but not required, to take advantage of the semantics specified by axioms to perform optimizations that possibly have side-effects on the observable behavior of the program, which are typically prohibited (with few exceptions such as copy constructor elision). In the above example, compilers may reassociate nested calls to operator() of type Op on several values of type T provided that there is a concept map for types Op and T to the concept Semigroup.

Axioms can also assist in software verification, software testing, and other program analyses and transformations.

See also

• ConceptGCC