SE-0393: Value and Type Parameter Packs

vykut · 2023-03-23T21:46:13.731Z

I don’t know if this has been mentioned before, but what if we were to constrain the generic type to a (new) variadic type, instead of marking it as a variadic generic with the each keyword?

Basically, instead of writing

func foo<each T>(_: repeat each T) -> each T {}
struct Foo<each T>  {
    let foo: (repeat each T)
}

Would it be possible to write

func foo<T: pack>(_: T) -> T {} // we know T is a pack
struct Foo<T: pack> {
    let foo: T.each // equivalent to (repeat each T)
}

If we want to constrain T to be a pack of Sequences, we could do

func foo<T: pack & Sequence>(_: T) -> T {}
struct Foo<T: pack & Sequence> {
    let foo: T.elements // equivalent to (repeat each T)
}

// also possible
func foo<T>(_: T) -> T where T: pack, T: Sequence {}
struct Foo<T> where T: pack, T: Sequence {
    let foo: T.elements // equivalent to (repeat each T)
}

By pack being a type rather than a keyword, that could also give devs the flexibility of extending its functionality

type pack { 
    // needs some kind of element semantics

    var elements: (Self.Element…) // equivalent to (repeat each T)
    var count: Int // number of elements in a pack
    func map<T>(_ transform: (Self.Element) throws -> T) rethrows -> [T] // iterates over each element of the pack and transforms it
}

EDIT:
So thinking about this a little longer, instead of constraining T to pack & Sequence & OtherProtocol, we could parametrize the pack constraint
e.g

type Variadic<Element> {} // or type Pack<Element>

func foo<T: Variadic>(_: T) -> T {}
struct Foo<T: Variadic> {}

func baz<T: Variadic<Sequence>>(_: T) -> T {}
struct Baz<T: Variadic<Sequence>> {}

Thank you!

Douglas_Gregor · 2023-03-23T22:35:06.967Z

xwu:

What is your evaluation of the proposal?

I think this is a fantastic proposal, and the right first step toward variadic generics. The care and level of detail provided in this proposal are exceptional, and I feel like it's hit the design sweet spot for such a challenging feature.

I have some quibbles with a few details of the proposal, which I'll get to below, but they are all minor.

xwu:

Is the problem being addressed significant enough to warrant a change to Swift?

It is. I included variadic generics in the "Generics Manifesto" years ago, back before we had a process for vision documents, because it's important kind of abstraction we're missing from the language. Folks end up writing lots of overloads based on arity, stamping them out manually or with external-source-generating tools, which is quite unfortunate. Macros will make some of this easier, but it still won't be a good state.

xwu:

Does this proposal fit well with the feel and direction of Swift?

Yes; we've been trending toward this for a while. The syntax proposed here---with repeat and each fits well with the way we've been introducing similar type-system features (some, any, borrowing, etc.).

xwu:

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I'm the original designer and implementer of C++ variadic templates, which are the most similar language feature to this. The design proposed here is better and more comprehensive than the direct "port" of variadic templates into Swift that I had previously been thinking of.

xwu:

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Read through the proposal and earlier iterations, light involvement in pitches, and watched the implementation from the sidelines.

Now to my actual commentary...

Elision of `repeat` for generic requirements

Early in the proposed solution, there is this exemption from the need to write repeat for generic requirements:

A pack expansion consists of the repeat keyword followed by a type or an expression. The type or expression that repeat is applied to is called the repetition pattern. The repetition pattern must contain pack references. Similarly, pack references can only appear inside repetition patterns and generic requirements:
func zip<each S>(_ sequence: repeat each S) where each S: > Sequence

I don't see any reason why this should be the one place where we allow the elision of repeat. It's inconsistent, and it feels like it's going to trigger ambiguities when there are local generic functions:

func f<each T>(_) {
  g(repeat {
    func h<U>(_: U) where each T == U
    })
}

For the nested functions inside that closure, the proposal means that all of the Ts == U, because there's an implicit repeat for the generic requirement, but perhaps I meant that only the current T is equal to U. I can't express that with the proposal now, but I think I should be able to. Making the repeat explicit for generic requirements, like it is everywhere else, improves expressiveness and eliminates an unnecessary special case.

There is a small writing thing in the proposed solution where we introduce pack expansions that tripped me up

The syntax for a pack expansion type is repeat each P , where P is a type containing one or more type parameter packs.
Written as repeat each expr , where expr is an expression referencing one or more value parameter packs.

In both cases, the each isn't part of the syntax of pack expansions: the syntax is repeat P or repeat expr, respectively, and there's a semantic constraint that somewhere in the type or expression (or generic requirement, per my comment above) that there be at least one each in there that isn't covered by another repeat.

`each` and parentheses

We will refer to each T as the root type parameter pack of the member type parameter packs (each T).A and (each T).A.B .

The required parentheses here are annoying. I feel like we've been through this before with (any P)? and regretted being pedantic. Could these rules be relaxed in some way, so that each T.A and each T.A.B would be acceptable?

If we get this simplification, we'll have to decide what it means if some day we get associated type parameter packs, where any of T, A, or B could be packs. I'd be fine with .each X indicating a nested parameter pack that's getting expanded, e.g., T.each A.B for cases where B is the pack that's being expanded.

Value parameter packs

Minor nit, but this one-off sentence before the "capture" discussion

Note that pack expansion expressions can also reference type pack parameters, as metatypes.

reads as if the only use of a type pack parameter in a pack expansion expression is as a meta type; that not true, since there are other syntactic constructs one could use such as as? each T that aren't metatypes. I suggest either generalizing this sentence or striking it.

Overload resolution

There are other replies about the overload-resolution behavior, so we need not belabor the point here, but I find the fact that this is to be ambiguous:

func overload<T>(_: T) {}
func overload<each T>(_: repeat each T) {}

overload(1)

to be surprising. Usually, I've tried to describe the overloading rules as "if the parameters of A can be forwarded to B, but the converse is not true, A is more specialized than B". That hints that the fixed-arity version is more specialized than the variadic version, which also makes intuitive sense. (It's the same, but for just one argument)

Macros!

Value parameter packs are defined thus:

A value parameter pack is a function parameter or local variable declared with a pack expansion type.

but we also want macro parameters to be eligible to be value parameter packs.

Future directions

I'm very sad to see pack iteration subsetted out of this proposal. I understand the complexities here, but this feels like one of those places where we can take a very difficult feature and make it accessible.

Doug

jrose · 2023-03-27T06:23:40.054Z

Discussion has quiesced a little, but I had some more thoughts around the proposed each syntax, having to do with names.

That said, I’m going to fold it away because (1) it’s more bikeshedding, and (2) it’s an argument about what’s ‘natural-sounding’ to a native English speaker, and while that can encourage correct usage it should never be our most important goal. After all, we have many non-native-English-speaker users of Swift.

The repeat syntax is pretty obviously important: it indicates the type or expression being repeated. You could spell it differently, but some form of it is needed. each, however, has felt redundant in many of the examples; if it were omitted, the compiler would easily detect that something went wrong, and even know exactly how to correct it if repeat were already present.

The cycle seems to be 'we need these symbols to clarify what types of things we're referring to!' followed by 'wait, it turns out words already do that.' [xkcd: Sigil Cycle]

A lot of these examples have used each T as the name of the type parameter pack, and yeah, sometimes there’s no better name. But usually Swift tries to go for something better than that, and we therefore have a choice of whether a name should be singular or plural. (This was brought up in the pitch phase as well, when the working syntax still used ellipses like C++.)

There are three relevant names: the declared type parameter pack; the “nouny” name of a value parameter pack, property pack, or local binding pack; and the “verb-or-prepositiony” name of a “fluent”, “reads-like-a-sentence” function name or argument label. The last one, fortunately, is trivial in English: both verbs and prepositions do not change based on whether the object is plural (“consume an apple” vs “consume apples”; “into the box” vs “into the boxes”). The first one reads very well with each if it’s written using a singular noun: each Subview: View (“each subview is a View”), (repeat Optional<each Input>) -> Bool (“a function where you repeat Optional<_> for each input and return a boolean”).

But the second one is a problem, because parameter names (and nouny argument labels) really want to be plural:

/// - subviews: One or more views to include within this view

findFirstMatching(candidates: apple, orange, goat) { preventsScurvy($0) }

Both of those would read worse to a native English speaker in singular form. We could allow writing parameters as each subview in documentation, but nouny argument labels still show up enough that I don’t think we should disregard this.

This is too bad, because I like each. It has pretty good connotations for me within repeat and in the repeat-less syntax proposed for constraints (though now that it’s been pointed out that does seem odd to me too). But I think these things want to be plural for clarity in documentation and at the call site, and that means each no longer fits for me.

(Unfortunately, I cannot think of what would; remember, the important use is not when you declare the type pack, but within repeat, that goes from a plural to a singular. Perhaps this is why Python forces you to name the element in a list comprehension, instead of making the expression based on the name of an existing iterator.)

// Terrible exploration showing where 'each' is used
func process<pack Subviews>(subviews: repeat Optional<unpack Subviews>)
where repeat unpack Subviews: View {
  let labels: repeat String = repeat (unpack subviews)?.label ?? ""
  // …
}

hborla · 2023-03-28T01:03:35.077Z

Thanks for catching the issues in the proposal text, I clarified those in [SE-0393] Minor proposal clarifications. by hborla · Pull Request #1994 · apple/swift-evolution · GitHub.

Douglas_Gregor:

Elision of repeat for generic requirements

Early in the proposed solution, there is this exemption from the need to write repeat for generic requirements:
A pack expansion consists of the repeat keyword followed by a type or an expression. The type or expression that repeat is applied to is called the repetition pattern. The repetition pattern must contain pack references. Similarly, pack references can only appear inside repetition patterns and generic requirements:
func zip<each S>(_ sequence: repeat each S) where each S: > Sequence
I don't see any reason why this should be the one place where we allow the elision of repeat. It's inconsistent, and it feels like it's going to trigger ambiguities when there are local generic functions:

I actually considered early on whether we should write pack element requirements inside of a "requirement pack expansion", but decided against it because it seemed unnecessary. I hadn't thought of the local generic function inside a closure pattern case! I think it makes sense to require applying repeat to a generic requirement when the requirement conceptually represents N distinct requirements, one for each element of the substituted pack.

Douglas_Gregor:

each and parentheses

We will refer to each T as the root type parameter pack of the member type parameter packs (each T).A and (each T).A.B .

The required parentheses here are annoying. I feel like we've been through this before with (any P)? and regretted being pedantic. Could these rules be relaxed in some way, so that each T.A and each T.A.B would be acceptable?

I'm concerned about this suggestion because of the impact it would have on pack expansion expressions. If we still require precise application of each in expressions, there would be a difference between the way you reference packs at the type-level and at the value-level. Relaxing the parenthesis requirements in expressions means that it's no longer syntactically clear which value in a member access chain is a value pack, so it has to be inferred (by both the compiler and the programmer). If you have repeat f(each x.y().z), it's not obvious which part of the subexpression produces a value pack, which is critical for understanding which parts of the subexpression are evaluated once before the loop vs at each iteration over the pack elements.

This is a similar problem to associated type packs, and it manifests in expressions as soon as we have stored property packs or tuple/array expansion. It's a problem that we need to confront now, because we already have an experimental implementation of expanding tuple values that contain pack expansions and the pitch is imminent!

Douglas_Gregor:

Usually, I've tried to describe the overloading rules as "if the parameters of A can be forwarded to B, but the converse is not true, A is more specialized than B". That hints that the fixed-arity version is more specialized than the variadic version, which also makes intuitive sense.

After reading through the reviews at the beginning of this thread, I agree that the fixed-arity overloads should be considered more specialized than an overload with a parameter pack. @xwu pointed out that this will make it easier for existing APIs to add a new overload using parameter packs while allowing existing callers to still resolve to the old APIs, which is a compelling practical justification.

Douglas_Gregor:

Future directions

I'm very sad to see pack iteration subsetted out of this proposal. I understand the complexities here, but this feels like one of those places where we can take a very difficult feature and make it accessible.

I think pack iteration is relatively straightforward to implement, but I'm fretting about the spelling of pack iteration in light of the repeat spelling for pack expansions. That's solvable, though. Do you feel strongly about including pack iteration in this initial proposal?

