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: Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>
Date: Sat, 6 May 2023 12:02:19 -0400
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-06 16:02:33