Pitch: Variadic generic types abstracting over packs

Evolution Pitches
1

Allow Generic Types to Abstract Over Packs

Introduction

Previously SE-0393 introduced type parameter packs and several related concepts, allowing generic function declarations to abstract over a variable number of types. This proposal generalizes these ideas to generic type declarations.

Motivation

Generic type declarations that abstract over a variable number of types arise naturally when attempting to generalize common algorithms on collections. For example, a lazy ZipSequence might be generic over two sequences. It would be possible to declare a ZipSequence type which presents the elements of a fixed list of sequences as a sequence of tuples:

struct ZipSequence<each S: Sequence>: Sequence {
  typealias Element = (repeat each S.Element)

  let seq: (repeat each S)

  func makeIterator() -> Iterator {
    return Iterator(iter: (repeat (each seq).makeIterator()))
  }

  struct Iterator: IteratorProtocol {
    typealias Element = (repeat each S.Element)

    var iter: (repeat each S.Iterator)

    mutating func next() -> Element? {
      return ...
    }
  }
}

Proposed solution

In the generic parameter list of a generic type, the each keyword declares a generic parameter pack, just like it does in the generic parameter list of a generic function. The types of stored properties can contain pack expansion types, as in let seq and var iter above.

Detailed design

Swift has the following kinds of generic type declarations:

  • Structs
  • Enums
  • Classes (and actors)
  • Type aliases

A generic type is variadic if it directly declares a type parameter pack with each, or if it is nested inside of another variadic type. In this proposal, structs, classes, actors and type aliases can be variadic. Enums will be addressed in a follow-up proposal.

Single parameter

A generic type is limited to declaring at most one type parameter pack. The following are allowed:

struct S1<each T> {}
struct S2<T, each U> {}
struct S3<each T, U> {}

But this is not:

struct S4<each T, each U> {}

However, by virtue of nesting, a variadic type might can still abstract over multiple type parameter packs:

struct Outer<each T> {
  struct Inner<each U> {
    var fn: (repeat each T) -> (repeat each U)
  }
}

Referencing a variadic type

When used with a variadic type, the generic argument syntax S<...> allows a variable number of arguments to be specified. Since there can only be one generic parameter pack, the non-pack parameters are always specified with a fixed prefix and suffix of the generic argument list.

struct S<T, each U, V> {}

S<Int, Float>.self  // T := Int, U := Pack{}, V := Float
S<Int, Bool, Float>.self  // T := Int, U := Pack{Bool}, V := Float
S<Int, Bool, String, Float>.self  // T := Int, U := Pack{Bool, String}, V := Float

Note that S<Int, Float> substitutes U with the empty pack type, which is allowed. The minimum number of generic arguments is equal to the number of non-pack generic parameters. In our above example, the minimum argument count is 2, because T and V must always be specified:

S<Int>.self // error: expected at least 2 generic arguments

If the generic parameter list of a variadic type consists of a single generic parameter pack and nothing else, it is possible to reference it with an empty generic argument list:

struct V<each T> {}

V<>.self

Note that V<> is not the same as V. The former substitutes the generic parameter pack T with the empty pack. The latter does not constrain the pack at all and is only permitted in contexts where the generic argument can be inferred.

A placeholder type in the generic argument list of a variadic generic type is always understood as a single pack element. For example:

struct V<each T> {}

let x: V<_> = V<Int>()  // okay
let x: V<_, _> = V<Int, String>()  // okay
let x: V<_> = V<Int, String>()  // error

Stored properties

In a variadic type, the type of a stored property can contain pack expansion types. The type of a stored property cannot itself be a pack expansion type. Stored properties are limited to having pack expansions nested inside tuple types, function types and other named variadic types:

struct S<each T> {
  var a: (repeat each Array<T>)
  var b: (repeat each T) -> (Int)
  var c: Other<repeat each T>
}

This is in contrast with the parameters of generic function declarations, which can have a pack expansion type. A future proposal might lift this restriction and introduce true "stored property packs":

