C++ Logo

std-proposals

Advanced search

Re: [std-proposals] DR: concepts std::strict_weak_ordering / std::equivalence_relation must be resticted by semantic requirements

From: Nikl Kelbon <kelbonage_at_[hidden]>
Date: Sun, 7 May 2023 12:01:10 +0400
Your arguments may be broken easily with this:
#include <concepts>
#include <functional>
int main() {
   static_assert(std::strict_weak_order<std::equal_to<>, int, int>);
}

https://godbolt.org/z/3zaKb8cTM

We already have this in standard. Equal to already 'strict weak order'.

If you are saying ' The code should *not* compile.'

    void foo(strict_weak_order<int, int> auto);
    void foo(std::relation<int, int> auto);

So, if compiler now cannot decide which 'foo' more constrained, then this
'bar' overload set will not be invocable with 'equal_to<>'(ambigious)
void bar(std::strict_weak_order<int, int> auto);
void bar(std::equivalence_relation<int, int> auto);

Then i will demonstrate more real case of this problem with user defined
concepts.

template<typename T>
concept A = std::strict_weak_order<T, int, int> && std::copy_constructible<T
>;

template<typename T>
concept B = std::equivalence_relation<T, int, int>;
bool foo(A auto) { return true; }
bool foo(B auto) { return false; }
int main() {
    foo(std::equal_to<>{});
}
So, now we now, that compiler cannot decide that strict_weak_order >
equivalence_relation or else.
But here compiler MUST see ambiguity then, because it cannot decide
ordering on those concepts. But there are equal, so this code compiles
https://godbolt.org/z/GKzbxn93b

It seems like a logic error, those concepts are not equal, compiler cannot
decide which is more contrained, but compiler compiles this code as if
strict_weak_order --> equivalence_relation

About others:
I may propose to return 'std::weak_ordering' or better (strong ordering)
from predicates. It may solve problem atleast for types which are
std::partial_ordering(compiler will see atleast some errors) and add
contracts in concepts system like
concept equivalence_relation = relation<R, A, B> && contract(A a, B b) { a
== b -> b == a };
And for example compiler will add debug checks with asserts/ throw
/terminate where it sees foo(equivalence_relation<x, y> auto a);


сб, 6 мая 2023 г. в 20:02, Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>:

