Yet another concept checker
I would like to know if many people in the community think the following library would be useful. I would like to define concepts using this syntax: template<typename left_type, typename right_type = left_type> struct less_than_comparable { static var<left_type const> left; static var<right_type const> right; static var<bool> b; typedef CONCEPTS_USE_PATTERN(b = (left < right)) constraints; }; In the code above the less_than_comparable<T, U> concept is defined. The var<> type is meant to resemble the Var<> in Stroustrup's concept proposals. The CONCEPTS_USE_PATTERN(EXP) macro expands to BOOST_TYPEOF(EXP). The b, left and right variables have lambda-like capabilities where you can apply any operation on them and they return a complex type that remembers what operations have been applied. Functions that want to enforce concepts would use this syntax: template<typename operand_type> bool my_less_than(operand_type left, operand_type right) { // Enforce the model. typedef less_than_comparable<operand_type> model; BOOST_STATIC_ASSERT(is_match<model>::value); constrained_proxy<1, model> constrained_left(constrain<1, model>(left)); constrained_proxy<2, model> constrained_right(constrain<2, model>(right)); // Use the constrained proxies just like regular types. return (constrained_left < constrained_right); } Obviously this syntax is more cumbersome than the current Boost Concept Check Library's. But it offers more power too: 1) The author doesn't have to hand-craft an archetype class! The model knows what operations should be allowed and the constrained_proxy<> class enforces that only those operations are taken. 2) It is possible to check whether a model is valid without causing a fatal error. That's what the is_match<model> metapredicate is for. This could be used to dispatch different optimized code depending on which concepts the type is known to model. Now, there are some things that can't be detected by library code (like the presence of a default constructor) so I would have to rely on authors to provide hints about those. I'm planning on just assuming that any requirements I can't detect are fulfilled, and then the compiler will complain if that's wrong. 3) The concepts can be built up from primitives using and_ and or_ and not_ operations, just like in Stroustrup's proposals. For example, the concept above could have included this statement instead: "typedef and_<CONCEPTS_USE_PATTERN(b = left < right), CONCEPTS_USE_PATTERN(b = right < left), copy_constructible<left> > constraints;" 4) This use pattern syntax more closely resembles the C++0x use pattern proposals than any other existing library. 5) The constrained_proxy class prevents certain errors where a pathological type behaves unexpectedly. I'm talking about functions like "evil_bool_proxy operator<(mytype, mytype)" where evil_bool_proxy defines its own && and || operators. In the expression, "(a < b) && (c < d)" the constrained_proxy enforces that the && operation gets applied to bool values, not to evil_bool_proxy values. 6) This mechanism allows you to express that a model has important semantic implications also. The library assumes that a model is valid if it is a structural match. But you can override that by saying, "template<typename value_type> declare_match<forward_iterator<istream_iterator<value_type> > > : false_ { };" 7) Traits classes could potentially be added to this library so that authors could express mappings such as that the constrained_proxy should call a free function "push_back(my_seq, elem)" instead of the normal "my_seq.push_back (elem)" for a given sequence type. So far I have gotten var<> and declare_match<> and is_match<> to compile. I've also finished and_<>, or_<> and not_<>. I'm working on constrained_proxy<>. -- chad
"Chad Parry" <spam@chad.parry.org> writes:
I would like to know if many people in the community think the following library would be useful.
I would like to define concepts using this syntax:
template<typename left_type, typename right_type = left_type> struct less_than_comparable { static var<left_type const> left; static var<right_type const> right; static var<bool> b; typedef CONCEPTS_USE_PATTERN(b = (left < right)) constraints; };
Chad, this looks like really interesting work. I should point out that I have recently changed the Boost concept checking library to support a syntax much closer to that of conceptc++ (http://www.generic-programming.org/languages/conceptcpp/). In particular: 1. you can access associated types through concepts, e.g.: template <class I> boost::ForwardIterator<I>::difference_type distance(I start, I finish); 2. BOOST_CONCEPT_ASSERT((SomeConcept< ... >)) works in all contexts and produces readable error messages. 3. You can refine concepts via inheritance, with no need to explicitly assert the base concepts: template <class TT> struct InputIterator : Assignable<TT> // HERE , EqualityComparable<TT> // HERE { // associated types typedef typename boost::detail::iterator_traits<TT>::value_type value_type; typedef typename boost::detail::iterator_traits<TT>::difference_type difference_type; typedef typename boost::detail::iterator_traits<TT>::reference reference; typedef typename boost::detail::iterator_traits<TT>::pointer pointer; typedef typename boost::detail::iterator_traits<TT>::iterator_category iterator_category; BOOST_CONCEPT_ASSERT((SignedInteger<difference_type>)); BOOST_CONCEPT_ASSERT((Convertible<iterator_category, std::input_iterator_tag>)); // valid expressions ~InputIterator() { TT j(i); (void)*i; // require dereference operator ++j; // require preincrement operator i++; // require postincrement operator } private: TT i; }; 4. You can use "where" clauses on generic functions: template<typename RanIter> BOOST_CONCEPT_WHERE( ((Mutable_RandomAccessIterator<RanIter>)) ((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>)) , (void)) sort(RanIter,RanIter) { ... } I think there are probably other features I'm forgetting; it's been a few months ;-)
In the code above the less_than_comparable<T, U> concept is defined. The var<> type is meant to resemble the Var<> in Stroustrup's concept proposals.
I don't recommend trying to emulate those proposals unless you mean the very recent ones written with the authors of conceptc++. The concept support we get is probably going to look a lot more like conceptc++ than like the early Stroustrup/Dos Reis proposals.
The CONCEPTS_USE_PATTERN(EXP) macro expands to BOOST_TYPEOF(EXP). The b, left and right variables have lambda-like capabilities where you can apply any operation on them and they return a complex type that remembers what operations have been applied.
Functions that want to enforce concepts would use this syntax:
template<typename operand_type> bool my_less_than(operand_type left, operand_type right) { // Enforce the model. typedef less_than_comparable<operand_type> model; BOOST_STATIC_ASSERT(is_match<model>::value);
That won't produce a readable error message.
constrained_proxy<1, model> constrained_left(constrain<1, model>(left)); constrained_proxy<2, model> constrained_right(constrain<2, model>(right)); // Use the constrained proxies just like regular types. return (constrained_left < constrained_right); }
Obviously this syntax is more cumbersome than the current Boost Concept Check Library's. But it offers more power too:
1) The author doesn't have to hand-craft an archetype class! The model knows what operations should be allowed and the constrained_proxy<> class enforces that only those operations are taken.
Ah, so. The point here is that if you can instantiate my_less_than with something (anything) without causing an error, my_less_than can only be using operations allowed by the model, because the function only really operates on the constrained_proxy. Very clever.
2) It is possible to check whether a model is valid without causing a fatal error.
I don't believe that can be done in general. There are many usage patterns (or pseudosignatures as in conceptc++) that *can't* be checked in C++98 without causing an error. For example, we have no non-fatal test for default constructibility. How would you handle that in your system [I see the answer below]?
That's what the is_match<model> metapredicate is for. This could be used to dispatch different optimized code depending on which concepts the type is known to model. Now, there are some things that can't be detected by library code (like the presence of a default constructor)
Aha! So in what sense does your system make that non-fatal checking possible where it wasn't possible before? Oh, it encodes the usage pattern in a type, which is then converted into a metafunction. Very very clever. Unless I'm missing something, you can't represent lots of important usage patterns other than default construction, e.g.: std::swap(x, y) ??
so I would have to rely on authors to provide hints about those. I'm planning on just assuming that any requirements I can't detect are fulfilled, and then the compiler will complain if that's wrong.
That defeats one of the main purposes of concept checking: early detection of errors before a large instantiation backtrace is generated.
3) The concepts can be built up from primitives using and_ and or_ and not_ operations, just like in Stroustrup's proposals. For example, the concept above could have included this statement instead: "typedef and_<CONCEPTS_USE_PATTERN(b = left < right), CONCEPTS_USE_PATTERN(b = right < left), copy_constructible<left> > constraints;"
I think I'd better leave it to Doug Gregor to explain why "or" constraints are problematic.
4) This use pattern syntax more closely resembles the C++0x use pattern proposals than any other existing library.
Unless you're looking at the wrong proposals ;-) Usage patterns don't really work for compiler support of concept checking, because they hide intermediate types that need to be explicit.
5) The constrained_proxy class prevents certain errors where a pathological type behaves unexpectedly. I'm talking about functions like "evil_bool_proxy operator<(mytype, mytype)" where evil_bool_proxy defines its own && and || operators. In the expression, "(a < b) && (c < d)" the constrained_proxy enforces that the && operation gets applied to bool values, not to evil_bool_proxy values.
6) This mechanism allows you to express that a model has important semantic implications also. The library assumes that a model is valid if it is a structural match. But you can override that by saying, "template<typename value_type> declare_match<forward_iterator<istream_iterator<value_type> > > : false_ { };"
That's fine if you're doing it just for checking, but it's not fine for dispatch. Consider what happens to vector(i1, i2) when i1 and i2 are input iterators that structurally mimic forward iterators.
7) Traits classes could potentially be added to this library so that authors could express mappings such as that the constrained_proxy should call a free function "push_back(my_seq, elem)" instead of the normal "my_seq.push_back (elem)" for a given sequence type.
So far I have gotten var<> and declare_match<> and is_match<> to compile. I've also finished and_<>, or_<> and not_<>. I'm working on constrained_proxy<>.
Well, it looks really interesting (really!), but I think you should review the ConceptC++ publications, in particular N1849, before investing more time in it. Also, IMO, you should try to model the standard concepts and see how it works out in practice. Lots of food for thought in your work, for sure. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Aug 20, 2006, at 11:48 PM, David Abrahams wrote:
3) The concepts can be built up from primitives using and_ and or_ and not_ operations, just like in Stroustrup's proposals. For example, the concept above could have included this statement instead: "typedef and_<CONCEPTS_USE_PATTERN(b = left < right), CONCEPTS_USE_PATTERN (b = right < left), copy_constructible<left> > constraints;"
I think I'd better leave it to Doug Gregor to explain why "or" constraints are problematic.
They are problematic for technical reasons (e.g., one needs to type- check a template an exponential number of times when it uses or constraints), but the real issue with or constraints is that they aren't sufficiently motivated. I've never actually needed them myself (ever), and the two examples I've seen have better solutions. For example, consider an abs() function that can work for either Integral or Floating-point types: template<typename T> where Integral<T> || Floating<T> T abs(T x); Or constraints work here, but we could just as easily have used a different concept (say, "Numeric") that better matches the requirements of abs: template<typename T> where Numeric<T> T abs(T x); To make this formulation equivalent to the one using ||, we need to ensure that all Integral and Floating types are also Numeric. With the benefit of foresight, we would have made Integral and Floating refinements of Numeric: concept Numeric<typename T> { ... } concept Integral<typename T> : Numeric<T> { ... } concept Floating<typename T> : Numeric<T> { ... } Even without foresight, we're fine: just write two "concept map" templates that turn Integral and Floating types into Numeric types: template<Integral T> concept_map Numeric<T> {} template<Floating T> concept_map Numeric<T> {} So, our new abs() works with both Integral and Floating types, like the || version, but it's better in several ways. First, the compiler only needs to type-check abs() once (not twice). Second, the declaration of abs() more closely reflects its actual requirements. Finally, abs() can now be used with any Numeric type---even those that are neither Integral nor Floating, such as rational numbers. I am, of course, very interested in seeing real-world examples using ||. Every example I've seen is better implemented without it. Of course, assuming we do have some real-world use cases, someone still needs to figure out how to implement || constraints without an exponential blow-up.
4) This use pattern syntax more closely resembles the C++0x use pattern proposals than any other existing library.
Unless you're looking at the wrong proposals ;-)
Usage patterns don't really work for compiler support of concept checking, because they hide intermediate types that need to be explicit.
There is some work on trying out usage patterns for real, in the context of ConceptGCC. I don't know the status, but eventually it should show us just how critical those intermediate types are.
Well, it looks really interesting (really!), but I think you should review the ConceptC++ publications, in particular N1849, before investing more time in it. Also, IMO, you should try to model the standard concepts and see how it works out in practice.
I strongly suggest that we focus on the latest concept proposal, N2042. N2042 is the result of countless hours of discussions among the authors of the two different concepts proposals, and it is the only concepts proposal that will be moving forward. You can find up-to-date information on the concepts proposals, compiler, etc. on the ConceptC++ home page: http://www.generic-programming.org/languages/conceptcpp/ Cheers, Doug
"Douglas Gregor" <doug.gregor@gmail.com> wrote in message news:ECF14E7B-BC49-4021-9828-A1EF57C862E9@cs.indiana.edu...
On Aug 20, 2006, at 11:48 PM, David Abrahams wrote:
[snip]
Well, it looks really interesting (really!), but I think you should review the ConceptC++ publications, in particular N1849, before investing more time in it. Also, IMO, you should try to model the standard concepts and see how it works out in practice.
I strongly suggest that we focus on the latest concept proposal, N2042. N2042 is the result of countless hours of discussions among the authors of the two different concepts proposals, and it is the only concepts proposal that will be moving forward.
You can find up-to-date information on the concepts proposals, compiler, etc. on the ConceptC++ home page:
That's exactly the kind of feedback I was hoping for. I'll focus more of my attention on these items you brought up: 1) Try to mimic the declarative syntax rather than the use pattern syntax. (There's probably no reason why both can't be supported simultaneously in a library solution like this.) 2) Require authors to declare that their types model a concept; don't assume matches based on syntax. Allow for concepts to be declared with the opposite default behavior if they wish. 3) Try to make the errors user-friendly. 4) Add support for associated types. (I've already thought a lot about this and it won't be too hard.) 5) Improve the user experience for signatures that are known to be undetectable by library code. This includes the DefaultConstructible<T> concept, for example. I've already thought a little about this. I know how to elegantly encode requirements like Swappable<T, U> but I'll save that for another post. :) Thanks for the encouragement! I'll report again when I have made some progress. In the meantime, anyone who replies to me privately is welcome to have access to the sources. -- chad
"Chad Parry" <spam@chad.parry.org> writes:
"Douglas Gregor" <doug.gregor@gmail.com> wrote in message news:ECF14E7B-BC49-4021-9828-A1EF57C862E9@cs.indiana.edu...
On Aug 20, 2006, at 11:48 PM, David Abrahams wrote:
[snip]
Well, it looks really interesting (really!), but I think you should review the ConceptC++ publications, in particular N1849, before investing more time in it. Also, IMO, you should try to model the standard concepts and see how it works out in practice.
I strongly suggest that we focus on the latest concept proposal, N2042. N2042 is the result of countless hours of discussions among the authors of the two different concepts proposals, and it is the only concepts proposal that will be moving forward.
You can find up-to-date information on the concepts proposals, compiler, etc. on the ConceptC++ home page:
That's exactly the kind of feedback I was hoping for. I'll focus more of my attention on these items you brought up: 1) Try to mimic the declarative syntax rather than the use pattern syntax. (There's probably no reason why both can't be supported simultaneously in a library solution like this.)
Whew; good luck with that one!
2) Require authors to declare that their types model a concept; don't assume matches based on syntax. Allow for concepts to be declared with the opposite default behavior if they wish.
That's might not be the best idea if you want the checker to be useful with C++98 generic libraries, which as a rule, don't make that requirement. Don't forget, when C++0x comes along, we'll have language support and a library solution won't be worth much.
3) Try to make the errors user-friendly. 4) Add support for associated types. (I've already thought a lot about this and it won't be too hard.)
Why don't you start with what I've already done to the library and work from there? I have already done quite a lot to improve the error messages and support associated types. It would be a shame to reinvent those wheels. Plus, we have a large suite of working concept checking templates based on real-world use cases (e.g. STL). As I implied in an earlier post, no matter how clever your system, if it doesn't handle the existing use cases well, it's a non-starter.
5) Improve the user experience for signatures that are known to be undetectable by library code. This includes the DefaultConstructible<T> concept, for example. I've already thought a little about this. I know how to elegantly encode requirements like Swappable<T, U> but I'll save that for another post. :)
One can do it, but I'm not sure it's really _worth_ doing. It's going to be at least a little inconvenient for users. It's almost impossible to get people to use concept checking _today_, despite its many benefits. I think you need to take care not to add too many barriers if you want your ideas to be adopted. -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (3)
-
Chad Parry -
David Abrahams -
Douglas Gregor