GATs could eliminate the need for traits for the operations

[steffahn]

I haven’t studied use-cases of typenum too deeply, so I’m not sure how beneficial this is in the first place… and implementing this would also possibly be somewhat of a breaking change (?) (or maybe not?)… but as far as I understand, as of now, it’s not possible to state simple bounds such as I: Integer, J: Integer and then do an addition op!(I + J) on them. You would need an additional I: Add<J> bound. And I just realized that with GATs this doesn’t need to be the case anymore. I had that insight when writing something like

pub struct False;
pub struct True;

pub trait TypeBool {
    type And<Other: TypeBool>: TypeBool;
    type Not: TypeBool;
}
impl TypeBool for True {
    type And<Other: TypeBool> = Other;
    type Not = False;
}
impl TypeBool for False {
    type And<Other: TypeBool> = False;
    type Not = True;
}

and as we (should) all know, if nand is possible, then everything is possible :-)

Here’s a longer example / proof of concept (click me!)

Below is an example implementation of unsigned integer addition. This is simply the first implementation I came up with, I’m claiming neither that it’s particularly beautiful, nor optimal in any manner.

struct B0;
struct B1;

trait Bit {
    const U128: u128;
    type And<Other: Bit>: Bit;
    type Or<Other: Bit>: Bit;
    type Xor<Other: Bit>: Bit;
    type Xor3<Other1: Bit, Other2: Bit>: Bit;
    type Carry3<Other1: Bit, Other2: Bit>: Bit;
    type AddUnsigned<Other: Unsigned>: Unsigned;
    type Not: Bit;
    // successor of UInt<U, Self>
    type SuccUIntUSelf<U: Unsigned>: Unsigned;
}
impl Bit for B0 {
    const U128: u128 = 0;
    type And<Other: Bit> = B0;
    type Or<Other: Bit> = Other;
    type Xor<Other: Bit> = Other;
    type Xor3<Other1: Bit, Other2: Bit> = Other1::Xor<Other2>;
    type Carry3<Other1: Bit, Other2: Bit> = Other1::And<Other2>;
    type AddUnsigned<Other: Unsigned> = Other;
    type Not = B1;
    // successor of UInt<U, B0>
    type SuccUIntUSelf<U: Unsigned> = UInt<U, B1>;
}
impl Bit for B1 {
    const U128: u128 = 1;
    type And<Other: Bit> = Other;
    type Or<Other: Bit> = B1;
    type Xor<Other: Bit> = Other::Not;
    type Xor3<Other1: Bit, Other2: Bit> = <Other1::Xor<Other2> as Bit>::Not;
    type Carry3<Other1: Bit, Other2: Bit> = Other1::Or<Other2>;
    type AddUnsigned<Other: Unsigned> = Other::Succ;
    type Not = B0;
    // successor of UInt<U, B1>
    type SuccUIntUSelf<U: Unsigned> = UInt<U::Succ, B0>;
}

struct UTerm;
struct UInt<U, B>(U, B);

trait Unsigned {
    const U128: u128;
    type Add<Other: Unsigned>: Unsigned;
    type AddCarry<Other: Unsigned, C: Bit>: Unsigned;
    type AddUInt<OtherU: Unsigned, OtherB: Bit>: Unsigned;
    type AddUIntCarry<OtherU: Unsigned, OtherB: Bit, C: Bit>: Unsigned;
    type Succ: Unsigned;
}
impl Unsigned for UTerm {
    const U128: u128 = 0;
    type Add<Other: Unsigned> = Other;
    type AddCarry<Other: Unsigned, C: Bit> = C::AddUnsigned<Other>;
    type AddUInt<OtherU: Unsigned, OtherB: Bit> = UInt<OtherU, OtherB>;
    type AddUIntCarry<OtherU: Unsigned, OtherB: Bit, C: Bit> =
        UInt<<OtherB::And<C> as Bit>::AddUnsigned<OtherU>, OtherB::Xor<C>>;
    type Succ = UInt<UTerm, B1>;
}
impl<U: Unsigned, B: Bit> Unsigned for UInt<U, B> {
    const U128: u128 = B::U128 + 2 * U::U128;
    type Add<Other: Unsigned> = Other::AddUInt<U, B>;
    type AddCarry<Other: Unsigned, C: Bit> = Other::AddUIntCarry<U, B, C>;
    type AddUInt<OtherU: Unsigned, OtherB: Bit> =
        UInt<U::AddCarry<OtherU, B::And<OtherB>>, B::Xor<OtherB>>;
    type AddUIntCarry<OtherU: Unsigned, OtherB: Bit, C: Bit> =
        UInt<U::AddCarry<OtherU, B::Carry3<OtherB, C>>, B::Xor3<OtherB, C>>;
    type Succ = B::SuccUIntUSelf<U>;
}

