Use type-trait to differentiate between concepts with different semantics but same syntax

[tomaszkam]

As the consequence of the resolving issue #19 the library now defines two concepts Relation<F,T> and StrictWeakOrder<F,T> (probably EqualityRelation<F,T> is also needed for unordered_map) that has different semantical meaning but share the same syntactic constrain.

As consequence the following statements according to concept relation defined in Concept TS:

1. StrictWeakOrder<F,T> subsumes Relation<F,T>
2. EqualityRelation<F,T> subsumes Relation<F,T>
3. Relation<F,T> subsumes EqualityRelation<F,T>
4. Relation<F,T> subsumes StrictWeakOrder<F,T>
5. StrictWeakOrder<F,T> subsumes EqualityRelation<F,T>
6. EqualityRelation<F,T> subsumes StrictWeakOrder<F,T> The last four relations of the concepts are pretty questionable.

This problem may be addressed by introducing models_strict_weak_order<F,T> and models_equality_relation<F,T> with default implementation that has BaseCharacteristic of true_type. The declaration of appropriate concept would look like follows:

template <class F, class T>
concept bool StrictWeakOrder() {
  return Relation<F, T>() && models_strick_weak_order<F,T>::value;
}

template <class F, class T>
concept bool EqualityRelation() {
  return Relation<F, T>() && models_equality_relation<F,T>::value;
}

Such resolution will eliminate the last four cases of subsuming relation, as constrainsmodels_strick_weak_order<F,T>::value and models_equality_relation<F,T>::value are unrelated. Returning true as default remove burden from the user.

In addition this trait may be left as implementation detail and wording could only say that implementation shall guarantee that the questionable subsume relation are not held. However exposing the trait provides a way to opt-out type that meets syntactical concept requirements from modeling concept with wrong semantic.

[ericniebler]

I'm no expert on concepts yet, but maybe @asutton can confirm the subsumption relationships you describe. Your solution seems reasonable.

[CaseyCarter]

I'll confirm them: per N4377 [temp.constr.order]/1:

A constraint P is said to subsume another constraint Q if, informally, it

can be determined that P implies Q, up to the equivalence of types and expressions in P and Q.

Two concepts with identical constraints trivially subsume each other.

On Wed, May 27, 2015 at 12:35 PM, Eric Niebler notifications@github.com wrote:

I'm no expert on concepts yet, but maybe @asutton https://github.com/asutton can confirm the subsumption relationships you describe. Your solution seems reasonable.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106006889.

Casey Carter

[ericniebler]

Crap. If only we had explicit concept refinement.

[ericniebler]

If we do add the traits, I'd prefer to see them defined as:

template <class F, class T, class U = T>
struct models_strict_weak_order : std::false_type {};

template <class F, class T, class U>
  requires Relation<F, T, U>()
struct models_strict_weak_order : std::true_type {};

Returning true for a type that doesn't even model Relation seems weird to me.

[tomaszkam]

What is wrong with defining using type_trait to represent the semantics requirements attached to syntatic one? For example ForwardIterator<I> could be defined as InputIterator<I> with allows_multiple_iteration<I>::value. And use of type traits:

• Provides a know way opt-in/opt-out a type.
• We have explicit mark that this concepts is more that syntax. Every binary regular function is relation.
• Work nicely with existing concept refinement syntax. If I have access to allows_multiple_iteration<I>::value I can write requirements for RandomAccessIterator without referring to InputIterator definition and this concept will keep their relation, Explicit concept refinement does not work if two independent set of concepts from libraries are merged - defining all appropriate concepts_maps is quadratic problem.

From beginning I considered prosing your solution, so only types fulfilling Relation returns true for models_strict_weak_order, but I was afraid that such approach would lead to chicken and egg problem for general usage of such solution. Although I do not have any specific example in mind.

Also I found it inconsistent that StrictWeakOrder does not requires CommonType but TotalltyOrdered does. The argument about metamathematical soundness applies to both.

[CaseyCarter]

The base template should probably cause a compile error or substitution failure, since it doesn't make sense to ask if a non-Relation models StrictWeakOrder. Doing so indicates a programming error:

