Where do generics get complex enough to consider trait objects?

I'm doing some exercises to learn the mindset required to code in rust, And I had a few problems understanding the limits up to which we can push generics, and where to prefer trait objects or enums instead.
As @Phlopsi said here, there are of course trade-offs; I don't care much about binary size and privacy; so performance and flexibility are what we need to optimize here, but we're gonna have to pay for it with increased complexity.
I've been working on a small symbolic math library as an exercise to learn rust better, and I feel like I've reached some dead ends with generics.
I'm pretty sure there's something wrong with my mindset here, cuz it feels like I'm still bound to the Object Oriented mindset and handling abstract interfaces like I do in C#; but the problem is that generics seems to spread like a virus in my codebase.

Consider the following :

pub trait VectorSpaceElement: Sized + PartialEq + Copy + Neg<Output = Self>
    + Add<Self, Output = Self> + Sub<Self, Output = Self>
    + Mul<Self, Output = Self> + Div<Self, Output = Self>
    + AddAssign<Self> + SubAssign<Self> + MulAssign<Self>
    + DivAssign<Self> { }
impl VectorSpaceElement for i8 {}
impl VectorSpaceElement for i16 {}
impl VectorSpaceElement for i32 {}
impl VectorSpaceElement for i64 {}
impl VectorSpaceElement for f32 {}
impl VectorSpaceElement for f64 {}
impl VectorSpaceElement for i128 {}
impl VectorSpaceElement for isize {}
#[derive(Clone, PartialEq, Debug)]
pub struct Symbol {
    name: String,
}
impl Symbol {
    pub fn new(name: &str) -> Self {
        return Self {
            name: name.to_string(),
        };
    }
}
impl Display for Symbol {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        return f.write_str(&self.name);
    }
}

pub type SymbolMap<TResult> = Box<dyn Fn(&Symbol) -> Option<TResult>>;
pub trait Expression {
    type SimplifyOutput: Expression;
    type EvaluateOutput: Expression;
    fn simplify(&self) -> Self::SimplifyOutput;
    fn evaluate<TResult: VectorSpaceElement>(
        &self,
        map: SymbolMap<TResult>,
    ) -> Self::EvaluateOutput;
}
impl<Element: VectorSpaceElement> Expression for Element {
    type SimplifyOutput = Element;
    type EvaluateOutput = Element;
    fn simplify(&self) -> Self::SimplifyOutput {
        self.clone()
    }
    fn evaluate<TResult: VectorSpaceElement>(&self, _: SymbolMap<TResult>) -> Self::EvaluateOutput {
        self.clone()
    }
}
#[derive(Clone, PartialEq, Debug)]
pub enum SymbolOrValue<Value: VectorSpaceElement> {
    Symbol(Symbol),
    Value(Value),
}
impl<Value: VectorSpaceElement> Expression for SymbolOrValue<Value> {
    type SimplifyOutput = Self;
    type EvaluateOutput = Self;
    fn simplify(&self) -> Self::SimplifyOutput {
        return self.clone();
    }
    fn evaluate<TResult: VectorSpaceElement>(
        &self,
        map: SymbolMap<TResult>,
    ) -> Self::EvaluateOutput {
        return self.clone();
    }
}
impl Expression for Symbol {
    type SimplifyOutput = Self;
    // This is where I'm beginning to get into trouble
    type EvaluateOutput = SymbolOrValue<VectorSpaceElement>;
    fn simplify(&self) -> Self::SimplifyOutput {
        return self.clone();
    }
    fn evaluate<TResult: VectorSpaceElement>(
        &self,
        map: SymbolMap<TResult>,
    ) -> Self::EvaluateOutput {
        if let Some(value) = map(self) {
            return SymbolOrValue::Value(value);
        }
        return SymbolOrValue::Symbol(self.clone());
    }
}

