RFC: variadic generics

[eddyb]

The Problem

• fn types need a reform, and being able to define a trait with a variable number of type parameters would help
• working with functions which have a variable number of arguments is impossible right now (e.g. a generic bind method, f.bind(a, b)(c) == f(a, b, c)) and defining such functions may only be done (in a limited fashion) with macros
• tuples also have similar restrictions right now, there is no way to define a function which takes any tuple and returns the first element, for example

The Solution: Part One

C++11 sets a decent precedent, with its variadic templates, which can be used to define type-safe variadic functions, among other things.
I propose a similar syntax, a trailing ..T in generic formal type parameters:

type Tuple<..T> = (..T); // the parens here are the same as the ones around a tuple.
// use => expansion
Tuple<> => ()
Tuple<int> => (int,)
Tuple<A, B, C> => (A, B, C)

The simple example above only uses ..T, but not T itself.
The question which arises is this: what is T? C++11 has a special case for variadic parameter packs, but we can do better.
We have tuples. We can use them to store the actual variadic generic type parameters:

// Completely equivalent definition:
type Tuple<..T> = T;
// Detailed expansion of (..T) from above:
Tuple<> => (..()) => ()
Tuple<int> => (..(int,)) => (int,)
Tuple<A, B, C> => (..(A, B, C)) => (A, B, C)

The Solution: Part Two

Now that we know the answer is "tuples", everything else is about extending them.
The prefix .. operator would expand a tuple type:

// in another tuple type:
type AppendTuple<T, U> = (..T, U);
type PrependTuple<T, U> = (U, ..T);
AppendTuple<PrependTuple<Tuple<B>, A>, C> => (A, B, C)
// in a fn type's parameter list:
type VoidFn<..Args> = fn(..Args);
VoidFn<A, B, C> => fn(A, B, C);
// in a variadic generic parameter list:
Tuple<..(A, B, C), ..(D, E, F)> => (A, B, C, D, E, F)

Then we can do the same thing with values:

// in another tuple:
(..(true, false), ..(1, "foo"), "bar") => (true, false, 1, "foo", "bar")
// in a function call:
f(..(a, b), ..(c, d, e), f) => f(a, b, c, d, e, f)

There's only one piece missing: we're still not able to define a function which takes a variable number of arguments.
For this, I propose ..x: T (where T is a tuple type) in a pattern, which can be used to "capture" multiple arguments when used in fn formal arguments:

// Destructure a tuple.
let (head, ..tail) = foo;
// This function has the type fn(int, A, B, C), and can be called as such:
fn bar(_: int, ..x: (A, B, C)) -> R {...}

A type bound for ..T (i.e. impl<..T: Trait>) could mean that the tuple T has to satisfy the bound (or each type in T, but that's generally less useful).

Examples:

// The highly anticipated Fn trait.
trait Fn<Ret, ..Args> {
    fn call(self, .._: Args) -> Ret;
}
impl Fn<Ret, ..Args> for fn(..Args) -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}
impl Fn<Ret, ..Args> for |..Args| -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}

// Cloning tuples (all cons-list-like algorithms can be implemented this way).
impl<Head, ..Tail: Clone> Clone for (Head, ..Tail) {
    fn clone(&self @ &(ref head, ..ref tail)) -> (Head, ..Tail) {
        (head.clone(), ..tail.clone())
    }
}
impl Clone for () {
    fn clone(&self) -> () {
        ()
    }
}

// Restricting all types in a variadic tuple to one type.
trait ArrayLikeTuple<T> {
    fn len() -> uint;
}
impl<T> ArrayLikeTuple<T> for () {
    fn len() -> uint {0}
}
impl<T, ..Tail: ArrayLikeTuple<T>> ArrayLikeTuple<T> for (T, ..Tail) {
    fn len() -> uint {
        1 + Tail::len()
    }
}

// And using that trait to write variadic container constructors.
impl<T> Vec<T> {
    fn new<..Args: ArrayLikeTuple<T>>(..args: Args) -> Vec<T> {
        let v: Vec<T> = Vec::with_capacity(Args::len());
        // Use an unsafe move_iter-like pattern to move all the args
        // directly into the newly allocated vector. 
        // Alternatively, implement &move [T] and move_iter on that.
    }
}

// Zipping tuples, using a `Tuple` kind and associated items.
trait TupleZip<Other>: Tuple {
    type Result: Tuple;
    fn zip(self, other: Other) -> Result;
}
impl TupleZip<()> for () {
    type Result = ();
    fn zip(self, _: ()) -> () {}
}
impl<A, ATail: TupleZip<BTail>, B, BTail: Tuple> TupleZip<(B, ..BTail)> for (A, ..ATail) {
    type Result = ((A, B), ..ATail::Result);
    fn zip(self @ (a, ..a_tail), (b, ..b_tail): (B, ..BTail)) -> Result {
        ((a, b), ..a_tail.zip(b_tail))
    }
}

Todo

• better formal descriptions
• figure out the details of pattern matching
• more examples

[catamorphism]

Have you tried implementing the same use cases using macros? If so, how well did it work?

[eddyb]

Well, I'm not sure if any of this can be implemented with macros. You can emulate some variadic functions with macros (by writing them as macros in the first place), but it's nowhere near automatic.

[nikomatsakis]

My feeling: I think we will eventually want something like this if we aim to have trait types subsume closure types, but not for 1.0. I liked the idea of leveraging tuples but I don't know if complications arise and so forth.

[emberian]

@nikomatsakis afaik @eddyb is actively working on impleementing this

[emberian]

(also, 👍 on the proposal)

