A vision for variadic generics in Swift

Evolution Pitches
,
26

At the implementation level, I actually already added a "fake" Builtin.TheTupleType type with a generic signature <Elements...> that we can hang tuple conformances and extensions off of. So internally the compiler uses the same mechanism here as member lookup and conformance checking for nominal types. This won't be exposed to users though, like the rest of the Builtin module it's an implementation detail.

It's more that adding a new Tuple type to the standard library probably wouldn't simplify the language a whole lot, once you consider that the compiler still needs to special-case various behaviors involving it.

I just remembered another one -- the implicit conversion from (T, U, ...) -> () to ((T, U, ...)) -> () for closure values passed as function arguments.

The tuple labels thing sounds like the most source breaking possibility, and I would love to know if you think that this thing I posted the other day and tagged you and @hborla in is a relevant idea/could change anything

Your idea of adding named generic arguments is interesting, and I think we can explore this possibility at some point. However what we'd need to make struct Tuple<T...> a drop-in replacement for built-in tuples is a bit different; we want the concrete substitution for the Elements generic parameter to carry labels, so, eg if you instantiate the type with Tuple<a: Int, b: String>, then any mention of T... in the body preserves the labels a:b:. For example,

extension Tuple {
  func toArray() -> Tuple<Array<T>...> {}
}

let x = Tuple<a: Int, b: String>.toArray()
// x has type Tuple<a: Array<Int>, b: Array<String>>

It's also not clear how function calls would actually work, eg how do you call f() with T := {a: Int, b: String}? Since the parameter is unlabeled, perhaps f(a: Int, b: String) makes sense:

func f<T...>(_: T...) {}

But what if it has a label?

func f<T..., U...>(t: T..., u: U...) {}

I actually think we could one day solve these problems (or just say that labeled packs can only appear in a subset of the positions where packs can appear today) and support this in the future in a forward-compatible way, but maybe it's best to subset it out for now.