The line below my comment is a compile-time error, because VectorSpaceElement is a trait and its size is not known during compile-time.
There are multiple workarounds using trait objects (I can of course put it in a Box), but if we want to stay on the generic path, then we're gonna have to make Symbol (and all its implementations, and everywhere it is used) generic too. Something like this :

pub struct Symbol<Value: VectorSpaceElement> {
    name: String,
    _phantom: PhantomData<Value>,
}
pub enum SymbolOrValue<Value: VectorSpaceElement> {
    Symbol(Symbol<Value>),
    Value(Value),
}
impl<Value: VectorSpaceElement> Expression for Symbol<Value> {
    type SimplifyOutput = Self;
    type EvaluateOutput = SymbolOrValue<Value>;
    fn simplify(&self) -> Self::SimplifyOutput {
        return self.clone();
    }
    fn evaluate<TResult: VectorSpaceElement>(
        &self,
        map: SymbolMap<TResult>,
    ) -> Self::EvaluateOutput {
        // And of course now we're gonna getting errors here
        // so we have to change the signature of 'evaluate' to use another associated type
        if let Some(value) = map(self) {
            return SymbolOrValue::Value(value);
        }
        return SymbolOrValue::Symbol(self.clone());
    }
}

Next stop, some operation traits (like BinaryOperation) and structs (like BinaryAddition) will be added, And they need to be implemented for each of the 4 combinations of Symbol and VectorSpaceElement, They sure can easily be implemented as generics too, but the fact that Symbol itself is generic is just going to add a whole lot of other generic parameters to those operations; and the story continues.

So my problem is, I don't exactly know where to draw the line ?
Where should I just say 'That's enough generics for now' and use a Box ?

When you have 5-line where clauses, I think it's time to back out.

Do you intend to support arbitrary user-supplied custom types? If you only need to support the primitive numeric types, then I suggest using a macro to generate non-generic impls for each.

I'd suggest that if this were for real use, you'd probably only want f64 elements. It looks like you're putting in a lot of extra complexity that may have no value for a real use case.

But here's the thing @kornel , When I have 5 lines of where clauses then it means changing back to trait object will face a lot of limitations; i.e. I'm gonna have to remove all my generic functions or 'Self' types in those traits.

And @droundy, in some cases you might want to evaluate Symbols with Vectors or Complex numbers (Which also implement VectorSpaceElement trait), so that trait is not just for numeric types, I only put those in this example.
And no, it's not for real use. Just an exercise.

I was kinda hoping to make complex compile-time types by adding, subtracting, multiplying and dividing all kinds of 'Expression's together.
So for example, a Symbol plus another Symbol would give you an 'BinaryAddition<Symbol, Symbol>', then adding that to a BinaryAddition<Symbol, i32> would give you BA<BA<Symbol, Symbol>, BA<Symbol, i32>>, then you'd evaluate and simplify the whole thing replacing your symbols with values and it would give you a simple numeric type, depending on what you replaced those Symbols with.

If that's not for real use then there are no definite answer. Consider Rust's cousin: C++. It has templates which are very similar to generics in Rust.

And there are an MFC (based on boxing) and WTL (templates based).

Both libraries from the very same developer (Microsoft), both are still supported, both have their proponents.

There are so many pro- and contra- involved that even if you do have a real-world use in mind it's not always easy to decide where to stop and switch from impl *Trait* to dyn *Trait* and without real-world use it's just impossible.

2 Likes

:thinking: So it's context based. That's what I've been afraid of, but thanks that answers my question.

This is the Rust way. It's a toolbox with a lot of tools in it. It can be hard to decide which tool to use, and often you really do not know if you have picked the right tool. What I have found is I quite rarely define my own generic structs ( not counting lifetime parameters ) but instead use dyn. IMO, most of the time dynamic dispatch is quite acceptable, except for container-type classes where you want maximal performance. If it turns out to be a performance problem, you can re-factor. Avoid premature optimisation, is my feeling.

1 Like