DRY and higher trait bounds

help
1

Let's say I want to abstract over different bigint implementations (like given by the crates num, ramp and rust-gmp). I could come up with the following trait:

trait Integer:
    Sized + Eq + Ord + Clone
    + Add<Output=Self> + Sub<Output=Self> + Mul<Output=Self> + Div<Output=Self> + Rem<Output=Self> + Neg<Output=Self>
    + From<u64> + Hash
{
    fn zero() -> Self;
    fn one() -> Self;
    fn invert(&self, modulus: &Self) -> Option<Self>;
    fn powm(&self, exp: &Self, modulus: &Self) -> Self;
}

Unfortunately, this is not enough. I also need that the basic arithmetic operations are implemented for references as well. Things like &a + b, a + &b and &a + &b have to work. This leads me to trait bounds like the following on every function:

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
struct GcdResult<T> {
    /// Greatest common divisor.
    gcd: T,
    /// Coefficients such that: gcd(a, b) = c1*a + c2*b
    c1: T, c2: T,
}

/// Calculate greatest common divisor and the corresponding coefficients.
fn extended_gcd<T: Integer + Clone>(a: T, b: T) -> GcdResult<T>
    where
      for<'a, 'b> &'a T: Add<&'b T, Output=T>,
      for<'a> &'a T: Add<T, Output=T>,
      for<'a> T: Add<&'a T, Output=T>,
      for<'a, 'b> &'a T: Sub<&'b T, Output=T>,
      for<'a> &'a T: Sub<T, Output=T>,
      for<'a> T: Sub<&'a T, Output=T>,
      for<'a, 'b> &'a T: Mul<&'b T, Output=T>,
      for<'a> &'a T: Mul<T, Output=T>,
      for<'a> T: Mul<&'a T, Output=T>,
      for<'a, 'b> &'a T: Div<&'b T, Output=T>,
      for<'a> &'a T: Div<T, Output=T>,
      for<'a> T: Div<&'a T, Output=T>,
      for<'a, 'b> &'a T: Rem<&'b T, Output=T>,
      for<'a> &'a T: Rem<T, Output=T>,
      for<'a> T: Rem<&'a T, Output=T>,
      for<'a> &'a T: Neg<Output=T>,
{
    // Euclid's extended algorithm
    let (mut s, mut old_s) = (T::zero(), T::one());
    let (mut t, mut old_t) = (T::one(), T::zero());
    let (mut r, mut old_r) = (b, a);

    while r != T::zero() {
        let quotient = &old_r / &r;
        let mut tmp;
        tmp = r.clone(); r = old_r - &quotient * r; old_r = tmp;
        tmp = s.clone(); s = old_s - &quotient * s; old_s = tmp;
        tmp = t.clone(); t = old_t - quotient * t; old_t = tmp;
    }

    let _quotients = (t, s); // == (a, b) / gcd

    GcdResult { gcd: old_r, c1: old_s, c2: old_t }
}

These trait bounds have to be repeated for every function that is generic over Integer. Is there a way to include the constraints in the trait definition? Can it be automatized using macros?

If you want to play with the example given here, you can find the full code on Github.

3 Likes
2

You can write the where-clause in the trait definition, if you replace all the Ts with Self. Still not really pretty, but I don't think you can use macros there.

BTW, why do you put modular invert in the trait? Normally the inverse is computed by using the extended gcd, so you would get a circular dependency.

Also, maybe you can remove the cloning with std::mem::replace.

3

I tried that, but it does not work. Adding it to the trait works, but after removing the bounds from the functions I'm getting compiler errors along those lines:

src/main.rs:148:1: 176:2 error: the trait `for<'a> core::ops::Neg` is not implemented for the type `&'a T` [E0277]

That is because gmp provides a very efficient implementation of powm. num does not, so I had to implement it via the extended gcd. (The full code implements the discrete logarithm via brute force.)

Yes, but it does not improve performance. It does not require Clone though.

4

Last I checked, where clauses on a trait were not enforced, nor were they used by other code to work out what was/was not implemented for a given type.

I "solved" a similar problem with lots of associated types, but it was a huge mess and not something I really want to try again.

5

AIUI, only direct super traits are elaborated, and &Self: ... fall outside of that. I'd love to see that improved, as it seems perfectly natural that a required bound should be able to be assumed when the trait is used. https://github.com/rust-lang/rust/issues/20671

6

That seems really strange to me. Why does it not give an error or warning if it is ignored anyway? The current behavior to just silently fail is very confusing.

Thanks for the link!

7

Although it seems you still can’t reduce the per-function trait bound boilerplate to one trait, you can reduce it to two:

fn extended_gcd<T: Integer>(a: T, b: T) -> GcdResult<T>
    where for<'a> &'a T: IntegerOps<T>
{
    …
}

I sent you a pull request. See also rust-num/num#94.

2 Likes