Traits with generic references & associated types

My dream is this: I want to have traits AlgebraAdd<A,B,Output=C> etc. that mirror the standard operations, but where &self is some carrier/domain/"context" type which performs the algebraic operation with additional information that the "element" types might not have access to. (For example element types might be rug::Integer but the "algebra" might have context like a modulus that should be applied to all values).

So I naively set out and define:

pub trait AlgebraAdd<T,U> {
  type Output;
  fn algebra_add(&self, a: T, b: U) -> Self::Output;
}
pub trait AlgebraRem<T,U> {
  type Output;
  fn algebra_rem(&self, a: T, b: U) -> Self::Output;
}

I might want to start making a naive quotient ring that works over any base ring that has AlgebraRem.

pub struct NaiveQuotient<A,M> {
  domain: A,
  modulus: M,
}

(To make this concrete, the base ring might for example be univariate polynomials over the integers -- Z[X] -- so A might be UnivariatePolynomials<K> and M might be some specific polynomial in the form of Vec<K>.)

Now, basically what I want to have is this super-generic definition of addition on NaiveQuotient<A,M>:

impl<A,L,R,M,T> // Is it OK to have T only appear on the right-hand side of later type class constraints?
  AlgebraAdd<L,R>
  for NaiveQuotient<A,M>
where
  A: AlgebraAdd<L,R,Output=T> + AlgebraRem<T,???> // <- I've tried for<'a> AlgebraRem<T,&'a M> but then how do I refer to its ::Output?
{
  type Output = ???; // anything like <A as for<'a> ..>::Output doesn't parse.
  fn algebra_add(&self, a: L, b: R) -> Self::Output {
    let r = self.domain.algebra_add(a, b);
    self.domain.algebra_rem(r, &self.modulus) // <- most of my problems stem from wanting to pass this as a reference.
  }
}

(In general, for most of these types, I want to have at least AlgebraBinaryOp<T,&T,Output=T> or something similar.)

The introduction of &self.modulus (i.e. &M) seems to force me to introduce lifetimes, which is the first thing that confuses me. The AlgebraRem trait is defined in terms of generic parameters <T,U> (where U=&M just "happens" to be a reference here) -- how could there ever be an issue of worrying about the "lifetime" of U? What I want to say is that A fulfills the trait AlgebraRem<T,&M> where &M will "obviously" outlive my usage of the trait (i.e. the call to AlgebraRem::algebra_rem()) so the compiler shouldn't have to worry about it?

When I try to tell the compiler to not worry about it with for<'a> AlgebraRem<T,&'a M> I couldn't figure out how to refer to this type class' associated Output type, since now it's a family of types, not just one?

I might just be super confused. Any sort of input on where I'm going wrong or how to implement this would be appreciated.

Or even links to libraries that have already done this sort of stuff before.

The higher-rank trait bound A: for<'a> AlgebraRem<T, &'a M> is indeed the way to ask for an implementation that covers some "arbitrarily short" lifetime existing only inside the body of algebra_add, but as you've noticed, this doesn't play well with associated types, because there's no way of naming the specific short lifetime used to determine Output. The only way I can think of to get around this is to move the borrow into the signature of algebra_rem, so the compiler can see that the lifetime of that borrow can't influence Output:

pub trait AlgebraRem<T, U> {
    type Output;
    fn algebra_rem(&self, a: T, b: &U) -> Self::Output;
}

I don't know if that conflicts with something else you want to do with AlgebraRem.

1 Like

It's fine to add "extra" type parameters like T to an impl, as long as they are fully determined by the other parameters. This compiles:

pub trait AlgebraAdd<T, U> {
    type Output;
    fn algebra_add(&self, a: T, b: U) -> Self::Output;
}
pub trait AlgebraRem<T, U> {
    type Output;
    fn algebra_rem(&self, a: T, b: U) -> Self::Output;
}

pub struct NaiveQuotient<A, M> {
    domain: A,
    modulus: M,
}

impl<A, L, R, M, T, U> AlgebraAdd<L, R> for NaiveQuotient<A, M>
where
    for<'a> A: AlgebraAdd<L, R, Output = T> + AlgebraRem<T, &'a M, Output = U>,
{
    type Output = U; // anything like <A as for<'a> ..>::Output doesn't parse.
    fn algebra_add(&self, a: L, b: R) -> Self::Output {
        let r = self.domain.algebra_add(a, b);
        self.domain.algebra_rem(r, &self.modulus) // <- most of my problems stem from wanting to pass this as a reference.
    }
}

However, I wonder if you're writing the code you intend to write, given

There really is no situation in which the compiler will accept "this lifetime works; don't worry about it". The compiler, not you, is the one that actually picks lifetimes, so it has to know what the relationships actually are in order to do that. The borrow of self.modulus doesn't "obviously" outlive anything - it doesn't have to have any particular lifetime, unless you want to link it with a lifetime of Self::Output, which requires (at least) GATs. I can make that compile, too, but only with a M: 'static bound which is... probably? not what you want?

3 Likes

Thanks for the replies!

OK, I think I see my misunderstanding:

