A vision for variadic generics in Swift

This cleverly avoids involving the type of an empty tuple, but is that always possible?

protocol SomeProto {
    static func foo()
}

extension String : SomeProto {
    static func foo() { print("hello from String.foo()") }
}

struct S<Element...> where Element : SomeProto {
    init(_ elts: (Element...)) { }
    func dropFirst<First, Rest...> where (Element...) == (First, Rest...) { /* elided */ }
    func callFoo<First, Rest...>(_ type: First.Type = First.self) where (Element...) == (First, Rest...) {
        type.foo()
    }
}

let a = S("hello")
print(type(of: a)) // "S<String>"

let b = a.dropFirst()
print(type(of: b)) // "S<>"

b.callFoo() // what implementation of `foo()` is called?

The type of b is S<>, so you cannot call b.callFoo() because S<> does not satisfy the same-type requirement on callFoo().

If (Elements...) == (First, Rest...) is not satisfied when Elements == { }, I think this implies the empty pack doesn’t contain itself? I think this is desirable, since it seems to provide a base case for recursion.

Can you clarify what you mean by containment here?

The type substitution and matching rules written down in my pitch:

If Elements = {}, then (Elements...) = (), and () doesn't match (First, Rest...) because (First, Rest...) has one non-variadic element, so it can only match a tuple of length greater than or equal to one.

(_: Int) would match (First, Rest...) with First := Int and Rest := {}, and (Int, String) would match (First, Rest...) with First := Int and Rest := {String}, for example.

Thank for you such a thorough response!

Obviously you’re one the authorities on this, so if you say we can’t get rid of tuples under the hood then I suppose that’s that, but if I could ask a little more about it would love to know a little more.

Is it fair to say that most of the reasons you gave are about why it might be complicated to implement, as opposed to why it would be unacceptably source breaking? 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

1 Like

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

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

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.

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

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

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?

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

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

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)

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

1 Like

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.

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

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)>()

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

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