Introducing Concepts

August is turning out to be a big month for C++. The Technical Specification for Concepts has been submitted to the ISO for publication [ N4549 ], and its implementation has landed in GCC [ GCC ]. I’ve heard the phrase “ This is a big deal ” a number of times, but I think I like Eric Niebler’s July 20th tweet the best: he wrote, “ This will change everything ” [ Niebler15 ].

It may not be obvious why a new language feature would be such a big deal, or why it would have any significant impact on the way you write code. Think about the way that your C++ programming has changed since C++11 was published. How often do you use auto ? What about initializer lists? Lambda functions? constexpr ? Move semantics? Variadic templates? I’ve often heard it said that C++11 feels like a totally different language. It certainly does to me.

C++11 feels different because we now have language support for ideas that had previously been supported by obscure programming idioms, copious amounts of template metaprogramming, or extensive macro libraries (yuck!). The improvements introduced in C++11 obviate the need for many of those approaches, allowing C++11 programs to much more clearly reflect their designers’ intents. These features allow ideas to be represented directly in the language and not hidden behind impenetrable walls of clever code.

The Concepts TS includes a number of improvements to better support generic programming by:

• allowing the explicit specification of constraints on template arguments as a part of a template’s declaration,
• supporting the ability to overload function templates and partially specialize class and variable templates based on those constraints,
• providing a syntax for defining concepts and the requirements they impose on template arguments,
• unifying auto and concepts to provide uniform and accessible notation for programming generically,
• dramatically improving the quality of error messages resulting from the misuse of templates, and
• doing all of this without imposing any runtime overhead or significant increases in compile times, and also
• without restricting what can be expressed using templates.

This is the first article in a series introducing the language features included in the Concepts TS. This one focuses on the use of concepts to declare and constrain generic algorithms. Future articles will focus on concept definition and design, another on overloading and specialization, and potentially an article on generic data structure design with concepts.

For those interested in getting started with concepts, information is available at http://asutton.github.io/origin/ . This includes instructions for downloading and installing GCC from source (the implementation was merged into GCC 6.0, which has not yet been released). Note that the Concepts TS does not include library extensions for concepts. Predefined concepts and wrappers around standard facilities are provided by the Origin C++ Libraries. An abbreviated list of those concepts is given in the appendix.

Background

The idea of constraining template arguments is just as old as templates themselves [ Stroustrup94 ]. However, it wasn’t until the early 2000s that work started in earnest on a language design to provide those capabilities. That work culminated in what eventually became known as C++0x concepts [ Gregor06 ]. The development of those features, and their application to the C++ Standard Library were a major focus of the C++ Standards Committee for C++11 [ N2914 ]. However, those features were ultimately removed due to some significant unanswered questions and a looming publication deadline [ Stroustrup09 ].

Work resumed (outside of the C++ Standards Committee) on concepts in 2010. Bjarne Stroustrup and I published a paper discussing how to minimize the number of concepts needed to specify parts of the Standard Library [ Sutton11 ], and a group from Indiana University initiated work on a new C++0x concepts implementation in Clang [ Voufo11 ]. As a result of the rekindled work, we (all of those actively working on concepts), were invited by Alex Stepanov (father of the STL) to take part in a week-long workshop with the goal of specifying all of the concepts needed to fully constrain the STL algorithms, and to suggest a language design that could express those constraints. The result of that work is published in the Palo Alto report [ N3351 ].

When I presented this paper at the C++ Kona 2012 meeting, the committee was cautious about engaging in another large-scale experiment involving concepts. When I left that meeting, I did so with the goal of designing the minimum set of language features that would allow users to constrain templates like we did in N3351. Working with Bjarne Stroustrup and Gabriel Dos Reis, that initial goal evolved into a much more complete language extension called Concepts Lite [ N3701 ].

Around that time, the C++ Standards Committee began using Technical Specifications (TS) to publish extensions to the language and library. This gives the committee the opportunity to gain implementation experience and user feedback before committing to a particular design.At the C++ Bristol 2013 meeting (the week after the ACCU 2013 conference), a work item for a TS on concepts was voted into existence. The Concepts TS [ N4549 ] is the result of that work.

