1

A path towards stable generic const expressions

 3 months ago
source link: https://lcnr.de/blog/generic-const-expressions/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is damaged, please click the button below to view the snapshot at that time.
A path towards stable generic const expressions :3

A path towards stable generic const expressions

After the stabilization of a const generics MVP in version 1.51, the Const Generics Project Group looked towards allowing computation as arguments for const parameters. The currently stable subset only allows generic parameters to be mentioned by themselves. It is therefore not possible to embed generic computations in the type system. This means that the following is currently not allowed:

fn push_to_array<T, const N: usize>(arr: [T; N], value: T) -> [T; N + 1] {
    // Using `N + 1` is not allowed on stable.
    todo!()
}

trait EncodeToBytes {
    const LENGTH: usize;
    fn encode(&self) -> [u8; Self::LENGTH];
    // As `Self` is generic, this causes an error on stable.
}

While trying to get these examples to work correctly, we’ve encountered many challenges, preventing us from stabilizing feature(generic_const_exprs) in any reasonable timeframe. To a large part, these issues are caused by generic parameters and where-clauses used by generic constants being implicit. While quite technical, you can check out our internal documents to figure out more about some of the existing issues.

Because of this, we’ve recently looked into reducing the scope of feature(generic_const_exprs) in a way that greatly simplifies the implementation and design while still being fairly expressive.

This post has been written by BoxyUwU and myself and represents our opinion. The proposed changes will still have to go through the official decision process before their stabilization.

Generic free and associated constants

As explored in the next section, our idea relies on generic named constants. For this we want to implement both generic free constants and generic associated constants. In other words, we intend to allow the addition of generic parameters and where-clauses to these constructs.

const ADD<const N: usize, const M: usize>: usize = N + M;
trait WithAssoc {
    const ASSOC<T>: usize;
}
// The position of `where`-clauses isn't final and
// should follow the decision made for GATs.
const REQUIRES_TRAIT<T, U>: usize = <T as WithAssoc>::ASSOC::<U>
where
    T: WithAssoc; 

We don’t think there are too many open design questions about this addition. While this will need an RFC, it will hopefully be fairly uncontroversial.

Allowing generic named constants in types

On the “const generics side”, we intend to add standalone generic named constants to the allowed arguments for const parameters. With this, the required generic parameters and where-clauses are explicit, avoiding or at least simplifying most of the issues with feature(generic_const_exprs). For now, we use feature(min_generic_const_exprs) when talking about this design.

Examples

const ADD<const N: usize, const M: usize> = N + M;
fn push_to_array<T, const N: usize>(
    arr: [T; N],
    value: T,
) -> [T; ADD::<N, 1>] {
    // using `N + 1` instead would still error here.
    todo!()
}

trait EncodeToBytes {
    const LENGTH: usize;
    fn encode(&self) -> [u8; Self::LENGTH];
    // This will be allowed and be usable.
}

While this simplifies things, it is not trivial and has the following potential issues.

Const evaluatable bounds

With feature(generic_const_exprs) we currently require the user to add where-clauses asserting that used generic constants do not fail to evaluate in surprising ways. This is also relevant for feature(min_generic_const_exprs) and will not be considered further in this post.

Opaque and transparent named constants

Consider the following example using the above definitions.

impl<const N: usize> EncodeToBytes for [u8; N] {
    const LENGTH: usize = N;
    fn encode(&self) -> [u8; N] {
        *self
    }
}

This should compile. When only considering generic constants equal if they are the same named constant, this will however fail. The compiler will try to unify Self::LENGTH of the trait definition with the generic parameter N. As these are different, we would get an error. This is something we have to avoid.

We therefore need to sometimes look into named constants when deciding whether they should unify. We have not yet decided on how explicit this should be. Always looking into generic named constants means that changing their body, e.g. from ADD::<N, 1> to ADD::<1, N>, would be a breaking change. Always having this be opt-in makes using them a lot more cumbersome.

Considering the following two constants:

const ADD<const N: usize, const M: usize>: usize = N + M;
const ADD_ONE<const N: usize>: usize = ADD::<N, 1>;

If ADD_ONE is opaque, [u8; ADD::<N, 1>] and [u8; ADD_ONE::<N>] are two different types, while they are equivalent if ADD_ONE is transparent. As we intend to always evaluate constants if they do not use any generic parameters, [u8; ADD::<3, 1>] and [u8; ADD_ONE::<3>] are always equivalent.

Standardization

As feature(min_generic_const_exprs) only allows named constants, users can’t directly write N + 1 but have to use a generic constants instead.

If different libraries were to define their own constants for the same expression, they would be incompatabile. A similar issue arises with commutative operations, e.g. one function using ADD::<N, 1> while another one uses ADD::<1, N>.

Mitigation for this issue is twofold, we start by adding constants for most common operations to the standard library, e.g. in a module std::constants. With this, crates can then use the constants defined there instead of redefining them, allowing cross-crate unification to succeed. In addition to this we can add lints encouraging some canonical form, e.g. by warning against ADD::<1, N> and suggesting ADD::<N, 1>. We should also lint against users redefining constants found the standard library.

Future compatability

While feature(min_generic_const_exprs) will allow arbitrary expressions, you will have to use named constants which isn’t perfect. To our knowledge, this feature will not add any noteworthy complications to adding something closer to the ideal feature(generic_const_exprs) later on.

Once feature(generic_const_exprs) is stable, we will also want to update the standard library to use expressions directly and to deprecate the std::constants module. For this, we will once again need a way to look into associated constants so that the unification of N + 1 and ADD::<N, 1> succeeds.

back


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK