Modelling mathematical structures with parameterized types

help
1

When modelling mathematical algebraic types (objects we would like to add, multiply, ...), it is quite common to use parameterized types. The classical examples are matrices: Since we don't want to add matrices of different shapes, we can make the shape part of the matrix type, so the compiler can help us avoiding mistakes (like adding a 2x2 and a 3x3 matrix). Since we might also need to create matrices of arbitrary shape at runtime, we also need an extra "dynamic matrix" type. When adding two dynamically shaped matrices, we need to check compatibility at runtime, and have to panic if their shapes mismatch. This is more or less how the Array<T,D> type from the ndarray crate works. D can be a fixed dimension like Ix2, or dynamic IxDyn.

What can we do however, when dealing with objects whose parameters cannot be determined by their data? Consider for example the "Integers modulo M" type. Here, the values can be represented by integers between 0 and M-1, and addition is normal integer addition, followed by the "modulo M" operation. Note that M really belongs to the type: "Integers modulo 2" and "Integers modulo 3" are considered completely different types, and I would never want to add values from one with the other. So it is very tempting to implement it this way:

struct IntMod<const M: i32>(i32);

impl<const M: i32> Add for IntMod<M> {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        IntMod((self.0 + rhs.0).rem_euclid(M))
    }
}

However, since M cannot be derived from the underlying data, I see no clever way to implement a dynamic version of that struct. Of course we can just move M from the type into the struct itself:

struct IntModDyn {
    x: i32,
    m: i32
}

impl Add for IntModDyn {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        if self.m != rhs.m {
            panic!()
        }
        IntModDyn {
            x: (self.x + rhs.x).rem_euclid(self.m),
            m: self.m
        }
    }
}

This however seems to be a complete waste of memory, as we just doubled the space usage of the struct. Also, I see no reasonable way to generalize IntMod<M> and IntModDyn into a single struct like Array<T,Ix2> and Array<T,IxDyn> are generalized by Array<T,D>.

Are there well known workarounds for this kind of situation?

2

For unifying

struct IntMod<const M: i32>(i32);

and

struct IntModDyn {
    x: i32,
    m: i32
}

you could follow an approach such as

#[derive(Copy, Clone, Debug)]
struct IntMod_<M: Modulus> {
    x: i32,
    m: M,
}

#[derive(Copy, Clone, Debug)]
struct ConstModulus<const M: i32>;

#[derive(Copy, Clone, Debug)]
struct DynModulus(i32);

trait Modulus: Copy {
    fn modulus(self) -> i32;
}
impl<const M: i32> Modulus for ConstModulus<M> {
    fn modulus(self) -> i32 {
        M
    }
}
impl Modulus for DynModulus {
    fn modulus(self) -> i32 {
        self.0
    }
}

type IntMod<const M: i32> = IntMod_<ConstModulus<M>>;
type IntModDyn = IntMod_<DynModulus>;

impl<M: Modulus> std::ops::Add<Self> for IntMod_<M> {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        // assertion most likely gets optimized away for the `IntMod` case using `ConstModulus`
        assert_eq!(
            self.m.modulus(),
            other.m.modulus(),
            "`IntModDyn` with mismatching moduli",
        );
        // TODO: think about whether overflow should be handled
        Self {
            x: (self.x + other.x).rem_euclid(self.m.modulus()),
            ..self
        }
    }
}
3 Likes
3

Well, if a value can be modulo an arbitrary m, there’s no other option than storing m in the value. Technically you could also deduplicate the m values by storing them out-of-line behind a pointer or other key, but that does not make sense when we’re just talking about a couple of bytes. At least unless you know you only need an eg. u8-sized key to a lookup table, but indirection is always costlier than no indirection all else being equal.

(Nb. The width and height of a dynamically sized matrix type cannot be just "deduced from the data", either, they have to be explicitly stored somewhere.)

If you want to store a lot of integers modulo the same m, then it can make sense to have a separate "IntModMArray" type that only stores m once. In some cases it might also be reasonable to have a "repository" of modular integers, stored in a hashmap keyed by m. And for the cases of a small m, it may of course make sense to have smaller (u16, u16) and even (u8,u8) types.

To be generic over types with either a static or dynamic modulus, you’d use a common trait that you impl for both kinds of types.

To reduce code duplication, it may make sense to represent both static and dynamic modulos using the same type family (ie. a generic type), by instead abstracting over the type of m and use a zero-sized type when the size is statically known, something like:

trait Modulus {
    fn m(self) -> u32;
}

/// Statically known m
struct Mod<const M: u32>;

/// Dynamic m
struct DynMod(u32);

impl<const M: u32> Modulus for Mod { 
    fn m(self) -> u32 { M }
}

impl Modulus for DynMod {
    fn m(self) -> u32 { self.0 }
}

struct ModularInt<M: Modulus> {
    val: u32;
    mod: M;
}
2 Likes
4

But if you want to do that dynamically, you need to store the modulus somewhere. This is exactly like saying that even storing x is a complete waste of memory. Obviously it isn't. Variables and struct fields and other places are for storing run-time data in memory. This is not a waste of memory, this is what it is for.

1 Like
5

Thanks a lot for sharing your thoughts! This seems to be the right way for unifying the constant case and the dynamic case. I like that we keep type safety for the constant case in that way.

However, there must be a way to avoid memory waste in the dynamic case for being adequate in serious use cases. (@H2CO3 of course you are right that the modulus must be stored somewhere, but I would still like to avoid duplicating it over and over again with every add operation performed.)

Consider for example using this struct in a cryptography crate, where thousands of operations are performed with the same modulus. There might also be more complex number systems involved, where instead of a modulus we might have a way larger parameter set (like parameters for a finite field, or even for an elliptic curve over a finite field).

Maybe my biggest modelling mistake was trying to implement the Add trait in the first place? I just thought about using a custom Add trait, where the parameter set is separated from the data part. Like so:

trait ParameterizedAdd<P, Rhs = Self> {
    type Output;

    fn add(self, rhs: Rhs, params: P) -> Self::Output;
}

This can be implemented directly for the data part (i32 in our example), and it does not matter anymore that the modulus cannot be derived from the data.

trait Modulus {
    fn modulus(self) -> i32;
}

impl<P: Modulus> ParameterizedAdd<P> for i32 {
    type Output = Self;

    fn add(self, rhs: Self, params: P) -> Self::Output {
        (self + rhs).rem_euclid(params.modulus())
    }
}

Technically this seems completely fine to me, but of course now we are losing all syntactic sugar (we cannot use x+y anymore for addition modulo M). This approach is way less convenient than the first one, but it might be the right way to go when caring about performance?

6

You could use the ghostcell trick to statically link each instance of IntMod to a context knowing the modulus Rust Playground

Though note that this is probably not ergonomic and the errors messages are pretty bad.

2 Likes
7

Wow, this is fancy! Didn't know that trick (and also don't fully understand yet what is really going on). But it is a nice idea to have a context with fixed modulus.