Commutative multiplication and addition

[mqudsi]

I was surprised to learn that the implementation of core::ops::{Add, Mul} (keywords: addition, multiplication) is not automatically (and exclusively) commutative. This is often not a problem for cases where it is possible to both impl Mul<X> for Y and impl Mul<Y> for X, but this is not an option when generics are involved.

For example, this implementation of Mul allows multiplying Size by any basic number type (from num_traits), as in Size(12) * 2 or Size(42) * 1.0:

impl<T, U> Mul<U> for &Size<T>
where
    T: ToPrimitive,
    U: ToPrimitive
{
    type Output = Size<u64>;

    fn mul(self, other: U) -> Self::Output {
        // omitted
    }
}

but it is not possible to define an ergonomic and efficient inverse to support the commutative variant of the same operations (2 * Size(12) or 3.0 * Size(7)), because the following is illegal:

impl<T> Mul<Size<T>> for ToPrimitive
where
    T: ToPrimitive,
{
    type Output = Size<u64>;

    fn mul(self, other: Size<T>) -> Self::Output {
        Size::Bytes((self as u64 * other.bytes()) as u64)
    }
}

as the self parameter to the mul function results in an attempt to define a non-generic parameter with unknown size.

I would like to use this issue to sound out ideas to support commutative operations, at the very least for operations that are typically (read: mathematically) commutative, but would appreciate any insight or commentary that sheds light on anything I'm missing here first.

[burdges]

Your second block defines an operation on a trait object, but then attempts to consume that DST by value, and uses a syntax slated for deprecation: https://github.com/rust-lang/rfcs/blob/master/text/2113-dyn-trait-syntax.md You want:

impl<T,U> Mul<Size<T>> for U
where
    T: ToPrimitive,
    U: ToPrimitive,

[mqudsi]

I kind of got lost drafting the post, I think the point that I was trying to make is that no matter which way you approach it, it's not going to work due to language/design constraints. Your example would work great if ToPrimitive were defined in the same crate, but not in the case where it isn't.

I guess my real question is if there is (as a thought experiment) an alternative way that select operators could be implemented that wouldn't end up running into the restrictions on trait implementations.

[burdges]

I believe #2451 explains why everything works fine.

[ExpHP]

I would like to use this issue to sound out ideas to support commutative operations, at the very least for operations that are typically (read: mathematically) commutative,

Two words: Matrix multiplication.

[ExpHP]

Eight more words: string concatenation in the standard library, no less.

[ExpHP]

But more in the spirit of the thread, I think the closest one can get to making something like this work is by using a proc-macro to implement a DSL; You can replace all + and * operations in an expression with calls to a different trait that is implemented symmetrically for the types in a crate.

Alternative two: A newtype can be used:

pub struct Scale<T>(pub T);

impl Mul<MyType<U>> for Scale<T>
where MyType<U>: Mul<T> {
    ...
}

This second alternative scales just a bit better for cross-crate usage, but unfortunately I'm not certain that the ergonomical cost of using either of these workarounds offsets the benefits to the user.

[burdges]

Right, there is no problem with

impl<T> Mul<Size<T>> for u64
where T: ToPrimitive,

but if you replace the u64 with a U: ToPrimitive then you get an "error[E0210]: type parameter U must be used as the type parameter for some local type (e.g. MyStruct<U>)".

I think #2451 fixes this.

[ExpHP]

I do not think #2451 fixes this, as the Self type is uncovered.

Specifically it permits impls where:

• Any of:
  • Trait is a local trait (false)
  • All of
    • At least one of the types T0..=Tn must be a local type. Let Ti be the
      first such type. (true; T1 is local)
    • No uncovered type parameters P1..=Pn may appear in T0..Ti (excluding
      Ti) (false; T0 has an uncovered type parameter)

---

My suggestion for Scale was that this is a dedicated newtype solely for writing a multiplication in reversed order. It has zero benefits for ergonomics, only for readibility in places where a certain order is typically expected, by allowing somebody to write

Scale(2.0) * matrix
// as opposed to the unconventional form
matrix * 2.0

[mqudsi]

@ExpHP Exactly, and I think it's clear to everyone that the ergonomics of your distinct Scale type are not exactly ideal.

[hosford42]

Why can't there be a RevMul trait corresponding to an implementation of multiplication with the reverse handedness, similar to how Python uses __mul__ and __rmul__ to handle both commutative and non-commutative multiplication in a generic fashion? If Mul is implemented for two types, this is used; otherwise, the compiler searches for a RevMul implementation. This gets around the issue entirely, by making both hands generically implementable, but not requiring commutativity.

[hosford42]

Commutative multiplication would look like this:

use someone_elses_lib::OtherStruct;

struct MyStruct ...;

impl Mul<OtherStruct> for MyStruct {
    type Output = Self;
    fn mul(self, rhs: OtherStruct) -> Self::Output {
        ...
    }
}
impl RevMul<OtherStruct> for MyStruct {
    type Output = Self;
    fn rev_mul(self, lhs: OtherStruct) -> Self::Output {
        self.mul(lhs)
    }
}