hborla · 2023-03-28T01:33:10.674Z

jrose:

Discussion has quiesced a little, but I had some more thoughts around the proposed each syntax, having to do with names.

FWIW I wrote a note on naming convention in the parameter pack vision document/extended future directions writeup from a few months back, where I recommend explicitly using either no argument label or a plural argument label when writing an API that uses parameter packs. I do think it's unfortunate that the default will be the singular name in the absence of a separate argument label, though.

An interesting aside on this document

I never updated this vision document for the repeat/each spelling proposed here because most of the content was incorporated into this proposal, but you can kinda see how we arrived on repeat/each from the explanations in the document

In the section on patterned pack expansion

The ellipsis is called the expansion operator , and the type or expression that the expansion operator is applied to is called the repetition pattern . The repetition pattern must contain pack references. Given a concrete pack substitution, the pattern is repeated for each element in the substituted pack.

Consider a type parameter pack T and a pack expansion Mapped<T>... . Substituting the concrete pack {Int, String, Bool} will expand the pattern Mapped<T> by repeating it for each element in the concrete pack, replacing the pack reference T with the concrete type at each position. This produces a new comma-separated list of types Mapped<Int>, Mapped<String>, Mapped<Bool> .

In the note on naming convention

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>.

jrose · 2023-03-28T03:39:09.538Z

Documentation comments are my main remaining concern; maybe we can indeed allow (require??) each in the parameter list there?

tikitu · 2023-03-28T05:42:26.650Z

This is pure bikeshed I’m afraid, but have you considered distinguishing the pack declaration from the pack reference in spelling?

func variadic<repeating S>(_: repeat each S) where each S: Sequence { ... }

func < <repeating Element: Comparable>(lhs: (repeat each Element), rhs: (repeat each Element)) -> Bool

hborla · 2023-03-28T21:22:12.345Z

jrose:

Documentation comments are my main remaining concern; maybe we can indeed allow (require??) each in the parameter list there?

I like this idea. I started a discussion thread over in the Swift Documentation category to get some input from the folks working on documentation tools: SE-0393: Doc comments for parameter packs

xwu · 2023-03-28T22:19:13.027Z

hborla:

This builds and runs on main under -enable-experimental-feature VariadicGenerics

Putting my reviewer hat back on—

For those of you who haven't yet, the nightly development snapshots now include a substantial implementation of this feature under the flag above. Give it a whirl and share what you think after some hands-on experimentation!

Morten_Bek_Ditlevsen · 2023-03-29T11:50:39.644Z

@hborla, @John_McCall , @Slava_Pestov

It is so awesome to get to play with this!

It is so much easier for me to find heads and tails in the proposal when actually having to solve the type puzzle of a function signature!

I find the keywords quite intuitive.

I've 'implemented' sorting Arrays on variadic number of keypaths and a standard zip functionality with any arity.

It is very easy to imagine the iteration over value packs and also being able to define local packs.

Thank you so much for all of the work so far. I can't wait for this amazing feature to become part of the language!

Zollerboy1 · 2023-03-29T12:31:08.579Z

Morten_Bek_Ditlevsen:

I've 'implemented' sorting Arrays on variadic number of keypaths and a standard zip functionality with any arity.

Can you maybe share some of the code you wrote? Most of the functions I've tried to write so far have resulted in a compiler crash for me with the latest nightly snapshot.

Morten_Bek_Ditlevsen · 2023-03-29T12:47:27.963Z

Certainly! So far only the function signatures - and calls to the functions compile.

I'm running Xcode 14.3 RC2 with the development snapshot 2023-03-27.

I got crashes too, but those were all related to actually calling functions returning tuples - which I guess is supported by this proposal already, but perhaps not completely working in this build. Removing the calls to these functions fixed the crashes.

So, here are my implementations

extension Array {
    func mySorted<each Component>(_ keyPaths: repeat KeyPath<Self.Element, each Component>) -> [Self.Element] where each Component: Comparable {
        // Just return something for now
        return self
    }
}

struct User {
    var name: String
    var age: Int
    var points: Int
}

