C++ Concepts
in [C++]
|
Prev: C++/CLI limitations?
Next: SHA1
From: Joel Eidsath on 29 Sep 2005 11:12 I came across a comment on Slashdot that gives me an excuse to write about the "A concept design" paper before the standards committee: "It was certainly interesting in the 'bad old days' when no two compilers implemented things like templates the same way. Of course, I'm no fan of templates, since they are essentially a kludge to work around the fact that there are atomic variable types that are not part of the OO implentation in C. If there were some abstract type from which int, char, etc, were derived then templates would be unnecessary. In other words, templates only exist because C++ isn't fully OO. Of course, then we wouldn't have 'template metaprogramming' and there would be a whole bunch of computer geeks who would have to stop writing papers and articles showing us how smart they are implementing the Sieve of Eratosthanes that prints prime numbers in compiler warnings, and get back to doing useful work. :-P" This is wrong (except maybe for the stuff about template metaprogramming). But there is not much functional difference between templates, as implemented now, and functions in more OO languages that work on the base object for all types. What makes templates different is the idea behind them. The OO idea of a generic function is a function that works for some base type and any type derived from it. The reasoning behind this is something like "type hierarchies are 'IS A' so a function that works for a base should work for derived types as well." Real world code does not follow this paradigm, however. Instead, generic functions are envisioned to work on types with a given set of properties. There is no reason to expect that these properties should obey class hierarchies, even a majority of the time. It is the OO languages that have the kludge: an abstract base class from which everything derives, not C++. And C++ 'concepts' are going to make this clear: Stroustrup's and Dos Reis' paper for the standard committee is available here: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf Abstract: "We describe a design of 'concepts' (a type system for types) for improved support of generic programming in C++. This paper presents a current best-effort design based on previous work followed by lengthy discussions of technical details. The design is based on the principles that simple things should be simple (whereas more advanced programming techniques may require some extra work), that there should be no performance degradation compared to current template techniques, and that essentially all current template techniques should be improved by the use of concepts. The design achieves perfect checking of separately compiled templates at the cost of minor restrictions on the instantiation mechanism." The rest of this post is some comments about the paper. We're first asked to consider STL's fill(): template<class ForwardIterator, class ValueType> void fill(ForwardIterator first, ForwardIterator last, const ValueType & v) { while (first!=last) { *first = v; ++first; } } Here it is with concepts: template<class For, class V> where Forward_iterator<For> && Value_type<V> && Assignable<For::value_type,V> void fill(For first, For last, const V& v) { while (first!=last) { *first = v; ++first; } } In a more condensed form: template<Forward_iterator For, Value_type V> where Assignable<For::value_type,V> void fill(For first, For last, const V& v) { while (first!=last) { *first = v; ++first; } } That For "is a" Forward_iterator and V "is a" Value_type should not be confused with the OO "is a." For "is a" Forward_iterator in that it obeys the properties defined for Forward_iterator. Concepts allow two sorts of errors to be picked up by the compiler: 1) Concept violations in the arguments passed to a template at point of call. 2) Concept violations inside the template itself. I am somewhat wary about this. Catching 1 should be the main justification of concepts. In effect, it is the template designer saying to the user of the template "your types must possess these properties, or they won't work as template arguments." Catching 2, however, is saying "so long as your types possess these properties, they will work as template arguments." The problem with 2 is that it won't always be true. I see this as a problem similar to exception specifications. I don't really see a problem with catching both types of violations, but I wish it was possible to separate them. Section 2.2 describes overloading based on concepts. This is amazing and my mouth is watering for a compiler that implements it. Section 3 describes how to create concepts. I dislike that there are no provisions for negative concepts. For example, I might like to have something like "Not_Assignable" for use in creating slow careful algorithms rather than the fast awesome algorithms I might create with "Assignable". (This is something different than negative static_asserts mentioned later.) Most of the time, the fact that a compiler uses the most constrained concept definition seems to obliviate the need for this, but this would allow a more obvious implementation of advance, as done in 6.4. There may be concepts that violate "the predicate of L must imply the predicate of K" (from 6.4) but we still want to choose one or the other. Another feature that is missing is some sort of user concept specification. I imagine that this will be achieved with type traits, but a formal implementation would be nice. User concept specification would allow class designers to specify runtime guarantees for their classes. Something like "Trust_me_guys_this_member_function_wont_ever_return_zero" might be a useful thing to have. One thing that puzzled me was that there were no examples in the paper that involved concepts involving OO hierarchy determination. Would one use dynamic_cast<>? There is another thing missing from concepts that limit their utility. I don't see how to implement it, however: Hopefully everyone learned about induction proofs in high school. For induction to work, you need to prove that "P true for x" implies "P true for x + 1" and also a specific instance of P. (Usually P of 1 or 0.) I see concepts as equivalent to the first general condition of induction, but not the second. It would be nice to have some constraints on class T initialized with 0, for instance. Sometimes this will be possible to know at compile-time, sometimes not. Hence the difficulty. (Other similar constraints might be the behavior of an empty container, or an iterator at the end of a container.) Again, this seems impossible to implement in general, but maybe someone reading will have a flash of insight. Perhaps something along these lines could be be achieved with a mix of user concept declarations and compiler-evaluated declarations. Joel Eidsath [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: David Abrahams on 30 Sep 2005 21:31 "Joel Eidsath" <jeidsath(a)gmail.com> writes: > I came across a comment on Slashdot that gives me an excuse to write > about the "A concept design" paper before the standards committee: > > "It was certainly interesting in the 'bad old days' when no two > compilers implemented things like templates the same way. Of course, > I'm no fan of templates, since they are essentially a kludge to work > around the fact that there are atomic variable types that are not part > of the OO implentation in C. If there were some abstract type from > which int, char, etc, were derived then templates would be unnecessary. > In other words, templates only exist because C++ isn't fully OO. Hah. > Of course, then we wouldn't have 'template metaprogramming' and there > would be a whole bunch of computer geeks who would have to stop writing > papers and articles showing us how smart they are implementing the > Sieve of Eratosthanes that prints prime numbers in compiler warnings, > and get back to doing useful work. :-P" > > This is wrong (except maybe for the stuff about template > metaprogramming). No comment. > But there is not much functional difference between templates, as > implemented now, and functions in more OO languages that work on the > base object for all types. Yes, there is. Covariant argument types (the kind you need in order to do int + int and complex + complex with the same '+' operation -- or swap, for that matter) can't be implemented using traditional OO without compromising static type safety. Among other things. > It is the OO languages that have the kludge: an abstract base class > from which everything derives, not C++. And C++ 'concepts' are going > to make this clear: > > Stroustrup's and Dos Reis' paper for the standard committee is > available here: > http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf I hope you're aware that there's a competing concepts proposal: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1849.pdf > Concepts allow two sorts of errors to be picked up by the compiler: > 1) Concept violations in the arguments passed to a template at point > of call. > 2) Concept violations inside the template itself. > > I am somewhat wary about this. Catching 1 should be the main > justification of concepts. In effect, it is the template designer > saying to the user of the template "your types must possess these > properties, or they won't work as template arguments." Catching 2, > however, is saying "so long as your types possess these properties, > they will work as template arguments." The problem with 2 is that it > won't always be true. What do you mean? > I see this as a problem similar to exception > specifications. I don't really see a problem with catching both types > of violations, but I wish it was possible to separate them. > > Section 2.2 describes overloading based on concepts. This is amazing > and my mouth is watering for a compiler that implements it. I hope you're aware that the competing concepts proposal supports that, and it has been implemented: http://www.osl.iu.edu/~dgregor/ConceptGCC/ You can download that compiler and use it today. > Section 3 describes how to create concepts. I dislike that there are > no provisions for negative concepts. For example, I might like to have > something like "Not_Assignable" for use in creating slow careful > algorithms rather than the fast awesome algorithms I might create with > "Assignable". You don't need that. If you create two overloads, only one of which requires Assignable, it will be chosen in preference to the other one. You can put the slow implementation in the overload that doesn't require Assignable. > (This is something different than negative static_asserts mentioned > later.) Thank goodness. The need for those is what bothers me the most about the Stroustrup and Dos Reis proposal. > Most of the time, the fact that a compiler uses the most constrained > concept definition seems to obliviate the need for this, but this > would allow a more obvious implementation of advance, as done in > 6.4. You can always create a Not_Assignable concept that contains no requirements and is thus satisfied by everything, if that helps. > Another feature that is missing is some sort of user concept > specification. I don't know what that means. > I imagine that this will be achieved with type traits, No, concepts will obviate type traits. > but a formal implementation would be nice. User concept specification > would allow class designers to specify runtime guarantees for their > classes. Something like > "Trust_me_guys_this_member_function_wont_ever_return_zero" might be a > useful thing to have. What you're referring to sounds a lot more like it should be called "runtime semantic guarantees" than "user concept specification." > One thing that puzzled me was that there were no examples in the > paper that involved concepts involving OO hierarchy determination. > Would one use dynamic_cast<>? You lost me. > There is another thing missing from concepts that limit their utility. > I don't see how to implement it, however: > > Hopefully everyone learned about induction proofs in high school. For > induction to work, you need to prove that "P true for x" implies "P > true for x + 1" and also a specific instance of P. (Usually P of 1 or > 0.) I see concepts as equivalent to the first general condition of > induction, but not the second. It would be nice to have some > constraints on class T initialized with 0, for instance. Again, these are runtime semantic guarantees. > Sometimes this will be possible to know at compile-time, sometimes > not. How could it ever be known at compile time? -- Dave Abrahams Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Hyman Rosen on 30 Sep 2005 21:30 Joel Eidsath wrote: > Stroustrup's and Dos Reis' paper for the standard committee is > available here: > http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1782.pdf It would be nice if they could vet the paper and remove its many typographical and grammatical errors. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Edson Manoel on 30 Sep 2005 21:34 >...If there were some abstract type from >which int, char, etc, were derived then templates would be unnecessary. >In other words, templates only exist because C++ isn't fully OO. >... >This is wrong (except maybe for the stuff about template >metaprogramming). But there is not much functional difference between >templates, as implemented now, and functions in more OO languages that >work on the base object for all types. There is a HUGE difference that I think you didn't understand well: in other OO languages, such as Java, every object is actually a pointer to an object in the heap. So, you can have a generic "Object" from whom everyone is derived, and you can have horrible functions taking Object as parameter that dynamically cast it down to some Interface or object and use it... but the casting is made AT RUNTIME, and if you pass the wrong object, the user will get a RUNTIME error. The templates in C++ are all bound and checked AT COMPILATION TIME -- if you pass the wrong object, the compiler will spit an error, forcing you to fix it. Also, the code runs faster because you don't need to have the overhead of dynamic casts, virtual table calls and heap allocation; it uses less memory because your containers can store the values directly instead of storing pointers to the objects allocated one-by-one in the heap. Metaprogramming is a very powerful and useful tool... but maybe _template_ metaprogramming is not the best approach to it, maybe in the future they can come up with better ways to do metaprogramming, because template metaprogramming is being abused in ways that compilers just wasn't made to support. You will only fully understand Concepts when you understand what really templates are all about. You are confusing runtime behavior with compilation time behavior... Concepts have nothing to do with dynamic_casts... they will be something like "static interfaces" (or traits) checked on compilation time. Concepts already exists, read a STL documentation for example... they just are not "implemented" in the language... although the Boost libraries implement a concept_check, the article is proposing adding it to the core language. Edson T. M. Manoel [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: kanze on 30 Sep 2005 21:59
Joel Eidsath wrote: > I came across a comment on Slashdot that gives me an excuse to > write about the "A concept design" paper before the standards > committee: > "It was certainly interesting in the 'bad old days' when no > two compilers implemented things like templates the same way. > Of course, I'm no fan of templates, since they are essentially > a kludge to work around the fact that there are atomic > variable types that are not part of the OO implentation in C. > If there were some abstract type from which int, char, etc, > were derived then templates would be unnecessary. In other > words, templates only exist because C++ isn't fully OO. > Of course, then we wouldn't have 'template metaprogramming' > and there would be a whole bunch of computer geeks who would > have to stop writing papers and articles showing us how smart > they are implementing the Sieve of Eratosthanes that prints > prime numbers in compiler warnings, and get back to doing > useful work. :-P" > This is wrong (except maybe for the stuff about template > metaprogramming). But there is not much functional difference > between templates, as implemented now, and functions in more > OO languages that work on the base object for all types. > What makes templates different is the idea behind them. With regards to the comments in Slashdot: what makes templates different is that they enforce invariants accross the type system at compile time. In a language with purely dynamic typing (Lisp, Smalltalk), there is no need for templates (in the C++ sense -- some dialects of Lisp are very powerful when it comes to generic programming). It's interesting to note that Java has felt the need to add a form of templates, exactly for this reason -- Java's implementation, from what little I understand, does not support generic programming, but it does allow compile time enforcement of invariants over the type system. In the end, the distinction has nothing to do with OO or not OO; it has to do with static typing vs. dynamic typing. A language with static typing needs some form of generic classes or templates. (And it doesn't need a common base class like Object in order to be OO. Supposing "being OO" is a useful goal, or even has a meaning.) > The OO idea of a generic function is a function that works for > some base type and any type derived from it. The reasoning > behind this is something like "type hierarchies are 'IS A' so > a function that works for a base should work for derived types > as well." Real world code does not follow this paradigm, > however. Instead, generic functions are envisioned to work on > types with a given set of properties. There is no reason to > expect that these properties should obey class hierarchies, > even a majority of the time. I disagree. The whole point of static type checking is that the compiler detects errors, rather than the run-time library. For run-time genericity, the requirement of a common base type (or something similar) is essential for static type checking. > It is the OO languages that have the kludge: an abstract base > class from which everything derives, not C++. That is a kludge. Because what functionality is common to all possible classes? But the problem isn't there. Having a common base class doesn't do any harm in itself; it may even be useful for supporting things like reflection. The problem is elsewhere: given an abstract container, how do you ensure at compile time that only type X is inserted into that container? Or more generally, how do you enforce invariants over the type system at compile time (which is what static type checking is all about)? -- James Kanze GABI Software mailto:james.kanze(a)free.fr Conseils en informatique orient?e objet/ Beratung in objektorientierter Datenverarbeitung 9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |