Boost logo

Boost :

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-04-11 12:45:11

On Apr 10, 2006, at 4:35 PM, Paul Mensonides wrote:
> Doug, is there an up-to-date paper on concepts?

I'm basing my comments on the most recent "Indiana" proposal for
concepts, described in committee paper N1849:

However, we are busy working on a new proposal for concepts that
should be available in the near future. The new proposal will have
different syntax in several places and should have greatly improved

> Imagine a world where either 1) copious amounts of implementation
> detail bubbles
> up the hierarchy of concept requirements,

This claim has been made before, but has yet to be proven. With
concepts, your templates need to require what they use, e.g., if you
want to treat some type "Iter" as an Input Iterator in your
implementation, you have to say that in the interface. Otherwise, you
don't get the benefits of separate type checking for templates. We've
looked at a few examples that others have had where implementation
details bubble up, but they were all either due to misunderstanding
of how concepts worked or very poor abstractions. Did you have a
particular example in mind?

> 2) the 2-megabyte error messages we
> get now are replaced with 2-megabyte error messages of concept
> failures deep in
> the hierarchy of concept requirements,

The 2MB error messages we get today are mostly due to the need to
include the instantiation context with the message. We get something
that says "no operator< for x < y", which shows up in some
implementation detail function __introsort_loop(), called from
__introsort(), called from __sort(), called from sort(), called from
<where the user actually made the mistake>. Each of these functions
needs to also have the list of template arguments it was given.
That's a lot of text.

Concepts provide separate type-checking, so the error will show up in
one of two places:

        1) In the definition of __introsort_loop(), before it is
instantiated, if there is no suitable operator<. No instantiation
stack needed, because there's no instantiation yet.

        2) In the user code, where the user actually made the mistake. This
error will say that the requirement for, e.g., LessThanComparable is
not satisfied by the types involved. No instantiation stack needed,
because we haven't tried to instantiate sort().

To try to make this description a little more "real", I've appended
the output of both GCC and ConceptGCC when trying to compile this
simple program:

   list<int> l;
   sort(l.begin(), l.end());

> or 3) ad-hoc polymorphism, the greatest
> strength of the template mechanism in C++, is simply dropped in
> favor of, at
> best, non-extensible lists of alternatives.

Concepts (and Generic Programming itself) have always been about
extensibility and avoiding lock-in.
Let's take the trivial example of a min() function and examine it's
use with and without concepts. Without concepts, it looks like this:

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

You can instantiate min() with any type U so long as there is a <
operator that can compare two U's. The compiler does this by
substituting U for T throughout the body of the template, and then
looking up the < operator for two U's.

With concepts, one would create a LessThanComparable concept and use
that within the declaration of min():

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

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

You can instantiate min() with any type U so long as there is a <
operator that can compare two U's. There are some subtle differences
(i.e., the concept-based min() has been fully type-checked at
definition time), but the use of min() will be the same either way.

However, concepts give you more flexibility. For instance, let's
assume that we want to use min() on our Employee type but we don't
want to add a global operator< for Employees. Without concepts, we
would need to write some kind of adaptor class to use when calling min
(): it would wrap up a reference to an Employee, provide some
alternative definition of operator<, and then probably convert to an
Employee reference. Each time we use min(), we need to remember to
construct this adaptor. The end result looks something like this:

class Employee { ... string id; ... };

