Re: [boost] Report from Berlin C++ Standards Committee meeting

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:

        http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1849.pdf

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  
presentation.

> 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 {
public:
   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 x.e.id < y.e.id;
}

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 x.id < y.id;
   }
};

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  
adaptation).

> 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:

        http://www.osl.iu.edu/~dgregor/ConceptGCC/

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

        Doug

Sorting list iterators with GCC:

/usr/include/c++/4.0.0/bits/stl_algo.h: In function 'void std::sort 
(_RandomAcces
sIterator, _RandomAccessIterator) [with _RandomAccessIterator =  
std::_List_itera
tor<int>]':
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  
std::__final_insertion
_sort(_RandomAccessIterator, _RandomAccessIterator) [with  
_RandomAccessIterator
= 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
::_List_iterator<int>]'
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  
std::__insertion_sort(
_RandomAccessIterator, _RandomAccessIterator) [with  
_RandomAccessIterator = std:
:_List_iterator<int>]':
/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
::_List_iterator<int>]'
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
::_List_iterator<int>]'
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 
(std::_List_iterat
or<int>, std::_List_iterator<int>)'
/usr/local/conceptgcc/lib/gcc/powerpc-apple- 
darwin8.2.0/4.0.1/../../../../includ
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  
'std::MutableRandomAccess
Iterator<std::_List_iterator<int> >'