I was thinking of the type variables like this: given a generic trait that only works on a blank type U, with no lifetime or constraint (AsRef, Borrow, Copy, etc.), there was no way for that trait to actually extract or store a reference to U (barring any unsafe stuff?), thus it will always be "safe" to pass U=&T because the trait can only interact with a blank type U in a generic way. (Like how in Haskell there's really one possible implementation for foo :: X->X and that is foo x = x.)

But this is obviously wrong because there's nothing stopping an impl of that trait to say U: Borrow<X> and thus extract a reference it can store?

So a follow-up question: is there a way to achieve or express what I was originally thinking in Rust? E.g. pub trait Foo<X> where X: NoWayForAnyImplToStoreAReferenceToThis { .. }? To the point where the compiler would see Foo<&T> and be OK with it so long as this T outlives any call to Foo's associated functions? Or is that an insane question?

Yeah, I ideally want the AlgebraXXXXX<L,R> etc traits to be completely generic, because for some types it might be more efficient for the implement to take ownership of both arguments, in other cases both LHS and RHS might be references.

Yes! That's actually what I figured out / ended up doing after a couple of hours. Although I'm getting somewhat worried about the number of type variables and if the trick of adding more of them will continue to work when I start to implement generic algorithms (e.g. part of my dream is a default GCD(x,y) that magically works for univariate polynomials, Euclidean domains, element-wise on vectors over such, etc).

That's mostly correct, I think, but I'm going to take issue with some of it because I'm not clear on what you mean by "store" and "extract".

Let's take std::ops::Add as a simpler example:

trait Add<Rhs> { /* in std, Rhs defaults to Self but that's not relevant */
    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
}

We could write a function like this:

fn add_ref<'b, A, B>(a: A, b: &'b B) -> <A as Add<&'b B>>::Output
where
    A: Add<&'b B>,
{
    a + b
}

This signature is in a sense "maximally generic", because it accepts any 'b from the caller and makes no guarantees about what Output is. But this does mean that Output can contain 'b; for instance, someone could implement Add like

impl<'rhs> Add<&'rhs Foo> for Foo {
    type Output = (Foo, &'rhs Foo);
    fn add(self, rhs: &'rhs Foo) -> Self::Output {
        (self, rhs)
    }
}

Note that to write this I didn't need to make any assumptions about Foo - it doesn't have any Borrow or AsRef bounds or anything like that; just the fact that Rhs is a reference is enough for an impl to make use of that fact in its associated items. An impl (post monomorphization) always knows the concrete types of Self and all type parameters.

Now, if that's not what you want for add_ref, you can hoist the output type to a type parameter, and push the choice of 'b into add_ref itself:

fn add_ref2<A, B, O>(a: A, b: &B) -> O
where
    for<'b> A: Add<&'b B, Output = O>,
{
    a + b
}

This works for the same reason the previous version works: generics are chosen by the caller. So while the original add_ref had the caller choosing 'b and having to deal with whatever Output type that gave, with add_ref2 the caller chooses O and add_ref2 itself has freedom to pick 'b as long as it satisfies A: Add<&'b B, Output = O> (which is all lifetimes 'b, because of the bound, so the caller's "choice" of O is actually fully determined by A and B).

Note that add_ref2 is less generic than add_ref, because it's "easier" for a type to implement Add<&'some_specific_lifetime B> than for<'any_old_lifetime> Add<&'any_old_lifetime B>. add_ref2 can therefore call add_ref, but not the other way around. The tradeoff for this lack of genericity is a stronger guarantee: the Output (return type) is known not to depend on add_ref2's choice of 'b.

Both add_ref and add_ref2 are sensible function signatures that have their uses. One is not better than the other; it just depends on what you intend to do with them. There is an inherent tradeoff between genericity and guarantees; if you want to be maximally generic, you have to make do with guaranteeing next to nothing, like add_ref has to make do with whatever Output type it gets from choosing 'b, A and B.

Perhaps I'm rambling a bit. Are we on the same page so far?

Well... yes and no. If you don't want the trait impl to know what the type parameter is... just don't parameterize the trait at all:

trait Add {
    type Output;
    fn add<Rhs>(self, rhs: Rhs) -> Self::Output;
}

The obvious problem with this trait is that it's not possible to implement usefully, because no impl knows the concrete type of Rhs so you can't do anything interesting with it. The best you can do is delegate to another trait:

trait Add {
    type Output;
    fn add<Rhs: AddTo<Self, Output = Self::Output>>(self, rhs: Rhs) -> Self::Output;
}

trait AddTo<Lhs> {
    type Output;
    fn add(self, lhs: Lhs) -> Self::Output;
}

Now you can use Add as a generic bound with an Output that doesn't depend on the choice of Rhs, but when you go to write add_ref3, well, it doesn't help much.

fn add_ref3<'b, A, B>(a: A, b: &'b B) -> A::Output
where
    A: Add,
    &'b B: AddTo<A, Output = A::Output> // hmm...
{
    a.add(b)
}