type Add<U1, U2> = <U1 as Unsigned>::Add<U2>;

/*
// in a proc-macro crate

use proc_macro::{TokenStream, TokenTree};
use quote::quote;

#[proc_macro]
pub fn u(lit: TokenStream) -> TokenStream {
    let mut tokens = lit.into_iter();
    let lit = tokens.next().unwrap();
    assert!(tokens.next().is_none());
    let TokenTree::Literal(lit) = lit else { panic!() };
    let mut lit = lit.to_string().parse::<u128>().unwrap();

    // don't judge me, this is just the first implementation I came up with…
    // …yes, my background involves functional programming :'-D

    let mut n: Box<dyn FnOnce(_) -> _> = Box::new(|x| x);
    while lit > 0 {
        let bit = if lit % 2 == 0 { quote!(B0) } else { quote!(B1) };
        n = Box::new(move |x| n(quote!(UInt<#x, #bit>)));
        lit = lit / 2;
    }
    n(quote!(UTerm)).into()
}
*/

use name_of_the_crate::u;

fn main() {
    dbg!(<u!(0)>::U128); // testing the macro…
    dbg!(<u!(1)>::U128);
    dbg!(<u!(2)>::U128);
    dbg!(<u!(3)>::U128);
    dbg!(<u!(4)>::U128);
    dbg!(<u!(5)>::U128);
    dbg!(<u!(6)>::U128);
    // now some additions
    dbg!(Add::<u!(10), u!(23)>::U128);
    dbg!(Add::<u!(1002311), u!(4402310)>::U128);
    dbg!(1002311 + 4402310);
    dbg!(Add::<u!(0), u!(4402310)>::U128);
    dbg!(Add::<u!(1002311), u!(0)>::U128);
}

I’m posting this here, because I’m not sure if that’s a known thing yet :-)

Also I’m not 100% certain whether there isn’t any non-GAT way of doing the same, but I couldn’t come up with any approach so far, so maybe this really is a new thing that GATs allow us to do?

[paholg]

That's really neat! Definitely a huge ergonomic improvement. Not sure if it would be a breaking change to add to typenum's traits, but worst case, we could create new traits.

[droundy]

I'd say worst case you have a major revision bump.

[Qqwy]

I'm taking a stab at implementing this. I managed to get Add and Sub (and Succ, Pred, Trim) working (for Unsigned ints only) so far.
It's gonna be some time to finish it though, since typenum has quite many features.

I don't think it will be possible (nor, to be honest, desireable) to create this in a backwards-compatible way. The new API is so much simpler that downstream code would mainly have to 'throw most bounds away' to upgrade.

[Qqwy]

FYI, implementation of most of the binary operators turns into something like this:

(For a given Op like Add or Sub.)

Here, Op<L, R> is a type alias (defined as type Op<L, R> = <L as UnsignedImpl>::Op<R>;. All others are GATs implemented on either the UnsignedImpl trait or the BitImpl trait. (Both of which are sealed, #[doc(hidden)], public traits).

For many operators, (luckily), some of these subbranches can be simplified (Such as when the outcome is the same, regardless of whether Br is B0 or B1, or when we can delegate to another simpler GAT to calculate the outcome of a combination).

[Qqwy]

Managed to get DivRem work, but currently it still uses the simple 'repeated subtraction' algorithm. That was simplest to implement but leads to impractically slow build times (and hitting the recursion limit) on large numerals.

So that will need to be changed to the more complicated binary long division 🤐 .

[steffahn]

I’m revisiting this again, and have some new ideas to further reduce the number of associated types traits like Bit, Unsigned, etc… would need to have.

In any case, if me or someone else, re-implements at least some nontrivial algorithms of typenat in a GATty manner, one of the concerns should be not to make the thing perform a lot worse. On that note, I’m wondering: Is there any performance benchmarks for typenum?

I’ve spotted mentions such as on UInt stating “Conceptually, U should be bound by the trait Unsigned and B should be bound by the trait Bit, but enforcing these bounds causes linear instead of logrithmic (sic) scaling in some places, so they are left off for now. They may be enforced in future.” What approach can one use to reproduce these observations, to check of changes or re-implementations of stuff don’t result in similar worsening of performance?

Typical benchmarks are for run-time, though compilation time can of course also be measured, but I’m not sure where to find example use-cases that make heavy use of typenat computation that could be measured in compile-times. Do we have something like that somewhere?

[paholg]

I definitely had some rudimentary performance benchmarks, but I guess I never committed them.

I think I just had a python script that generated a bit of Rust code that performed a division, and looped through larger and larger numbers. This was fine for the issue at the time (exponential time for division), but I'm not sure it'd be as useful for a general purpose benchmark.