In a previous article, Dave classified the uses of concepts into Three Kinds of Concepts: syntactic concepts that merely describe syntax (without any semantics), foundational concepts that have a universally agreed-upon syntax and semantics, and non-trivial concepts that have a higher complexity than the other concepts and are generally domain- or application-specific.
Next, we’ll classify the different kinds of concept maps according to their intended purpose. Where a concept is a set of type requirements, a concept map says how a type (or set of types) satisfy those requirements, and although there are three kinds of concepts and three kinds of concept maps, there is no one-to-one mapping between them. The kind of concept map used depends not only on the concept, but on its relationship with the mapped type(s). Let’s dig in!
Intentional Mapping
Intentional concept maps occur when a programmer designs a class with
the goal of modeling a particular concept. For example, I might design
a new iterator type (call it MyIter) to model BidirectionalIterator,
so that I can use MyIter with algorithms like std::inplace_merge or
adaptors like std::reverse_iterator. To make MyIter work properly, I would
need to be sure that its interface meets all of the requirements of
BidirectionalIterator.
To do that, I’d use a concept map:
concept_map BidirectionalIterator<MyIter> { /* ... */ }
Here I am stating that MyIter is a BidirectionalIterator, which
has two effects at the language level:
The compiler checks
MyIterimmediately for structural (as opposed to semantic) conformance to theBidirectionalIteratorrequirements.MyItercan now be used where aBidirectionalIteratoris required. SinceBidirectionalIteratoris not anautoconcept,MyIterwould not be treated as a model on the basis of structural conformance alone.
It has several equally-important effects at the design level:
It documents that
MyIteris-aBidirectionalIterator. IfMyIteris to be used as aBidirectionalIteratorby other (people’s) code, this relationship must be more than mere fallout ofMyIter‘s implementation: it must documented somewhere. Otherwise, there’s no assurance that it won’t change without warning. By placing the documentation in the code, we’ve made it easy to find for programmers who will work with and maintainMyIterin the future. We also make it easy for other tools (say, a concepts-capable Doxygen) to translate this statement into a reference manual.It makes sure that future changes to
MyIter(or to the structure of iterator concepts) do not silently break the relationship betweenMyIterandBidirectionalIterator.It gives me a place, in the concept map’s body, to define operations specific to
MyIter‘s role as aBidirectionalIterator.
Concept maps are useful both when originally designing a data type (to
ensure that its interface is correct), and to provide “documentation
with teeth” that ensures that that interface is not broken by future
changes. Note that the most of the reasons for intentionally writing
concept maps have nothing to do with whether or not the concept itself
is auto.
Post-hoc Mapping
A type is mapped to a concept post-hoc when the type’s creator had no specific intention to model the concept in question. Post-hoc mapping often occurs during library composition,1 when existing data types need to be matched up with concepts from a different library to use the facilities of that library. This is a particularly important use case for concept maps, because post-hoc mapping allows built-in and 3rd-party types to model both auto and non-auto concepts without changing either the type itself or the concept.
There are two different kinds of post-hoc concept maps: trivial maps and adaptive maps.
Trivial Post-hoc Mapping
A trivial mapping is used when the syntax of the data type already happens to meet the syntactic requirements of the concept. In this case, the concept map itself has an empty body. Trivial mapping tends to occur when there is already an established syntactic form, but the corresponding C++ concept hasn’t been declared or is not yet widely known.
Trivial concept maps may seem, well, trivial, but since trivial concept maps were a major factor in the failure to reach consensus on concept support for C++0x, they deserve closer examination. We will definitely be looking further into the origins of trivial concept maps in the next installment of this series. For now, though, let’s move on to our last kind of concept mapping.
Adaptive Post-hoc Mapping
Adaptive mapping is used when a data type meets the requirements of a concept, but with a different syntax.2 For example, one can use adaptive mapping to represent the edge connectivity of a graph using the nonzero elements of a sparse matrix (a technique used in efficiently solving systems of equations), or to form an iterator over consecutive integers using an actual int:
concept_map RandomAccessIterator<int> { int const& operator*(int const& x) { return x; } int operator[](int const& x, std::size_t n) { return x + n; } // int already supplies the other operations };
An adaptive concept map is always explicitly written, since the concept map itself must provide the mapping from the syntax expected by the concept over to the operations that the data type actually provides: neither the concept nor the data type itself will change.
Adaptive post-hoc concept mapping is the most powerful of the kinds of
concept maps, because it can be used to smooth over the syntactic
differences between separately-developed libraries. It can also be used
to establish relationships between different concepts. For example, we
can state that every BackInsertionSequence is also a Stack:
template<BackInsertionSequence Cont> concept_map Stack<Cont> { typedef Cont::value_type value_type; void push(Cont &c, const Cont::value_type &x) { c.push_back(x); } void pop(Cont &c) { c.pop_back(); } value_type &top(Cont &c) { return c.back(); } bool empty(const Cont &c) { return c.empty(); } }
Concept Map Recap
Not all concept maps are created equal or written for the same reasons. Here we have classified the different kinds of concept maps into three categories: intentional concept maps, which specify that a type is designed to meet the requirements of a specific concept; trivial post-hoc concept maps, which note that a type happens to meet the requirements of a concept it wasn’t originally designed for; and adaptive post-hoc concept maps, which provide a syntactic bridge between separately-developed types and concepts. In our next article in this series, we’ll explore the interactions between the different kinds of concepts and concept maps.
// ----- File: Point.hpp ------ // Declare a Point class with the intention that it // model EqualityComparable struct Point { double x, y; }; // Supply the operations that make Point EqualityComparable concept_map EqualityComparable<Point> { bool operator==(Point a, Point b) { return a.x == b.x && a.y == b.y; } } |
-
Strictly speaking, library composition is when you take two (or more!) separately-developed libraries and use their components together, but this phenomenon isn’t really specific to libraries. The same thing happens when using different parts of an application together, or bringing a new library into an application, since most applications are really made up of a set of domain-specific libraries tied together with a common user interface. Concept maps are important for library composition regardless of whether the library has been separately packaged and stamped as an official library. ↩
-
Adaptive maps can also be used intentionally, to supply a model’s operations in a way that explicitly associates them with their role in fulfilling certain concept requirements: ↩
- Three Kinds of Concepts
- Three Kinds of Concept Maps
- To Auto or Not? That is the Question
Regarding the Stack example:
template<BackInsertionSequence Cont> concept_map Stack<Cont> {/*...*/}It seams there are two ways of saying that every instance of concept A is also an instance of concept B: one is the concept map as you describe; the other is concept refinement. Would concept-based function overloading work for the concept_map way too? I.e. if I have two function overloads: one for
BackInsertionSequenceand one forStackand I call it forvector:Will the compiler prefer either overload, or will I have an ambiguity?
Great question; that would be ambiguous.
A data type may meet requirements of a concept in more than one way. For example int can be made into a Monoid with + and 0 as identity, or with * and 1. Is this possible for such concept maps to coexist in a single program, and how can I control which one is picked by a code that uses given concept?
Hi Robert,
Yes, such concept maps can coexist in a single program. During the development of the concepts proposal, I wrote the following paper to argue in favor of this, using the term “scoped concept maps”.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2098.pdf
Subsequently, this idea was accepted and incorporated into the draft standard.
The way for such concept maps to coexist is for them to be defined in separate namespaces. To control which concept map is used, you can choose to import one or the other of the concept maps from its namespace (there’s a new kind of using directive for concept maps).
The standardese for scoped concept maps is available in the following paper:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2414.pdf
Hi, It was said that in the concept map we only list members that are not structurally identical to that of the concept. Why then the following definition in the concept_map Stack example:
typedef Cont::value_type value_type;
Regards.
That definition is there for exposition purposes, to call out the relationship between the value_type of ‘Cont’ when viewed as a BackInsertionContainer vs. when ‘Cont’ is viewed as a Stack. The definition is technically redundant, since
Cont::value_typeis just a shorthand forBackInsertionContaienr<Cont>::value_type.I am not sure I understand. Do you mean that omitting the typedef will work, like that:
template<BackInsertionSequence Cont> concept_map Stack<Cont> { void push(Cont &c, const value_type &x) { c.push_back(x); } ... }I thought that only by writing the concept map, I already state that if
Contwhich is anyBackInsertionSequencehas member typedefvalue_type(which it always does), andStack‘s concept requires the member typedef of the same name. The two should be matched automatically.Why isn’t BidirectionalIterator auto concept ? specifically, BidirectionalIterator does not have problem like ForwardIterator and InputIterator. By not making it auto concept, we have to write concept_map with empty body since I already make my iterator class conform structurally (thus there is nothing to map).
I personally like N2906, since it clarifies the role of concept and concept map. I personally dislike having to write concept map if I know that certain type already conform both structurally and semantically to a concept. I think writing concept map should be reserved to a situation where there are concepts that has same syntactical requirement but different semantic requirement, and I think those kind of concepts are rare. By making concept not auto by default, I believe we choose the wrong default.
I defer to Doug on the actual reasons, since he wrote the wording, but I can give you my opinion: because it doesn’t need to be, and it wouldn’t buy you much.
In principle, it does. A ForwardIterator could masquerade as a BidirectionalIterator in exactly the same way as InputIterators often masquerade as ForwardIterators. In practice, it’s less likely to be an issue with BidirectionalIterator, since it is syntactically more distinguished from ForwardIterator than ForwardIterator is from InputIterator. But it’s just a question of degree.
I have two questions:
iterator_categorytypedef?Can you explain in what way it clarifies those roles? Is that experience of clarification due to the changes N2906 would make to those roles, or simply to the paper’s explanatory text? If the former, how did the specification sans-N2906 changes make those roles unclear?
Okay, here’s where this article is relevant. Are you talking about trivial post-hoc mapping now?
Are you saying that concept maps should never be used in other situations, or that you should never be forced to write concept maps in other situations, or something else?
I assume you’re just ignoring post-hoc adaptive mapping now, because if you ever want to do that, you need a concept map,
autoconcept or not.That is the argument made by N2906.1 It’s an easy argument to understand. The basis of countervailing arguments is much more subtle, and requires careful analysis of the different ways in which concepts and concept maps are used. That’s why we’re running this article series. Once you look at the issue with awareness of these distinctions, I think the imperative to make concepts
autoby default is far less compelling, but we need one more article to finish laying that groundwork. Of course, by the end, you may still think concepts should beautoby default, and that’s fine. In the meantime, I encourage you to try thinking about the issue in terms of the concept and concept map classifications we’ve laid out, and see if it changes anything for you.N2906 suggests a much more radical remedy than changing the default, though, by proposing that non-
autoconcepts be eliminated altogether. That said, by introducing explicit refinement, it would allow the creation of something that acts exactly like a non-autoconcept, so it’s hard for me to see the point of that change. ↩sorry for late reply, I have been in a place where Internet connection is privileged (and I am not priviledged
)
Yes, My entire comment is about trivial post-hoc mapping. sorry for not being clear earlier.
you said : “A ForwardIterator could masquerade as a BidirectionalIterator in exactly the same way as InputIterators often masquerade as ForwardIterators. In practice, it’s less likely to be an issue with BidirectionalIterator, since it is syntactically more distinguished from ForwardIterator than ForwardIterator is from InputIterator. But it’s just a question of degree.”
My reply is : I may defer this to my reply to Mr.Gregor reply, but can you give me your version about the expanded version of this statement, especially I do not understand about ForwardIterator masquerading as BidirectionalIterator, since both concept can be differentiated syntactically (isn’t it ?).
you said : “I have two questions:
Were you planning to embed an iterator_category typedef? “
Is it enough to have an iterator the required operator/operations (operator ++ , — , *, etc.) to be recognized as BidirectionalIterator? I am aware that it is possible to define types that conform syntactically to BidirectionalIterator Syntactically but does not conform to it semantically. But I am consenting adult, and I am quite willing to take responsibility of my action.
Why do we still need iterator_category typedef if we already have concept ?
you said ” “Can you explain in what way it clarifies those roles? Is that experience of clarification due to the changes N2906 would make to those roles, or simply to the paper’s explanatory text? If the former, how did the specification sans-N2906 changes make those roles unclear?”
My answer: I personally has a little theory, something like this: If there is a type T and a concept C, there are two things that need to be done with T and C
With N2906, the Discrimination Role is primarily the job of type checker and concept declaration. concept_map primary role is adaptation role. This is possible because N2906 makes the default in favor to what we call auto concept. Let’s talk about default later. By not making the default favoring auto concept, we give concept_map much more responsibility to Discrimination role, thus making the role somewhat overlap with type checker.
“Are you saying that concept maps should never be used in other situations, or that you should never be forced to write concept maps in other situations, or something else?”
Why should I state the obvious that a type with operator (++ , –, * ) and has appropriate semantic (which I guarantee myself) is bidirectional iterator. I mean, It’s more work and it’s verbose, right? and more importantly template without concept in principle does not require anything like that.
“I assume you’re just ignoring post-hoc adaptive mapping now, because if you ever want to do that, you need a concept map, auto concept or not.”
I think concept_map in post-hoc adaptive mapping is essential, My question is why we need it in trivial post-hoc mapping (well, not really. I actually ask why something as trivial as BidirectionalIterator is not auto concept, but it come close in spirit).
As additional note, I think N2906 is proposing elimination non-auto concept in the name only, since, as you said, it still possible for us to define something like non-auto concept. However it is achieved by making the refinement explicit, and taking analogy from inheritance, it will require more thought to do that. So, I guess (may be wrong, I do not write N2906) it is all about shifting the default in favor to auto concept.
It potentially has the same problem, since one could easily have a ForwardIterator with an
operator--that doesn’t have the meaning required for it to be a BidirectionalIterator. However, we (as a community) have a lot of experience with the iterators, and such an type is rather unlikely. The BidirectionalIterator concept is so widely used that it’s possible it could be auto and it probably would never matter. However…The decision to make a concept “auto” or not is something that’s generally done when we initially write the concept, before we’ve had the years of experience we have with iterators. Given that the ForwardIterator and InputIterator concepts look syntactically different, I’m willing to bet that many people would have made ForwardIterator “auto”. Then, after a bunch of code was written without concept maps, we’d hit the first istream_iterator instance and we would have a serious problem: ForwardIterator would have to become non-auto and now we have to write a bunch of concept maps to fix existing code. Concepts evolve over time, as we find more models of those concepts (“hey, we can provide iteration through a stream with this interface!”) that change our understanding of existing concepts and introduce new concepts (e.g., putting MultiPassInputIterator between InputIterator and ForwardIterator in the concept hierarchy). Non-auto concepts allow such seamless evolution, because the user has stated their intentions; auto concepts make evolution harder, because we have to guess at the intentions of users.
So, unless you’re dealing with some really simple syntactic concept, I would not make a concept auto.
When you write your iterator class, you already make an explicit statement that your iterator conforms to the BidirectionalIterator concept. It looks like this:
A concept map is the same kind of statement, but a concept map actually has teeth: the compiler will check that assumption, to make sure you got all of the various operators and their variants declared correctly. Once you’ve been able to compile the concept map, you know that you’ve met the syntactic requirements of the concept, and there will be no surprises, either now (“why didn’t it pick the BidirectionalIterator overload over the InputIterator one? I could swear that I implemented all of the requirements of BidirectionalIterator…”) or later (“someone must have tweaked the interface to my iterator type, because now it’s failing to get used as a BidirectionalIterator”).
N2906 presents a different view of concept maps. It views concept maps more as a fix (when syntax doesn’t line up) or as a necessary evil (when we’re forced to use explicit refinement). I have a very different view: I view concept maps as a part of the generic programming process, documenting and enforcing the relationships between the types I write and the concepts they are meant to model.
How do you “know” that a certain type already conforms both structurally and semantically? Aside from the most trivial of concepts, it’s a significant amount of work to make sure that your type meets every single requirement of a particular concept. Testing that type with an algorithm or two doesn’t really help, because not all algorithms use all of the requirements of the concept.
I work on a C++ compiler (written in C++), and I was shocked at how many broken iterator types we had that were in continuous use: we’re missing iterator_category’s and “pointer” types and “difference_type”s and so on, sometimes we have bad return types for
operator++/operator--, etc. These iterator types “work” with some templates, fail with others, etc., because they are wrong even though the author “knew” that the type conforms to the appropriate iterator concept.By writing a concept map, I know that I have met the syntactic requirements of a concept because the compiler has checked that for me. Anything less than that is a guess, and a hedge that things won’t get changed in the future.
“Note that the most of the reasons for intentionally writing concept maps have nothing to do with whether or not the concept itself is auto.”
What is the point of auto concepts then, if they require writing concept maps too?
Auto concepts in and of themselves don’t require writing concept maps, although a concept map might be required by circumstance, e.g. for post-hoc adaptation. Doug is saying that there are good reasons for intentionally writing concept maps regardless of whether they’re required by the language.