In this article series, we’re trying to understand the consequences of
choosing to make a given concept auto—so the compiler can decide that
types model the concept on the basis of syntactic structure alone—or
non-auto—so types must be explicitly declared to be models, via a
concept_map. In the first two articles, we identified three kinds of
concepts
and three kinds of concept
maps.
Here we’ll discuss the two modes of auto concept failure.
Structural Aliasing
Structural aliasing is the simplest kind of implicit conformance
problem: it occurs when a type meets the syntactic, but not the
semantic requirements of a given auto concept. This sort of thing
tends to happen with the simplest concepts that aren’t purely
syntactic:
the foundational
concepts.
Even if there is widespread agreement that a concept implies a certain
syntax, it’s very common that the syntax has been used for other things.
For example, Chris Jefferson wrote this on a C++ committee mailing list:
I have a type I use regularly where
operator<does not define a [strict weak] ordering (but it defines a very natural operation). On occasion, people have given this type tostd::sort, and expected it to work, instead their program tends to crash in unpredictable ways.
The desire to be protected from such mistakes is consistent with the C++ tradition of protecting against accident rather than deliberate circumvention. 1
What Goes Wrong
To review, a “conceptified” declaration of std::sort might look like
this: 2
template< RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare = less<Iter::value_type> > requires ShuffleIterator<Iter> && CopyConstructible<Compare> void sort(Iter first, Iter last, Compare comp = Compare());
Fig 1. y is incomparable with x and with z, but z<x
When no comparison object is passed, the value_type‘s operator< must
model
StrictWeakOrder,
as with the built-in numeric types. However, it isn’t hard to find a
type whose natural and appropriate “<” relation fails to satisfy the
concept. For example, given two mathematical sets a and b, a<b
usually means “a is a proper subset of b.” The proper subset
relation is a partial (but not
strict weak) ordering because incomparability—the property of
having no defined order—isn’t transitive, as shown by the Venn diagram
in Fig 1. That is,x‖y ∧ y‖z ⇏ x‖z. 3
This is an example of structural aliasing because Chris’ type
satisfies the structural (i.e. syntactic), but not the semantic,
requirements of the sort algorithm.
Fixes
There are basically three known approaches to this problem:
Don’t make simple, foundational concepts
auto. Users must write (empty) concept maps to indicate conformance:class my_type { … }; bool operator<(mytype const& x, mytype const& y); concept_map StrictWeakOrder<std::less<my_type> > {};
Users have always had to be careful. Tell them not to do that. We can’t prevent all misuses.
Allow explicit negative concept maps, so that the author of the type in question can say “it ain’t no strict weak thang:”
class mathematical_set { … }; bool operator<(mathematical_set const& x, mathematical_set const& y) { return x.is_subset(y); } concept_map !StrictWeakOrder<std::less<my_type> > {};
In my opinion, #1 isn’t really an option. Foundational concepts are so commonly modeled that users could be writing lots and lots of empty concept maps, just to avoid a few relatively rare cases of structural aliasing. #2 is at the other extreme, and is nearly as unworkable. It’s only a matter of time before something like this happens:
template <class T> concept Bar { }; template <Bar B> void algo1(B x) { // un-specialized implementation. Does lots of linear searching } template <Bar B> requires StrictWeakOrder<std::less<B> > void algo1(B x) { // optimization that sorts a sequence of B's and uses binary search } template <Bar B> void algo2(B x) { algo1(x); }
The author of algo2 should have every right not to document that he
is calling algo1, and the author of algo1 should be allowed to add
the optimized implementation for StrictWeakOrders without breaking
existing code. This is either a leakage of implementation details or
a modularity hole, depending on which algorithm author you decide to
blame.
Since foundational concepts tend to be well-known, it’s reasonable to expect the author of a type whose syntax mimics that of—but that does not model—a foundational concept to write a negative concept map indicating as much. It would be worthwhile to add the negative concept map feature to C++ to support these cases. For other kinds of concepts, though, there’s not much one can do to fight structural aliasing.
Semantic Refinement
Concepts often turn out to refine other concepts having the same or very
similar syntactic structure, so that the differences between the two
concepts are mostly constraints on behavior rather than on interface.
Unfortunately, it is especially dangerous to to declare these refined
concepts auto because algorithms are commonly specialized to optimize
based on the refinement.
For example, if we know the Callable operation used with
std::accumulate actually models the refined concept Associative, we
can distribute the computation across N cores by breaking the input into
N subranges, accumulating them, and using the operation again to combine
the partial results:
concept Associative<typename F, typename...Args> : Callable<F,Args...> {}; // Serial accumulate template < InputIterator Iter, MoveConstructible T, Callable<auto, const T&, Iter::reference> BinaryOperation > requires HasAssign<T, BinaryOperation::result_type> && CopyConstructible<BinaryOperation> T accumulate(Iter first, Iter last, T init, BinaryOperation binary_op); // optimized parallel version template < ForwardIterator Iter, MoveConstructible T, Associative<auto, const T&, Iter::reference> BinaryOperation > requires HasAssign<T, BinaryOperation::result_type> && CopyConstructible<BinaryOperation> T accumulate(Iter first, Iter last, T init, BinaryOperation binary_op);
As you can see above, Associative adds no syntactic requirements to
those of Callable: it is a purely semantic refinement. If
Associative were declared auto, even calls with non-Associative
operations would be dispatched to the parallel implementation of
accumulate, yielding an incorrect result at runtime. In
general, the manifestation of accidental conformance within a
refinement hierarchy can be any form of undefined behavior—see the
classic problem with InputIterator and ForwardIterator as
detailed in N1798 for a particularly bad example, which would
cause your program to crash—if you were very lucky.
When It Bites
It’s tempting to think, since an auto concept that semantically
refines another concept is so plainly broken, that people will quickly
learn not to make those concepts auto. Nonetheless, it’s pretty easy
not to notice you’ve made this mistake. By definition, the problem
can’t be caught at compile-time. You can’t always see it by casual
inspection: as in N1798 a semantic refinement can add a few
trivial syntactic requirements, so the more-refined concept won’t have
an empty body. To notice it in testing,
you have to pass a model of the less-refined concept to an algorithm that—like our
accumulateexample above—has been specialized for the more-refined onethat specialization has to give the wrong result, and
that result has to be checked by the test.
So it looks like this problem stands a very good chance of slipping into shipped code.
Also, because they don’t work well in all refinement relationships,
auto concepts can pose an obstacle to code evolution. Once you
release an auto concept into the wild, you have to hope you don’t
discover later that it refines some very similar concept, and in general
this kind of discovery is not unusual. An analogous event occurs in the
OOP world when a class aquires a new base during OOP refactoring, if
all or nearly all of the class’ interface ends up in the base class.
In fact, these kinds of refinements are extremely common
among—that’s right—foundational concepts. 4 So even though
foundational concepts should ideally be auto, one must be very sure
that the domain has been fully-explored so that these concepts won’t be
discovered, later, to semantically refine others. In fact, if you look
back at Chris Jefferson’s example, you’ll see that it also
exhibits semantic refinement—a StrictWeakOrder is-a PartialOrder,
both of which are foundational concepts. That refinement relationship
simply didn’t make any difference in his case because he didn’t use his
type with an algorithm that could accept a PartialOrder but was
optimized for StrictWeakOrder.
Next Up
In the next article of this series, we’ll wrap up with an analysis of
the ways that generic code evolves, how often certain kinds of concepts
and maps will be needed, who will write them, and a sober look at the
actual user burden of the empty concept maps that will sometimes be
needed for non-auto concepts. See you soon!
-
Bjarne Stroustrup, The C++ Programming Language, Special Edition, section 10.2.2, page 226 ↩
-
See Douglas Gregor, Unifying Operator and Function-Object Variants of Standard Library Algorithms Document number N2743=08-0253 ↩
-
Technically, C++ pointers have the same property. Pointers into distinct arrays can’t be compared with “<,” so if you point x and z into one array and y into another, we have the same relationship. Fortunately,
std::lessis there to make the comparisons legal and give us a total ordering of all pointers that we can use to put them in astd::set. ↩ -
Semantic refinements are especially common among the algebraic structures (see SemiRing/Ring, Group/AbelianGroup, BinaryOperator/SemiGroup, etc.) ↩
- Three Kinds of Concepts
- Three Kinds of Concept Maps
- To Auto or Not? That is the Question
couldn’t this be done with (implicit)auto maps and without negaive concept maps?:
template< typename T > struct IsStrictWeakOrder : boost::mpl::true_type {}; template< typename T > concept StrictWeakOrder { bool <( const T&,const T& ); requires IsStrictWeakOrder< T >::value == true; // or similary };
template<> struct IsStrictWeakOrder< mathematical_set > : boost::mpl::false_type {};
Your thinking about Structural Aliasing:
and Semantic Refinement:
“it is especially dangerous to to declare these refined concepts auto because algorithms [...]“
seems to agree with Stroustrup (N2960 – Simplifying the use of concepts )
It is true? What do you think about the solution that he proposes in the N2960?
Sigh. I’ve been reluctant to answer this question because there are so many ways to respond. Therefore, I’ll pick the simplest of my possible answers, which is: “solution to what?”
In the July 2009 meeting in Frankfurt, B. Stroustrup presented is concerns about “usability” of concepts as they were defined in the last Working Draft Standard (2914).
N2906 explains in details this concerns, I will not repeat them here, but I think they can be summarized in this way: to use standard library the user is required to write a lot of concept map because lot of foundational concepts are not “auto”.
I like concepts, and I am disappointed that this feature will not be in the next standard. My point of view is limited (I read many papers on concepts but I have no experience with them) but I agree with the concerns raised by N2906 and I agree with the remedy of B. Stroustrup: make all concepts implicit/auto and make only some refinement (ForwardIterator) explicit.
In your posts you correctly use a notation that refers to the last approved documents on concepts. But in this post you say: “Don’t make simple, foundational concepts auto […] isn’t really an option”. I think there is an open discussion on this point. The N2914 had many foundational concepts non-auto. Do you think this would have been a problem? Do you think that the N2914 had this bug? If so, do you think the solution for the standard library is to made auto many foundational concepts (more than N2914) without a change in the concept mechanism but only introducing negative concepts map?
Stroustrup goes further and proposes to change the definition/refinement mechanism so all concepts are auto/implicit (no auto keyword in front of concept), and only some problematic refinement will be explicit (=non auto), the refinement witch match syntactically with the “base” concepts but not semantically. So it proposes to make all concepts in the standard library implicit except for ForwardIterator. «I don’t see any that are likely to get accidentally matched. All seems to have distinguishing operations ». Do you like this solution? To me it appears not necessary but more elegant.
If I am not wrong the problem in the example of Chris Jefferson remains open without negative concept maps even in the design of B. Stroustrup (but he is not opposed to negative concept maps). So this post in not on the problem of Chris Jefferson.
Those questions have only the aim to know more on the underling discussions on concepts in the community because what I know is only what some people (like you) write!
Thanks, Michelangelo
Okay, now I understand what problem you’re talking about solving. My response:
autoconcepts altogether, with the aim of preventing concept authors from choosing to require explicit conformance.auto, but weren’t. The right answer would have been to make thoseauto. That would have gone a long way toward solving the perceived problem.I see nothing wrong with insisting that operator< default to implement StrictWeakOrder, or that operator< and operator== combine to implement the trichotomy law, and forcing anyone who wishes otherwise to be explicit about what they’re doing. I don’t want to have to look at an implementation to figure out whether operator< is a partial or strict weak order. I don’t even want to see these concept_map statements. It would be preferable to write
class mathematical_set fails StrictWeakOrder {};
so that I know where to look.
Mark, if I understand you correctly, I agree with you, which is why I think negative concept maps are probably the right answer. I assume that by what you’ve written here you intend a class definition, and there would be something between the braces? If so, you and K-ballo are both pointing in the same direction as N2916, which is especially relevant to the next article in this series and will be raised there.
Except that N2916 talks about explicitly stating what concepts a class models, while it would generate fewer headaches to be explicit about what concepts a class models syntactically but not semantically. There are far fewer of those.
And yes, I forgot my “…” between “{” and “}”.
I don’t think I agree about “fewer headaches.” In general, the author of a class can’t know about all possible the concepts he’d need to deny he’s modeling.
Mark, how about going even further and insisting that operator< implement a total order, as in Elements of Programming?
OK. Done. But apparently I have to say more in order for the website to accept my comment as meaningful.
Then replace
operator<with any other name. This is not about the sanctity of particular mathematical operators.I am just a casual bystander when it comes to concepts, so excuse me while I digress on the subject. After reading this post, I don’t see how C++ would benefit from a feature like auto concepts. So what are auto concepts and why do we want them?
Are auto concepts just a structural conformance test tool? Auto concepts only check for structural aliasing. They may be able to check semantic properties, only if they are already defined syntactically. And writing
typedef forward_iterator_tag iterator_categoryis not that different from writingconcept_map ForwardIterator< my_type >. We can already do most of syntactic conformance checks with today’s tools, and the new features packed with C++0X should allow us to check everything else (don’t they?). Are auto concepts just an SFINAE-less way to do that?Are auto concepts just a backward compatibility tool? Are they about having today’s code run unmodified on a ‘conceptualized’ version of STL (or Boost or any other library)? Will auto concepts eventually became obsolete, and the auto keyword would once again be free to be imprinted with a different meaning?
Are auto concepts just a language tool to save coders some typing in the default scenarios? If that’s the case, then there is precedent for this in the language: constructors, destructors and assignment operators. Concepts would be better off following such convention, having
= defaultpull those foundational concepts that do match syntactically, and= deletenitpick those foundational concepts which while matching syntactically don’t match semantically.Consider what auto concepts have already done to the language. std::less has hijacked the meaning of operator less to that of operator strict weak order;
operator <is implemented even when its meaningless for a class, just to be able to place those objects in standard containers. All it would have really taken is a specialization of std::less.I hope I haven’t just publicly embarassed myself, but please enlighten me: why do we want auto concepts? After all, isn’t explicit better than implicit?
I wouldn’t characterize them that way, no.
I think you mean “conformance,” not “aliasing.”
Sorry, I don’t understand what you mean by “defined syntactically.” Could you explain that?
Now you’re just preachin’ to the choir
. But seriously, it’s one thing to demand an explicit declaration of conformance for a nontrivial concept like ForwardIterator, for which building a new model takes some real effort, and quite another to make people write such declarations for something like EqualityComparable. Still, I think even for EqualityComparable, requiring the explicit declaration wouldn’t cause the kind of outcry that those “not in the choir” are certain we’d have. But the reasons for that are in the next article in the series.
Not really. Even with C++0x extended SFINAE, we won’t be able to do concept-based overloading.
That’s certainly a part of their role. But I don’t think it amounts to that alone.
It’s already getting a different meaning.
I think that’s close to the mark, though some would argue with your use of “just” in that sentence.
Sorry, I can’t envision what you’re proposing here. Hypothetical code examples might help.
That was already true in C++98, and I don’t see what it has to do with structural vs. explicit conformance.
It is?
Sigh—if only more people subscribed to the Zen of Python. I think the track record of C++ in this area at least shows clearly that implicit behavior ought to have been more often explicitly requested (e.g. think of converting constructors among other things), so I can’t understand the drive to make concepts
autoby default, or even exclusively.Let’s assume a standardized set of fundamental concepts. Be it {DefaultConstructible, Assignable, EqualityComparable, … }.
Were a type T to have no associated concept maps or have a ‘default concept map’ definition (something like
concept_map my_type = default;), then T would be considered to have a concept_map definition for each concept C in the set of fundamental concepts for which it conforms syntactically. If T has a ‘default concept map’ definition, then a ‘delete concept map’ definition would deny semantic conformance to one of the fundamental concepts.struct my_type_1 {}; // no concept_map definitions for my_type_1 // my_type_1 conforms to DefaultConstructible, Assignable, EqualityComparable, ... struct my_type_2 { my_type_2( int v ) : _a( v ){} int const _a; }; concept_map my_type_2 = default; // my_type_1 conforms to EqualityComparable and others, but not to DefaultConstructible and Assignable struct my_type_3 { void operator =( my_type_3 const& right ) { std::cout << "I'm not being assigned via op=" << std::endl; } }; concept_map my_type_3 = default; concept_map Assignable = delete; // my_type_3 conforms to DefaultConstructible, EqualityComparable and others, but not to AssignableI hope these examples help clarify my proposal.
Thanks for the explanation; I think I understand it now.
I think eliminating the concept_map statements and saying “struct my_type_3 fails Assignable” is a whole lot easier to read. It should be the compiler’s job to figure out what concepts a class models.
That’s not always practical. What concepts does the expression:
[](T x, T y) { return x > y; }
model? As in sort(f, l, [](T x, T y) { return x > y; });
Come to think of it, how does one specify concept maps for lambda functions anyways?
The difficulty of figuring out how to concept-constrain lambda expressions is part of the reason lambdas in C++0x are not polymorphic, i.e. you have to specify the types of their parameters. I have some ideas about how it could be implemented, but they are far from baked.
It models BinaryPredicate, and T must model TotalOrder.
Mark, Being totally ordered is a semantic property, so won’t the compiler have problems determining in all cases whether a function implements a total ordering?
It is more important to worry about what is the right thing to do than to worry about what practical problems may result. Any third grader intuitively knows that x < y implies a total ordering without thinking about it. We programmers need to do the same.
Practically speaking, though, the compiler already has problems determining whether two iterators form a valid range. Some compilers have an iterator debugging flag that checks to make sure the range is valid. A compiler could have a similar debugging flag that takes two values being compared and makes sure that either x < y, x > y, or x = y. Transitivity is harder to check but not impossible.
Upon reflection, I think the flawed assumption that Chris Jefferson ought to be able to use operator< on mathematical sets just because he wants to needs to be examined closely. If he had used is_subset(x, y), no programs would have crashed. Their assumption about operator< was correct; its existence is the problem.
TotalOrder isn’t a property of T it’s a property of the operation, and in that case, it’s only a property if T provides an overload of operator< that also defines a total order. The point I was trying to make (and that Dave gave a good answer for–good answer Dave!) was that the compiler doesn’t know anything about the lambda function except that’s it’s probably a binary predicate, which is basically what the other respondent, Student, said.
I think your assumption that Chris uses
operator<“just because he wants to” is flawed. Chris is using the standard mathematical meaning for operators in the domain his library implements, which gives it all the legitimacy it needs in my book. At the very least, I think it’s reasonable to assume that his users demand to use<for “strict subset,” so it isn’t just his personal preference.Again, Chris or somebody else chose to give operator< an unintuitive meaning in their library. The proper mathematical symbol for subset is not “<”, it’s a U on its side, and nobody expects that symbol to implement a total ordering (it’s too bad it’s not on our keyboards). The people whose programs are crashing certainly don’t think it’s reasonable, and neither do I. The overload in this case confuses people, which is bad. Programmers and compilers would be much better off with an agreement that “<” implements a total ordering, even with the “cost” of personal preference being taken away. Then we don’t need any code that says one class is totally ordered and another is not, which is another source of bugs.
Wow, this is embarrassing. I know “⊊” is a symbol for “strict subset,” but I could swear that while writing this article I read (in a reliable source) about “<” being used for that purpose… but of course, now I can’t find it.
But, again, the point of this article doesn’t depend on someone violating the sanctity of the expected semantics for a mathematical operator. You can’t agree about the meaning of all names in advance; that’s why we have namespaces.
< is often used in ascii text, just because we don’t have a nice ⊊ or ⊂ (which is what I would more usually) use. If C++ allowed us to invent arbitrary new operators, based on a unicode symbol, then we wouldn’t have to undertake this operator abuse
Certainly it’s on the edge of dodgy, although I consider it nowhere near as bad as boost::spirits use of (for example) dereference for kleene star
I am not certain whether we can or can’t agree on the meanings of all names in advance, but the mathematical foundations of computer science are an area where we must agree.
Whoops! That should have been a reply to Dave’s comment:
“You can’t agree about the meaning of all names in advance; that’s why we have namespaces.”
I’m really beating this page to virtual shreds, sorry about that.
(
(Note, when I wrote this I decided it looked a bit sarcastic. I don’t mean it that way
)
Yes, lets see about the mathematical foundations of computer science.
Well everyone can agree that a+b == b+a. Except woops, we’ve just broken std::string. Also, a + b – a = b. Except woops, float doesn’t accept that.
Well, at least a = b doesn’t effect b. Except woops, now std::auto_ptr is gone (although, there are strong arguments that std::auto_ptr should go!). And that is before we even start to talk about many of the crazy operator overloading libraries that do things like capture expressions.
Obviously doing something like making < not a proper ordering is a major deviation, and a programmer who does it must be sure that the gains outweigh the costs. I think, and still believe, the benefits outweigh the costs for me. But, if concepts added more tools that helped make my strange code even easier and safer to use, that would be great too.
Now that you talk about float, does IEEE 754 implement a total order? What about NaNs and infinities?
Unfortunately, NaN != NaN, which is why we all have to assume that NaNs don’t exist in our code or write “if (!isnan(x))” everywhere. Perhaps the most influential standard in all of computer science broke equality.
Chris, your examples are great.
String concatenation is indeed non-commutative. Using + instead of * there has been a mistake since the earliest days of the language. String concatenation is associative only.
Floats (and integral types) suffer from underflow, overflow, and (in particular for floats) precision issues. However, the underlying abstract entities (real numbers, integers) do not have these problems. Float and int are ‘properly partial,’ as described in Ch. 1 of Elements of Programming, and we have to deal with the consequences.
a = b should not change the state of b, otherwise equality is not transitive (a = b; c = b; assert(a == c)). A slippery slope forms when we ask, “What is the ‘state’ of b?” One could argue that reference counting or statistics gathering is not part of b’s state, though if the reference count hits 0 that definitely changes b’s state. If I were given a choice between only smart pointers and only smart programmers (not to say you can’t have both sometimes), I would prefer only smart programmers every time.
Do you think it should be required that “a+b == b+a”? Because that is something that most people expect, and something that almost every type which implements + supports.
Do you think that “a = b” shouldn’t change b (ignoring rvalue references)? Because that is something that most people expect, and something almost every type which implements = supports.
Using operators in an unusual way is always a trade-off. However, if it is possible with concepts to make such code safer, then surely it would be a good idea to support that?
A further thing I do is use + for union and * for intersection of sets. This is actually better in some ways than + and * on floats, as sets with + and * form a field, whereas with floats you only “almost” get a field, and also have to worry about issues like NaN. Given these operators, which would you prefer to write on a day-to-day basis, once you were used to the library?
A + B < C * D or: strictsubset(union(A,B), intersect(C, D)) ?
Yes! + is commutative and has been that way for centuries. If a + b != b + a, you probably should call your operation *. Every high schooler who learns to multiply 2×2 matrices understands that intuitively.
Yes! Assignment statements should not change the state of an object. Only I propose writing “a <- b” so that “=” can go back to 5 centuries of meaning as equality.
Using operators in an unusual way is a side effect of not having every useful mathematical symbol available in C++. I would so much rather see A + B < C * D written using the correct glyphs, which apparently only the cool kids know how to type in here, but barring that I would resist the temptation to use + for union and * for intersection. To do otherwise is to create code that is meaningful for some group of people and incomprehensible to another group. Mathematics is not written that way, and computer science has the potential to do for mathematics what mathematics has done for every other science.
I find it interesting that you think it is obvious that a+b==b+a, but not that ab==ba. Also, are you suggesting the concatination operator for std::string be changed to *?
I think it’s perhaps important to seperate two issues here, in an ideal world, and what we can do day-to-day with current C++.
In an ideal world, I would love to be able to declare my own operators based on unicode. It’s not hard to type into modern keyboards, and using an editor which does automatic snippet replacement makes it even easier.
However, given current C++, we can’t do that. We can just design libraries which are as easy to use as possible. Given that, I’m going to use + for union and * for intersection. That is common notation for mathematicans, as sets for a field, and the main (only) users of that particular library are mathematicans. Of course, if anyone else was going to use it, they would need to do some documentation reading.
It’s all about tradeoffs. I believe the tradeoff of strange operators is better than having to write strictsubset(union(A,B), intersect(C,D)). One of the worst things I’ve ever had to do was write some maths-intensive code in Java, where there is no operator overloading.
Which is easier to read for the traditional quadratic equation? (bb – sqrt(4ac))/(2a), or (b.multiply(b).minus(math.sqrt(Integer(4).multiply(a).multiply(c))).divide(Integer(2).multiply(a)) ?
Of course in general ab != ba. Let a = [1 0; 2 1] and b = [2 -1; 0 1] (MATLAB notation for 2×2 matrices). The products are very different.
But this group is not “C++Current”, it’s “C++Next”. Let’s design the next C++ to give you the ease you are looking for without requiring documentation reading (or some other initiation ritual) for newcomers. Leave Java for its intended purpose: shuttling data around quickly and not worrying about performance. Let’s nail down the foundations of C++ securely to the math from which computer science sprung.
And the first quadratic expression is easier.
(I am the Chris Jefferson in question).
I agree with you that using < for set subset might be surprising and unusual, but it was natural for the code I wanted to write, and I didn’t want to write is_subset(x,y) all the time. This particular code is in current common usage and works fine. There is not any particularly natural total ordering I want to define on my sets, so if I didn’t do this the operators would go unused. While there are occasional mistakes, I believe overall the code is easier to read.
Given that the purpose of concepts is to mark what concepts a type supports, it seems like it would be a great shame if there was no way mark a type as not satisfying a particular concept.
The standard does not guarantee what particular operators will do, and it is far to late to put such restrictions on now. For example, + on strings is fundamentally different to + on integral types. << is used for shifting and streaming. Many libraries overload operators in various exciting ways to do things like expression building.
I suspect if concepts ever appear there will be many auto concepts, because they are much easier to integrate into existing C++03 codebases (when I played with concepts, I did exactly this myself).
Is e.g.
concept_map StrictWeakOrder<std::less<my_type> > {}; concept_map StrictWeakOrder<std::less<my_type> > {};legal? It seems like it should be (so long as the map bodies are the same), much like duplicate extern declarations are legal. If duplicate concept_maps aren’t legal, then we stand to lose one of the most important aspects of templates: the ability to use two unrelated types that happen to share an interface with the same body of code.
In Java’s generics, you have to declare your type parameters with the class/interface that you want to call methods from, e.g.
to be able to call get(int) and assign the result to a T reference. This has the unfortunate effect that only code that implements the interface/extends the class, i.e. only code that was designed to work together, can be used with generics in this way. This is my concern with concepts, more than the syntactic burden of empty concept_maps: that “generic” code will have to be specifically designed to be used generically.
So far, I’ve been calm about it because the decoupling of concept_maps from class declarations means I can add the concept_map if other code doesn’t provide it, but that could present a maintenance problem if the other code is updated to include it and the maps conflict.
I don’t know, but you can look at the specification yourself and find out. It’s certainly legal if they’re in different scopes. In that case, the maps can even be different. Is this question directly related to the article somehow? If not, that’s OK; I just don’t want to miss the connection if there is one.
How so?
An important feature of GP in C++ today is that you don’t have to do that, and everyone working on concept support (even those who disagreed on other issues) was very concerned about preserving that feature.
Take a look at N2098 and N2414—which were accepted—and call me in the morning
re: “Is this question directly related to the article somehow?” and “How so?”
It’s related to the rest of my comment, at least. My concern is that if I want to use a concept_map to declare that a library class realizes a concept, and then in the next version of the library the library author adds that concept, do I have to change my code? If so, it will make it difficult to adapt a class I don’t control, especially if I’m going to give my code to someone else who won’t control either library. If the ODR applies like most everything else, it’s harmless (so long as the library author agrees on the body of the concept_map).
re: “…and everyone working on concept support (even those who disagreed on other issues) was very concerned about preserving that feature.”
Excellent. I haven’t been following very closely outside of this blog and anything that pops up on the Boost lists, so I wasn’t as sure, especially as I tended to read about disagreements and making concepts more complex rather than keeping them simple.