Re: [boost] Report from Berlin C++ Standards Committee meeting

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-12 09:10:23

On Apr 11, 2006, at 4:31 PM, Paul Mensonides wrote:
>> However, we are busy working on a new proposal for concepts
>> that should be available in the near future. The new proposal
>> will have different syntax in several places and should have
>> greatly improved presentation.
>
> Okay, this is what I suspected--that a lot of the details exist  
> mostly in the
> collective minds of those close to the proposal.

... and scattered throughout various academic papers, presentations,  
tutorials, etc :)

> I really hope that is the case.  However, all examples that you've  
> shown seem to
> allow transitive compatibility--meaning f can call g without  
> listing the
> requirement for g if f and g both have the same requirements on  
> their operands
> (etc.).  I don't see how this could possibly work without binding g  
> at the point
> of f's definition--i.e. _not_ during the second phase.

Ah, this is the issue at hand. Yes, we change when and how names are  
bound. There are still two phases to
I'll use the lower_bound algorithm to illustrate how name resolution  
works:

   template<InputIterator Iter> void advance(Iter& x, difference_type  
n); // #1
   template<BidirectionalIterator Iter> void advance(Iter& x,  
difference_type n); // #2

   template<ForwardIterator Iter> where LessThanComparable<value_type>
   Iter lower_bound(Iter first, Iter last, const value_type& value)
   {
     difference_type n = distance(first, last);
     Iter mid = first;
     advance(mid, n/2); // we're concerned with this call...
   }

   template<RandomAccessIterator Iter> void advance(Iter& x,  
difference_type n); // #3

When we initially type-check lower_bound, we need to determine if  
there is an advance() that we can call. Both #1 and #2 have been  
seen, so we check them. Can we call #1? Sure, because every  
ForwardIterator is also an InputIterator. Can we call #2? Nope, our  
ForwardIterator is not guaranteed to be a BidirectionalIterator. So,  
we call #1 our "seed" function and use it for type-checking the  
template. Type-checking succeeds.

Now, let's consider what happens with this call to lower_bound:

   vector<int> v; lower_bound(v.begin(), v.end(), 17);

When instantiating a template that uses concepts, we don't perform  
the normal second phase lookup with ADL. Instead, we do a more  
limited lookup designed to make sure that instantiation cannot fail  
[*]. So, when we instantiate the call to advance() in lower_bound(),  
we start with our "seed" function #1. We then look for any other  
functions named "lower_bound" in the same namespace as our seed that  
are specializations of the seed, and add those functions to our  
candidate set along with the seed. This means that our candidate set  
will contain #1, #2, and #3. We perform normal partial ordering of  
function templates on this candidate set, then end up choosing #3.  
That's the behavior we want and expect: pick the best function when  
we instantiate.

        Doug

[*] Yes, instantiation can still fail if partial ordering of function  
templates returns an ambiguity. We can synthesize it all we want, but  
it has yet to actually bite us in practice.