class employee_with_less_than {
   employee_with_less_than(const Employee& e) : e(e) { }
   operator const Employee& () const { return e; }
   const Employee& e;

bool operator<(employee_with_less_than x, employee_with_less_than y) {
   return <;

void f(Employee e1, Employee e2) {
   min(employee_with_less_than(e1), employee_with_less_than(e2));

Concepts allow one to adapt syntax through the use of "concept
maps" (called "models" in N1849). Concept maps mean that you never
have to match the exact syntax required by a concept, because you can
tell the compiler how your types meet the requirements of a concept.
For instance:

concept_map LessThanComparable<Employee> {
   bool operator<(Employee x, Employee y) {
     return <;

void f(Employee e1, Employee e2) {
   min(e1, e2); // Okay, uses LessThanComparable<Employee>::operator<

Concept maps can be templates, too, which allows you to adapt an
entire class of types to a concept. For instance, every vector<T> can
be made into a Stack; every type that meets the requirements of a
Front Insertion Sequence and a Back Insertion Sequence can be made
into a Queue, and every type that is a Weighted Graph can be made
into a Matrix.

> IOW, I've yet to see a concept mechanism that could even be used to
> implement
> the STL (about the simplest possible example) with the same degree of
> extensibility that we have now. Maybe a concept mechanism can be
> designed that
> minimizes how much extensibility is lost, but either way, it's
> hardly the
> all-around-win-scenario that you're implying above.

We immediately rejected any design that could not express the STL.
The appendix of N1849 contains many examples illustrating how the STL
can be expressed with our concept proposal. These aren't straw men or
guesses or wishes: they were copied directly out of the
implementation of the Standard Library in ConceptGCC, and they work
as expected.

I am fully aware that I sound like a raving lunatic, claiming to fix
all of the current problems with templates. ConceptGCC implements
enough of the Indiana concepts proposal to express most of the STL,
from the simplest concept like CopyConstructible all the way to proxy-
laden InputIterators. We know how to express the rest of the STL, and
much of the non-STL Standard Library, using concepts, and have also
looked at expressing concepts from other libraries (e.g.,
Boost.Graph, Boost.Function). What we've found is that we can improve
the quality of template libraries (by catching bugs earlier; we've
found several in libstdc++), their usability (with shorter/better
error messages), and their composability (by allowing syntax

> Perhaps my understanding is out-of-date. If so, corrections are
> welcome.
> However, my opinion (watching this from the very beginning) is that
> concepts are
> fundamentally at odds with ad-hoc polymorphism and second-phase
> lookup. In
> order to do it, you have to make significant concessions in those
> two areas--and
> I doubt this has changed.

There are always tradeoffs when introducing a type system into an
untyped language. The question is whether one can express all of the
interesting and useful constructs within the type system. If there's
some useful construct that you are concerned might not be expressible
with concepts, please give us an example and we'll discuss it.

You can try out concepts today with ConceptGCC and/or read N1849 to
learn about some of the details of concepts. In the near future,
we'll have a revised proposal (with new concept syntax) and an
improved version of ConceptGCC that implements the revised proposal.
If you're itching to learn about concepts now, I suggest starting
with the ConceptGCC tutorial and compiler at:

When we have the revised compiler/proposal available, I'll make an
announcement here on Boost.


Sorting list iterators with GCC:

/usr/include/c++/4.0.0/bits/stl_algo.h: In function 'void std::sort
sIterator, _RandomAccessIterator) [with _RandomAccessIterator =
sort_list.cpp:8: instantiated from here
/usr/include/c++/4.0.0/bits/stl_algo.h:2570: error: no match for
'operator-' in
'__last - __first'
/usr/include/c++/4.0.0/bits/stl_algo.h: In function 'void
_sort(_RandomAccessIterator, _RandomAccessIterator) [with
= std::_List_iterator<int>]':
/usr/include/c++/4.0.0/bits/stl_algo.h:2571: instantiated from
'void std::sort
(_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = std
sort_list.cpp:8: instantiated from here
/usr/include/c++/4.0.0/bits/stl_algo.h:2214: error: no match for
'operator-' in
'__last - __first'
/usr/include/c++/4.0.0/bits/stl_algo.h:2216: error: no match for
'operator+' in
'__first + _S_threshold'
/usr/include/c++/4.0.0/bits/stl_algo.h:2217: error: no match for
'operator+' in
'__first + _S_threshold'
/usr/include/c++/4.0.0/bits/stl_algo.h: In function 'void
_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = std:
/usr/include/c++/4.0.0/bits/stl_algo.h:2220: instantiated from
'void std::__fi
nal_insertion_sort(_RandomAccessIterator, _RandomAccessIterator)
[with _RandomAc
cessIterator = std::_List_iterator<int>]'
/usr/include/c++/4.0.0/bits/stl_algo.h:2571: instantiated from
'void std::sort
(_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = std
sort_list.cpp:8: instantiated from here
/usr/include/c++/4.0.0/bits/stl_algo.h:2130: error: no match for
'operator+' in
'__first + 1'
/usr/include/c++/4.0.0/bits/stl_algo.h:2220: instantiated from
'void std::__fi
nal_insertion_sort(_RandomAccessIterator, _RandomAccessIterator)
[with _RandomAc
cessIterator = std::_List_iterator<int>]'
/usr/include/c++/4.0.0/bits/stl_algo.h:2571: instantiated from
'void std::sort
(_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = std
sort_list.cpp:8: instantiated from here
/usr/include/c++/4.0.0/bits/stl_algo.h:2136: error: no match for
'operator+' in
'__i + 1'

Sorting list iterators with ConceptGCC:

sort_list.cpp: In function 'int main()':
sort_list.cpp:8: error: no matching function for call to 'sort
or<int>, std::_List_iterator<int>)'
e/c++/4.0.1/bits/stl_algo.h:2843: note: candidates are: void std::sort
(_Iter, _I
ter) [with _Iter = std::_List_iterator<int>] <where clause>
sort_list.cpp:8: note: unsatisfied model requirement
Iterator<std::_List_iterator<int> >'

Boost list run by bdawes at, gregod at, cpdaniel at, john at