Constraining templates

Let’s start with a generic algorithm that would be typical of something you can find in production today.

  template<typename R, typename T>
  bool in(R const& range, T const& value) {
    for (auto const& x : range)
      if (x == value)
        return true;
    return false;
  }

Ostensibly, this function returns true if value can be found within range . We infer this from the definition because we have some expectations about the behaviour of for loops and equality comparisons. However, it would be better if we had some kind of annotation that expresses kinds of types that we can accept for range and value . Today, we do this using comments, external documentation, naming conventions, or some combination thereof. While that might be helpful for a programmer reading the definition of the function or its reference documents, that documentation is not enforceable by the compiler.

What happens when a developer inevitably misuses the template? Maybe he or she writes something like this:

  vector<string> v { ... };
  in(v, 0);

I tested with both GCC-4.9 and Clang-3.7. They both agree that this use of those arguments with in is incorrect, and they both agree that the reason is because std::string s cannot be compared for equality with integer values. Who knew?

Of course, I had to do a little digging to figure that out. GCC produced 162 lines of diagnostic messages, while Clang produced 57. Errors resulting from the incorrect use of templates are notoriously verbose and can often be quite difficult to parse. This example isn’t especially bad: there’s only one level of instantiation. Getting errors within a stack of deeply nested or even recursive template definitions is not at all uncommon. These kinds of errors tend to discourage the use of templates, especially among students and novice users.

These are two of the problems that concepts are designed to solve. We want to explicitly state requirements on template arguments as part of a template’s declaration, and we want to check those requirements at the point of that template’s use. This allows the algorithm designer to clearly state what is expected, and it allows the compiler to check the use of the algorithm against those expectations. If an error occurs, it can be diagnosed immediately.

Using the concepts TS, we could write the constrained version of the algorithm like this:

  template<typename R, typename T>
    requires Range<R>() 
          && Equality_comparable<T, Value_type<R>>()
  bool in(R const& range, T const& value);

We can use a requires clause to specify constraints. The requires keyword is followed by a constant expression that, when instantiated, determines whether or not the template declaration can be used, or in this case, called.

Range and Equality_comparable are concepts . A concept is a constant expression involving template arguments that we can evaluate at compile time. Here, we use two predicates (functions returning bool s) to say that R must be a Range and that we must be able to compare values of T with the value type of R using == . The definitions of those predicates can be found in the Origin libraries and will discussed in depth in a future article.

Value_type is an alias that names the type of the contained objects. You can think of Value_type<C> as shorthand for typename C::value_type , although in practice, its definition is more complex.

When the in function is used, the compiler checks the requires clause against the deduced template arguments. Compiling the ill-formed example above with the concepts-enabled version of GCC gives the following (note type names have been simplified):

  In function ‘int main()’:
  error: cannot call function ‘bool in(const R&,  const T&) [with R = vector<string>; T = int]’
     in(v, 0);
            ^
  note:   constraints not satisfied
     in(R const& range, T const& value)
     ^
  note:   concept  ‘Equality_comparable<Value_type<vector<string>>,  int>()’ was not satisfied

The error is diagnosed at the point of use – where in is called – and not within its instantiation. The diagnostics clearly indicate the specific failure in the use of the template. Your experience with compiler diagnostics may vary; designing good diagnostics is hard, and the implementation of concepts is still a work in progress. However, any conforming implementation should be able to tell you that you cannot call in with those arguments because the constraints are not satisfied.

The Concepts TS also allows you to constrain class templates, variable templates, alias templates, and template template parameters (of course!). You can attach constraints to member functions and even non-member functions (seriously). Constraints can include predicates with non-type template arguments ( Prime<N> , anybody?) and even template template arguments. However, these topics are outside the scope of this article, and many of them deserve a more thorough treatment than could possibly be given here.

Declaration style

In the example above we first said that we needed two type arguments and then, separately, what we required from those types. However, concepts allow us to state both at the same time. We could have defined in like this:

  template<Range R,
    Equality_comparable<Value_type<R>> T>
  bool in(R const& range, T const& value);

