Pre-RFC core::ops traits for relational operators

language design
1

Motivation: In general, this helps building better DSLs for many applications, e.g., array processing, machine learning, numerics, SIMD, parallelism, etc.

For example, consider this APL example from 1962 that implements signum (return 0 if 0, -1 if negative, and +1 if positive) on arrays:

(x>0)-(x<0)

(that's all the code)

Here, x > 0 tests whether each element of an array is 0, returning an array containing 1s where this is true, and 0 where this is false`.

In C++, this signum function can be implemented in exactly this way, e.g., using Eigen or many other libraries for manipulating arrays.

Now try to implement signum for arrays in Rust using your favourite Rust library, e.g., ndarray, packed_simd, etc. Using packed_simd, x<0 would be x.lt(0), since SIMD vectors cannot implement PartialOrd.

Reference-level explanation: Add the following traits to libcore core::ops that get used to lower the relational operators:

  • LessThan for <
  • LessEq for <=
  • GreaterThan for >
  • GreaterEq for >=
  • Equals for ==
  • NotEquals for !=

These traits all follow the same pattern, exemplarily shown here for LessThan:

// mod core::ops 
trait LessThan<Rhs = Self> {
    type Target;
    fn less_than(&self, rhs: &Rhs) -> Self::Target;
}
impl<T: ?Sized + PartialOrd<Rhs>, Rhs: ?Sized> LessThan<Rhs> for T {
    type Target = bool;
    fn less_than(&self, other: &Rhs) -> bool {
        PartialOrd::lt(self, other)
    }
}

There is an implementation of this proposal by @CAD97 here: https://github.com/CAD97/rust/commits/cmp

Unresolved questions:

  • Would this change be technically possible? I think so, but not sure.
  • If so,
    • what would the drawbacks of making this change be?
    • are there any other motivating examples I should be aware of?
4 Likes
2

I don't know. It sounds like quite a mess that you can have the Ord::cmp and eg LessThan::less_than that do something else. That sounds like a terrible footgun to me and adds a lot of complexity.

1 Like
3

How is that possible? If you implement PartialOrd for a type, you can't implement LessThan for it because of the blanket impl, since those two would overlap, and vice-versa (if you implement LessThan for a type, you can't implement PartialOrd for it either).

4

Ah, sorry, I was writing faster than thinking. This still pollutes the core::ops module a bit, but if it's not possible to misuse this way, then it's probably fine.

1 Like
5

So unless I'm missing something with coherence, it shouldn't be possible (the blanket impl is there to try to achieve that, and it isn't default, so it is not specializable).

That is, for any given type, you have to choose between:

  • implementing PartialEq, and then you get ops::Eq, and ops:NotEq for free
  • implementing ops::Eq or ops::NotEq or both, but if you implement one of these, your type cannot implement PartialEq.

(and similar for PartialOrd)

For arrays, for example, a problem might be that you actually want a == b to either return a bool or another array, depending on context, and for the bool-returning impl to be PartialEq. I'm not sure whether that is worth pursuing, or what the best way to achieve that would be. We could make the "Target" type an input type, e.g., trait ops::Eq<Target, Rhs = Self> or similar, but that has other problems..

6

I'm skeptical that it's a net win to add new semantic meanings to these operators, mutually exclusive with the meanings they already have in all Rust code written today, unless there's some visible signal that we're switching meanings on purpose like a #[per_element_relops] macro.

This seems like a textbook example of a really common pattern I see with overloaded operator and numerics sugar proposals in general, so at the risk of scope creep, I think it's worth explicitly raising the broader question: Why do these operations require dedicated language syntax, and none of the other thousands of things we already have functions/methods for?

I often see it just assumed without argument (or even an explicit statement of the assumption!) that some kinds of code need operators or other dedicated syntax without any user-defined macros, or else Rust is just not a competitive language for them, but unlike async/await I've never seen anyone actually make the case for that. I'm totally on board with "building better DSLs" for numeric code, but why doesn't "building a better macro library" cover those cases? Am I just missing some common knowledge here?

5 Likes
7

Am I wrong or is specialization coming and will remove protections offered by blanket impls?

8

@atagunov: The impls need to opt-into being specializable (e.g. using the default impl syntax), and this impl does not do that.

@Ixrec

Why do these operations require dedicated language syntax, and none of the other thousands of things we already have functions/methods for?

No operator needs dedicated language syntax. But if you are going to argue that + is common enough to need special syntax, I can also argue that < is common enough to do so as well. Adding two arrays to produce a new array is as common to me as an element wise < operation that also produces a new array with the element wise results. This is IMO obvious to anybody using a programming language to do math, which is why pretty much most languages with good support for math (C++, Matlab, Julia, APL, Python, etc.) support this syntax.

If anything, the really odd language in the crowd is Rust. Some operators, like +, are purely syntactic, and the Add trait is used to customize their behavior in whatever way users want. For example, the standard library goes as far as using + to denote addition for integers, which is associative commutative, while also using + to implement string concatenation, which isn't associative commutative. That is, a T: Add is meaningless from the semantic point of view, and that is fine.

However, simultaneously, the standard library does not have a syntactic customization point for <. Instead, it has a pseudo-semantic customization point called PartialOrd, which requires some unspecified semantics (e.g. see https://github.com/rust-lang/rust/pull/53386 to get a feeling of how hard it is to achieve consensus on what PartialOrd "should" mean), but that does not actually guarantee any semantics. That is, at least as specified, T: PartialOrd is kind of meaningless as well, because users can implement PartialOrd to not denote any partial order, and that's actually safe and ok, and even if they attempt to implement a partial order, its unclear what's allowed and what isn't.

I'd see an RFC like this one as a language bug fix that turns < and similar operators into pure syntactic operators. If some users want to give them extra meaning, e.g., they can use a separate trait, like PartialOrd, to try to convey them that meaning. I personally think that making PartialOrd part of the language was a mistake, because the trait semantics aren't well thought, and such traits would have benefited from some "iteration" outside the standard library before being included, and then following a proper RFC process with peer-review. Fixing this is going to be at least a bit hacky, because of the need to preserve backward compatibility, but the blanket impl achieves that.

8 Likes
9

Ah, I wasn't consciously aware of this discrepancy before. Intentionally separating the "syntax traits" Add/Less/etc from the "semantic traits" like Eq/Ord does seem like a very good idea, and if we do that it immediately becomes natural that Ord methods have specific semantics but > is allowed to mean anything, so generic code should always prefer the Ord methods over Less methods or > operator.

In a vacuum I'd probably prefer to just not have some of these, but now I agree that what we've already stabilized makes this the least messy state we could plausibly migrate to.

10

In a vacuum I'd probably prefer to just not have some of these, but now I agree that what we've already stabilized makes this the least messy state we could plausibly migrate to.

I think that, to allow purely syntactic customizations of <, we are going to need to add something somewhere, so that's going to increase complexity.

I also thought a bit about what could we do if we could throw everything away, and re-do it now with the benefit of hindsight, and I ended up at exactly this proposal. For example, we could start with adding only syntactic traits, like LessThan for <. But many users want all the relational operators to "mean" a particular ordering, and implementing 6 traits is tedious and error prone. So chances are we would have added PartialEq and PartialOrd traits that, when implemented, come with blanket impls for the syntactic operators that do the right thing, just like in this proposal. So maybe this is the right way?

11

This is somewhat off topic, but I think you mean "commutative" rather than "associative" - I believe string concatenation is associative (s1 + (s2 + s3) is equivalent to (s1 + s2) + s3), but not commutative (s1 + s2 is not necessarily equal to s2 + s1).

1 Like
12

It's both not commutative and not associative in the current implementations, given (s1, s2, s3): (String, &str, &str) then (s1 + s2) + s3 works while s1 + (s2 + s3) fails with error[E0369]: binary operation `+` cannot be applied to type `&str`.

13

Oh, right, I see what you mean, thanks.

14

@jugglerchris FWIW I meant commutative. I've fixed it above, thanks!

@Nemo157 I think that the implementations of Add<String> for String is associative. However, there are also impls of Add<&str> for String and Add<String> for &str, and there is no Add<&str> for &str. I understand each of these as being different operations. Sure, these can all be called using the same + syntax, but I'm not sure whether talking about associativity across distinct operations makes sense. E.g. it would be like saying that addition is not associative because (1 + 3) * 4 returns a different value than 1 + (3 * 4) - that claim is not true because + and * are distinct operations, and so are IMO the different impls of Add. This is a blessing and a curse, e.g., it is, for example, what allows packed_simd to do vector * (scalar * scalar), where there are two different operations being performed with the same syntax: a vector * scalar product, and a scalar * scalar product.

2 Likes
15

C++ iostream is famous for "syntactic" use of operator overloading without regards for their semantics, and I don't think it went well.

C++ also ended up adding a spaceship operator, quite similar to Ord, to fix annoyances caused by separate overloads for <, >, etc.

Even if Ord/PartialOrd doesn't cover all use cases, having only one way to do the overload makes it easier to teach the language and understand code that uses overloading.

I think + overload for strings in Rust was a mistake. It's a narrow syntax sugar that only works sometimes. Rust is unique in splitting strings into owned/growable/borrowed flavors, so you can't think of + as a general string concatenation operator, but you should know the implementation behind it to understand what it maps to in what cases. Ownership complicates other clever overloads as well.

8 Likes
16

If Rust wants to enable more syntax sugar, I suggest allowing custom infix functions/operators, so that users can define their own new operators with their own semantics, without creating ambiguity around existing operators. a vecmul! b or a v* b or a \* b or a ⊗ b, etc.

7 Likes
17

I agree with << and >> in c++ being slightly confusing for new comers. I have seen quite a few questions about why using bitshift on an ostream does something.

I do like the idea of custom infix operators. However, that comes with severe parsing difficulties. Unless it was somehow "registerable" before parsing.

18

This would work terribly with #[derive(PartialOrd)] and generic impls.

In Python, numpy arrays do this kind of stuff with the comparison operators, and as a result it makes it impossible to use == on e.g. a dict that contains array values. The more nested your data structures are, the more complicated code you have to write just to work around this.

I for one am glad that when I need to write a unit test in rust, I can just use assert_eq! without a second thought.

3 Likes
19

The problem with syntax extensions that add new lexemes is that, in most cases, they complicate the language for all Rustaceans while providing little benefit. My initial foray into Rust was along this line, looking at adding lexemes for wrapping arithmetic operators for use with crypto code. But then I examined potential usage statistics within the compiler and the existing crypto code base on crates.io, and found that the new lexemes would replace at most 5% of the uses of the similar non-wrapping Rust operators.

For me the big issue with all such syntax-extension proposals is their justification: How much harder does the proposal make it to learn and use Rust for the average user, vs. how much benefit does it provide in actual code use? IMO the postfix try operator ? earns its weight. How many other proposed lexemes will be used frequently enough to justify the learning and parsing/recognition complexity that they impose on all Rust programmers?

3 Likes
20

PartialOrd is already used to overload the comparison operators directly. The same holds for ==/!= by PartialEq.

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a66154a5a780194d2729f206f5915c4f

If this weren't the case and these operators use (partial_)cmp directly, this proposal could hold more weight. As it is, since these operators already have an overload path, arguing for adding another one is going to take a lot of doing.

Yes, the purpose of this would be to genericize the comparison operators to return any type. But is this really desirable?

Rust so far has generally taken a position of "don't overload operators to do anything other than the obvious meaning that has been drilled into your head since elementary". This is, at least in part, pushback from programmers looking at the "symbol soup" code enabled by C++ (and Haskell).

"Should the comparison operators be limited to returning bool?" That's the question under discussion here. To note is that the mathematical operators do allow arbitrary output types, though they could have somewhat realistically required the output to be the lhs type.

I don't know what I think is the "morally correct" answer for the Rust language today. There is great read-first clarity in knowing _ < _ is always typed at bool within an inferred type context. But you can argue that it would be more consistent with the mathematical operators to have a trait for each operator with an associated output type.

Note that the OP example also requires bool - bool : {integer}, which I don't think would ever happen.

5 Likes