[eddyb]

I've done some research for the first part, expanding ..T where T is a tuple type, into a list of types (another tuple, fn arguments, actual generic type params. am I missing anything?), and it seems doable, I just need to make sure I'm not leaving unchecked cases around (it's not trivial to be conservative by default).

[brendanzab]

@catamorphism The issue with macros is: a. they cannot be used in methods, b. they are brittle and don't give very good error messages, and c. they have no knowledge of the type system. The nice thing about variadic generics is also that it will allow us to desugar lots of the language.

@eddyb Have you looked at D's variadic type params?

[Blei]

@eddyb: maybe another implementation to look at would be clay, though they have a quite a bit more powerful generics system than Rust.

[eddyb]

@bjz I have now, it uses tuples as well, but I'm not seeing tuple destructuring (e.g. let (head, ..tail) = self;) nor tuple expansion (e.g. (head.clone(), ..tail.clone())), and it has array syntax for tuples, doesn't look as nice IMO.

@Blei oh, Clay has pretty much the same concept, AFAICT. Thanks for that, better to reinvent the wheel in a way that works (and we like prior work in Rust, don't we?).

[liigo]

@eddyb Why not T.. ? (A,B,C).. => A,B,C

fn call(self, args: Args..) -> Ret {
self(args..) // much more intuitive, i think
}

[eddyb]

@liigo prefix .. is already used in fixed-length vectors (though it means something different there), vector pattern matching, structural record update and it fits with prefix notations across the language (e.g. pointer types).
Also, as @Blei pointed out, Clay has prior work on this tuple-based model, and it uses the same prefix .. notation.
There are probably some grammar details (which I'm not entirely familiar with) that make a prefix .. easier to parse than a postfix ...

That being said, I'm not fundamentally opposed to a postfix .., as long as you can get the core devs to agree on it.

[glaebhoerl]

My only concern here is whether/how this might interact with type inference, and future things like higher-kinded types (or i.o.w. just the presence of a kind level above the type level at all), type-level currying if we ever add it (see "Type system thoughts" email for why we might want to), and so forth. In particular, if we have kinds, would ..type or whatever be one?

And, there's some of this in the OP, but could you do a compare-and-contrast (of advantages/disadvantages, expressiveness, simplicity/complexity etc.) relative to C++'s variadic templates? Variadic templates are super useful, but they're also super far away from anything that could be called simple and elegant.

[nikomatsakis]

I'll admit to some trepidation about potential interactions with other parts of the type system as well. I don't know what problems might arise because I haven't given this any serious thought, and I don't think I will have time to give this serious thought until the rest of the system is more nailed down.

[nikomatsakis]

I read over the proposal in more detail and I've got some thoughts and questions. First off, I think we may want to model this in the Rust model that I've been working on. This is, after all, what it's for -- to uncover complications that arise before we are knee deep in implementation. Unfortunately the model is currently limited to the reduction semantics (no type system yet).

Second, here is an attempt to codify the rules that I see in what you wrote. Let me know if you think this is accurate:

1. A type parameter declared as ..T is required to be instantiated with a "tuply" type, meaning either an actual tuple type (U, ...) or another type parameter U also declared as ..U. The aim here is to ensure that during monomorphization such types will ultimately be tuples.
2. The (formal) type grammar is extended with new forms that include an expando type Tz. In each case, Tz must be a "tuply" type parameter (see below).

• (T1, ..., Tn, ".." Tz) -- expando tuple
• fn(T1, ..., Tn, ".." Tz) -- expano function type
• |T1, ..., Tn, ".." Tz| -- expando closure type
• proc(T1, ..., Tn, ".." Tz) -- expando proc type
• N<T1, ..., Tn, ".." Tz) -- expando path type

1. As a convenience, we allow users to write types like (A, B, ..(C, D)) that are not part of the formal type grammar. We normalize such types immediately into the equivalent (A, B, C, D). We also permit users to write N<A,...,N, M, O> and we normalize that to N<A,...,N,(M,O)>
2. When substituting a value for an tuply type parameter, if the tuply is used in an expando position, the tuple is normalized. So for example applying the substitution [..S => (C, D)] to the type (A, B, ..S) yields the type (A, B, C, D).
3. The definitions of traits and expressions are also extended in a somewhat similar way. In the case of expressions, the "expando" values must be of tuply type.

I think this largely holds together, but this is only a cursory examination. Mostly just trying to extract rules from the examples.

I didn't think too hard about HKT, but my first thought is that a tuply type parameter just has kind * (it must after all be matched to a tuple, which is a type), and hence that this kind of "fits in" relatively ok.

Some questions / thoughts

• I guess we want ..T to declare a tuply type parameter vs a type bound T:Tuple, since it corresponds to syntactic sugar on the referencing side.
• There is some ambiguity in various parts, e.g., the meaning of ..T:Trait (does that mean that T, the tuple type, implements Trait? Or that all the types ..T individually implement Trait?) Both have some value. To be consistent I imagine we'd have to add a notion like ..T:..Trait to distinguish the difference.
• At least one example is bogus, I believe. The description writes:

type AppendTuple<T, U> = (..T, U);
type PrependTuple<T, U> = (U, ..T);
AppendTuple<PrependTuple<Tuple<B>, A>, C> => (A, B, C)

But by the rules I gave above this an error, because T (as declared n AppendTuple and PrependTuple) was not declared as tuply. Hence it should be:

type AppendTuple<..T, U> = (..T, U);
type PrependTuple<..T, U> = (U, ..T);
AppendTuple<PrependTuple<Tuple<B>, A>, C> => (A, B, C)