(I'm actually not a huge fan of labeled tuples at all! If I was designing a new Swift-like language from scratch, I would probably omit them entirely).

1 Like
27

Amazing! At the moment I have no particular personal needs on this front, I just feel a sort of existential discomfort (perhaps evidence of excessive emotional attachment to Swift) when I imagine a feature that we would love to have as a community being rendered forever impossible due to an oversight or external business pressures. If the door remains open then I’m happy as a clam for now

2 Likes
28

I meant “contained” in the same sense that the empty string ε is a substring of itself, because ε + ε = ε.

Having played around with it more on paper, I’m getting the sense that the current design avoids this issue by preventing an empty pack from being assigned to a non-variadic type parameter, whereas you can assign ε to a string.

29

I'm a little confused by this analogy, but perhaps it will help to clarify that an empty string is still a string. A parameter pack is not itself a type or a value, so a parameter pack cannot be assigned to or unified with something that is a type or a value. Packs are also flat lists, so packs cannot contain other packs.

For example, () is not an empty pack, it's an empty tuple. If we write a same-type requirement between the two tuple types (Elements...) == (), unification drills into the tuple structure and unifies Elements... with the empty list {}.

4 Likes
30

Yes, generic parameter packs can only ever bind to type packs, and plain old generic parameters can only ever bind to plain old types. A type pack is not a type.

Type packs are never written directly, but they arise when the type checker matches two tuple types or two function types against each other, and one of the two sides contains a generic parameter pack. So if you're calling func foo<T...>(_: Array<T>...) with an argument list whose argument types are (Array<Int>, Array<String>), then we bind T to the type pack {Int, String}.

There's no directly-expressible 'concatenation' operation on packs. However, if T and U are two packs, then (T..., U...) forms a new tuple type whose elements are the elements of the first pack, followed by the second. If you then match (T..., U...) against the tuple type consisting of a single type pack (V...), then V is bound to the type pack containing the elements of T followed by the elements of U. If either T or U is empty, everything works out as you expect.

1 Like
31

My brain has lost a lot of the context from the single-element tuple discussion, so forgive me if I’m retreading ground.

My understanding is that in shipping Swift, there is a strict division between scalars and tuples, and that () (aka Void) is a scalar, not a tuple. It was determined that type packs require admitting single-element tuples, but does it necessarily follow that zero-element tuples must exist, or that () is an (the?) instance of a zero-element tuple?

I also don’t recall a resolution to the question of whether single-element tuples are synonymous with scalars. Void has to remain a scalar, so if () is the spelling of a zero-element tuple, what is the definition of Void? If scalars are one-element tuples, perhaps the answer is typealias Void = (_: ())? But given that “Packs are also flat lists, so packs cannot contain other packs”, how would one describe the shape of Void in a same-type conformance?

32

I don’t actually know what I expect in this case.

33

This does not match my understanding. My understanding is that Void / () is an empty tuple. I'm not sure what you mean by "scalar" here, but there is a distinction between nominal and structural types. Void and other tuple types are structural (along with function types and metatypes), whereas structs, enums, classes, and actors are nominal types. We've defined "scalar" in the variadic generics terminology as an individual type, e.g. Int, (), or a non-pack type parameter, which is contrasted with a type parameter pack which has a length.

2 Likes
34

Yeah, and in particular tuples (both empty and non-empty) are scalar types (but they can contain type packs, just like a function type's parameter list can contain a type pack)

35

Eg, if T := {Int, String} and U := {}, then (T..., U...) and (U..., T...) are both equal to (Int, String).

1 Like
36

OK, sorry for reusing terminology. This post from @John_McCall is what I was keying off:

I guess since John calls them “element values”, “element types” might be a good term for non-tuple types. (It may be the case that all non-tuple types are nominal types, but since it’s possible to invent new non-nominal, non-tuple types in the future, I’m resisting using that term.)

That makes (_: Void) a tuple whose single element is the empty tuple, which yields Peano arithmetic: 0 ≡ (), 1 ≡ (_: ()), etc.

The thing I’m trying to figure out is whether that means it’s possible to match the () inside (_: ()), and whether it’s therefore possible to match a type variable to the empty list within (), because that’s where the problems emerge from. It sounds like as long as (_: T) is distinct from T, this isn’t possible, because a pack can unify with the inside of (_: T), but not with T itself.

37

Ah, I see. I think John's terminology isn't actually useful here because the tuple vs non-tuple distinction is not actually an important one in variadic generics.

The unification operation you're thinking of is only defined for types, and packs are not types, so a tuple can only unify with another tuple and not with another pack.

However, you can unify a one-element tuple that contains a type parameter pack (T...) with an empty tuple (), which will bind T to the empty type pack {}.

Similarly, unifying (T...) with the one-element tuple type (_: Int) binds T to the type pack {Int}.

Unifying (T...) with the Int type fails, because the right hand side is not a tuple type.

By this logic, unifying (T...) with (_: ()) will bind T to the type pack {()} which contains a single element, the empty tuple type.

Anywhere I had a tuple type above, I could have used a function type instead. So for instance, unifying (T...) -> () with (Int, String) -> () will bind T to {Int, String}.

2 Likes
38

Would it be possible for a type to have two variadic type parameters? E.g.

struct Example<(First...), (Second...)> {}
Example<(Void, Bool, Int), (Character, String)>()
39

I've added a note about naming convention to the document. I'll paste it here for ease of quoting for further questions, thoughts, and other feedback. Please let me know what you think!

A note on naming convention

In code, programmers naturally use plural names for variables representing lists. However, in this design for variadic generics, pack names can only appear in repetition patterns where the type or expression represents an individual type or value that is repeated under expansion. The recommended naming convention is to use singular names for parameter packs, and plural names only in argument labels:

struct List<Element...> {
  let element: Element...
  init(elements element: Element...)
}

List(elements: 1, "hello", true)

More broadly, packs are fundamentally different from first-class types and values in Swift. Packs themselves are not types or values; they are a special kind of entity that allow you to write one piece of code that is repeated for N individual types or values. For example, consider the element stored property pack in the List type:

struct List<Element...> {
  let element: Element...
}

The way to think about the property pack let element: Element... is "a property called element with type Element, repeated N times". When List is initialized with 3 concrete arguments, e.g. List<Int, String, Bool>, the stored property pack expands into 3 respective stored properties of type Int, String, and Bool. You might conceptualize List specialization for {Int, String, Bool} like this:

struct List<Int, String, Bool> {
  let element.0: Int
  let element.1: String
  let element.2: Bool
}

The singular nature of pack names becomes more evident with more sophisticated repetition patterns. Consider the following withOptionalElements method, which returns a new list containing optional elements:

extension List {
  func withOptionalElements() -> List<Optional<Element>...> {
    return List(elements: Optional(element)...)
  }
}

In the return type, the repetition pattern Optional<Element>... means there is an optional type for each individual element in the parameter pack. When this method is called on List<Int, String, Bool>, the pattern is repeated once for each individual type in the list, replacing the reference to Element with that individual type, resulting in Optional<Int>, Optional<String>, Optional<Bool>.

The singular naming convention encourages this model of thinking about parameter packs.

2 Likes
40

This isn’t planned, at least initially, because with a purely positional syntax for generic arguments there’s no way to disambiguate which concrete types end up in which pack. Some possibilities are to introduce argument labels for generic parameters, or the parenthetical notation in your example, or even to disallow writing the variadic type directly and force the user to rely on inference (but that seems like the worst option).

We’ll address these in the “Future Directions” section of the variadic types pitch.

2 Likes
41

A workaround for this in the meantime is to use outer generic types as ad-hoc "argument labels" for type arguments:

struct Zip<First...> {
  struct With<Second...> {
    typealias Value = ((First, Second)...)
  }
}

Zip<Int, String>.With<Bool, Int>.Value // ((Int, Bool), (String, Int))
11 Likes
42

Wow, that’s pretty.

Awesome, this whole explanation clarified my understanding and especially in light of the fact this is an advanced feature anyway I find your justification entirely satisfying.

If I’ve understood correctly, the reality of the reasoning matches the essence of what I was getting at in my question quoted below, although with your clarifications I see that my description could not be said to be correct as written.

1 Like
43

Thank you for the detailed explanation! Maybe I will just have to let it sink in, but initially I just don’t have the same intuition as you, because to me your hypothetical expanded version of the List struct would read more naturally as:

struct List<Int, String, Bool> {
  let elements.0: Int
  let elements.1: String
  let elements.2: Bool
}

It does feel like a closer question when it comes to more complex pack expansions, but I don’t find it too unnatural to read, e.g.:

return List(elements: Optional(elements)...)

In my mental model, when elements is expanded into a comma-separated list of, well, elements, each element takes along its own copy of the surrounding structure in which it sits. So Optional(elements), when treated with the expansion operator, naturally becomes Optional(elements.1), Optional(elements.2), and so on.

As I mentioned, another spelling that feels natural on first thinking of it would be element*, so we would have

return List(elements: Optional(element*)...)

This has a bit of the best of both worlds, in that the word itself is singular as is each element type, while the asterisk marks it as different from a normal value name with a particular connotation of plurality. That said, I imagine such a spelling might raise other issues including source compatibility and maybe it does not stand up to serious scrutiny.

3 Likes
44

FWIW, in my mental model, that's what the pack expansion operator ... does. It isn't element that's plural, it's Optional(element). Under substitution, the name element is replaced with an individual element from the pack.

Another FWIW, I didn't really internalize any of this until I wrote out some code examples and experimented with both naming conventions, so I encourage you to do the same and see how that evolves your understanding! That's not to say that you'll think about the code in the same way that I do - everyone internalizes concepts differently. In any case, I think it's a helpful exercise for folks participating in this discussion :slight_smile:

5 Likes
45

Thank you for writing this. I found myself nodding along when reading it, as you’ve covered the (large!) space of features and capabilities that I’d hope for variadic generics, and it fits together well.

The area I’m least convinced of is the use of “.element” for getting a pack from a tuple. It's an interesting operation, because it takes a single value and then expands it out into a pack.

For one thing, I think it would help if you tied this bit together explicitly with concrete packs and extensions on tuple types, because it would feel less magical if it had a signature we could write in the language:

extension <Element...> (Element...) {
  var element: Element... { /* it's okay for this implementation to be magic */ }
}

That might also make the behavior of .element on a tuple that contains an element labeled "element" clearer, because we'll need some name-lookup rule deals with extensions on labeled tuple types in the general case.

Also, I was a little surprised that this section doesn't contain an example of forwarding, because I think that's really the big win from getting a pack from a tuple:

struct CapturedArguments<Result, Parameters...> {
  var arguments: (Parameters...)

  func evaluate(with function: (Parameters...) -> Result) -> Result {
    return function(arguments.element...)
  }
}

Forwarding is mentioned earlier, but only in the "this is why packs and tuples are different" section as a reason for making them different.

Now, the moment I see forwarding, scope creep sets in and I would like to also solve the variadic forwarding problem. Can I have .element on an array, for example?

func f(_ args: Int...) { }
func g(_ args: Int...) {
  f(args.element...)  // could this make sense?
}

It's in a sense very different, because the length of the array is a run-time value, so you have a concrete type [Int] that would need to be expanded into a homogeneous parameter pack of runtime-computed length. But I think we can express that notion of a "homogeneous parameter pack of runtime-computed length" already through the generics system:

func gPrime<T...>(_ args: T...) where T == Int { 
  f(args.element...) // okay, I think? expand the homogeneous pack and capture results into array
}

Allowing an array (or any Sequence?) to be turned into a homogeneous parameter pack has a similar feel to implicit opening of existentials, because it takes a run-time-computed value (length for arrays vs. dynamic type for existentials) and turns it into something more static (# of arguments in a pack vs. generic argument of the dynamic type of the existential). For example:

func printAll<T...>(_ args: T...) { }

func printArray<Element>(_ array: [Element]) 
  printAll(array.element...) // # of parameters in the pack "T" depends on length of array!
}

Doug

6 Likes