Here, both Range and Equality_comparable<Value_type<R>> declare type parameters. The concept named by each declaration determines the kind (and type) of the declared template parameter. Note that you can use the same notation to declare non-type template parameters, and even variadic templates.

When concepts are used to declare template parameters, the compiler internally transforms these into a requires clause. In fact, this declaration is equivalent to the previous one; the constraints are the same, so they both declare the same function. You can also combine the two notations. Here is another way of declaring the function in .

  template<Range R, typename T>
    requires Equality_comparable<T, Value_type<R>>
  bool in(R const& range, T const& value);

The Concepts TS defines other ways that you can declare this function, which will be introduced in subsequent articles.

The Concepts TS supports multiple notations for the declaration of constrained templates in order to provide flexibility in their presentation, and to improve readability and writability. Not all templates need a requires clause, but many do. If we had only added a requires clause, declarations would necessarily become more verbose. If we had only added a terse syntax, we would not be able to fully express the constraints for every template. As a result, the syntax allows a variety of expressions, allowing a developer to judge for themselves what is appropriate in their work.

Programming with placeholders

The overarching goal of the Concepts TS is to improve support for generic programming, and ‘generic’ is starting to show up everywhere in our source code. How many times have you written something like this?

  for (auto iter = c.begin(); iter != c.end();    ++iter)
    // Do stuff...

Or like this?

  for (auto const& x : c)
    // Do stuff

These examples don’t appear to be generic (where’s the template?), and yet they are. The types of iter and x depend entirely on the type of c ; auto simply acts as a placeholder for the deduced type of those variables. When you’re trying to read the code, the resolution of that placeholder doesn’t actually matter. On the surface, the iter and x have generic type.

One of the criticisms that I often hear about auto is that it hides information in the source text, and that the deduction rules can sometimes give unexpected errors or behaviours [ Orr13 ]. In order to know what iter and x are, and how to use them correctly, we need to look at the declaration of c and understand the rules of type deduction.

One of the arguments for using auto is that it improves encapsulation by hiding type details [ Sutter12 ]. Essentially, it helps you to write against the interface of the c such that changes to the definition of c ’s type (or associated types) may not require changes to these for loops.

The Concepts TS provides two related features. First, it allows the use of a concept in place of auto . This is important. It allows us to gain the benefits of type deduction without the total loss of information. Contrast these examples with the ones above:

  for (Pointer iter = c.begin(); iter != c.end();
    ++iter)
    // Do stuff

  for (String const& x : c)
    // Do stuff

Here, Pointer and String are concepts, and they introduce placeholder types (just like auto ). The deduced type is required to satisfy that constraint. That means, for example, that iter ’s type is required to have the ‘shape’ T* , for some T .

The second thing that the Concepts TS does is to allow placeholders nearly everywhere. For example, we can write declarations like this.

  tuple<Number, String> t = make_tuple(0, "abc"s);

Number and String are concept names and therefore introduce placeholders. Here, the type of t is ultimately deduced as tuple<int, string> . The reason that we included this feature is that it more precisely allows us to specify the shape of a type. Here, we might not want a specific tuple , and we don’t want any old tuple . We want one whose first element is numeric and whose second is a type of string.

The concepts TS also allows the use of placeholders in function parameters. We could declare sort like this:

  void sort(Sortable_container& c);

This declares sort to be a function template with a single template parameter, and an associated constraint. It is equivalent to writing this:

  template<Sortable_container C>
  void sort(C& c);

Which is of course equivalent to this:

  template<typename C>
    requires Sortable_container<C>()
  void sort(C& c);

This particular extension of the language has been somewhat controversial. Some say, “ it isn’t easy to tell if the declaration is a template or not ”. But I don’t think that matters too much. Developers tend not to look at actual declarations. If you’ve ever tried to read a Standard Library implementation, you will immediately understand why. Declarations often turn out to be macros, templates, or overloaded sets of functions. What’s ultimately important about a declaration (or set of declarations) is how they can be used.

Supporting multiple styles of declaration of constrained templates allows flexibility in presentation. For simple generic functions, this use of placeholders is ideal. I can think of no more effective or elegant way to declare sort than the first declaration above.

