Re: [boost] [guidelines] why template errors suck

Subject: Re: [boost] [guidelines] why template errors suck
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2010-11-26 00:39:22

AMDG

On 10/31/2010 7:48 PM, David Abrahams wrote:
> At Wed, 13 Oct 2010 10:09:39 -0700,
> Steven Watanabe wrote:
>> Sorry for the delayed response.
> Back atcha!  Been looking forward to getting back to this thread.

Me too, although I'm starting to feel like we're
going in circles.

>>> // A shorter way. Because of refinement, this one will only get
>>> // used when either S1 or S2 is empty.
>>>
>>> template<FusionSequence S1, FusionSequence S2>
>>>     // a constraint you could add for clarity, but don't need
>>>     // requires SameType<int_<0>, int_<S1::size_type()*S2::size_type()>   >
>>> concept_map LessThanComparable<S1,S2>
>>> {
>>>       constexpr operator<(S1 const&, S2 const&)
>>>       { return S1::size_type()<   S2::size_type(); }
>>> }
>> Isn't the extra constraint needed to make sure
>> that trying to compare sequences whose elements
>> are /not/ LessThanComparable won't silently misbehave?
> I see what you mean; I overlooked that issue.  Technically the correct
> answer is that I guess it depends on your desired semantics; as I
> coded it, it would mean
>
>    make_tuple(1, 2)<  make_tuple("a", "b", "c")
>
> is that misbehavior?  Well, I guess it's not what tuple is currently
> specified to do, so maybe it is.

I would find this behavior very surprising.
Anyway, this isn't really related to the main
discussion, so I'll leave it at that.

>>> template<NonEmptyFusionSequence S1, NonEmptyFusionSequence S2>
>>>     requires LessThanComparable<S1::front_type,S2::front_type>
>>>           &&   LessThanComparable<S1::next_type,S2::next_type>
>>> concept_map LessThanComparable<S1,S2>
>>> {
>>>       operator<(S1 const&   x, S2 const&   y)
>>>        { return front(x)<   front(y) || pop_front(x)<   pop_front(y) }
>>> }
>> Okay.  Here's why I don't like this.
>>
>> Suppose that I define a second algorithm with
>> exactly the same requirements.
> So the first algorithm is fusion::less.  If you accept the above
> concept_maps, fusion::less would just look like:
>
>       template<FusionSequence S1, FusionSequence S2>
>         requires LessThanComparable<S1,S2>
>       bool less(S1 const&  x, S2 const&  y)
>       {
>           return x<  y;
>       }
>
>> As an example,
>> I'll use what fusion::less actually does.  (It doesn't
>> quite do a lexicographical comparison.  It truncates
>> to the length of the shorter sequence.)  This may
>> be slightly contrived, but I'm sure you'll agree that
>> there exist algorithms with identical requirements,
>> neither one of which can be easily implemented
>> in terms of the other.
> Granted.
>
> Okay, so that would be
>
>       template<FusionSequence S1, FusionSequence S2>
>         requires LessThanComparable<S1,S2>
>       bool what_fusion_less_actually_does(S1 const&  x, S2 const&  y)
>       {
>           ...
>       }
>
> Right?  Same requirements.

That "..." is exactly what I'm confused about.
The theoretical requirements are the same.
What I don't understand is how to capture them
in a concept in a way that allows both algorithms
to be implemented.  The concept_map for
LessThanCompareable that you show above
is tightly coupled to the implementation of
the algorithm.  In order to implement what_fusion_less_actually_does,
we need to iterate over the sequence and compare
the elements.  The requirements only tell us that
the two template parameters are FusionSequences
and that we can compare the sequences /as a whole/.
I don't understand how the concept_maps, as defined above,
allow you to deduce that the elements are LessThanComparable.
How can the compiler know that the specialization
for NonEmptyFusionSequence is going to be chosen?
Even if you overload what_fusion_less_actually_does
to handle NonEmptyFusionSequences, the concept_map
that we care about has other constaints.  I don't see
how the compiler can deduce from the fact that
some of the constraints for a particular concept_map
are satisfied, that the others must be as well.  Of
course, you and I know that there is no other concept_map
available, but how can the compiler know that?

Any part of this problem can be solved, but I don't
know how to solve all of it at once.  So, I'll try to
restate exactly what's needed.  I think this should
cover all the constraints that I've thought of so far.

* A concept LessThanComparable for fusion sequences
* An algorithm less, which does a full lexicographical
   comparison of two fusion sequences.
* An algorithm what_fusion_less_actually_does
    which does a lexicographical comparison of
    two fusion sequences truncated to the length
    of the shorter sequence.
* Both algorithms must have the signature
     template<FusionSequence S1, FusionSequence S2>
     requires LessThanComparable<S1, S2>
     bool f(const S1&, const S2&);
* The solution must be extensible to more algorithms
    with the same requirements.  Changing the LessThanComparable
    concept to accommodate a new algorithm is not
    acceptable.
* Corollary: The solution must not depend on special
    characteristics of the problem.  (e.g. having the concept
    produce a 0,1,-1 by comparing the two sequences
    up to the length of the shorter sequence is not acceptable.)
* LessThanComparable for the sequences does not
    have to be the same concept as LessThanComparable
    for the elements.  Splitting it into two concepts is permissible,
    since the two uses have different purposes in this context.
* "Exercises for the reader" are strictly prohibited.  I don't
    think I'm really going to understand this until I have it
    ironed out to the point where it could be run through
    a (hypothetical) compiler that supports concepts.

>> Now, suppose that I want to write a function
>> template<FusionSequence S1, FusionSequence S2>
>> void foo(S1, S2);
>> which calls both of these algorithms.  How can I
>> write the requirements for foo?
>       template<FusionSequence S1, FusionSequence S2>
>         requires LessThanComparable<S1,S2>
>       bool foo(S1 const&  x, S2 const&  y)
>       {
>           return less(x,y)&&  what_fusion_less_actually_does(x,y);
>       }

This would be wonderful, if there were a way to define
LessThanComparabe that makes this possible.
I don't know how to do it.

>> a) requires LessThanComparable<S1, S2>  &&
>> TruncatingLessThanComparable<S1, S2>
>>      Is every function template that calls foo also going to
>>      have to list both of these?  This is silly and makes foo
>>      difficult to change, because the concept requirements
>>      include extraneous information.  Remember that the
>>      two sets of types that model these concepts are the same.
>> b) Leave it with just FusionSequence.
>>      I hope this won't compile unless you have a concept_map
>>      LessThanComparable<FusionSequence, FusionSequence>
>>      which is a bad idea, as I explained above.
>> c) Somehow define a concept that allows both LessThanComparable
>>      and TruncatingLessThanComparable to be deduced.  This
>>      would be ideal, but I don't have the least idea how to accomplish it.
>> d) Something else I haven't thought of?
> I don't understand why you'd go down any of those roads.  Am I missing
> something?

I think we just haven't yet reached common ground on what
the problem I'm having is.

In Christ,
Steven Watanabe