template <...>
struct explicitly_opt_out_of_{StrongerConcept};

template <...>
  requires WeakerConcept<...>
struct explicitly_opt_out_of_{StrongerConcept} : std::false_type {};

[ericniebler]

Also I found it inconsistent that StrictWeakOrder does not requires CommonType but TotalltyOrdered does.

StrictWeakOrder refines Relation, which requires Common.

[tomaszkam]

The base template should probably cause a compile error or substitution failure, since it doesn't make sense to ask if a non-Relation models StrictWeakOrder.

Wouldn't this compiler error be generated during check of StrictWeakOrder<F,T> if wrong argument is passed?

Also I see nothing wrong in instigating models_strict_weak_order<F,T> (or other such tag in general) without relation. Consider writing implementation of this trait for call wrapper like reference_wrapper:

template<typename F, typename T, typename V = T>
struct models_strict_weak_order<reference_wrapper<F>, T, V> 
  : models_strict_weak_order<F, T, V>
{};

StrictWeakOrder refines Relation, which requires Common.

Your proposed implementation check heterogeneous version of the Relation even if only one argument is provided. Do we need to have specialization for 'models_strict_weak_order<F,U,U>' that will use Relation<F, U> instead of Relation<F, U, U> or this two concepts are equivalent?

[ericniebler]

Wouldn't this compiler error be generated during check of StrictWeakOrder<F,T> if wrong argument is passed?

Hard errors are to be avoided.

Your proposed implementation check heterogeneous version of the Relation even if only one argument is provided. Do we need to have specialization for 'models_strict_weak_order' that will use 'Relation' instead of 'Relation' or this two concepts are equivalent?

I would hope that Relation<F, T>() and Relation<F, T, T>() are equivalent. If they're not, it's a bug. It's possible that Relation<F, T>() is easier to check, in which case, a specialization of models_strict_weak_order<F, T, T> might speed up compile times, but it would strictly be an optimization -- unless there's some weird subsumption thing I don't know about.

[asutton]

None of these solutions work because we expect function pointers and lambdas to work with them. Explicit concepts won't help you here either.

If the subsumption problem is really a problem -- I'm not terribly worried about it myself -- then just drop those concepts. I only define them as a notational device.

Please don't try to standardize frameworks for declaring semantic properties. It's a rabbit hole. In fact, avoid them wherever possible. Prefer reasonable preconditions. On May 27, 2015 2:26 PM, "tomaszkam" notifications@github.com wrote:

The base template should probably cause a compile error or substitution failure, since it doesn't make sense to ask if a non-Relation models StrictWeakOrder.

Wouldn't this compiler error be generated during check of StrictWeakOrder<F,T> if wrong argument is passed?

Also I see nothing wrong in instigating models_strict_weak_order<F,T> (or other such tag in general) without relation. Consider writing implementation of this trait for call wrapper like reference_wrapper:

template<typename F, typename T, typename V = T>struct models_strict_weak_order<reference_wrapper, T, V> : models_strict_weak_order<F, T, V> {};

StrictWeakOrder refines Relation, which requires Common.

Your proposed implementation check heterogeneous version of the Relation even if only one argument is provided. Do we need to have specialization for 'models_strict_weak_order' that will use 'Relation' instead of 'Relation' or this two concepts are equivalent?

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106024435.

[tomaszkam]

None of these solutions work because we expect function pointers and lambdas to work with them. Explicit concepts won't help you here either.

For this reasons the traits are required to be true by default - so out of box, meeting Relation<F, T>() will imply StrictWeakOrder<F,T> being true. The addition of (by default always true) additional constrain is only aimed to affect subsumes relation of concepts.

[CaseyCarter]

The hard error is a non-starter: I had some confused notion about && short-circuiting and avoiding instantiation of the trait during constraint checking, which is most certainly not required behavior. I'm still in favor of substitution failure / unspecified behavior for the base template that keeps such opt-out traits from being useful instead of simply a way to opt out.

[asutton]

So it's only useful for class types? Sounds like a hack. On May 27, 2015 2:59 PM, "tomaszkam" notifications@github.com wrote:

None of these solutions work because we expect function pointers and lambdas to work with them. Explicit concepts won't help you here either.

