A vision for variadic generics in Swift

Parameterized extensions of nominal types are something we would like to add at some point. The syntax for tuple conformances can be introduced without the full feature though, the only overlap is parser support.

Good question.

There are a couple of reasons, maybe not entirely convincing. Tuple elements can have labels, whereas type packs cannot carry labels (as currently proposed, at least).

Another reason is that tuples have special behavior in the type checker with implicit conversions between tuple types where element types convert, for example. Of course, you can imagine a language where Tuple is a type in the standard library that still has special type checker behavior (just like Optional does today, for example).

Tuples are also special in other ways, for example an obscure difference between a tuple and a generic struct is that closures can be stored in a tuple at different abstraction levels (calling conventions) whereas a closure stored in a generic struct (struct G<T> { var t: T }) must be wrapped in a thunk that passes all parameters and results indirectly. But again, Optional has the same behavior where SILGen knows how to apply re-abstraction thunks as needed to the optional payload.

Perhaps if we were starting from scratch, we could do away with tuples as a primitive type entirely, but for now having tuples be their own thing still continues to make sense.

There's no real reason this cannot be supported eventually. My thinking is that adding members to arbitrary tuple types is potentially confusing and merits further discussion, and initially we would only allow this exact syntax

extension <T...> (T...): P where T: P {}

that is,

  • the extension must define a conformance of the tuple type to P
  • the conformance must be conditional on each element conforming to P
  • no other requirements are permitted

However, we could relax these restrictions over time if good use-cases are proposed, and then something like

extension (Int, Bool) {}

would desugar to

extension <T...> (T...) where (T...) == (Int, Bool) {}

You could even imagine something like

extension <T..., U> (T...) where (T...) == (Int, U, Bool), U: Equatable {}

with the shorter equivalent form

extension (Int, some Equatable, Bool) {}

But all that extra sugar could probably go in a stand-alone pitch/proposal.

5 Likes

Ah, I missed this during the SE review. Thanks for the reference!

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