struct S<each T> {
  var a: repeat each Array<T>
}

Requirements

The behavior of generic requirements on type parameter packs is unchanged between generic functions and generic types.

Conformances

Variadic structs, classes and actors can conform to protocols. The associated type requirements of the protocol may be fulfilled by a type alias whose underlying type contains pack expansions.

Type aliases

As with the other variadic types, a variadic type alias either has a generic parameter pack of its own, or can be nested inside of another variadic generic type.

The underlying type of a variadic type alias can reference pack expansion types in the same manner as the type of a stored property. That is, the pack expansions must appear in nested positions, but not at the top level.

typealias Element = (repeat each S.Element)
typealias Callback = (repeat each S) -> ()
typealias Factory = Other<repeat each S>

Unlike structs and classes, but like other type aliases, variadic type aliases can also be nested inside of generic functions.

Classes

While there are no restrictions on non-final classes adopting type parameter packs, for the time being the proposal restricts such classes from being the superclass of another class.

An attempt to inherit from a variadic generic class outputs an error. The correct behavior of override checking and initializer inheritance in variadic generic classes will be dealt with in a follow-up proposal:

class Base<each T> {
  func foo(t: repeat each T) {}
}

// error: cannot inherit from a class with a type parameter pack
class Derived<U, V>: Base<U, V> {
  override func foo(t: U, _: V) {}
}

Source compatibility

Variadic generic types are a new language feature which does not impact source compatibility with existing code.

ABI compatibility

Variadic type aliases are not part of the binary interface of a module and do not require runtime support.

All other variadic types make use of new entry points and other behaviors being added to the Swift runtime. Since the runtime support requires extensive changes to the type metadata logic, backward deployment to older runtimes is not supported.

Replacing a non-variadic generic type with a variadic generic type is not binary-compatible in either direction. When adopting variadic generic types, binary-stable frameworks must introduce them as wholly-new symbols.

Future directions

A future proposal will address variadic generic enums, and complete support for variadic generic classes.

Another possible future direction is stored property packs, which would eliminate the need to wrap a pack expansion in a tuple type in order to store a variable number of values inside of a variadic type. However, there is no expressivity lost in requiring the tuple today, since the contents of a tuple can be converted into a value pack.

Alternatives considered

The one-parameter limitation could be lifted if we introduced labeled generic parameters at the same time. The choice to allow only a single (unlabeled) generic parameter pack does not preclude this possibility from being explored in the future.

Another alternative is to not enforce the one-parameter limitation at all. There would then exist variadic generic types which cannot be spelled explicitly, but can still be constructed by type inference:

struct S<each T, each U> {
  init(t: repeat each T, u: repeat each U) {}
}

S(t: 1, "hi", u: false)

It was felt that in the end, the single-parameter model is the simplest.

We could require that variadic classes are declared final, instead of rejecting subclassing at the point of use. However, since adding or removing final on a class is an ABI break, this would preclude the possibility of publishing APIs which work with the existing compiler but can allow subclassing in the future.

15 Likes
2

If the need arises, would it be possible to have let x: V<repeat _> = V<Int, String>() or some such to indicate a variable number of inferred types?

3 Likes
3

Or in full generality, repeat each _. Then you can get really fancy: G<repeat Array<each _>>.

4 Likes
4

This is great, but I find the limitation on properties hard to understand, why can't you have a when presumably you could have b?

struct S<each T> {
  var a: (repeat each T)
  var b: (repeat each Box<T>)
}
struct Box<T> { 
  var contents: T
}

Is it harder to implement, or what is the reason to not allow it?

It also seems like a pretty strange situation that we don't allow multiple variadic generic parameters, simply because of notation. It would seem that we should then look for alternative notation, rather than limit the functionality. For example, we could use semicolons within type packs, or braces around them when needed:

struct V<each T, each R> {}

