[concept] concept-based overloading (N2081)
Hello all, How do I use Boost.ConceptCheck and/or Bosot.EnableIf to implement concept-based overloading (as discussed in N2081)? For example, from N2081, the following functions are selected based on `Iter` matching one of the two specified concepts: template<InputIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { while (n > 0) { ++x; --n; } } template<BidirectionalIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { if (n > 0) while (n > 0) { ++x; --n; } else while (n < 0) { --x; ++n; } } How do I program this in C++ using Boost libraries? N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction... Please just point me to the documentation if this has already been addressed there. Thank you very much. -- Lorenzo
On 5/27/2010 10:38 AM, Lorenzo Caminiti wrote:
Hello all,
How do I use Boost.ConceptCheck and/or Bosot.EnableIf to implement concept-based overloading (as discussed in N2081)?
For example, from N2081, the following functions are selected based on `Iter` matching one of the two specified concepts:
template<InputIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { while (n> 0) { ++x; --n; } }
template<BidirectionalIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { if (n> 0) while (n> 0) { ++x; --n; } else while (n< 0) { --x; ++n; } }
How do I program this in C++ using Boost libraries?
N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction... Please just point me to the documentation if this has already been addressed there.
Thank you very much.
Do you mean the iterator_category / iterator_traversal metafunctions in boost/iterator/iterator_traits.hpp ? http://www.boost.org/libs/iterator/doc/iterator_traits.html template< class Iterator > typename boost::disable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator >::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for IncrementableIterator's
template< class Iterator > typename boost::enable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator >::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for BidirectionalIterator's
I think the primary way to currently effect "concept-based" overloading is via tags or similar metafunction-based methods. There do exist introspection techniques, though, such as proto's can_be_called or is_incrementable in boost/detail/, so it is possible to overload based on (some) syntactic properties. Is that what you're looking for? - Jeff
On Thu, May 27, 2010 at 1:48 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/27/2010 10:38 AM, Lorenzo Caminiti wrote:
N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction... Please just point me to the documentation if this has already been addressed there.
Do you mean the iterator_category / iterator_traversal metafunctions in boost/iterator/iterator_traits.hpp ?
http://www.boost.org/libs/iterator/doc/iterator_traits.html
template< class Iterator > typename boost::disable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator >::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for IncrementableIterator's
template< class Iterator > typename boost::enable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator >::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for BidirectionalIterator's
I think the primary way to currently effect "concept-based" overloading is via tags or similar metafunction-based methods. There do exist introspection techniques, though, such as proto's can_be_called or is_incrementable in boost/detail/, so it is possible to overload based on (some) syntactic properties.
Is that what you're looking for?
Essentially, the above code from Jeff got the job done for what I needed. I used `enabled_if` and tagging. Also thanks to everyone else for the very informative comments. -- Lorenzo
On 5/27/2010 12:57 PM, Lorenzo Caminiti wrote:
On Thu, May 27, 2010 at 1:48 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/27/2010 10:38 AM, Lorenzo Caminiti wrote:
N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction... Please just point me to the documentation if this has already been addressed there.
Do you mean the iterator_category / iterator_traversal metafunctions in boost/iterator/iterator_traits.hpp ? [...]
http://www.boost.org/libs/iterator/doc/iterator_traits.html
template< class Iterator> typename boost::disable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator>::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for IncrementableIterator's
template< class Iterator> typename boost::enable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator>::type, boost::bidirectional_traversal_tag >
::type advance(...) { ... } // for BidirectionalIterator's
I think the primary way to currently effect "concept-based" overloading is via tags or similar metafunction-based methods. There do exist introspection techniques, though, such as proto's can_be_called or is_incrementable in boost/detail/, so it is possible to overload based on (some) syntactic properties.
Is that what you're looking for?
Essentially, the above code from Jeff got the job done for what I needed. I used `enabled_if` and tagging.
Also thanks to everyone else for the very informative comments.
Just so an "inferior" approach isn't mistaken as the "correct" solution, Thomas is right, you should use tag-dispatching if possible: template< class Iterator > void advance_dispatch(..., boost::incrementable_traversal_tag) { ... } template< class Iterator > void advance_dispatch( ..., boost::bidirectional_traversal_tag) { ... } template< class Iterator > void advance(...) { advance_dispatch(..., typename iterator_traversal< Iterator >::type()); } And now that I've written this, I see this exact example is already elaborated on at the boost website: http://www.boost.org/community/generic_programming.html#tag_dispatching Sorry for any misdirection, - Jeff
On Thu, May 27, 2010 at 4:59 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/27/2010 12:57 PM, Lorenzo Caminiti wrote:
On Thu, May 27, 2010 at 1:48 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/27/2010 10:38 AM, Lorenzo Caminiti wrote:
N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction... Please just point me to the documentation if this has already been addressed there.
Do you mean the iterator_category / iterator_traversal metafunctions in boost/iterator/iterator_traits.hpp ?
[...]
http://www.boost.org/libs/iterator/doc/iterator_traits.html
template< class Iterator> typename boost::disable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator>::type, boost::bidirectional_traversal_tag >
::type
advance(...) { ... } // for IncrementableIterator's
template< class Iterator> typename boost::enable_if< boost::is_convertible< typename boost::iterator_traversal< Iterator>::type, boost::bidirectional_traversal_tag >
::type
advance(...) { ... } // for BidirectionalIterator's
I think the primary way to currently effect "concept-based" overloading is via tags or similar metafunction-based methods. There do exist introspection techniques, though, such as proto's can_be_called or is_incrementable in boost/detail/, so it is possible to overload based on (some) syntactic properties.
Is that what you're looking for?
Essentially, the above code from Jeff got the job done for what I needed. I used `enabled_if` and tagging.
Also thanks to everyone else for the very informative comments.
Just so an "inferior" approach isn't mistaken as the "correct" solution, Thomas is right, you should use tag-dispatching if possible:
template< class Iterator > void advance_dispatch(..., boost::incrementable_traversal_tag) { ... } template< class Iterator > void advance_dispatch( ..., boost::bidirectional_traversal_tag) { ... } template< class Iterator > void advance(...) { advance_dispatch(..., typename iterator_traversal< Iterator >::type()); }
And now that I've written this, I see this exact example is already elaborated on at the boost website:
http://www.boost.org/community/generic_programming.html#tag_dispatching
Great! The code from the Boost links above is _exactly_ what I was looking for. Thanks a lot. -- Lorenzo
At Thu, 27 May 2010 20:30:18 -0400, Lorenzo Caminiti wrote:
On Thu, May 27, 2010 at 4:59 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
And now that I've written this, I see this exact example is already elaborated on at the boost website:
http://www.boost.org/community/generic_programming.html#tag_dispatching
Great! The code from the Boost links above is _exactly_ what I was looking for.
Actually that example is missing one crucial detail: inheritance of tags matching the refinement hierarchy. The first few lines *should* read: struct input_iterator_tag { }; struct bidirectional_iterator_tag : input_iterator_tag { }; struct random_access_iterator_tag : bidirectional_iterator_tag { }; or, if you want to reflect the standard accurately, struct input_iterator_tag { }; struct forward_iterator_tag : input_iterator_tag { }; struct bidirectional_iterator_tag : forward_iterator_tag { }; struct random_access_iterator_tag : bidirectional_iterator_tag { }; That detail is what allows us to avoid writing a separate version of advance_dispatch for forward iterators. -- Dave Abrahams Meet me at BoostCon: http://www.boostcon.com BoostPro Computing http://www.boostpro.com
On Thu, May 27, 2010 at 9:28 PM, David Abrahams <dave@boostpro.com> wrote:
At Thu, 27 May 2010 20:30:18 -0400, Lorenzo Caminiti wrote:
On Thu, May 27, 2010 at 4:59 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
And now that I've written this, I see this exact example is already elaborated on at the boost website:
http://www.boost.org/community/generic_programming.html#tag_dispatching
Great! The code from the Boost links above is _exactly_ what I was looking for.
Actually that example is missing one crucial detail: inheritance of tags matching the refinement hierarchy. The first few lines *should* read:
struct input_iterator_tag { }; struct bidirectional_iterator_tag : input_iterator_tag { }; struct random_access_iterator_tag : bidirectional_iterator_tag { };
or, if you want to reflect the standard accurately,
struct input_iterator_tag { }; struct forward_iterator_tag : input_iterator_tag { }; struct bidirectional_iterator_tag : forward_iterator_tag { }; struct random_access_iterator_tag : bidirectional_iterator_tag { };
That detail is what allows us to avoid writing a separate version of advance_dispatch for forward iterators.
I see. I have modified the Boost example to follow what STL does as you indicated above. All seems to be working well. Thanks a lot. -- Lorenzo
Lorenzo Caminiti wrote:
Hello all,
How do I use Boost.ConceptCheck and/or Bosot.EnableIf to implement concept-based overloading (as discussed in N2081)?
You can't, at least with the current ConceptCheck design. It would be possible to use SFINAE for expressions to do something similar, but expressions need to be present in declarations for that, and the concept definition system is based on the definition of a function; it would need to use a more per-expression macro-heavy syntax to support that kind of thing.
For example, from N2081, the following functions are selected based on `Iter` matching one of the two specified concepts:
template<InputIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { while (n > 0) { ++x; --n; } }
template<BidirectionalIterator Iter> // proposed concept syntax (not C++) void advance(Iter& x, Iter::distance_type n) { if (n > 0) while (n > 0) { ++x; --n; } else while (n < 0) { --x; ++n; } }
How do I program this in C++ using Boost libraries?
That case is quite trivial, you can simply use the iterator_category, no need to check whether the types fulfill special expressions.
N2081 briefly mentions this can be done in C++ using SFINAE, etc.
Using SFINAE, you can deduce at compile-time things similar to auto concepts, with a few caveats: access errors (private vs public) produce hard errors.
On Thu, May 27, 2010 at 1:38 PM, Lorenzo Caminiti <lorcaminiti@gmail.com>wrote:
How do I use Boost.ConceptCheck and/or Bosot.EnableIf to implement concept-based overloading (as discussed in N2081)?
How do I program this in C++ using Boost libraries?
N2081 briefly mentions this can be done in C++ using SFINAE, etc. I think I could use `enable_if` if I had some sort of `is_input_iterator` metafunction..
You pretty much need to use tag dispatching to be able to handle concept-based overloading with refinement of concepts, rather than straight SFINAE. The main reason for this is most easily shown with some pseudo code: // Imagine that these represent true overloads based on concepts void foo( forward_iterator it ); // foo 1 void foo( random_access_iterator it ); // foo 2 // SFINAE enable_if-style expressions template< typename T > typename enable_if< is_forward_iterator< T > >::type bar( T it ); // bar 1 template< typename T > typename enable_if< is_random_access_iterator< T > >::type bar( T it ); // bar 2 Now do "foo( some_std_list.begin() )". As you'd expect, foo 1 is called. Similarly, do "bar( some_std_list.begin() )". Again, as you'd expect, bar 1 is called However, what if you call "foo( some_std_vector.begin() );" foo 2 is of course called, but if you do "bar( some_std_vector.begin() )" your expression is now ambiguous since T is a random access iterator, which in turn is also a forward iterator via refinement. Both overloads are valid candidates with one no better than the other. The "foo" example works because foo 2 is a better match than foo 1, but with a basic SFINAE approach, that is not the case. The way the desired behavior is simulated in C++, as you are probably familiar with already, is tag dispatch, where the tags are related directly in C++ through inheritance, allowing the compiler to pick the better match via overload rules with regard to inheritance for the tag parameter. There are ways you can probably think of, avoiding tag dispatch, to get the overloads in the "bar" example to be picked as you'd like for this simple case, but it would be tough to make the overloads "future proof" with respect to unknown refinements and overloads that may be written at some later point in time. With tag dispatch, no such problem exists and writing overloads is still fairly intuitive. Unfortunately, even in C++0x, I personally do not believe that there is a better way to do this without tag dispatch. -- -Matt Calabrese
participants (5)
-
David Abrahams -
Jeffrey Lee Hellrung, Jr. -
Lorenzo Caminiti -
Mathias Gaunard -
Matt Calabrese