😱 Status quo: nalgebra

a huge thanks to Andreas Borgen Longva and Sébastien Crozet for the help with figuring this out

nalgebra is a linear algebra library. At the core of that library is a type struct Matrix<T, R, C, S> where T is the components scalar type, R and C represents the number of rows and columns and S represents the type of the buffer containing the data.

Relevant for const generics are the parameters R and C. These are instantiated using one of the following types:

#![allow(unused)]
fn main() {
// For matrices of know size.
pub struct Const<const R: usize>;
// For matrices with a size only known at runtime.
pub struct Dynamic { value: usize }
}

The authors of nalgebra then introduce a type alias

#![allow(unused)]
fn main() {
pub struct ArrayStorage<T, const R: usize, const C: usize>(pub [[T; R]; C]);
/// A matrix of statically know size.
pub type SMatrix<T, const R: usize, const C: usize> =
    Matrix<T, Const<R>, Const<C>, ArrayStorage<T, R, C>>;
}

To deal with the lack of generic const expressions, they add a trait for conversions from and to typenum for all Const up to size 127 (source).

Whenever they now need some computation using Const<N>, they convert it to type nums, evaluate the computation using the trait system, and then convert the result back to some Const<M>.

Disadvantages

While this mostly works fine, there are some disadvantages.

Annoying `ToTypenum` bounds

Most notably this adds a lot of unnecessary bounds, consider the following impl:

#![allow(unused)]
fn main() {
impl<T, const R1: usize, const C1: usize, const R2: usize, const C2: usize>
    ReshapableStorage<T, Const<R1>, Const<C1>, Const<R2>, Const<C2>> for ArrayStorage<T, R1, C1>
where
    T: Scalar,
    Const<R1>: ToTypenum,
    Const<C1>: ToTypenum,
    Const<R2>: ToTypenum,
    Const<C2>: ToTypenum,
    <Const<R1> as ToTypenum>::Typenum: Mul<<Const<C1> as ToTypenum>::Typenum>,
    <Const<R2> as ToTypenum>::Typenum: Mul<
        <Const<C2> as ToTypenum>::Typenum,
        Output = typenum::Prod<
            <Const<R1> as ToTypenum>::Typenum,
            <Const<C1> as ToTypenum>::Typenum,
        >,
    >,
{
    type Output = ArrayStorage<T, R2, C2>;

    fn reshape_generic(self, _: Const<R2>, _: Const<C2>) -> Self::Output {
        unsafe {
            let data: [[T; R2]; C2] = mem::transmute_copy(&self.0);
            mem::forget(self.0);
            ArrayStorage(data)
        }
    }
}
}

As these bounds infect the public API, they are also a large backwards compatability concern.

`ToTypenum` is only implemented up to fixed size

That's annoying. ✨

Cannot use associated constants

It is currently also not possible to have the size of a matrix depend on associated constants:

#![allow(unused)]
fn main() {
trait MyDimensions {
   const ROWS: usize;
   const COLS: usize;
}

fn foo<Dims: MyDimensions>() {
    // Not possible!
    let matrix: SMatrix<f64, Dims::ROWS, Dims::COLS> = SMatrix::zeros();
}
}

While this can be avoided by going to back to typenum and using associated types, this adds a lot of unnecessary bounds and inpacts all of the code dealing with it.

Generic parameters aren't exhaustive

Because R and C are generic parameters and not constants, the compiler doesn't know that DefaultAllocator: Allocator<T, R, C> holds for all R and C, leaking implementation defaults and causing signatures to be far less readable than necessary.

Wishlist

Ideally, Matrix could be changed to the following:

#![allow(unused)]
fn main() {
enum Dim {
    Const(usize),
    Dynamic,
}

struct Matrix<T, const R: Dim, const C: Dim, S> { ... }

type SMatrix<T, const R: usize, const C: usize> =
    Matrix<T, Dim::Const(R), Dim::Const(C), ArrayStorage<T, R, C>>;
}

For this to work well there have a bunch of requirements for const generics:

User-defined types as const parameter types

We have to be able to use Dim as a const param type

Consider injective expressions to bind generic params

With this change, nalgebra needs impls like the following

#![allow(unused)]
fn main() {
impl<T, const R: usize, const C: usize> for SMatrix<T, R, C> {
    // ...
}
}

For this impl to bind R and C, the expression Dim::Const(N) has to bind N. This is sound as constructors are injective. It seems very desirable to at least enable this for expressions using constructors.

Without this, one gets an error message like the following:

error[E0207]: the const parameter `R` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:5:12
  |
5 | impl<T, const R: usize, const C: usize> for SMatrix<T, R, C> {
  |               ^ unconstrained const parameter
  |
  = note: expressions using a const parameter must map each value to a distinct output value
  = note: only used in the expression `Dim::Const(R)`
  = note: proving the result of expressions other than the parameter are unique is not supported

Merge partial impls to be exhaustive

By adding one trait impl impl for Dim::Dynamic and one for Dim::Const(N), it should be enough to consider that trait to be implemented for all Dim.

Ideally, the compiler should figure this out by itself, or it can be emulated using specialization by manually adding an impl for all Dim which always gets overridden.

Generic const expressions

For example when computing the Kronecker product which has the following simplified signature:

#![allow(unused)]
fn main() {
pub fn kronecker<T, const R1: Dim, const C1: Dim, const R2: Dim, const C2: Dim>(
    lhs: &Matrix<T, R1, C2>,
    rhs: &Matrix<T, R2, C2>,
) -> Matrix<T, R1 * R2, C1 * C2> {
    ...
}
}

For this generic const expressions have to be supported.

const Trait implementations

For R1 * R2 to work we need const trait impls, otherwise this can be written using mul_dim(R1, R2) or something.

`Default` for arrays

nalgebra currently has to work around Default not being implemented for all arrays where T: Default.

Const Generics Project Group