OtherStruct doesn't need to know about MyStruct. And it shouldn't need to know about it to implement commutative multiplication.

(Edited for clarity.)

[RustyYato]

How would you desugar a * b to calls to mul or rev_mul without making it a breaking change to add an implementation of either Mul or RevMul? For context, currently a * b desugars to something like Mul::mul(a, b).

[hosford42]

I'm pretty new to Rust so I'll ask another question rather than directly answer yours: Is it not doable for the compiler to desugar differently based on context? It seems like something as fundamental as operator overloading should be worthy of some special treatment from the language.

[RustyYato]

It is possible to desugar things based on context, but I don't think anything besides closures and the newly minted async/await syntax do this. (and given how pervasive closures are and how async/await's ergonomic improvements over combinators, this is justified).

In this case the danger is something like this:

// crate A:
struct Foo;

// crate B:
struct Bar;

impl RevMul<crate_a::Foo> for Bar { ... }

// crate C

fn main() {
    let _ = crate_a::Foo * crate_b::Bar;
    // desugars to
    let _ = ::core::ops::RevMul::rev_mul(crate_a::Foo, crate_b::Bar);
}

Now, let's say that we desugar by precedence: first, we try Mul, then RevMul.

Now, crate_a implements Mul:

// crate A

// snip ...

impl<T> Mul<T> for Foo { ... }

// crate C

fn main() {
    let _ = crate_a::Foo * crate_b::Bar;
    // desugars to
    let _ = ::core::ops::Mul::mul(crate_a::Foo, crate_b::Bar);
}

Note that the desugaring changed! This is a breaking change, especially if Mul::Output != RevMul::Output. Similar problems happen in reverse if we change the order of precedence.

So if not precedence how should you decide which of Mul::mul or RevMul::rev_mul to use?

Keeping in mind:

• We don't want to make it a breaking change to implement Mul
• that if you really wanted to, you could create a proc_macro
• use methods and side step this issue entirely
• and that sugar doesn't need to cover 100% of cases. just the majority of actually used cases

[hosford42]

We don't want to make it a breaking change to implement Mul

If a use statement was required for the multiplication operator to take effect, adding an implementation for Mul wouldn't be a breaking change, would it? And then downstream users could use whichever implementation they preferred, or even switch them up on a scope-by-scope basis if the need arose. Of course, that has the drawback that it would make the compiler cease to be backwards compatible, meaning it couldn't be implemented until the next major version was released.

[RustyYato]

If a use statement was required for the multiplication operator to take effect, adding an implementation for Mul wouldn't be a breaking change, would it?

If that were true, yes it wouldn't be a breaking change, however you don't need to use std::ops::Mul; to use the operator sugar: playground

Of course, that has the drawback that it would make the compiler cease to be backwards compatible, meaning it couldn't be implemented until the next major version was released.

More egregiously, it would mean adding a Mul or RevMul implementation would be a breaking change. There are only a handful of traits that are like this now, and most are nightly only. The only one on stable that I'm aware of is Drop, but Drop is very special, in ways that are undesirable for operators.

[mqudsi]

I wonder if we can have a phantom marker that indicates a type opts out of a default implementation , eg

struct Foo {
    x: i32,
    _revmult: core::phantom::PhantomRevMul,
}

This would forbid an impl of Mul where Mul::Output != Self or Rhs != Self allowing the single Mul impl to provide both directions (or else just allowing the otherwise potentially conflicting Mul<Output=T> to be implemented).

This would prevent breaking backwards compatibility since changes to a type, including adding a phantom member, are breaking. It would mean an extra compiler-internal special trait (like Unsize) but it’s really more of an implementation detail than anything else. It does introduce a new paradigm for opting out of (or into) a behavior via composition rather than impl but again, it is influencing language-level rather than lib-level behavior (sugaring) so that doesn’t seem too egregious to me.

(Whether this particular behavior is a default opt-in for a future edition or not is a different story.)

Personally, I think the problem is with making Output an associated type. I think the cleaner solution would have been a Mul<X, Y> trait that would desugar only in case of no ambiguous impl, otherwise requiring explicit trait typecasting to use.

[burdges]

Associated Output types simplify type inference considerably. It's obviously unacceptable for expressions like (a * b) * c to so slow down compilation or force intermediate type declarations.

In practice, rust code should bless a specific primitive type around which it optimizes performance, not be polymorphic over primitive types. As a rule, one should prefer distinguished scalar types like the Scale proposed above over operations with primitive types anyways, so maybe pub struct Scale(pub u32); or whatever.

All this seems moot now but..

Rust could've placed the LHS and RHS on eaual footing by defining Mul and Add to take roughly a 2-tuple, like

pub trait Mul {
    type Output;
    fn mul(self) -> Self::Output;
}

Rust could've even made * create some specially typed tuple before invoking this method, like

pub struct MulOp<LHS,RHS> {
    lhs: LHS,
    rhs: RHS
}