You now have a guarantee that A::Output doesn't depend on the lifetime chosen for &B, but you still have to qualify that in a where clause anyway to guarantee that you can actually call add. So there is not an apparent advantage to doing this over the regular Add<Rhs> trait (that is, in the case where B is passed in; if add_ref3 can choose B, this has the same effect for a type parameter as add_ref2 had for a lifetime parameter).

2 Likes

Thank you so much for the detailed answers!

Right, so if my understanding is correct, a lot of the prickly stuff I'm having issues with stem from the fact that I am using associated types (and returning them)?

As for the Output type: the only reason I have it at all is due to a few rare edge cases that can fail, and where Output=Option<T> (or Result) instead of Output=T. Those are the only two types of Output I intend to use, either a plain (owned) type T or failure-or-T. (However (a) for most traits there is no failure condition, so it doesn't make sense to just fix it to Option<T>, and (b) all traits might have a failure condition (depending on parameters on Self), so I can't simplify by fixing it to T for certain traits.)

Is there a way to constrain implementations of associated types, or a way to tell Rust that a given associated type will never require a lifetime?

One thing I am considering is 2x the number of traits, like:

pub trait Algebra {
  type Element;
}
pub trait SafeAlgebraAdd<T,U>: Algebra {
  fn algebra_add(&self, T, U) -> Self::Element;
}
pub trait UnsafeAlgebraAdd<T,U>: Algebra {
  fn algebra_add(&self, T, U) -> Option<Self::Element>;
}

No, it's great. I'm an expert rambler:

If "exceptions" were a thing I would use that, because the only reason I have these associated types is for exceptional situations. (As far as I know catching panics come with very few guarantees in Rust, so it's not the True Way.) For example (trigger warning: math), in the "algebra" (context, Self, whatever) of point addition over an elliptic curve (EllipticCurve<K>): if the domain (K: another algebra) is a proper field, then there's really no need for any Option or Result in the output type for addition or scalar multiplication; it will always be well-defined. But if the domain is not a field (and this has use cases), even addition here might fail in a disastrous way, which I feel sort of forces my hand for the rest of the design. Or, simpler, how in any field the antisocial 0 ruins the interface for all the good non-zero law-abiding citizen-elements, forcing inv(x) and div(x,y) to return an Option or Result.


As for the &T vs T stuff: In most cares I don't want to concern myself in higher-level traits if types are references or owned (although ideally I'd like "at least one" operand to be owned), most of these traits simply defer down to sub-traits and in the end there's just a few base structs with implementations that cover all (or nearly all) 2^arity cases of ref-or-owned, like Add<&Self,Output=Self>, Add<Self,Output=Self> for both Self and &Self, as well as a few Add<i32,Output=Self> etc for efficiency (From<i32>::from() might be expensive).

Perhaps there is a super obvious way to take care of situations like this in Rust already too, I'm pretty green. Because it strikes me like a problem that wouldn't be uncommon? Yet I've seen several libraries use macros to do a billion implementations to cover the combinations. The basic situation is: the types are potentially "big" and not Copy-able, so if I have op(&T,&T) I need to do at least one clone(), but if at least one of the arguments is owned, I can do some operations in-place on that one and avoid creating a temporary.

The constraint Type: 'static does that, but doesn't directly solve your problem of how to refer back to it from behind a reference elsewhere. But consider again @trentj's solution, slightly rewritten:

impl<A, L, R, M, T, RemOutput> AlgebraAdd<L, R> for NaiveQuotient<A, M>
where
    A: AlgebraAdd<L, R, Output = T> + 
       for<'m> AlgebraRem<T, &'m M, Output = RemOutput>,
//     ^^^^^^^ Over any lifetime,   ^^^^^^^^^^^^^^^^^^ Output must unify
{
    type Output = RemOutput; // <--- The unified Output
    // Same thing (but more confusing IMO):
    // type Output = <A as AlgebraRem<T, &'static M>>::Output;
    fn algebra_add(&self, a: L, b: R) -> Self::Output {
        let r = self.domain.algebra_add(a, b);
        self.domain.algebra_rem(r, &self.modulus)
    }
}

This... doesn't actually guarantee Output: 'static, even. Maybe T or M has a limited lifetime that infects RemOutput, for some selection of concrete types. But it does imply that 'm doesn't infect RemOutput, since any matching type has to unify over all possible 'm. And as far as I can tell, that's all you actually need. (Edit: Err, ignore my abuse of your traits where I implement div and not rem; the point is it works as intended even when T infects RemOutput with a lifetime.)

They then asked if you were sure you were writing what you meant, and the conversation has continued. But are you also sure this doesn't do what you want? I could be missing something, but it seems like the solution to your OP to me.

2 Likes

Another possibility:

pub trait AlgebraDiv<T,U>: Algebra {
  type Error;
  fn algebra_div(&self, T, U) -> Result<Self::Element, Self::Error>;
}

impl AlgebraDiv for SomethingWithAZero {
  type Error = String; // Something that can instantiate
  // ...
}

impl AlgebraDiv for AWorldWithNoZero {
  type Error = std::convert::Infallible; // Can never be instantiated
  // ...
}

See the documentation for some discussion. You do still end up with unwrap or the like all over your infallible implementations.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.