func myTest() {
    let users: [User] = [.init(name: "Morten", age: 45, points: 10000)]
    let sorted = users.mySorted(\.name, \.age, \.points)
}

This compiles! For the actual implementation, I imagine the following to work once the packs can be iterated over:

extension Array {
    func mySorted<each Component>(_ keyPaths: repeat KeyPath<Self.Element, each Component>) -> [Self.Element] where each Component: Comparable {

        return self.sorted(by: { a, b in
            for keyPath in repeat each keyPaths {
                if a[keyPath: keyPath] < b[keyPath: keyPath] {
                    return true
                } else if a[keyPath: keyPath] > b[keyPath: keyPath] {
                    return false
                }
            }
            return false
        })
    }
}

or something similar.

With regards to the zip, the declaration that compiles is:

func myZip<each T>(_ arrays: repeat [each T]) -> [(repeat each T)] {
    fatalError()
}
func test() {
    let a = myZip([1], ["sko"], [2.0])
}

This actually type checks and gives [(Int, String, Double)] as the type of a.

I'm not completely certain about the implementation here, but based on an example with counts of arrays in the proposal text, I assume that you can do:

func myZip<each T>(_ arrays: repeat [each T]) -> [(repeat each T)] {
    var result: [(repeat each T)] = .init()
    var length: Int = .max
    for array in repeat each arrays {
        length = min(length, array.count)
    }
    for i in 0..<length {
        let tuple = (repeat (each arrays)[i])
        result.append(tuple)
    }
    return result
}

So - not so certain about the actual implementations since those are not part of this proposal, but just seeing the pieces of the puzzle fit together is pretty awesome!

Zollerboy1 · 2023-03-29T13:29:26.093Z

Ah okay, so you don't actually have the function implementations yet. The implementations that you gave would indeed not work with the current proposal, because pack iteration is only a future direction for now.
I actually came up with an implementation for sorted which should work in theory but actually crashes the compiler right now:

enum Ordering {
    case lessThan
    case equal
    case greaterThan
}

extension Collection {
    func sorted<each T: Comparable>(by keyPath: repeat KeyPath<Element, each T>) -> [Element] {
        self.sorted {
            var ordering = Ordering.equal
            repeat ({
                guard ordering == .equal else { return }
                let keyPath = each keyPath
                let lhs = $0[keyPath: keyPath]
                let rhs = $1[keyPath: keyPath]
                if lhs < rhs {
                    ordering = .lessThan
                } else if lhs > rhs {
                    ordering = .greaterThan
                }
            }($0, $1))

            return ordering == .lessThan
        }
    }
}

Slava_Pestov · 2023-03-29T14:35:27.211Z

ensan-hcl:

There can be some concern on the expressional power of the each (T, U) syntax, because it cannot express something like shape(T) == shape(U) * 2. But as the proposal explicitly excluding such functionality, then each (T, U) syntax is almost self-evident solution.

Unfortunately I was able to think of one case this proposed syntax doesn't cover, and that's with nested generics. For example,

struct Outer<each T> {
  struct Inner<each U> {}  // how do I spell shape(T) == shape(U)?
}

ensan-hcl · 2023-03-29T14:43:37.868Z

This is an excellent point!
Your point has somewhat expanded my concern that it may be difficult to extend the proposed syntax directly to Variadic generic types.
Isn't it problematic to discuss variadic generics in function declarations separately from variadic generics in type declarations?

ensan-hcl:

I'm not sure who mentioned this, but there were relating discussion in a previous thread on variadic generics. If it's a function declaration, you can write the same-element requirement this way, but it's verbose in type declaration. For example, if there is a struct Sequences<each S: Sequence, T> where S.Element == T, it is necessary to write Sequences<Set<Int>, Array<Int>, Int>, instead of Sequences<Set<Int>, Array<Int>>. It's not ideal.

Slava_Pestov · 2023-03-29T15:09:50.964Z

ensan-hcl:

Your point has somewhat expanded my concern that it may be difficult to extend the proposed syntax directly to Variadic generic types.
Isn't it problematic to discuss variadic generics in function declarations separately from variadic generics in type declarations?

We support nested variadic generic functions too, so this concern with the proposed shape requirement syntax is not specific to types per se.

