Types as const Parameters

[pthariensflame]

Project Proposal: Types as const Parameters

Summary and problem statement

Rust’s current(ly planned) generics allow three distinct and unrelated forms of generic parameter: types, lifetimes, and const values. Here we propose a way to unify the three by making the first two particular cases of the third, retaining the existing separate syntax as a simple sugar over the unified form, and thus preserving full backwards compatibility. This automatically subsumes variadic generics, as well as arbitrarily more complex and expressive forms of data structures and computation over types, as ordinary const Rust.

Motivation, use-cases, and solution sketches

As Rust gets more and more expressive const computation, and unlocks const generics, it's become apparent that the language for working with types is noticeably less expressive than the language for working with const values. Some particular pain points include the ability to use data structures of values, such as slices, or Options, but that types have no such capabilities. Variadic generics have been proposed a number of times to address this partially, but none of these attempts have gotten far. Further, there are cases of a type constructor wanting to accept a variable number of types in a non-list-like way, which variadic generics don’t handle well if at all.

Here we propose a single extension to Rust’s generics system that automatically solves both of the above problems and then some, while arguably simplifying the generics model rather than further complicating it. The idea is to treat each of types and lifetimes as just another type of const value, desugaring “normal” type and lifetime generic parameters to const generic parameters (e.g.,

Foo<'a, 'b, X, Y, Z>

desugars to

Foo<{'a}, {'b}, {X}, {Y}, {Z}>

, and each can be written in user code just when the other can). To accomplish this, a new standard module {core, std}::type_level will be introduced, and types Type and Lifetime will be placed within it (names very bikesheddable). These two types can only appear in const context: as the types of const values, const generic parameters, and function parameters of const fns (list not meant to be exhaustive but only suggestive). The previous example’s declaration would then desugar from (e.g.)

struct Foo<'x, 'y, A, B, C> { ... }

to

struct Foo<const x: Lifetime, const y: Lifetime, const A: Type, const B: Type, const C: Type> { ... }

. Likewise, (non-generic) associated types in traits would desugar to associated consts of type Type, and similarly for non-associated type aliases. (Making that desugaring work for the generic case naturally extends the ability to have generic parameters to consts of all kinds, which seems reasonable, if not particularly motivated unto itself.)

What does this unification buy us? For one thing, we now have variadic generics "for free": we can just use slices of types! For example:

struct VarFoo<const tys: &[Type]> { ... }
// …
let vf: VarFoo<{&[i64, i32, i64, u32, String]}> = …

Tuples of const-computed form can be supported easily by introducing {core, std}::tuple::Tuple with exactly the above declaration signature, and making existing tuples desugar to it.

Having types and lifetimes as const values lets us write const fns manipulating them, and lets us put them in additional data structures besides just slices. For example:

• a rose tree of types Rose<Type> where Rose is defined as:

  #[derive(PartialEq, Eq, Clone, Debug)]
  enum Rose<T> {
      Leaf(T),
      Node(Vec<Rose<T>>),
  }

  would be a useful const generic parameter to a type of "heterogenous trees", a.k.a. nested tuples;
• an Option<Type> would be useful const generic parameter to an "optionally typed box", i.e., something like Box<Any> but where the contained type might or might not actually be specified;
• a descriptor for a finite state machine FSM<Type>, where each node is associated with a type and there's a marked “current” node, is a useful generic parameter to a coroutine/generator in order to describe which possible types it can yield when.

The unification of types and lifetimes under consts also makes it easier (though still not immediate or automatic) to implement higher-rank constraints quantifying over types and const values rather than just lifetimes, since the work of dealing with lifetimes as a special case will already have been done and much of it could probably treat types and (other) consts the same way.

A third member of {core, std}::type_level is needed if we want to express const computations around constraints: Constraint would be the type of (fully specified) constraints, while bounds would be treated as unary type constructors of eventual type Constraint rather than Type. Like its fellows, Constraint would only be usable at typechecking/const-evaluation time. We don't see a need to introduce Constraint at the same time as Type and Lifetime, though; it can be added later, or not at all, and the rest of the above will still work perfectly well. Having Constraint would also make static assertions much easier to specify and use, as they could just take one or more Constraints and check them in the standard way.

Prioritization

This fits into the lang team priorities under both “Const generics and constant evaluation” and “Trait and type system extensions”, as well as to a more limited extent under “Borrow checker expressiveness and other lifetime issues”.

Links and related work

In addition to the attempts at variadic generics linked above, this also relates by its nature to HKTs and GATs, as well as const generics as a whole. The author is certain there are many more interested parties but doesn't know how to find or link them; help would be very appreciated here.

The ideas here are of course broadly related to dependent types and the uses they've been put to; a closer analog to this exact feature are the DataKinds and ConstraintKinds features of GHC Haskell. To the author's knowledge, no other language has implemented something like this short of implementing full dependent types; in particular, C++ continues to maintain—and even reinforce—the distinction between types and constexpr values that this proposal would like to erase.

Initial people involved

The author (@pthariensflame) has been privately stewing this idea over for a few months; to their knowledge no one else has yet proposed this for Rust.

[rustbot]

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

[pthariensflame]

Zulip link above is broken; use this one instead.

[scottmcm]

We discussed this in the 2020-10-19 lang team triage meeting.

This sounds like it could be a nice simplification in the future, and the idea of reifying more of the type system into values is interesting. However, this builds on const generics, which are still ongoing. There are also still plenty of unknowns here, like how to use these values to produce items. So like we've been doing with other steps-to-variadic-generics RFCs for now,

@rfcbot close

(As this is a close I'll check the boxes of those who were in the meeting.)

[rfcbot]

Team member @scottmcm has proposed to close this. The next step is review by the rest of the tagged team members:

• @cramertj
• @joshtriplett
• @nikomatsakis
• @pnkfelix
• @scottmcm
• @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to close, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

[nikomatsakis]

Per the FCP above, closing the issue. Thanks @pthariensflame!