However, this notation is not suitable for every template declaration. Many templates involve multiple template parameters and need more complex requirements to fully describe their interactions. Bjarne Stroustrup refers to this as the onion principle . As he puts it, “ the more layers you peel off, the more complicated things you can do, and the more you cry ” [ Stroustrup15 ].

The use of concept names as placeholders allows us to write our programs almost entirely in terms of abstract data types. I admit that I am excited to see the impact these features will have on the way C++ is written and taught.

Defining templates

While library developers have always had to consider a template’s constraints, the language has not provided a means of enforcing them. Concepts gives us the means to enforce those constraints and a framework for thinking about them in a more concrete way. That said, adding constraints to a template declaration does not change the way that you write its definition. The concepts TS makes no changes to lookup rules (for better or worse), and there are no extra language rules or restrictions that apply to the definition of constrained templates.

When considering a template’s constraints, we must select concepts that reflect coherent abstractions used within the algorithm. A concept is not simply the minimal set of requirements for a particular implementation of a particular algorithm, but a fundamental building block for our thinking and our code. The in algorithm requires two such building blocks: ranges and equality comparison.

A range type is any type that can be used in a range-based for loop. That is, every range r must provide the operations begin(r) and end(r) . Equality comparison requires the use of == and != . Even though != is not used by the in algorithm, it is nonetheless required. The building block of the algorithm is equality, not the set of expressions used in its implementation.

An implementation should use only the operations and types that are required of its arguments. Otherwise, we will get the same kinds of template errors that we have always gotten. However, this rule is not enforced by the Concepts TS. What if, at some point, we added some ad hoc debugging code to our algorithm?

  template<Range R,  Equality_comparable<Value_type<R>> T> 
  bool in(Range const& range, T const& value) {
    for (auto const& x : range) {
      cout << x << '\n';
      if (x == value)
        return true;
    }
    return false;
  }

Should we update the requirements? Doing so would almost certainly break existing code.

In the Concepts TS, it doesn’t matter that streaming values of T is not part of the building blocks of the algorithm. However, if you supply a range of some non-streamable type, your program will fail to compile, and you will get the usual, lengthy template error messages.

Checking template definitions against their requirements would be useful, but we shouldn’t do so at the expense of useful facilities such as debugging output, logging, timing, and statistics gathering. We are currently thinking about how best to support template definition checking.

Conclusions

The Concepts TS offers a number of improvements to better support generic programming. The ability to clearly and concisely state the constraints on template arguments and the abstractions of placeholders greatly improve the language’s readability and usability. However, the features presented here only just scratch the surface. Concepts will fundamentally change the way that generic libraries are designed, implemented, and used. They will change how generic programming is taught. Concepts are a big deal, and this does change everything.

Acknowledgments

The design of the features in the Concepts TS was the result of collaboration with Bjarne Stroustrup and Gabriel Dos Reis. That material is based upon work supported by the National Science Foundation under Grant No. ACI-1148461. Bjarne Stroustrup also provided valuable feedback on an early draft of this paper.

Jason Merrill is responsible for merging the Concepts implementation into GCC, and has improved its usability significantly. Ville Voutilainen and Braden Obrzut have also contributed to the implementation.

The WG21 Core Working group spent many, many hours over several meetings and teleconferences reviewing the Concepts TS design and wording. This work would not have been possible without their patience and attention to detail. Many people have submitted pull requests to the TS or emailed me separately to describe issues or suggest solutions. I am grateful for their contributions.

References

[GCC] http://www.gcc.org

[Gregor06] D. Gregor, J. Järvi, J. Siek, B. Stroustrup, G. Dos Reis, and A. Lumsdaine. ‘Concepts: Linguistic support for generic programming in C++’. In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’06), pages 291–310, Portland, Oregon, 22-26 Oct 2006.

[Niebler15] Niebler, E (ericniebler). ‘The Concepts TS was voted out today! Concepts are (almost) an ISO standard. Congrats, A. Sutton. This will change everything.’ 20 Jul 2015. Tweet.

[N2914] Becker, P. (ed). Working Draft, Standard for Programming Language C++. ISO/IEC WG21 N2914, Jun 2009.