For this reasons the traits are required to be true by default - so out of box, meeting Relation<F, T>() will imply StrictWeakOrder<F,T>. It is only aimed to affect subsumes relation of concepts.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106036551.

[tomaszkam]

The hard error is a non-starter: I had some confused notion about && short-circuiting and avoiding instantiation of the trait during constraint checking, which is most certainly not required behavior. I'm still in favor of substitution failure / unspecified behavior for the base template that keeps such opt-out traits from being useful instead of simply a way to opt out.

What about the forwarding call wrappers that wraps any function? Like the one in my example.

[tomaszkam]

So it's only useful for class types? Sounds like a hack.

As I said in orignal post:

In addition this trait may be left as implementation detail and wording could only say that implementation shall guarantee that the questionable subsume relation are not held.

And by questionable subsuming relation I mean:

1. Relation<F,T> subsumes EqualityRelation<F,T>
2. Relation<F,T> subsumes StrictWeakOrder<F,T>
3. StrictWeakOrder<F,T> subsumes EqualityRelation<F,T>
4. EqualityRelation<F,T> subsumes StrictWeakOrder<F,T>

Furthermore, the problems with lambdas and pointer types affects only concept related to using function all syntax. For all other it think having per-type setting is enough, so exposition of traits like allow_multiple_passes to distinguish ForwardIterators from InputIterators is not an hack.

[asutton]

Yeah. I know all that.

But having a standard facility that works for some types and not others is still a hack, and it's not a road we need to go down.

Like I said, I would be happier removing those those concepts than building some overly complicated framework that doesn't actually solve the problem. Although I note that the problem you describe doesn't reference any actual code, so I'm skeptical that the problem needs solving.

It's also worth noting that strict weak order and equivalence relation appear as preconditions in EoP. And the current standard. On May 27, 2015 3:26 PM, "tomaszkam" notifications@github.com wrote:

So it's only useful for class types? Sounds like a hack.

As I said in orignal post:

In addition this trait may be left as implementation detail and wording could only say that implementation shall guarantee that the questionable subsume relation are not held.

And by questionable subsuming relation I mean:

1. Relation<F,T> subsumes EqualityRelation<F,T>
2. Relation<F,T> subsumes StrictWeakOrder<F,T>
3. StrictWeakOrder<F,T> subsumes EqualityRelation<F,T>
4. EqualityRelation<F,T> subsumes StrictWeakOrder<F,T>

Furthermore, the problems with lambdas and pointer types affects only concept related to call-ability. For all other it think having per-type setting is enough.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106038230.

[tomaszkam]

Like I said, I would be happier removing those those concepts than building some overly complicated framework that doesn't actually solve the problem. Although I note that the problem you describe doesn't reference any actual code, so I'm skeptical that the problem needs solving.

In general the problem exists in STL2 for the ForwardIterator and InputIterator and was resolved using user provided iterator_category. It will also be present if ContigousIterator will be added in addition to RandomAccessIterator. If the problem reoccurs multiple time (now for functors) we should think of single consistent solution.

Maybe using a type trait is not a best way, it is best that I was able to present. I believe that the semantics information can only be received from the user and type trait is the way that we currently approach such problems (is_placeholder, is_bind_expression). But regardless if solution will be based on proposed trait approach, we need to have one.

[asutton]

Apples and oranges.

Why do you think this is needed? On May 27, 2015 3:58 PM, "tomaszkam" notifications@github.com wrote:

Like I said, I would be happier removing those those concepts than building some overly complicated framework that doesn't actually solve the problem. Although I note that the problem you describe doesn't reference any actual code, so I'm skeptical that the problem needs solving.

In general the problem exists in the current wording for STL2 for the ForwardIterator and InputIterator. I will also be present if ContigousIterator will be added in addition to RandomAccessIterator. If the problem reoccurs multiple time (now for functors) we should think of single consistent solution.

Maybe using a type trait is not a best way, it is best that I was able to present. But we need to have one.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106055099.

[tomaszkam]

Why do you think this is needed?