> On Sat, May 6, 2023 at 10:12 AM Nikl Kelbon via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>
>> Now (for compiler) std::strict_weak_ordering<...> is same as
>> std::relation<...>, and std::equivalence_relation is same as std::relation
>> This produces amgibuity:
>>
>> #include <concepts>
>> #include <functional>
>>
>> bool foo(std::strict_weak_order<int, int> auto x) { return true; }
>> bool foo(std::relation<int, int> auto x) { return false; }
>>
>> int main() {
>> foo(std::less{});
>> }
>>
>> I propose create a two different implementation concepts
>> strict_weak_order_sematic_requirement<R, T, U>
>> and
>> equivalence_relation_semantic_requirement<R, T, U>
>>
>> #include <concepts>
>> #include <functional>
>> // Must be different for equivalence_relation
>> template<typename...>
>> concept always_true = true;
>> template<typename T, typename A, typename B>
>> concept strict_weak_order_semantic_requirement =
>> always_true<T, A, B>;
>> template<typename T, typename A, typename B>
>> concept strict_weak_order = std::relation<T, A, B>
>> && strict_weak_order_semantic_requirement<T, A, B>;
>>
>> bool foo(strict_weak_order<int, int> auto x) { return true; }
>> bool foo(std::relation<int, int> auto x) { return false; }
>>
>> int main() {
>> foo(std::less{});
>> }
>>
>>
> This doesn't express a "semantic requirement"; it expresses a *syntactic*
> requirement — and the particular syntactic requirement it expresses is a
> no-op!
> So this would incorrectly allow me to write a caller like
>
> void foo(strict_weak_order<int, int> auto); // #1
> void foo(std::relation<int, int> auto); // #2
>
> foo(std::less<int>()); // OK, less is a strict weak order
> foo(std::equal_to<int>()); // Uh-oh! This calls foo #1, not foo #2!
>
> See https://godbolt.org/z/a56T49s8o
>
>
>> [...] this solves ambiguity in overload resolution(
>> https://godbolt.org/z/n7ovccf9n) and explicitly in code declares our
>> intensions.
>>
>
> That's the problem exactly: the code you've written actually *disguises*
> your intention, and quietly compiles as if `equal_to<int>` were a strict
> weak order. It's not. The code should *not* compile.
>
> Right now, strict_weak_order has both syntactic and semantic requirements
> — just like `std::copy_constructible`. When I write
> template<std::copy_constructible T> void bar(T t);
> I'm expressing my intent that the type not only have a copy constructor,
> but actually be copy constructible. `auto_ptr<int>` has a copy constructor,
> but it doesn't behave like one; it doesn't model the semantic requirements
> of `std::copy_constructible`. My use of a C++20 Concept in `bar` clearly
> expresses my *intent* that you shouldn't go instantiating `bar` with
> types like `auto_ptr`. Even if the code happens to compile, I don't
> *intend* to support semantically-non-copy-constructible types.
>
> When I write
> template<std::strict_weak_order<int, int> T> void foo(T x);
> I'm expressing my intent that the type not only have a call operator, but
> that it actually be a strict weak order. `equal_to<int>` has a call
> operator, but it doesn't behave like a strict weak order; it doesn't model
> the semantic requirements of `std::strict_weak_order`. My use of a C++20
> Concept in `foo` clearly expresses my intent that you shouldn't go
> instantiating `bar` with types like `equal_to`. Even if the code happens to
> compile, I don't *intend* to support semantically-non-strict-weak-order
> relations.
>
> So if you were to change the library to apparently permit things like
> "overload sets selecting between weak orders and relations," you'd be
> *destroying* the intent of the code. We'd end up with everything being
> quietly treated as a weak order, and people would be writing bugs all the
> time.
>
> May be in future implementation of this semantic concepts will be possible.
>>
>
> No, computer languages are invariably purely *syntactic*; there is no way
> to express *semantics* in a computer language except by tying it to
> syntax.
> (I've talked about how to reflect semantics in syntax in some previous
> talk. I think it was "The Best Type Traits C++ Doesn't Have" (2018)
> <https://www.youtube.com/watch?v=MWBfmmg8-Yo>, but I can't quickly find
> the timestamp in that talk, if it exists at all. Off-topic, I'm pleased to
> announce that Clang/libc++ now has two of those three. Uptake is slow, but
> it's happening. ;))
>
> For example, the iterator hierarchy does this:
> struct I1 {
> using iterator_category = std::input_iterator_tag;
> };
> struct I2 {
> using iterator_category = std::forward_iterator_tag;
> };
> `I1` will be treated as an input iterator. `I2` will be treated as a
> forward iterator. We can tell this at compile time by inspecting (
> *syntactically*) `I1::iterator_category` versus `I2::iterator_category`.
> There is no corresponding tag system for predicates. We could certainly
> imagine one — and you're welcome to propose it for standardization —
> struct Less {
> static constexpr bool is_regular_invocable = true;
> static constexpr bool is_strict_weak_order = true;
> };
> struct EqualTo {
> static constexpr bool is_regular_invocable = true;
> static constexpr bool is_equivalence_relation = true;
> };
> struct NotEqualTo {
> static constexpr bool is_regular_invocable = true;
> };
> template<class T>
> concept regular_invocable = invocable<T> *&& T::is_regular_invocable*;
> template<class R, class T, class U>
> concept equivalence_relation = relation<R, T, U> *&&
> R::is_equivalence_relation*;
>
> However, there are at least two massive problems that such a proposal
> would need to overcome.
>
> (1) `R::is_equivalence_relation` is not granular enough to support
> `std::equivalence_relation<R, T, U>`. It's totally possible for a relation
> to be an equivalence relation over one domain (T,U) but not over another
> domain (T,U). For example, `equal_to` is an equivalence relation over
> (error_code, error_code), but not over (error_code, error_condition). And
> yes, that particular example is purely due to terrible library design; but
> I suspect there are more realistic examples too, if you care to look for
> them.
> So this means we would need a syntactic flag something like
> template<class T>
> struct EqualTo {
> template<class, class> static constexpr bool
> is_equivalence_relation = false;
> template<> static constexpr bool is_equivalence_relation<T, T> =
> false;
> };
> template<class R, class T, class U>
> concept equivalence_relation = relation<R, T, U> *&& R::template
> is_equivalence_relation<T, U>*;
> That's getting really messy. Nobody would want to actually write that
> version of `Less`. And then if you want
> `EqualTo<float>::is_equivalence_relation<int, int>` to reflect reality,
> that would be a whole mess *imposed on the author of `EqualTo`*, which is
> a very high cost... and for what benefit? Just so that if you get it a
> little bit wrong, your calls to `ranges::unique` will annoyingly fail to
> compile? That is a *terrible* cost/benefit ratio.
>
> (2) We can't use the syntax `R::is_equivalence_relation` anyway, because *`R`
> will most often be a lambda* with no place to hang that tag. Lambda types
> are anonymous; none of your usual tricks (e.g.
> `std::relation_traits<R>::is_equivalence_relation`) will work for lambdas.
> We need somehow to enforce that
> [](int x, int y) { return x < y; }
> is treated as a strict weak order, and
> [](int x, int y) { return x <= y; }
> is not. That's *literally impossible*.
>
> So the current design — while weird — is pretty much the best we can do.
>
> HTH,
> Arthur
>

Received on 2023-05-07 08:01:26