[N3351] Stroustrup, B., Sutton, A. (eds). A Concept Design for the STL. ISO/IEC WG21 N3351, Feb 2012.

[N3701] Sutton, A., Stroustrup, B., Dos Reis, G., Concepts Lite. ISO/IEC WG21 N3701, Jun 2013.

[N4549] Sutton, Andrew (ed). ISO/IEC Technical Specification 19217. Programming Languages – C++ Extensions for Concepts, Aug 2015.

[Orr13] Orr, R., ‘Auto – a necessary evil (Part 2)’, Overload , vol. 116, Aug 2013.

[Sutton11] Sutton, A. and Stroustrup, B. ‘Design of concept libraries for C++. In Proceedings of Software Language Engineering (SLE’11). 3–4 Jul, 2011.

[Sutter12] Sutter, H. ‘GotW #94 Solution: AAA Style (Almost Always Auto)’. Blog post. 12 Aug 2013.

[Stroustrup94] B. Stroustrup. The Design and Evolution of C++ . Addison-Wesley, 1994.

[Stroustrup09] B. Stroustrup. ‘No ‘Concepts’ in C++0x’. ACCU Overload vol. 92. Aug 2009.

[Stroustrup15] Personal communication, 30 August 2015.

[Voufo11] Larisse Voufo, Marcin Zalewski, and Andrew Lumsdaine. ConceptClang: an implementation of C++ concepts in Clang. In Proc. 7th ACM SIGPLAN Workshop on Generic Programming (WGP'11), pages 71-82, 2011.

Appendix: Origin concepts

The following is a brief list of concepts provided by the Origin C++ Libraries and their requirements. Note that this is not intended to be an exhaustive list. These are based on the concepts defined in the Palo Alto TR [ N3351 ].

Foundational concepts

These are the base concepts that reflect the value-semantic style of modern C++. They establish the basic requirements for construction, comparison, and the semantic foundation needed to support logical reasoning about programs.

• Movable<T> – Requires a type that can be both move constructed and assigned from an rvalue of type T .
• Copyable<T> – Requires a type that can be both copy constructed and assigned from an rvalue of type T . All copyable types must also be movable.
• Equality_comparable<T> – requires a type that can be compared using == and != .
• Totally_ordered<T> – Requires a type that can be compared using < , > , <= , and >= . Totally ordered types must also be equality comparable.
• Equality_comparable<T, U> – Requires the equality comparison of values of type T and type U .
• Totally_ordered<T, U> – Requires the total ordering of values of type T and type U .
• Semiregular<T> – Requires a copyable type that can be default constructed.
• Regular<T> – Requires a semiregular type that is also equality comparable.
• Ordered<T> – Requires a regular type that is also totally ordered.

Functions

The function concepts in Origin are variadic concepts. The first template argument is the type of the callable object: either a function pointer, function object type, or a lambda closure type. The remaining template arguments are the types of the function arguments that the function type must accept.

• Function<F, Args...> – Requires a type F that can be called with the argument types in Args .... The return type is unspecified.
• Predicate<P, Args...> – Requires a function P that can be called with the argument types in Args ... and returns bool .
• Relation<P, T> – Requires a binary predicate P that takes arguments of type T .
• Unary_operation<F, T> – Requires a function F that takes an argument of type T and has a return type of T .
• Binary_operation<F, T> – Requires a function F that takes two arguments of type T and has a return type of T .

Iterators and ranges

The iterator category is essentially the same as that in C++. All iterator types can be dereferenced and incremented.

• Input_iterator<I> – Requires an iterator type that can be used in single pass algorithms, and dereferencing can be used to read the iterator’s value type.
• Output_iterator<I, T> – Requires an iterator type that can be used in single pass algorithms and values of type T can be assigned through its dereferenced result.
• Forward_iterator<I> – Requires an input iterator that can be used in algorithms requiring multiple passes over a range of values, or that require multiple simultaneous references to values in a range.
• Bidirectional_iterator<I, T> – Requires a forward iterator that can also be decremented.
• Random_access_iterator<I, T> – Requires a bidirectional iterator that supports constant time random access.
• Range<R> – Requires a type that can work with a range-based for loop.