Re: [boost] [range] How to extend Boost.Range?

From: David Abrahams (dave_at_[hidden])
Date: 2005-09-11 05:29:29

"Eric Niebler" <eric_at_[hidden]> writes:

> David Abrahams wrote:
>> "Eric Niebler" <eric_at_[hidden]> writes:
>> 
>>>><quote> 
>>>>
>>>>
>>>>>is also well formed and has the same meaning:
>>>>>
>>>>>    using namespace unspecified-namespace;
>>>>>    boost_range_begin(x);
>>>>
>>>></quote>
>> 
>> 
>> That doesn't look right to me.  First of all, it seems to me that
>> telling users that
>> 
>>      using namespace unspecified-namespace;
>>                      ^^^^^^^^^^^^^^^^^^^^^
>> 
>> is well-formed is next to useless.  How is a user supposed to satisfy
>> that requirement?  Am I missing something?  
>
>
> It's not useless. It's saying that there exists a namespace such that 
> after you make its symbols visible via a using declaration, an 
> unqualified call to boost_range_begin(r) will, through the magic of ADL, 
> be equivalent to boost::begin(r), for all types R that satisfy the Range 
> concepts -- even if R has no associated namespaces, like int[5]. The 
> implication of the requirement is that in order to satisfy the Range 
> concept, users must define a boost_range_begin() overload that can be 
> found via ADL.

Or, they can somehow put it in unspecified-namespace, whose identity
we're not telling them.  Or they can put it in the global namespace,
as long as it's been seen before the point of use, but I don't think
we want to encourage them to try that, for the same reason we don't
want to encourage them to put it in boost::.

I understand where you're going with this, but:

  1. I think the thread of implication is a too hard to derive without
     your guidance

  2. I'm afraid it might tempt users to try an incantation other than
     boost::begin(x) to get the begin iterator of x.

  3. It might be too strict if explicit specialization of boost::begin
     works (whether it will work probably depends on whether
     boost::begin itself is overloaded).

  4. It overemphasizes a detail that most of the audience for the
     concept definition doesn't need.

> I put the using declaration in the requirement because without it, users 
> might rightly wonder how a type such as int[5] could fulfill this 
> particular requirement. 

Yeah, that's the same reason I have been saying we need to tell them
in detail about boost::begin() in a way that makes it clear.  If we do
it the way you're suggesting, even it were possible to divine that
int[5] is a range just by reading the reference docs, we'd still need
to somehow describe the effects of boost::begin on it so that a reader
knows what its begin iterator is (in principle it could be anywhere in
the array).  So why not simply document that there exists in namespace
boost:

    template <class T, std::size_t N>
    T* begin(T(&x)[N])

with semantics

    return &x[0];

??

> The using declaration gives implementers the leeway to put
> boost_range_begin() someplace besides global scope, and it also
> gives them the leeway to call that namespace whatever they like
> without having to tell you.

That makes sense now, but still doesn't seem right for reasons listed
above.

> Now, if we want to allow users to make a type like unsigned short * 
> satisfy the Range concept, we might want to change 
> "unspecified-namespace" to "implementation-defined-namespace" so that 
> they don't have to put their overloads at global scope. *shrug*

In that case we would have to simply define the namespace and put
_that_ in the docs.  After all, we can't count on the C++
implementation to tell us which one to use ;-)  And if you're thinking
of how it would look in a standards proposal, why wouldn't we want
users to be able to make that short* model Range portably?  I think
the namespace had better be defined by the spec.

>> Secondly, and I could be wrong, but I don't think that statement can
>> be true for some of the types modeling range.
>
> Really?

Maybe I was indeed wrong ;-)

>>>If you want to treat a type as a range, you need to include the file
>>>that makes that type a conforming range. I don't see any problem
>>>with that.
>> 
>> 
>> I do.  Does the type satisfy the concept or doesn't it?  Normally,
>> that question is (and should be) answerable based on the visibility of
>> the type alone.  
>> 
>
> Why? We've already committed ourselves to letting users satisfy the
> Range concept non-intrusively through the use of free functions and
> ADL.  The user can put those free functions anywhere she feels
> like. If they're visible, bingo! the type is a range. If not, it
> isn't. 

Exactly.

> That leads directly to the situation Thorsten describes --
> that in one translation unit, a type may satisfy the concept and in
> another it may not. If you have a problem with that, then you have a
> problem with non-intrusively satisfying a concept. Frankly, I still
> don't see it as a problem.

I am uncomfortable with documenting that the standard containers
already model Range if it is really dependent on whether a particular
header has been #included.  That's a different question.  In that
case, the library is supposedly delivering "Range-ness."

> <snip>
>
>> 
>>>Of course. And I'm saying that for a type to conform to the range 
>>>concept, it must do more than ensure that boost::begin(), boost::end(), 
>>>and boost::size() are well-formed and have the proper semantics. 
>> 
>> 
>> Aside from defining the correct traits to deduce the return types of
>> these functions, that's all it must do.  Concepts are for describing
>> the requirements of generic algorithms.  
>
> Ah, now I understand the disconnect. From the perspective of someone
> writing a generic algorithm, you're right, that's all that's
> necessary.  But what of the person trying to /satisfy/ the Range
> concept for their type? We're telling them that they need to
> overload boost_range_begin() et al., but they're looking at the
> Range concept and wondering how that gets them any closer.

We can hold their hands in the tutorial documentation and explain
everything in some detail.  The reference docs should be almost-
minimal and complete.  If you find out that boost::begin() has to work
for your type, you can go look at the description of that function and
see what's required.  This is no different from the iterator concepts
(incomplete C++98 iterator documentation aside) saying that

      std::iterator_traits<T>::value_type

must yield the value type of the iterator.  Then you go look at the
docs for iterator_traits and find out that you can put value_type in
your iterator class' body.  In case you're going to object that the
user could always specialize iterator_traits without looking at its
docs, don't forget that it could in principle have default template
arguments that make any given specialization fail.  So you really do
need to look at its docs.

> You're saying a Concept should not describe how it should be
> satisfied, just how it should be used. Is that right?

It should describe both, but it's okay if the former is not spelled
out all in one place, and I find the approach I'm suggesting to be
more understandable than yours.

>> I think the correct approach is to document what boost::begin()
>> et. al do.  After all, for a specific concrete type the user could
>> explicitly specialize boost::begin() et al.  There's no need to
>> provide an ADL overload.
>> 
>
> As the Perl guys say, "There's more than one way to do it!" But I don't 
> like Perl. :-P 

Me too.

> I like there to be one sanctioned way to do something. 

Me too.  "Minimal constraints on models" is a fundamental principle of
generic programming, but I wouldn't be surprised if, once we think
through the implications of explicit specialization of begin et. al.,
we will find that allowing explicit specializations to work will
unduly constrain implementations of the Range library.

> And I was going on the assumption that the Concept's requirements
> would be the final word on how to use *and* satisfy the Concept. But
> maybe I'm wrong.

You're not wrong; this is a question of how to approach delivering
that information.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com