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