Gnat - a typenum alternative without operator bounds

announcements
1

Hey,

I've been writing this on the side for over a year now and am happy to finally release my crate gnat. It uses generic associated types to be more expressive than typenum and generic_const_exprs. Here is an example of the elusive generic array concat function:

#![feature(generic_const_exprs)]
const fn concat_arrays_gcex<T, const M: usize, const N: usize>(
    a: [T; M],
    b: [T; N],
) -> [T; M + N]
where
    [T; M + N]:, // well-formedness bound
{
    todo!()
}

use generic_array::{GenericArray, ArrayLength};
const fn concat_arrays_tnum<T, M: ArrayLength, N: ArrayLength>(
    a: GenericArray<T, M>,
    b: GenericArray<T, N>,
) -> GenericArray<T, typenum::op!(M + N)>
where // ArrayLength is not enough, we also need to add a bound for `+`
    M: std::ops::Add<N, Output: ArrayLength>,
{
    todo!()
}

// Using this crate:
use gnat::{Nat, array::Arr};
const fn concat_arrays_gnat<T, M: Nat, N: Nat>(
    a: Arr<T, M>,
    b: Arr<T, N>,
) -> Arr<T, gnat::eval!(M + N)> { // no extra bounds!
    a.concat_arr(b).retype()
}

The only bound that is required is Nat, which specifies that the types are numbers. You can implement your own operations in a way that also does not require bounds, using bit-level operations, conditionals and recursion (which is also how Add is implemented). This can be used to implement any computable function, as it is turing-complete!

Disclaimer: Many compilers were harmed in the making of this library. ^^

4 Likes
2

Correction: I initially forgot that generic_const_exprsalso requires bounds for operations, so gnat is actually more expressive, not equivalent.

3

Nice!

If I understand correctly, the core of the design is:

pub trait NatExpr {
    /// Evaluates to [`Nat`].
    type Eval: Nat;
}

pub trait _Nat: _NatArrs + 'static {
    [..]
    type If<T: NatExpr, F: NatExpr>: Nat;
    [..]
}

The associated type If is implemented as either

        type If<T: NatExpr, F: NatExpr> = T::Eval;

or

        type If<T: NatExpr, F: NatExpr> = F::Eval;

depending on whether the nat is non-zero.

Operations like addition are performed by breaking the operands down bit-by-bit and using If to branch on those bits.

Importantly, if If just let you choose between two Nat-implementing types, then it would be impossible to implement any kind of recursive algorithm because both sides of the If would have to be fully evaluated to a number before choosing a side. Instead, this uses an intermediate NatExpr trait with corresponding types that just represent an expression, e.g. _Add<Foo, _Add<Bar, Baz>>. These then get turned into Nat after selecting a side, by evaluating the Eval associated type.

This does assume that rustc will only evaluate associated types when it needs to, and not preemptively try to evaluate associated types of every type it sees. That could hypothetically conflict with proposals to create some kind of central registry of which traits are implemented by every type, allowing for arbitrary dynamic trait downcasting. But those proposals never got far and I doubt they will ever become reality, at least not without some kind of per-trait opt-in. I'm sure plenty of existing code relies on the same lazy evaluation property that gnat does. Regardless, if breakage did occur, it could be worked around by making Eval or NatExpr generic with some dummy type argument. Any central registry would have to exclude generic traits and generic associated types, because it wouldn't know the generic arguments (and it couldn't precompute all possibilities because typically there are infinitely many possibilities).

Anyway,

I think it's horrible that Rust as a language requires this, but the implementation looks clean (as much as it can be under the circumstances). I would like to use this in the future.

2 Likes
4

Thanks so much for looking at my stuff!

Yeah, I would also like to live in a world where this was how generic_const_exprs worked (but I'm sure they have good reasons for requiring well-formedness bounds).

I'm not sure what you are saying with the registry part, or rather how that would create conflict with this crate that wouldn't already exist with typenum. Can you elaborate on that? (You are btw correct about how the internals work, I made sure they are written in a way that can be changed later)