let x1 = V<Int, Bool; String>() // T is { Int }, R is { Bool String }
let x2 = V<Int, { Bool, String }>() // ditto
let x3 = V<Int, (Bool, String)>() // ditto
1 Like
5

You can have both a and b. What you cannot have is this, without the parens:

struct S<each T> {
  var a: repeat each T
}

Recall that in a variadic generic function you can have both:

func f<each T>(t: repeat each T, tt: (repeat each T)) {}

f(t: 1, "hi", false, tt: (1, "hi", false))

Elsewhere pack types don't have a concrete spelling and we flatten them out into the surrounding comma-separated list, so it would be a bit odd if variadic generic types had this new syntactic form. I think labeled generic parameters would fit in better with the rest of the model, but I'd rather explore that in a separate proposal.

6 Likes
6

Hm, then it’s even harder to understand the reason for this limitation! What is the difference between storing it in a tuple and without? What does the tupleness prevent us from doing?

7

The limitation is there because you can do something with stored properties that you cannot with function parameters, and that is apply substitutions.

Consider these two definitions:

struct G1<each T> {
  var x: (repeat each T)
}

struct G2<each T> {
  var x: repeat each T
}

If I have

func f1(value: G1<Int, String>) {
  let x = value.x
}

Then the type of value.x is the tuple type (Int, String) because it's what we get after replacing T with Int, String inside (repeat each T).

Now consider

func f2(value: G2<Int, String>) {
  let x = value.x
}

Here it would appear that value.x is an "unwrapped" concrete pack type. This is the same reason that a function cannot return a pack expansion:

func bad<each T>(_ t: repeat each T) -> repeat each T {}
func good<each T>(_ t: repeat each T) -> (repeat each T) {}

In the above, it is not clear what concrete type to assign to the result of something like bad(1, "hi").

5 Likes
8

Thanks for the explanation, though I must say I never understood that limitation either, i.e. why you can't have a local variable with type repeat each T, or why you can't return that -- I don't quite understand what you mean by " it is not clear what concrete type to assign to the result of something like bad(1, "hi")". Wouldn't it just be { Int, String }?

I know there is no such syntax "in the surface language", though that is another thing I don't get. Why not just introduce it, especially if the lack of syntax is what's stopping us from having var x: repeat each T = ....

It seems that there is a desire to keep the full "vector" abstract in some sense, but that just seems to serve to make things harder to understand. Is there a technical reason against simply introducing a concrete (but elementwise and lengthwise generic) vector type? That would at least be much easier to understand.

9

The lack of surface syntax is not what's preventing us from introducing local variable and stored property packs. I think we should have both local variable and stored property packs in the future, but 1) those are both additive, and 2) those features do not prevent us from needing to work with abstract tuples. For example, to enhance the functionality of tuples themselves, we need to be able to write generic code that abstracts over the number of tuple elements, e.g. to implement conformances for all tuple types when their elements each conform to some protocol.

The issue with stored property packs is that they admit concrete packs as a concept into the language. Packs are not first-class values, so you cannot access a stored property pack concretely as a scalar value. We need to be able to project out certain elements from the stored property pack. That's another feature I think we should have, but it involves designing a suite of pack projection APIs into the language and standard library. Types that can abstract over parameter packs are still extremely useful without these enhancements, which is why there are separate future directions of SE-0393.

EDIT: There's a bit more commentary on concrete packs in the "variadic generics vision" document that I wrote a few months ago, though it uses the old ... syntax for pack expansion: https://github.com/hborla/swift-evolution/blob/variadic-generics-vision/vision-documents/variadic-generics.md#concrete-packs

6 Likes
10

Even before packs, we had this kind of thing because you can't write

func f() -> Int, String {}

And instead you write

func f() -> (Int, String) {}

The desire here is to avoid introducing a new concrete aggregate type that is basically the same as a tuple type.

8 Likes
11

I guess it all comes down to this. I don't quite get why they aren't, or even exactly what that means. I mean normal generic types aren't concretely known at compile time either, but we can still use a generic T as if it were, because in a concrete situation it will be known:

func allowed<T>(value: T) -> T? {
    let local: T = value // By the time we get here, T will be known
    if Bool.random() {
        return local
    } else {
        return nil
    }
}

func forbidden<each T>(value: repeat each T) {
    let local: repeat each T = value // presumably when we get here, we know what value looks like
}

EDIT:

I suppose it's related to the idea that a pack is "a comma separated list". And this is what I don't understand, why can't a pack just be a tuple? In the concrete case, that is essentially what it is anyway.

What do we gain from making this so abstract?

12

This is addressed in the alternatives considered of SE-0393.

3 Likes
13

Can a placeholder represent the empty pack type? For example:

struct S<T, each U, V> {}

S<Int, _, Float>.self  // T := Int, U := Pack{}, V := Float
14

The reasoning here reminds me of why Swift doesn’t model function arguments as tuples.

2 Likes
15

We do plan on allowing this eventually, but you will probably need to write let local: repeat each T = repeat each value.

Compare this with

let local: (repeat each T) = (repeat each value)

In the latter, local is a single value you can refer to and pass around. It's type is a tuple type.

I can also write:

let fn: (repeat each T) -> () = { ... }

And define a closure which takes a variable number of arguments. Now this is not the same as a closure taking a single tuple argument. This shows why packs are defined abstractly as "things that go in a comma-separated list" and not as a new set of expressions involving tuple types specifically.

Packs and non-packs exist in separate universes, and a pack can only be used with an explicit expansion operation. Tuples, function parameter lists and named variadic generic types are all first-class "locations" where type packs can expand. Value packs similarly appear in tuple literal expressions, call argument expressions, and one day, inside collection literal expressions too. If we privileged tuples as the core thing that can be variadic, we'd need new kinds of "splat" operations on both types and values to make it work in all of these other contexts where packs can expand today.

(Perhaps if someone else is designing a new Swift-like language that happens to have variadic generics, they wouldn't need tuples at all, instead there could be a struct Tuple<each T> type in the standard library.)

16

I would think not: the placeholder being for a scalar type only, I'd expect an empty pack would have to be spelled like any other pack with the hypothetical repeat each _.

(Not to mention that, in that specific example, _ shouldn't be inferred to be an empty pack anyway regardless of spelling, as placeholders have always indicated that there is something there to be inferred from other information without a fallthrough to "nothingness" in the absence of any information. For example, for a non-variadic generic type S<T>, S<_> isn't equivalent in the absence of other context to either S<Never> or a hypothetical type-erased AnyS.)

4 Likes
17

The absence of a placeholder represents the empty pack type. S<_, _> leaves T and V open, but binds U to the empty pack type.

4 Likes
18

Within the proposed features, how can I write ChainSequence<each S: Sequence>, in which all each S should have a type T as their element?

It will be possible to write as this.

struct ChainSequence<each S: Sequence, Element> where (each S).Element == Element {}

But it requires additional Element in the type declaration, and users have to write ChainSequences<[Int], Set<Int>, ArraySlice<Int>, Int> even though the last Element is evident.

Is there any other way to express this kind of types?

19

If an empty chain ChainSequences<> isn't important, one could presumably make the first sequence a scalar parameter, i.e.: ChainSequences<FirstSequence: Sequence, each S: Sequence> where repeat (each S).Element == FirstSequence.Element, I think?

2 Likes
20

This is a swell way to do it.

But I suspect empty chain is important, especially in generic context. For example, this will be impossible, because there's no 'non-empty' constraint.

func foo<each T: Sequence>(sequences: T) where (each T).Element == Int {
    var chain = ChainSequence(repeat each sequences)
}

And it must be something like this.

func foo<each T: Sequence>(firstSequence: some Sequence<Int>, _ sequences: T) where (each T).Element == Int {
    var chain = ChainSequence(firstSequence, repeat each sequences)
}

I don't think it is desirable to propagate this workaround to generic context.

1 Like