I do not have any specific case of code in mind. I just found it to be disturbing and misleading, that we will have EqualityRelation<F,T> and StrictWeakOrder<F,T> concepts defined in the standard, that are equivalent for overload resolution, while other pair of only semantically differentiable concepts for iterators is considered to be different. Would personally prefer to stay with Relation<F,T> if they will not be differentiable.

[ericniebler]

I can see that point of view. Some on the committee wanted StrictWeakOrder to make the algorithm constraints self-descriptive. It's more visible than a comment or a line in the documentation. I can also see that point of view. I have no strong feelings.

[asutton]

I do not have any specific case of code in mind. I just found it to be disturbing and misleading, that we will have EqualityRelation<F,T> and StrictWeakOrder<F,T> concepts defined in the standard, that are equivalent for overload resolution. Would prefer to stay with 'Relation'.

If there are no specific use cases, then it is clearly not necessary.

Like I've said, I would be okay removing those concepts. I am not definitely okay adding facilities that attempt to approximate them. However, the discussion about removing those concepts should not be a discussion on github's issue tracker. It needs to move to the L[E]WG reflector.

[tomaszkam]

One think that came to my mind. With the current definition, aren't following two declarations:

template<Range R1, Range R2, EqualityRelation<ValueType<R1>, ValueType<R2>> F>
bool equal_range(R1, R2, F f);
//use f(e1, e2) to compare elements

template<Range R1, Range R2, StrictWeakOrder<ValueType<R1>, ValueType<R2>> F>
bool equal_range(R1, R2, F f); 
//use !f(e1, e2) && !f(e2,e1) to compare elements
//the complement of strict weak order is equality relation

Considered to be redeclaration? [Edit: There are not.]

Having different constrain suggest that it is possible to write such code. My proposal would made them different, but calls would be ambiguous anyway, so no value is really added. Removing these constrains entirely will prevent attempts to write such code.

[sean-parent]

I think it is a good thing that overloads on EqualityRelation and StrictWeakOrder would cause a compile time ambiguity. We associate semantics with names - even when the syntax is identical. I do not see a need to introduce type functions to distinguish the two because one is not a refinement of the other and so there is no need to dispatch on the concept to a refined algorithm (unlike forward and input iterators).

On Wed, May 27, 2015 at 1:56 PM, Andrew Sutton notifications@github.com wrote:

I do not have any specific case of code in mind. I just found it to be disturbing and misleading, that we will have EqualityRelation<F,T> and StrictWeakOrder<F,T> concepts defined in the standard, that are equivalent for overload resolution. Would prefer to stay with 'Relation'.

If there are no specific use cases, then it is clearly not necessary.

Like I've said, I would be okay removing those concepts. I am not definitely okay adding facilities that attempt to approximate them. However, the discussion about removing those concepts should not be a discussion on github's issue tracker. It needs to move to the L[E]WG reflector.

— Reply to this email directly or view it on GitHub https://github.com/ericniebler/stl2/issues/36#issuecomment-106072229.

[tomaszkam]

I think it is a good thing that overloads on EqualityRelation and StrictWeakOrder would cause a compile time ambiguity.

Without addition of type trait, I think that this function will be considered to be redeclaration according to current rules. And if implementation will be provided for both them, the user will receive error about multiple definitions of is_equal, not about calls ambiguity, which will be misleading.

I have by mistake merged constrain equivalence that is used for redeclaration checking and functional constrain equivalence that is used for overload resolution. Discussed EqualityRelation and StrictWeakOrder are not considered to be equivalent, but only functionally equivalent. That means that my example with two is_equal overloads does not make sense - the behavior with and without the traits is equivalent.

[asutton]

I think it is a good thing that overloads on EqualityRelation and StrictWeakOrder would cause a compile time ambiguity.

Without addition of type trait, I think that this function will be considered to be redeclaration according to current rules. And if implementation will be provided from both them, the user will receive error about multiple definitions of is_equal, not that about calls ambiguity, which is misleading.

Overloading is defined in terms of the associated constraints, which are not normalized. So they would be distinct declarations, but ambiguous during overload resolution.

[ericniebler]

Nobody has asked for syntactic disambiguation of these concepts for a long time, and I was never convinced it was necessary. Closing.