inspired by a friend’s fledgling language design and motivated by the JeanHeyd Meneide RustConf Fiasco™ and improving the story for compile-time introspection, i decided i needed a place to spew the last year’s musings on variadic generics in Rust in one mighty, less-than-understandable catharsis.
i think somewhere in here is a considered and reasonable design, so that’s neat!
perhaps i’ll make this an RFC one day. probably not. you have my express permission to do that yourself.
this nugget of language jargon encapsulates the idea that we might want to bind to an arbitrarily large list of generic parameters, all at once. there are many reasons to want to do this:
- we might want to implement a trait for all tuples, where each element of the tuple implements the same trait.
bevy_ecs'sBundletrait is a compelling example of this. it is currently implemented with a macro on tuples of up to 15 elements. - similarly, implementing traits for function pointers with an arbitrary number of args.
- the aforementioned compile time introspection needs variadic generics in order to represent the types of fields/variants. a const-generic approach (
FieldFromIdx<0>) was tried but found lacking in areas. - apis like
Iterator::ziporfutures::joinwould be made much more ergonomic (and probably performant) if they allowed a variadic set of parameters.
i think there’s no reason not to limit the scope of variadic generics to tuples:
TEPID BEAR'S NOT TIP
this will go unjustified.
Variadic<(A, B, C)> // is valid syntax
Variadic<((A, B), C)> // is also valid
Variadic<A, B, C> // too many params 😡this allows us to store variadic parameters inline with other parameters of all types and so removes the awkward requirement that variadic parameters can be placed only at the end of a parameter list (which implies there can only be one variadic generic parameter in any given list!).
if you allow traits to be generic parameters1 then you maybe can promote most of the variadic generics system to the type system with a trait as such:
trait Tuple<trait Elem> {
type First: Elem;
type Last: Elem;
type Rest: Tuple<Elem>;
fn split_into(self) -> (Self::First, Self::Rest, Self::Last);
// `split_ref` etc.
}
// now it’s super easy to use variadic generics:
trait MyTrait;
fn variadic_fn<T>(params: T) where T: Tuple<MyTrait>;this does still require the compiler to know quite a bit extra about the Tuple trait otherwise we can’t do a whole lot with it and it also brings up an issue around how to implement Tuple for the unit tuple. maybe <() as Tuple<Foo>>::First should be the unit type () but that requires that () implements the Elem trait which complicates things:
trait Tuple<trait Elem> where (): Elem;another option is to use Rust’s ! and some trickery in split_into but that really poses all the same problems.
perhaps Tuple::Rest should not implement Elem at all and we should rely on compiler magic for all type transformations.
i definitely think this approach has merit but we might be better served making Tuple a marker trait and using fancy language features for all the important implementation gubbins.
previous suggestions for the syntax of trait bounds i have been universally unsatisfied with:
type Variadic<T @ ..Trait>this just doesn’t look like a trait bound to me. it also hides the tuple-ness of the implementation.type Variadic<(T @ ..): Trait>this is better, but it implies the tuple itself implementsTraitnot the elements contained inTand while it looks extensible (i.e.(T, U @ ..): Trait) there’s no reason in my eyes not to just use separate generic parameters.type Variadic<(..T): Trait>all the same criticisms as the above entry apply here too.
there’s one syntax that has been skipped by every proposal i’ve seen and to me it’s the most obvious of them all:
type Variadic<T: (..Trait)>;the benefits of this syntax:
- where without variadics we’d need a type and then a trait (
T: Trait), we use a type and then a trait for variadics too.(..Trait)can be conceptualised as a trait, the same wayVec<T>or*mut Tare recognisable as types. it’s not special syntax for generic parameters, but simply special syntax for a new set of traits which is much more Rusty imo and means we can use the same syntax in other places where we’d expect a trait (e.g. supertraits). - we’d use pretty much the same syntax across the trait and type levels2 without even getting into value-level composition.
- it keeps very much in-mind that variadic generics are backed by tuples. this comes more into play with the value-level composition/decomposition part of this proposal but i think it’s still aids clarity.
in the discussion between
(..Trait)vs(Trait..)i think both have pretty much equal merit, but i do vastly prefer..to...for consistency within the language.
there are also examples where we want a variadic list of parameters, but don’t care whether they implement some trait, so i propose the (..) syntax which desugars as such:
// super-sweet 😋
type Variadic<T: (..)>;
// yikes.. 😱
trait __Universal {}
impl<T: ?Sized> __Universal for T {}
type Variadic<T: (..__Universal)>;there’s one question about this syntax that i haven’t settled, which is whether we should allow some syntax like (..(Trait1 + Trait2)) even though this should be achievable already through (..Trait1) + (..Trait2). i am leaning towards no, especially since the first syntax is future-compatible with the second.
as i understand it, (..) + 'a would be a valid way of expressing the same thing as (..('a)) so we don’t really need anything special to support non-trait bounds as they stand (other than some good diagnostics).
i hope it’s not very controversial to say we should follow the syntax of languages like typescript w.r.t. how we compose types. the trait-level syntax defined above makes the grammar super simple:
TUPLE_TY = '(' TUPLE_ELEMENTS ')'
TUPLE_ELEMENTS = TUPLE_LIST | TUPLE_UNPACK
TUPLE_LIST = (TUPLE_ELEMENT ',')+ TUPLE_ELEMENT?
TUPLE_ELEMENT = TY | TUPLE_UNPACK
TUPLE_UNPACK = '..' TYhere are some examples:
// these three definitions are identical:
type Variadic<T: (..)> = T;
type Variadic<T: (..)> = (..T,);
// notice the lack of a final ','
type Variadic<T: (..)> = (..T);
// whereas (hopefully with a helpful diagnostic and fix available)
// this is straightforwardly a compile error:
type Variadic<T: (..)> = ..T;
// prepend/appending operations:
type Prepend<T: (..), U> = (U, ..T);
type Append<T: (..), U> = (..T, U);
type Delimit<T: (..), U> = (U, ..T, U);
// we can use multiple variadics together:
type Concat<T: (..), U: (..)> = (..T, ..U);however, there’s still one blind spot in this design:
fn variadic<T: (..), U: (..)>(params: (..T, ..U)) -> (T, U);
let (left, right) = variadic((0, 1, 2));
// what does this print?
println!("{left:?} vs. {right:?}");i don’t think it would be too difficult to enforce that when inference converts the type (i32, i32, i32) into (..T, ..U) it greedily generates T, so U is reduced to (). this seems like the most sane approach to me, though we could also try to make this a compiler error (i don't think its possible without violating semver somehow).
we should also allow this syntax in function pointers like Fn(..T) -> R, which wouldn't be impossible (i hope) and would allow us to implement traits over function pointers.
a solid end goal for a variadic generics implementation (probably post-mvp) is to be able to represent a ‘zip’ function for tuples, that turns (A, B, C) and (D, E, F) into ((A, D), (B, E), (C, F)) and the definitions provided above aren’t sufficient to do that.
fn zip<A: (..), B: (..)>(first: A, second: B) -> todo!(); // 😳this example has a couple of different parts, so let’s start with something a bit more simple to tackle one edge:
fn heapify<T>(params: T) -> todo!();
// for (A, B, C) i want to return (Box<A>, Box<B>, Box<C>).keen eyed type-system fantasizers like me might be chanting “HKT! HKT!” and you’d be right. we need some way of mapping A, B and C “through” Box. i’ve seen members of the language team declaring that type aliases and GATs should supersede old proposals for generalised HKTs and i absolutely agree. though that still doesn’t alone give us a solution here.
there are a million potential syntagma3 for this type of transformation, i’ll rank the ones that i’ve come up with in reverse order of quality (for reference, T is the type parameter above, and each option would be inserted above as the return type).
(..Box<T>). this might look sort-of okay-ish but is actually terrible. first of all, it really looks at first sight like this would produce(Box<(A, B, C)>,)(remember thatTis a tuple). moreover, what if i had a definition like the followingtype Box<T> = ()? then i might rightfully assume it resolves to()via(..()). whichever way you swing it, this has serious clarity and ambiguity issues.(Box<..T>). this one actually is sort-of okay-ish. it doesn’t have the same ambiguity concerns4 but i’m definitely not satisfied, and this one looks even more likeBox<(A, B, C)>! besides, it’s not clear how either of these modes of expression would do zipping (i.e. the same operation over multiple tuples).variadic_map!(P in T => Box<P>). this would be implemented as a compiler built-in macro at the type level, which i don’t think we have any of and so it would be interesting to implement. of course this isn’t the most natural or understandable syntax, but might be nice in the initial mvp or in the classic perpetually-unstable form. it’s also easy to see that for the zip use-case we could do something likevariadic_map!((L, R) in (A, B) => (L, R))to zipAandBtogether. maybe this could even be extended to variadic tuples of variadic tuples..(Box<P> for P in T). i’m not the biggest proponent for python’s way of doing things, but of all the options, this is, at least to me, by far the most readable. typically in syntax we’d want to put the dependencies (i.e.TandP) before their dependents, but i don’t mind the way it focusesBox<P>. you know as soon as you read "Box<P> for" that there are a bunch ofBoxes involved. also zip-ability is exactly the same as the above. my only reservation is how much it looks like value-level syntax.<T as Heapify>::Boxed. “wait, what?! you’re telling me we could’ve used pre-existing syntax, dodging the bikeshed bullet by cleverly reusing the language’s most powerful and established features all the while not expanding the already gigantic scope of this feature, this whole time?!” yep 👍, kinda. but it would take some special magic in the field of-
as of yet, we haven’t broached the idea of implementing traits on our shiny new type-level language features, so keeping the above problem in mind, let’s explore the possible options. coherence is a pretty technical and formal area of Rust’s design, so we’re going to need some more precise definitions:
- a tuple is finite if it contains no unpacking of generic parameters bound by variadic tuples.
(),(A, B)and(A, ..(B,))are all finite whereT where T: (..)is not. - all tuple types have a length range. this is either a constant
Nif the tuple is finite, or a end-unbounded rangeN..if it's not. - we can form realizations of infinite tuples, where unpacking of variadically-bound parameters
(..T)syntax is replaced with a finite list of type parameters, in order to make the tuple adhere to a particular finite length. these realizations are used to "lower" infinite tuple trait solving into a set of checks for finite tuples. as an example, if we want to realize(..T, ..U) where T: (..TraitA), U: (..TraitB)to a tuple with length 2, we can choose any of the following:(T1, T2) where T1: TraitA, T2: TraitA,(T1, U1) where T1: TraitA, U1: TraitB,(U1, U2) where U1: TraitB, U2: TraitB,
the rules for comparing two impls to see if they ever overlap are as follows:
- before anything else, we check if the possible length ranges for each target type overlap. if there is no overlap between the length ranges, the implementations definitely can never overlap for any theoretical type.
- otherwise, we take the start bound of the longer length tuple (let its type be
T1) and call itN(this is the smallest valid length for both tuples). we strip any variadic unpacking fromT1and use it to create a new finite tuple,L1. - we take
T2(the other target type) and permute through all the possible realizations that will give us a tuple with lengthN. we will call these new tuplesL2throughLM. - in this way, we have reduced our variadic tuple overlap checking into a set of easy finite checks. we can simply compare each tuple from
L2toLMagainstL1in the way the specialization graph already does. - in terms of performance, this algorithm is (worst-case, theoretically)
$O(\frac{2n!} {n!})$ where$n$ 5 is the larger of$s$ , the number of placeholder parameters that must be generated, and$v$ , the number of variadically-bound parameters unpacked intoT2and must be computed individually for eachimpl. if this complexity becomes unwieldy we could limit$v$ to some small number (perhaps$\le4$ ) which would mitigate combinatoric explosion. alternatively, we could consider alternative algorithms that scale better while preserving the same effects on coherence.
TEPID BEAR'S NOT TIP
i've not yet been able to prove that the rules above are perfectly adequate since they quite literally appeared to me in a dream. i am yet to find a counterexample, though.
now we can define our Heapify implementations:
trait Heapify {
type Boxed: (..);
}
impl Heapify for () {
type Boxed = ();
}
// there's no overlap with the above impl
// because this one has a length range of `1..`
// and the other has an exact length of `0`.
impl<T, U: (..)> Heapify for (T, ..U) {
type Boxed = (Box<T>, ..(<U as Heapify>::Boxed));
}
trait ContrivedList {}
impl ContrivedList for () {}
// there's no overlap between these two impls
// because the first is realised to `(i8, i8)`
// and the second to `(P1, u8)`.
// while there's overlap between `P1` and `i8`,
// `u8` and `i8` are distinct concrete types.
impl<T: (..ContrivedList)> ContrivedList for (i8, i8, ..T) {}
impl<T, U: (..ContrivedList)> ContrivedList for (T, u8, ..U) {}given the above definitions, simple tuple types should already be provable by induction like so:
<(A, B)>::Boxed
== (Box<A>, ..(<(B,)>::Boxed))
== (Box<A>, ..(Box<B>, ..(<()>::Boxed)))
== (Box<A>, Box<B>, ..(()))
== (Box<A>, Box<B>)
however we still don't have a way to prove it holds for all T: (..), even though it holds for all tuples length 0(there is only one!), and for all tuples of length 1.., and thus the U: (..) bound in the second impl cannot be relied upon. we need a way to combine these impls:
- definitions-wise, the goal type is the type we are trying to prove implements our trait.
- iterating though the possible lengths (
N) in the length range of the goal type, we filter out allimpls of out trait that don't matchN. - similar to overlap checking, for each remaining candidate
impl, we make two sets of realizations with lengthN. - we then need to prove that for every realization of the goal type, there exists one or more realizations of the
impltarget type that pass finite tuple trait solving. if that's the case, then we can say the candidate "passes" for the lengthNin the context of proving the goal type implements our trait. - if ever the same
implpasses for two consecutive lengths, we can assume it will pass for all lengths greater thanNand so we can return early, having proved the goal.
TEPID BEAR'S NOT TIP
the final point in that algorithm assumes a "twice in a row" rule that i haven't proved is correct. don't ask me why it is the case. equally, don't ask me to prove it is the case. i just know it. it is the single source of truth that i draw all my knowledge and belief from. to disprove it would leave me irreparably altered and i most assuredly would not believe you.
going back to our previous example:
impl Heapify for () {
type Boxed = ();
}
impl<T, U: (..)> Heapify for (T, ..U) {
type Boxed = (Box<T>, ..(<U as Heapify>::Boxed));
}to prove that the above U as Heapify is well-formed6, we need to prove forall<U> { U: Heapify } given U: (..).
- to try and prove this, we start by checking that
Uhas passingimplfor length 0. easily, we find that the realizationU -> ()matches()in the firstimpland so we do have passingimpl. - next we try length 1. the realization
U -> (U1,)matches(T, ..U) where U == ()in the secondimplso we have passingimplfor length 1 as well. - for length 2:
Umaps to(U1, U2)which matches(T, ..U) where U == (U1,)and so length 2 is valid. - lengths 1 and 2 both use the second
impl, so by the twice-in-a-row theorem this holds for all lengths greater than 1 as well. - as i understand it, this doesn't encroach on coinduction because the usage of
U: Heapifyis not part of the definition of the implementation, but part of its insides.
now that our type system is feature complete (enough), we can start using variadic tuples within our function bodies.
composition is pretty easy using what the community has called "unpacking". the most common syntax proposed works like so:
let vec2 = (x, y);
let vec3 = (...vec2, z);but it doesn't gel well with the rest of the design because it uses ... rather than .. and we could use .. if only for that (..vec2, z) already compiles on stable Rust and will produce a value of type (RangeTo<(X, Y)>, Z) - not really sufficient. our possible options:
- to get the obvious out of the way, we could (although definitely shouldn't) implement some arbitrary syntax
(unpack vec2, z),(~vec2, z), etc. (...vec2, z)is the one most often touted. i'm a firm believer that this one case does not motivate making all variadic generics syntax use...over double-dot, since we already use (and like) the concise..syntax.- we could, in one unprecedented, sweeping change, make
(..vec2, z)unpack by default, requiring people to use((..1), z)if they have a range they want to use.RangeTois definitely the least often used variant of range syntax and type inference would probably help a lot paired with some good diagnostics. i still think this change is going a bit too far. - we could offer
concat<A: (..), B: (..)>(a: A, b: B) -> (..A, ..B)implemented either withunsafeor compiler/stdlib magic. this is enough but is pretty obtuse ergonomically.concat(vec2, (z,))is pretty brutal. to note, there's definitely a signature in there somewhere that allowsconcatto take a variadic number of tuples as parameters. - we could gate the functionality behind a compiler-implemented macro,
compose!(..vec2, z), which prioritizes unpacking over range syntax. - maybe we could even reuse pattern matching syntax to allow
(vec2 @ .., z). i don't like how this conflates the two concepts, though. whatever we decide, i'm confident that unpack-based composition is the correct approach.
now we can build up tuple types and compose values that align with them, but are missing the crucial other half of the value story.
all the variadic proposals i've combed through contain some notion of {static, const, tuple} for that iterate through the elements in a tuple, type checking and unrolling at compile time during monomorphization:
let (x, y, z) = static for i in xyz {
i + 1
}this is fine (save that its really not very Rusty imho).
and then they realize most of the way through their proposal that we might want to iterate through multiple tuples at once, so they come up with this:
let (x, y, z) = static for (i, j, k) in (xyz, abc, nml) {
i + j + k
}and suddenly we're full throttle, blitzing down the syntactic slippery slope:
static for ijk in (xyz, abc) {
// can i do this?
let (i, ..) = ijk;
// most proposals say "yes, i think".
// looking at the above loop, on first iteration,
// we might reasonably expect `ijk == (x, a)`.
// but in reality it's probably more like `ijk == xyz`.
}effectively, we're unbuckling our users' shoes and handing out revolvers like campaign leaflets.
besides, there's a better way, and it doesn't require any new syntax to achieve.7
trait MyNumsSummed {
type Output: (..);
}
impl MyNumsSummed for () {
type Output = ();
}
impl<T: Add, U: (..Add)> for (T, ..U) {
type Output = (<T as Add>::Output, ..(<U as MyNumsSummed>::Output))
// `forall<U> { U: MyNumsSummed }` is provable given `U: (..Add)`,
// using the rules defined in "trait solving#candidate selection".
}
fn sum_my_nums<T: (..Add)>(xyz: T, abc: T) -> <T as MyNumsSummed>::Output {
match (xyz, abc) {
// both `xyz` and `abc` are empty; we have no work left to do.
((), ()) => (),
// both `xyz` and `abc` have > 1 element.
// we add what we can and recurse using the remaining elements.
(
(x, y_etc @ ..),
(a, b_etc @ ..),
) => {
let x: impl Add = x;
let y_etc: impl (..Add) = y_etc;
compose!(x + a, ..sum_my_nums(y_etc, b_etc))
},
// the tuples aren't the same length.
// perhaps the compiler will be able to detect that `xyz` and `abc`
// resue `T` and so are gauranteed to be the same length
// but this isn't necessary for an MVP.
_ => panic!("you've been a naughty boy!"),
}
}
fn main() {
let abc = (1u8, 2u16, 3u32);
let xyz = (2u8, 3u16, 5u32);
let summed_up = sum_my_nums(abc, xyz);
assert_eq!(summed_up, (3, 5, 8));
}implementation-wise, we just need to hold off on desugaring the arms into branches until monomorphisation when we have canonicalised the types.8
the most recent popular variadic generics proposal included the concept of "lifetime packs" (i.e. variadic lifetimes) and similar ideas for const generics. i'm going to be honest when i say that i just don't really understand what the point is or how it works, but even despite that, i think the functionality can be mirrored with what i call the "smuggler pattern":
trait Template {
type Smuggled<'a>;
}
struct Ref<T>(PhantomData<T>);
impl<T> Template for Ref<T> {
type Smuggled<'a> = &'a T;
}
trait Smuggler {
type Filled<T: Template>;
}
struct Lt<'a>(PhantomData<&'a ()>);
impl<'a> Smuggler for Lt<'a> {
type Filled<T: Template> = T::Smuggled::<'a>;
}
trait SmugglerList {
type Filled<T: Template>;
}
impl SmugglerList for () {
type Filled<T: Template> = ();
}
impl<B: Smuggler, U: (..Smuggler)> SmugglerList for (B, ..U) {
type Filled<T: Template> = (
B::Filled::<T>,
..(<U as SmugglerList>::Filled::<T>),
);
}
fn by_ref<T: Template, L: (..Smuggler)>() -> <L as SmugglerList>::Filled::<T>;
let things: (&'a u32, &'static u32) = by_ref::<Ref<u32>, (Lt<'a>, Lt<'static>)>();this example can probably be shrunk significantly but it illustrates how we can define a Template and instantiate it with a lifetime (held by Lt and injected via Smuggler). exactly the same setup would work for const generics.
often, especially to clean up the signature of functions like core::iter::zip, a language feature is suggested that allows us to specify a variadic number of parameters for a function. that would fit into this design as such:
trait IterList {
type Item;
}
impl IterList for () {
type Item = ();
}
impl<T: Iterator, U: (..Iterator)> IterList for (T, ..U) {
type Item = (..T::Item, ..(<U as ItemList>::Item));
}
fn zip<T: (..Iterator)>(..iters: T) -> impl Iterator<Item = <T as IterList>::Item>;i think whether or not this should be valid creeps far out of the scope variadic generics as specified in this document. personally, i think its pretty unRusty as it easily allows overloading:
trait CheekyParams: (..) {}
impl CheekyParams for (i32) {}
impl CheekyParams for (str, String) {}
fn be_cheeky(..params: impl CheekyParams);it could be handy to have the reverse syntax, allowing us to supply arguments to functions variadically:
let a = todo!();
let b = todo!();
let c = todo!();
let all_my_args = (a, b, c);
do_thing_with(..all_my_args);but even this has limited use. to know that do_thing_with is receiving correct arguments, we have to know that all_my_args is the right length and is typed correctly.
we might want to implement both anyway but constrain its applicability in function signatures to provably finite tuples. i think the syntax could be useful for function pointers:
trait Curry {
type Arg;
type Next;
fn with(self, arg: Self::Arg) -> Self::Next;
}
// the leaf implementation:
impl<T, R: FnOnce(T) -> R> Curry for F {
type Arg = T;
type Next = R;
fn with(self, arg: T) -> R {
self(arg)
}
}
// this implementation takes two leading args `T` and `U`,
// so that it applies only to functions with 2 or more args.
impl<T, U, V: (..), R, F: FnOnce(T, U, ..V) -> R> Curry for F {
type Arg = T;
type Next = impl FnOnce(U, ..V) -> R;
fn with(self, first: T) -> Self::Next {
// this is okay because `Self::Next: FnOnce<U>`.
// the types are bound to the same generic parameter.
move |second: U, ..rest: V| {
// this is okay because `Self: FnOnce<(T, U, ..V)>`.
// removing the concrete `T` and `U`, both sets of remaining parameters
// have type `U`.
self(first, ..rest)
}
}
}...
Footnotes
-
this can be done by introducing a new kind of generic parameter of the same order as const value parameters and type parameters ↩
-
is there a more recognisable name for this than “level”? kind? order? system? ↩
-
the partially-obsolete plural of "syntax". greek is a fantastic language, by the way ↩
-
unless we want to allow tuples to unpack across generic type parameters, like
Vec<..(T, Alloc)>which looks a bit mad, even for me. ↩ -
i'm confident this is the upper bound but it seems like a pretty disingenuous way to represent the complexity, which is dependent on both $s$ and $v$. if $v$ is $1$ (which it nearly always is), then the operation is $O(1)$. in particular this means if we disallow unpacking multiple
..Ts in a single tuple (which might be hard), the operation is always $O(1)$. a better upper bound is $O(\frac{v(s + v - 1)!} {s!v!})$, though i've only ever seen big $O$ defined in terms of a single variable. also, is $O(\frac{2n!}{n!})$ the same as $O(n!),$? if it isn't evident, i've never been taught big $O$, i just make it up as i go. ↩ -
i'm always a bit skittish about using this term because it seems to describe something very specific but i'm not quite sure what. did i get it right this time? ↩
-
is this starting to sound repetitive? is it? welcome to hell. ↩
-
is this how it already works? large parts of the Rust compiler are still MIRaculous to me. ↩