Concepts Lite: Constraining Templates with Predicates -- Andrew Sutton, Bjarne Stroustrup

During the C++11 standards development cycle, much work was done on a feature called "concepts" which aimed at providing systematic constraints on templates. Concepts was deferred from C++11 for lack of time to complete it, but work has continued.

In January 2012, the results of a major "concepts summit" were published as a 133-page report titled "A Concept Design for the STL" (WG21 paper N3351).

Now, a draft of new paper is available proposing a very useful subset of concepts, dubbed "Concepts Lite", for near-term consideration including at the spring ISO C++ meeting in Bristol, UK, this April. For example, imagine writing this template:

template<Sortable Cont>
void sort(Cont& container);

and when you call it like this:

list<int> lst = ...;   // oops, bidirectional iterators
sort(lst);             // today, results in very long "template spew" error message

getting this short and non-cryptic error message:

error: no matching function for call to ‘sort(list<int>&)’
   sort(l);
         ^
note: candidate is:
note: template<Sortable T> void sort(T)
   void sort(T t) { }
        ^
note: template constraints not satisfied because
note:   'T' is not a/an 'Sortable' type [with T = list<int>] since
note:     'declval<T>()[n]' is not valid syntax

That's an actual error message from the prototype GCC implementation linked below.

We're very excited about this feature and its continued progress. Here are links to the draft of the new paper:

Concepts Lite: Constraining Templates with Predicates (PDF) (Google Docs)

From the Introduction:

In this paper, we introduce template constraints (a.k.a., “concepts lite”), an extension of C++ that allows the use of predicates to constrain template arguments. The proposed feature is minimal, principled, and uncomplicated. Template constraints are applied to enforce the correctness of template use, not the correctness of template definitions. The design of these features is intended to support easy and incremental adoption by users. More precisely, constraints:

  • allow programmers to directly state the requirements of a set of template arguments as part of a template’s interface,
  • support function overloading and class template specialization based on constraints,
  • fundamentally improve diagnostics by checking template arguments in terms of stated intent at the point of use, and
  • do all of this without any runtime overhead or longer compilation times.

This work is implemented as a branch of GCC-4.8 and is available for download at http://concepts.axiomatics.org/~ans/. The implementation includes a compiler and a modified standard library that includes constraints. Note that, as of the time of writing, all major features described in this report have been implemented.

Related links:

Add a Comment

Comments are closed.

Comments (8)

0 0

Ivan Čukić said on Feb 24, 2013 04:08 PM:

The link http://concepts.axiomatics.org/~ans/ doesn't work for the wrong tilde symbol.
0 0

Germán said on Feb 24, 2013 08:09 PM:

The link is not working for me either. By the way, this proposal is really AWESOME. It integrates really well into the language, it finishes many wars of typenames and ::. The code is really readable and understandable. I do hope it's ready for C++14. If later concepts are added on top of that, with axioms and concept checking in variables, as in:


template <Sortable Cont>
void sort(Cont & cont) {
Random_access_iterator q = std::begin(c);
}


Generic programming could become really mainstream and easy. Though, I have a couple of questions:


1. If concepts are added in c++17 (not concepts lite only) as they are being defined, will this enable separate compilation for template functions in some way as with normal functions?
2. What is the relationship between modules and separate compilation? afaik, without separate compilation, templates in modules are going to be difficult. Must separate compilation be fully solved before allowing modules in C++?


P.S. BTW, markdown support would be great in this site when writing.
0 0

Germán said on Feb 24, 2013 09:21 PM:

The link is working again: http://concepts.axiomatics.org/~ans/
0 0

Philipp said on Feb 25, 2013 04:07 AM:

What I'm missing the most is an outline of a clear transition path, should concept maps and checking of template definitions ever be added to the standard.

The proposal is largely an enable_if on steroids baked into the language, including all its short-comings. The worst part of structural matching (identifying a modeled concept by checking the validity of syntax) are the false positives: just because a class has a member function my_type::size() it doesn't necessarily meet the semantic requirements the (imaginary) RandomAccessRange concept imposes and my_type might only be a model of BiDirectionalRange. How do i opt out of has_size<my_type>? I can specialize the trait, but this precludes use of the trait in other libraries where it might be applicable. So, we would end up with a proliferation of traits. I'm already imagining the horror: std::container::has_size, std::range::has_size, lib_a::has_size, lib_a::component_z::has_size and so on. While this might look contrived it is an example from real-code that suffered from the problem of structural matching being to eager. I'm not sure I actually want this to be in the language without concept maps.
0 0

Bjarne Stroustrup said on Feb 26, 2013 06:47 AM:

It is easy to imagine problems with any design. The C++0x concept design evolved into a monster of complexity. We had 130 "concepts" in the library and 70+ pages to describe the language mechanisms. To compare, algebra has on the order of a dozen concepts, and the original C with Classes manual was less than 70 pages. Compilation required heroic efforts.

First and foremost, we had to find a design that was about an order of magnitude simpler to implement and use. We must not simply recreate the mess that was the C++0x standard library "concepts". For our basic design see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf . Alex Stepanov (father of the STL is its primary designer, but just look at the list of participants). A research paper http://www.stroustrup.com/sle2011-concepts.pdf describes the background and rationale.

The proposal has been used to add constraints to the standard library algorithms (which is available). The mess of traits that you mention does not arise.
0 0

Philipp said on Feb 26, 2013 07:45 AM:

Please don't mistake what I've said as outright rejection. I'm aware that the design group consists of people that know what they are doing and I trust they know what makes sense in the language and what does not.

There were certainly too many concepts in the old proposals and the added constraints look good. But how do they map to the actual concepts defined in the library? Seeing an error about Mergable is not going to be helpful if there is no such concept. Also, how many constraints are anticipated for the whole library? Less than the 70 concepts of the old proposal?

A real example where structural matching fails: Assuming a standard container should be a model of Range, deducing that a Range is a RandomAccessRange by looking for a size member function does not work. list defines a constant time size member function even though it would only be a model of BidirectionalRange. There are several work-arounds: traits classes, additionally checking for operator[], or checking the tag of the nested iterator. I would expect to be able to write code without any of the work-arounds from a new language feature. At least the ability to opt-in or out of a constraint would be a good start. But maybe this is already possible with the constexpr syntax and I just don't see how to do it.

I appreciate the effort that is being put into bringing at least some form of concepts into the language despite the setbacks.
0 0

Bjarne Stroustrup said on Feb 26, 2013 01:02 PM:

Quick answer:

(1) See the constrained version of <algorithm> that comes with the implementation. We have mergeable, etc.
(2) The number of concepts should be 20 plus minus 4, depending on how much of of the standard library you count (the 130 count was for the complete C++0x standard library; the STL was about 103).
(3) You obviously can't distinguish Range from Container based on size(); obviously they both have a number of elements. You cannot distinguish two "concepts" that differ only in semantics; don't try to automatically distinguish those. If you want to be able to accept two similar concepts with the same semantics for their overlap, us an "or".

Look at Bjarne Stroustrup, Andrew Sutton, et al., “A Concept Design for the STL” (ISO/IEC JTC1/SC22/WG21 N3351, January 2012) for design principles and B. Stroustrup and A. Sutton: Concept Design for the STL. N3351==12-0041. for an extended example.
0 0

macson_g said on Dec 8, 2014 07:34 AM:

The linked PDF document has broken references. They appear as '??' in the text.