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