I plan on sending out a proposal for variadic generic types very soon -- it will be quite short compared to variadic generic functions because most of the concepts generalize immediately to different kinds of type declarations. Type aliases with type parameter packs are completely described by substitution model in the functions pitch already. Structs/enums/classes just have a couple of additional behaviors that will be spelled out.

Joe_Groff · 2023-03-29T15:52:27.237Z

Since each is only a contextual keyword, each (T, U) would also still parse as a function call, wouldn't it?

ctxppc · 2023-04-01T14:15:22.914Z

What is your evaluation of the proposal?

Great proposal! I don’t have much experience with variadic types but I do think repeat and case introduce clarity and expressiveness. It’s clear what packs are captured (which I understand as “iterated over”).

However, I think functions with variadic types should be ranked higher than functions with variadic (non-pack) parameters in overload resolution. We should leave a door open towards deprecating variadic parameters at some point. Such functions can be expressed using functions with variadic parameter packs without having to resort to a (probably heterogeneous) array, and therefore have better performance. For resiliency reasons (ABI?), a library vendor (and even the stdlib with its print function) might want to keep an overload with variadic parameters next to their new function using parameter packs.

Is the problem being addressed significant enough to warrant a change to Swift?

I’ve been waiting for this for years! This will greatly simplify writing code that work with tuples of variable size, such as buildBlock in result builder types or functions like zip.

Does this proposal fit well with the feel and direction of Swift?

The syntax is not trivial but new Swift coders should be able to find documentation and articles using the keywords repeat and each. Moreover, they don’t need to define such functions and types. This feature remains mostly out of sight at the call site or at the place of spelling out a type. For me, it passes the progressive disclosure test.

It also fits with Swift’s evolution of a stronger, more informed, and more helpful type system and away from relying on existential types where it’s not really needed.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

It’s clearer than C++’s spelling for the above-mentioned reasons.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

A quick reading but I’ve been following this topic on the side.

mwhiteside.dev · 2023-04-02T21:57:51.938Z

Blockquote
It seems odd to use each inside the generic angle brackets, where it's a reference not to 'each' scalar type, but to the pack itself. On the other hand, each makes perfect sense as syntax for the pack expansion, where the pack will be expanded to a list of each scalar type from the pack. And since that meaning is marked by each, I'm not sure that repeat is necessary at all.

I have a similar reaction. 'each' conveys expansion, or iteration, not declaration. The only point where I differ with @cmonsour is that, instead of pack as the alternative, I like many, which was one of the suggestions (not mine) in the initial pitch discussion. I see that choosing many as the syntax would have the downside of being an additional keyword, but, many has a sense of being a keyword in English too, whereas pack does not.

Edit: after another look at the alternatives considered section of the pitch, it looks like the ambiguities with the ... operator are all at the expansion site, not the declaration site. So another possibility might be: using the ... operator at the declaration (i.e., in the angle brackets) and the each keyword at the expansion. Maybe this is preferable if adding another keyword is unacceptable.

xAlien95 · 2023-04-03T22:48:30.015Z

Fantastic proposal, thank you for pushing variadic generics forward!

Admittedly, I wasn't pleased with repeat each at first given its length, but after spending some time with the last snapshots, I have to say it started growing on me. In a sense, if repeat Int where allowed, then an hypothetical repeat 10 Int could be seen as a "natural" extension to spell out [Pitch] Improved Compiler Support for Large Homogenous Tuples - #3 by Michael_Gottesman.

For clarification purposes, code that was working with the 2023-03-30 snapshot, isn't working with the 2023-04-01 one:

typealias Map<Base, Result> = Result

protocol P { var foo: String { get } }
extension Int: P { var foo: String { "integer!" } }
extension Double: P { var foo: String { "floating point number!" } }
extension [Int]: P { var foo: String { "list of integers!" } }

func foos<each S: P>(of p: repeat each S) -> (repeat Map<each S, String>) {
  return (repeat (each p).foo)
}

let r = foos(of: [1], 2.0, 3)
print(r)

The Map typealias is there only to provide a same-shape requirement between (repeat each S) and (repeat String). Is this the intended (or an intended) way to procede? Is it expected to work?