Variadic generics discussion

(Austin Zheng) #1

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described
in "Completing Generics" as a major objective for Swift 3.x. It can be
found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing
Generics, and attempts to remain as simple as possible while still being
useful for certain use cases (although I think there is still room to
simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative
designs. With enhanced existentials, there was already an informal
consensus that the feature would involve composing some protocols and class
requirements, and placing constraints on the associated types, and most
everything else was working out the various implications of doing so.
That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive
designs that use exclusively tuple-based patterns and no parameter packs. I
think Rust once considered a similar approach, although their proposal
ended up introducing a parameter-pack like construct for use with fn
application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

Variadic Generics
(Matthew Johnson) #2

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

Austin, this is really exciting! Thank you very much for all of the work you‚Äôre doing on ‚ÄúCompleting Generics‚ÄĚ. These features are at the very top of my list of desired features in Swift.

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map’ function

These are some very good and clearly articulated examples. Great work! This section is important because variadics are somewhat complicated and it is important to show people why we want them and what problems they can solve.

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

As far as I can tell, the way you are approaching `apply` would not allow the default arguments of the function passed as `function` to be used when calling `apply`. Arguments would have to be provided for all parameters when the function is invoked through apply.

I know that this difficulty is not directly related to variadic generics, but it does demonstrate a limitation of this approach to forwarding.

I have already run into a use case where I would like to accept a function and a pack of arguments, store the arguments, be able to compare them for equality, and later invoke the function with them. However, in order for this approach to make sense in my use case it would be essential that the user *not* need to explicitly provide arguments for parameters with defaults.

I bring this up in hopes that we might try to explore designs that would support this use case, and at least give it some consideration. I’m trying to think of ways to make this work but haven’t come up with anything obvious yet.

-Matthew

···

On May 28, 2016, at 3:03 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Xiaodi Wu) #3

Some initial thoughts, from a guy who doesn't remember his C++ very well:

* The motivation for using prefix ... at declaration and postfix ...
elsewhere seems lacking in this proposal; is this necessary in Swift? If
so, why? If not, can we stick with one or the other?
* There's going to be some Swift-specific funniness since ... is an
existing infix operator; currently, it's possible to define custom ...
prefix and postfix operators. Is there an intuitive syntax that avoids this
re-appropriating of an existing facility?
* It's a little bit unfortunate that #unpack() takes a triple and gives you
a pack. Shouldn't it be #pack()?

···

On Sat, May 28, 2016 at 16:03 Austin Zheng via swift-evolution < swift-evolution@swift.org> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature
described in "Completing Generics" as a major objective for Swift 3.x. It
can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing
Generics, and attempts to remain as simple as possible while still being
useful for certain use cases (although I think there is still room to
simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative
designs. With enhanced existentials, there was already an informal
consensus that the feature would involve composing some protocols and class
requirements, and placing constraints on the associated types, and most
everything else was working out the various implications of doing so.
That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive
designs that use exclusively tuple-based patterns and no parameter packs. I
think Rust once considered a similar approach, although their proposal
ended up introducing a parameter-pack like construct for use with fn
application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

1 Like
(Daniel Vollmer) #4

Hi,

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

I’ve only taken a short glance at this (and just like the proposal, I’m damaged by C++11, so my opinion is biased), so here are some thoughts:
- I’d prefer head + tail over first + rest, but that’s pretty irrelevant
- Often in C++, the need for recursion when using first + rest goes away when you can index into parameter packs (e.g. using integer_sequence) or have fold expressions.
- It might occasionally be useful to have multiple parameter packs (or argument packs). In C++ you can do that by wrapping it in a tuple. Do we have / need such an escape hatch?
- I have an argument pack. How would I apply a function taking a single argument to each element in the pack? Go via the tuple?
- Why is this a separate thing from Tuple itself? It feels so similar; I can convert between them, so why do I need this other thing?

  Daniel.

···

On 28 May 2016, at 22:03, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

(L Mihalkovic) #5

Something that long could probably use a "detailed design" section showing that some consideration was given to how to make it appear in a compiler.

···

On May 28, 2016, at 10:03 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(plx) #6

Thanks for getting the discussion started with such a thorough initial writeup.

My overall concern is this:

- on the one hand, I *very much* understand‚ÄĒand support‚ÄĒthe idea of starting simple and adding functionality later
- on the other hand, this is *already* a rather complicated proposal syntactically, semantically, and probably also in implementation
- on the gripping hand, I’m concerned that despite being so complicated, it’s perhaps too limited to pay for itself as-proposed

Or, put differently, if you believe there’s an optimal point on the complexity/functionality for a v1, I worry a bit after reading it that it’s buying too little practical functionality for the complexity it’ll bring, and that something a *little* more complex might provide a *lot* more practical utility.

To that end, I’ve provided some concrete-ish examples of things it’d be nice to be able to do via variadics and the additional features they would either *need* or at least *benefit* from having available.

All of these are very much ‚Äúnice to have‚ÄĚ features that need not be included in a first version, but they each illustrate one possible complexity/capability trade-off.

A.1: Support for uniform variadic-parameter associated-type constraints?

Consider trying to write a variadic form of this sequence:

  // given sequences a, b, provides a sequence equivalent-to
  // zip(a,b).lazy.map() {
  // ( min($0.0,$0.1), max($0.0,$0.1) )
  // }
  struct ExtremaSequence<A:Sequence,B.Sequence where A.Iterator.Element == B.Iterator.Element, A.Iterator.Element: Comparable> {
    private let a: A; private let b: B
  }

  struct ExtremaIterator<A:Iterator,B.Iterator where A.Element == B.Element, A.Element:Comparable> {
    private var a: A?
    private var b: B?
    
    mutating func next() -> (A.Element,A.Element)? {
      guard let nextA = a?.next() else {
        a = nil; b = nil;
        return nil
      }
      guard let nextB = b?.next() else {
        a = nil; b = nil;
        return nil
      }
      if nextA < nextB {
        return (nextA,nextB)
      } else {
        return (nextB,nextA)
      }
    }

  }

…would it be necessary to write the type’s generic parameters like this:

  struct VariadicExtremaSequence<E:Comparable,S… where S:Sequence, S.Iterator.Element == E>

‚Ķor would there be some way of writing a constraint like ‚Äúall `S.Iterator` must have same `.Element`?‚ÄĚ?

A.2: Support for non-uniform "parameter-to-parameter‚ÄĚ constraints

As an example:

  protocol ValueTransformer {
    associatedtype Input
    associatedtype Output
   
    func transformedValue(for input: Input) throws -> Output

  }

  // how to express this (if possible), mock syntax below
  struct LoggingValueTransformerApplier<
    T:ValueTransformer
    where
    …T[i],T[j]… => T[i].Output == T[j].Input> : ValueTransformer {

   typealias Input = #first(T…).Input
   typealias Output = #last(T…).Output

   private let (transformers) = (T...)

   func transformedValue(for input: Input) throws -> Output {
       // evaluate incrementally, logging input => (output | error) step-by-step
    }

}

…something like the above is definitely a "nice to have", but not having it will close off certain use cases.

B: Integer-Based Indexing

I see it‚Äôs been brought up already, but I‚Äôd *strongly* suggest making support for integer-based ‚Äúindexing‚ÄĚ into variadic packs a priority.

What concerns me is that without support for that, I suspect a lot of code would have to get "written twice‚ÄĚ if using the ‚Äúrecursive‚ÄĚ API on parameter packs.

Here’s a mock example:
  
¬†¬†// a ‚Äúweaker‚ÄĚ dictionary-like protocol
  protocol LookupTable {
    associatedtype Key: Hashable
    associatedtype Value

    subscript(key: Key) -> Value? { get }

  }

  /// Does a cascading search for values through a possibly *heterogeneous*
  /// collection of backing lookup tables…caching results to avoid subsequent searches
  struct HeterogeneousCascadingLookupTable<K:Hashable,V,T…
    where
    T:LookupTable,
    T.Key == K,
    T.Value == V> : LookupTable {

  private let (tables): (T…)
  private var valueCache: [K:V] = [:]
  private var missingKeys: Set<K> = []

  // implementation *with* integer-based indexing:
  subscript(key: K) -> V? {
    get {
      guard !missingKeys.contains(key) else { return nil }
      if let cached = valueCache[key] { return cached }
      for index in 0..<#count(T…) {
         if let v = tables[index][key] {
           valueCache[key] = v
           return v
         }
      }
      missingKeys.insert(key)
      return nil
    }
  }

  // implementation without integer-based indexing (or equivalent mechanism):
  subscript(key: K) -> V? {
    get {
      guard !missingKeys.contains(key) else { return nil }
      if let cached = valueCache[key] { return cached }
      if let value = self.lookupValue(for: key, in: self.tables) {
        valueCache[key] = value
        return value
      } else {
        missingKeys.insert(key)
        return nil
      }
    }
  }

  // recursive lookup implementation (necessary b/c our type itself
  // isn’t defined by recursively-nesting itself)
  private final func lookupValue<U…
    where
    U…: LookupTable,
    U.Key == K,
    U.Value == V>(for key: K, in tables: U…) -> V? {
    return #first(tables)[key] ?? self.lookupValue(for: key, in: #rest(tables))
  }

}

…which isn’t the end of the world, but having to write a separate recursive implementation of each method that needs to step-through the variadic parameters would spread things out a bit, it’d seem.

(Yes, this specific thing could be written today w/out variadics, but it illustrates the tradeoff here).

C: ‚ÄúVariadic-Sum‚ÄĚ / Structural-Union?

I mentioned this before in a response to the manifesto email, but will reiterate it here: there‚Äôs a fair amount of useful things you could do with variadic generics *if* there was also some similar way to get a ‚Äústructural union‚ÄĚ.

A simple motivating example is something like a `Chain` sequence (analogous to `Zip`); e.g. something for which `chain(a,b)` is the sequence of ‚Äėthe elements in `a`, then the elements in `b`.

Although the proposed variadics make the sequence itself easy to write:

  // for now I'd assume we need the `E` as a separate type parameter here,
  // but recall the previous point
  struct ChainSequence<E,S… where S:Sequence, S.Iterator.Element == E> {
    private let (…sequences): (S…)
    init(…arguments: S…) { … }
  }

‚Ķthe iterator is a bit more complicated. Without ‚Äústructural unions‚ÄĚ you‚Äôd probably wind up with something like this for a variadic implementation:

  struct ChainSequenceIterator<E,I… where I:Iterator, I.Element == E> {

    private var (…iterators): (I?…) // <- I hope this works

    mutating func next() -> E? {
      // find first non-nil iterator, try to get next element from it;
      // if next is non-nil, return that, otherwise nil it out and
      // find the *next* non-nil iterator, etc….
    }

  }

…which could be made to work, but is wasteful in some ways (you have space to store n iterators…). You can make it a little cleaner if you have some way of doing integer-based indexing into the variadic parameters, but that doesn’t change the space requirements (it’s still going to need room for all `n` iterators + bookkeeping).

If, however, you have some variadic-compatible structural unions, you can write it as (roughly):

  struct ChainSequenceIterator<E,S… where S:Sequence, S.Iterator.Element == E> {
     private let source: ChainSequence<E,S…>
     private var iterator: (S.Iterator |…) // (meant to be ~ `(S1.Iterator | S2.Iterator | S3.Iterator | …. | SN.Iterator)` )
     private var done: Bool = false

     mutating func next() -> E? {
       // if not `done`, try `next` on current iterator in `iterator`
       // if non-nil, return, otherwise advance to next iterator, etc., ...
     }
  }

…(how much space this actually saves depends on the size of `source` vs the size of the iterators, but it’s *possible* to save space this way).

Variadic generics *can* be added w/out structural unions ‚ÄĒ they‚Äôre a pure "nice-to-have" ‚ÄĒ but having support for variadic "product types" w/out corresponding variadic "sum types" is going to complicate-or-prevent certain constructs.

D: Make Parameter-Packs Named

I understand the appeal of the `…T`-style syntax, but I’d at least consider giving parameter-packs a more-concrete existence, e.g. something like this:

  // strawman declaration syntax:
  struct Foo<I,J,K#ParameterPack> {

    // `K` here will refer to the variadic parameter-pack itself;
    // cf the `typealias` below , but basically K ~ the tuple of its types

    typealias KValueTuple = #tuple(K) // == tuple of values of type K.0, K.1, etc.)
    typealias KTypeTyple - #typeTuple(K) // == tuple of types like K.0, K.1
    typealias FirstK = #first(K)
    typealias LastK = #last(K)
    static var kArity: Int { return #count(K) }
    // and so on

  }

  // straw man point-of-use syntax, can be adjusted of course:
  let concreteFoo = Foo<I,J,K:(K0,K1,K2,…,Kn)>

…which complicates the grammar, but IMHO feels a lot nicer than having a lot of "implicit rules" about what `…` means and so on.

···

On May 28, 2016, at 3:03 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #7

I significantly rewrote the proposal to take into account as much feedback as I could. (Many things, like syntax, haven't been changed yet, but will be in a forthcoming version.)

What I did change:

- Renamed 'packs' to 'vectors'
- Discussed variadic typealiases a bit, including things like "variadic String" for holding the results of vector computations
- There's a "every variadic associated type must be equal" constraint that can be defined now
- I added a section discussing a "fold" operation, to reduce a value pack/value vector into a single scalar with the help of a user-defined function.
- I changed the proposal so that making a tuple out of a vector now requires surrounding the vector with #tuple(), to get rid of the 'implicit' rules that plx brought up
- I added a section briefly discussing how this feature might be implemented.

Some thoughts:

- Things like indexing into a value vector by an integer value would be extremely powerful. But as far as I can tell they'd require a great deal of macro-like functionality to go along with them. A way to define constant expressions would be required, so we could define "#index = #count(T...)" or something. Then we'd need ways to manipulate that value (increment or decrement) if we wanted to work with the previous or next elements in a chain, we'd need compile-time conditional checking so that a variadic generic could behave correctly for the first or last item in a vector, and so forth. Omitting these expensive features is going to limit the number of uses variadic generics have; is this tradeoff going to be worth it? Could we push off those features to a later date, if/when Swift gets an actual compile time metaprogramming design?

- The more I think about things, the more I'm leaning towards the idea that tuples are the only construct necessary. We could get rid of most of the features of value packs/vectors, and allow them to only serve two roles: defining a variadic generic function, and spreading out a tuple in order to call a variadic generic function. (I think I prefer a spreading operator to bringing back the magic compiler tuple splat functionality.) They could also be "spread out" to define or specialize a different variadic generic type. Thoughts?

- With the existence of 'fold', might it be worth it to remove #tail() (and maybe #head), at least from v1? This would represent a slight loss of expressive power for common use cases in exchange for a considerable decrease in complexity.

Alternatively, some tuple-based designs might make this point obsolete. Imagine something like this:

func head<T, ...U>(input: (T, U...)) -> T { ... }
func tail<T, ...U>(input: (T, U...)) -> (U...) { ... }

Again, any comments are welcome. I hope to continue evolving this proposal as the community decides what they want and don't want to see.

···

On May 28, 2016, at 1:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

(Austin Zheng) #8

Thanks for your feedback!

I’ve only taken a short glance at this (and just like the proposal, I’m damaged by C++11, so my opinion is biased), so here are some thoughts:
- I’d prefer head + tail over first + rest, but that’s pretty irrelevant

It looks like C++ uses head/tail, so we should too.

- Often in C++, the need for recursion when using first + rest goes away when you can index into parameter packs (e.g. using integer_sequence) or have fold expressions.

My inclination is to keep things simple for now; more capabilities can be added in the future, when it becomes clearer what sort of compile-time metaprogramming story Swift wants to support. (Things like const expressions, compile-time control flow like described here for D's version of this feature (https://dlang.org/variadic-function-templates.html), etc.)

But a fold expression sort of construct is almost certainly worth considering in an initial proposal. It would, for example, considerably save you code size if you were to implement an (e.g.) equality between 72-ples.

- It might occasionally be useful to have multiple parameter packs (or argument packs). In C++ you can do that by wrapping it in a tuple. Do we have / need such an escape hatch?

I think so. I would expect you to be able to do something like this with the given semantics:

func foo<...T, ...U>(...args : T..., ...moreArgs: (U...)) { /* */ }

You have count(T) + 1 arguments, where the last argument is a tuple with count(U) members.

- I have an argument pack. How would I apply a function taking a single argument to each element in the pack? Go via the tuple?

This is definitely something that needs to be worked out.

- Why is this a separate thing from Tuple itself? It feels so similar; I can convert between them, so why do I need this other thing?

There are a couple of issues with implementing this using only tuples:

- There needs to be a way to distinguish between passing a tuple containing n elements to a function, and passing n arguments to that function via a tuple. Right now Swift makes no distinction between a 1-ple and the element contained within it.

- Using tuples for everything requires functions written to be used with variadic generics to specifically take a single tuple as an argument, or to bring back a redesigned version of the magical tuple splat functionality (https://github.com/apple/swift-evolution/blob/master/proposals/0029-remove-implicit-tuple-splat.md). A value pack isn't a tuple and doesn't have to worry about whether or not argument labels should match up with tuple member labels, etc.

- Tuples don't allow for generic functions that take a varying number of arguments, unless you want to write them as functions that take a variably sized tuple (see the "foo()" example above).

However, if there is a way to define these problems away I would be all too happy to see a proposal that exclusively deals with variadic tuples.

···

On May 28, 2016, at 3:21 PM, Daniel Vollmer via swift-evolution <swift-evolution@swift.org> wrote:

  Daniel.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #9

I appreciate your feedback! Some thoughts inline...

Some initial thoughts, from a guy who doesn't remember his C++ very well:

* The motivation for using prefix ... at declaration and postfix ... elsewhere seems lacking in this proposal; is this necessary in Swift? If so, why? If not, can we stick with one or the other?

I can't see any real reason to not change it if it's confusing and/or ugly. I stole the syntax from the generics manifesto for use as a starting point.

The only real reason would be if there would be some sort of syntactic ambiguity from using just one of the two. But I can't think of any - a type or value gets the leading dots iff it would be a declaration anyways.

We could even go further and only require any dots on the type parameters. Value packs would look the same as normal values (although they wouldn't be interchangeable), and the only way to tell would be to see that they were declared with a parameter pack as their type or constructed from another value pack. But that might be even more confusing to people reading the code.

* There's going to be some Swift-specific funniness since ... is an existing infix operator; currently, it's possible to define custom ... prefix and postfix operators. Is there an intuitive syntax that avoids this re-appropriating of an existing facility?

I gave this a bit of thought last night but didn't come up with anything compelling:

- Maybe something using "#": "func bar<T#.., U, V>", since '#' cannot start custom operators?
- A #pack(T) construct or other pseudo-function? "func bar<#pack(T), U, V>"
- Maybe an underscore followed by dots? "func bar<T_.., U, V>", but "_" already plays a role signifying something meant to be ignored or discarded
- Maybe we keep the three dots, but only use them with the generic type parameters (no naming conflict possible there). So you can declare a pack using T..., but you never use the three-dot syntax with a value pack.
- Carve out an exception in the grammar and require postfix dot operators to have four or more dots?

* It's a little bit unfortunate that #unpack() takes a triple and gives you a pack. Shouldn't it be #pack()?

That's a good point. What I had in mind was "unpacking" a scalar tuple's values into a value pack. But then we have an #unpack() operator that turns something into a "pack", which is absurd. It should be renamed, or we could change the terminology from "packs" to "vectors" (e.g. "parameter vector", "value vector") or something. Unpacking the members of a scalar into a "value vector" sounds a lot better.

···

On May 28, 2016, at 3:22 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sat, May 28, 2016 at 16:03 Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Xiaodi Wu) #10

Erm, autocorrect deserves credit for converting 'tuple' to 'triple.' Sorry.

···

On Sat, May 28, 2016 at 18:22 Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Some initial thoughts, from a guy who doesn't remember his C++ very well:

* The motivation for using prefix ... at declaration and postfix ...
elsewhere seems lacking in this proposal; is this necessary in Swift? If
so, why? If not, can we stick with one or the other?
* There's going to be some Swift-specific funniness since ... is an
existing infix operator; currently, it's possible to define custom ...
prefix and postfix operators. Is there an intuitive syntax that avoids this
re-appropriating of an existing facility?
* It's a little bit unfortunate that #unpack() takes a triple and gives
you a pack. Shouldn't it be #pack()?
On Sat, May 28, 2016 at 16:03 Austin Zheng via swift-evolution < > swift-evolution@swift.org> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature
described in "Completing Generics" as a major objective for Swift 3.x. It
can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing
Generics, and attempts to remain as simple as possible while still being
useful for certain use cases (although I think there is still room to
simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative
designs. With enhanced existentials, there was already an informal
consensus that the feature would involve composing some protocols and class
requirements, and placing constraints on the associated types, and most
everything else was working out the various implications of doing so.
That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive
designs that use exclusively tuple-based patterns and no parameter packs. I
think Rust once considered a similar approach, although their proposal
ended up introducing a parameter-pack like construct for use with fn
application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #11

Thank you for reading through the proposal!

These are some very good and clearly articulated examples. Great work! This section is important because variadics are somewhat complicated and it is important to show people why we want them and what problems they can solve.

Any more practical use cases you can come up with (preferably ones that are distinct from the few we have now) would be greatly appreciated.

My thinking is that it's best to keep the feature as described in this proposal as lightweight as possible, proposing only enough expressiveness so that most reasonable use cases can be expressed. There are two reasons for that:

- Design and implementation burden relative to benefit. This is not a top-priority feature in the manifesto, and will be competing with at least two or three other features for resources. It's also quite complicated, as-is. It will affect how Swift handles resilience. [*]
- This proposal should not become a variadic generics proposal with a half-thought-out compile time metaprogramming scheme hanging off it. What Swift gets in terms of macros, code generation, or compile-time expressions deserves a conversation of its own eventually.

More concretely, D has a "static if" construct (https://dlang.org/variadic-function-templates.html). It looks really nice - you could write a n-arity function that generates a `print("Hello, Matthew")` only if its arity is 3. I'm sure there are many use cases for it. Is building something similar worth spending time for during the Swift 3.x timeframe? Probably not, especially if it could be implemented in the future and the existing variadic generic semantics seamlessly extended to work with it.

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

As far as I can tell, the way you are approaching `apply` would not allow the default arguments of the function passed as `function` to be used when calling `apply`. Arguments would have to be provided for all parameters when the function is invoked through apply.

Yes. There are a lot of issues right now with the idea of using a value pack or a tuple to call a function, and most of them apply to the tuple splat discussion that took place a few months ago. Namely, the idea of a tuple or 'vector' of values does not map cleanly to Swift's function parameter conventions. You have inout params, params with default values, argument labels, and other stuff that tuples can't represent cleanly or at all.

I know that this difficulty is not directly related to variadic generics, but it does demonstrate a limitation of this approach to forwarding.

I have already run into a use case where I would like to accept a function and a pack of arguments, store the arguments, be able to compare them for equality, and later invoke the function with them. However, in order for this approach to make sense in my use case it would be essential that the user *not* need to explicitly provide arguments for parameters with defaults.

I bring this up in hopes that we might try to explore designs that would support this use case, and at least give it some consideration. I’m trying to think of ways to make this work but haven’t come up with anything obvious yet.

I do want to explore designs in this space, and I think we will need to figure it out at some point.

If a good solution cannot present itself in the time frame, I'd be willing to punt for the purposes of this proposal. My idea of a (sad, awful) fallback solution is to prohibit apply on functions with inout params, require an argument for every argument in the formal parameter list, and allow a fully qualified function reference to be called without re-specifying the argument labels:

struct Foo {
  func myFunc(x: Int, y: Int) { }
  func myFunc(x: Int, z: Int) { }
}

let x = Foo()
let theFunc = x.myFunc(_:y:)
// Cannot do this now
x.myFunc(_:y:)(1, 2)
// Have to do this:
x.myFunc(_:y:)(1, y: 2) // but 'y' is redundant on right; this was discussed during the tuple splat thread

// In the future...
x.someFunc(_:y:z...:)(1, 2, myPack...)

-Matthew

[*] On a tangential topic, how is Swift going to handle generics across module boundaries in the future? People are complaining that their library generics code is too slow because specialization is impossible, and specialization only happens on stdlib generic types because of some hacks. https://github.com/lorentey/BTree#generics notes that @_specialize might be exposed as an attribute for library author use in the future. It might be the case that every variadic generic type might need to be @_specialize by default, because I can't imagine a variadic equivalent to the dynamic-dispatch solution currently used to implement regular generics without specialization.

···

On May 28, 2016, at 7:41 PM, Matthew Johnson <matthew@anandabits.com> wrote:

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #12

This feedback is great.

Thanks for getting the discussion started with such a thorough initial writeup.

My overall concern is this:

- on the one hand, I *very much* understand‚ÄĒand support‚ÄĒthe idea of starting simple and adding functionality later
- on the other hand, this is *already* a rather complicated proposal syntactically, semantically, and probably also in implementation
- on the gripping hand, I’m concerned that despite being so complicated, it’s perhaps too limited to pay for itself as-proposed

Or, put differently, if you believe there’s an optimal point on the complexity/functionality for a v1, I worry a bit after reading it that it’s buying too little practical functionality for the complexity it’ll bring, and that something a *little* more complex might provide a *lot* more practical utility.

I agree. There is definitely work to be done to find the optimal complexity/benefit point.

To that end, I’ve provided some concrete-ish examples of things it’d be nice to be able to do via variadics and the additional features they would either *need* or at least *benefit* from having available.

Excellent!

All of these are very much ‚Äúnice to have‚ÄĚ features that need not be included in a first version, but they each illustrate one possible complexity/capability trade-off.

A.1: Support for uniform variadic-parameter associated-type constraints?

Consider trying to write a variadic form of this sequence:

  // given sequences a, b, provides a sequence equivalent-to
  // zip(a,b).lazy.map() {
  // ( min($0.0,$0.1), max($0.0,$0.1) )
  // }
  struct ExtremaSequence<A:Sequence,B.Sequence where A.Iterator.Element == B.Iterator.Element, A.Iterator.Element: Comparable> {
    private let a: A; private let b: B
  }

  struct ExtremaIterator<A:Iterator,B.Iterator where A.Element == B.Element, A.Element:Comparable> {
    private var a: A?
    private var b: B?
    
    mutating func next() -> (A.Element,A.Element)? {
      guard let nextA = a?.next() else {
        a = nil; b = nil;
        return nil
      }
      guard let nextB = b?.next() else {
        a = nil; b = nil;
        return nil
      }
      if nextA < nextB {
        return (nextA,nextB)
      } else {
        return (nextB,nextA)
      }
    }

  }

…would it be necessary to write the type’s generic parameters like this:

  struct VariadicExtremaSequence<E:Comparable,S… where S:Sequence, S.Iterator.Element == E>

‚Ķor would there be some way of writing a constraint like ‚Äúall `S.Iterator` must have same `.Element`?‚ÄĚ?

Yes. Right now the way the feature is written up implies:

- You can make all the pack members conform to the same protocols/subclass requirements
- You can make all the associated types conform to the same protocols/subclass requirements
- You can make all the associated types forced to be the same concrete type

The missing constraint(s) are:

- All the associated types must be equal across pack members (i.e. "all S.Iterator.Element's are equal")
- anything else?

A.2: Support for non-uniform "parameter-to-parameter‚ÄĚ constraints

As an example:

  protocol ValueTransformer {
    associatedtype Input
    associatedtype Output
   
    func transformedValue(for input: Input) throws -> Output

  }

  // how to express this (if possible), mock syntax below
  struct LoggingValueTransformerApplier<
    T:ValueTransformer
    where
    …T[i],T[j]… => T[i].Output == T[j].Input> : ValueTransformer {

   typealias Input = #first(T…).Input
   typealias Output = #last(T…).Output

   private let (transformers) = (T...)

   func transformedValue(for input: Input) throws -> Output {
       // evaluate incrementally, logging input => (output | error) step-by-step
    }

}

…something like the above is definitely a "nice to have", but not having it will close off certain use cases.

Oh, this is interesting. So a way to specify an equality relationship between "adjacent" sets of associated types?

B: Integer-Based Indexing

I see it‚Äôs been brought up already, but I‚Äôd *strongly* suggest making support for integer-based ‚Äúindexing‚ÄĚ into variadic packs a priority.

What concerns me is that without support for that, I suspect a lot of code would have to get "written twice‚ÄĚ if using the ‚Äúrecursive‚ÄĚ API on parameter packs.

Here’s a mock example:
  
¬†¬†// a ‚Äúweaker‚ÄĚ dictionary-like protocol
  protocol LookupTable {
    associatedtype Key: Hashable
    associatedtype Value

    subscript(key: Key) -> Value? { get }

  }

  /// Does a cascading search for values through a possibly *heterogeneous*
  /// collection of backing lookup tables…caching results to avoid subsequent searches
  struct HeterogeneousCascadingLookupTable<K:Hashable,V,T…
    where
    T:LookupTable,
    T.Key == K,
    T.Value == V> : LookupTable {

  private let (tables): (T…)
  private var valueCache: [K:V] = [:]
  private var missingKeys: Set<K> = []

  // implementation *with* integer-based indexing:
  subscript(key: K) -> V? {
    get {
      guard !missingKeys.contains(key) else { return nil }
      if let cached = valueCache[key] { return cached }
      for index in 0..<#count(T…) {
         if let v = tables[index][key] {
           valueCache[key] = v
           return v
         }
      }
      missingKeys.insert(key)
      return nil
    }
  }

  // implementation without integer-based indexing (or equivalent mechanism):
  subscript(key: K) -> V? {
    get {
      guard !missingKeys.contains(key) else { return nil }
      if let cached = valueCache[key] { return cached }
      if let value = self.lookupValue(for: key, in: self.tables) {
        valueCache[key] = value
        return value
      } else {
        missingKeys.insert(key)
        return nil
      }
    }
  }

  // recursive lookup implementation (necessary b/c our type itself
  // isn’t defined by recursively-nesting itself)
  private final func lookupValue<U…
    where
    U…: LookupTable,
    U.Key == K,
    U.Value == V>(for key: K, in tables: U…) -> V? {
    return #first(tables)[key] ?? self.lookupValue(for: key, in: #rest(tables))
  }

}

…which isn’t the end of the world, but having to write a separate recursive implementation of each method that needs to step-through the variadic parameters would spread things out a bit, it’d seem.

I'll write something up.

for index in 0..<#count(T…) {
    if let v = tables[index][key] {
        valueCache[key] = v
      return v
    }
}

I assume this is all compile time code generation (unroll the loop in the source #count(T...) times for each arity that T... is instantiated as, with a different 'tables' pack member value for each unrolled loop iteration).

(Yes, this specific thing could be written today w/out variadics, but it illustrates the tradeoff here).

C: ‚ÄúVariadic-Sum‚ÄĚ / Structural-Union?

I mentioned this before in a response to the manifesto email, but will reiterate it here: there‚Äôs a fair amount of useful things you could do with variadic generics *if* there was also some similar way to get a ‚Äústructural union‚ÄĚ.

A simple motivating example is something like a `Chain` sequence (analogous to `Zip`); e.g. something for which `chain(a,b)` is the sequence of ‚Äėthe elements in `a`, then the elements in `b`.

Although the proposed variadics make the sequence itself easy to write:

  // for now I'd assume we need the `E` as a separate type parameter here,
  // but recall the previous point
  struct ChainSequence<E,S… where S:Sequence, S.Iterator.Element == E> {
    private let (…sequences): (S…)
    init(…arguments: S…) { … }
  }

‚Ķthe iterator is a bit more complicated. Without ‚Äústructural unions‚ÄĚ you‚Äôd probably wind up with something like this for a variadic implementation:

  struct ChainSequenceIterator<E,I… where I:Iterator, I.Element == E> {

    private var (…iterators): (I?…) // <- I hope this works

    mutating func next() -> E? {
      // find first non-nil iterator, try to get next element from it;
      // if next is non-nil, return that, otherwise nil it out and
      // find the *next* non-nil iterator, etc….
    }

  }

…which could be made to work, but is wasteful in some ways (you have space to store n iterators…). You can make it a little cleaner if you have some way of doing integer-based indexing into the variadic parameters, but that doesn’t change the space requirements (it’s still going to need room for all `n` iterators + bookkeeping).

If, however, you have some variadic-compatible structural unions, you can write it as (roughly):

  struct ChainSequenceIterator<E,S… where S:Sequence, S.Iterator.Element == E> {
     private let source: ChainSequence<E,S…>
     private var iterator: (S.Iterator |…) // (meant to be ~ `(S1.Iterator | S2.Iterator | S3.Iterator | …. | SN.Iterator)` )
     private var done: Bool = false

     mutating func next() -> E? {
       // if not `done`, try `next` on current iterator in `iterator`
       // if non-nil, return, otherwise advance to next iterator, etc., ...
     }
  }

…(how much space this actually saves depends on the size of `source` vs the size of the iterators, but it’s *possible* to save space this way).

Variadic generics *can* be added w/out structural unions ‚ÄĒ they‚Äôre a pure "nice-to-have" ‚ÄĒ but having support for variadic "product types" w/out corresponding variadic "sum types" is going to complicate-or-prevent certain constructs.

This is interesting. Might it be possible with to accomplish this with existentials (this is sort of a cross-reference to a different proposal from the generics manifest)? An existential type as described below would work for any pack where all the elements were constrained in the same way. Not sure if it could be made to work in the case where the types in the pack are related to each other (as proposed earlier).

struct ChainSequenceIterator<E, S… where S:Sequence, S.Iterator.Element == E> {

  // A single variable that contains each iterator in turn; specific type doesn't matter as long as the element is E
  private var iterator : Any<Iterator where .Element == E>?

  // ...
}

D: Make Parameter-Packs Named

I understand the appeal of the `…T`-style syntax, but I’d at least consider giving parameter-packs a more-concrete existence, e.g. something like this:

  // strawman declaration syntax:
  struct Foo<I,J,K#ParameterPack> {

    // `K` here will refer to the variadic parameter-pack itself;
    // cf the `typealias` below , but basically K ~ the tuple of its types

    typealias KValueTuple = #tuple(K) // == tuple of values of type K.0, K.1, etc.)
    typealias KTypeTyple - #typeTuple(K) // == tuple of types like K.0, K.1
    typealias FirstK = #first(K)
    typealias LastK = #last(K)
    static var kArity: Int { return #count(K) }
    // and so on

  }

  // straw man point-of-use syntax, can be adjusted of course:
  let concreteFoo = Foo<I,J,K:(K0,K1,K2,…,Kn)>

…which complicates the grammar, but IMHO feels a lot nicer than having a lot of "implicit rules" about what `…` means and so on.

I think it makes sense to make pack usage explicit. I think the dots at site of declaration don't really cause trouble, though, and are a little nicer to read than T#ParameterPack.

···

On May 29, 2016, at 9:00 AM, plx via swift-evolution <swift-evolution@swift.org> wrote:

On May 28, 2016, at 3:03 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello swift-evolution,

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Daniel Vollmer) #13

- I have an argument pack. How would I apply a function taking a single argument to each element in the pack? Go via the tuple?

This is definitely something that needs to be worked out.

The C++ pack expansion rules http://en.cppreference.com/w/cpp/language/parameter_pack in the most basic case expand out and separate with commas, e.g.

  pack = (a, b, c)
  foo(pack …) => foo(a, b, c)

But then pattern (i.e. the part to the left of …) may also be more complicated, e.g.

  foo(pack++) … => foo(a++), foo(b++), foo(c++)

The fold expressions then ‚Äúonly‚ÄĚ replace the commas separating instantiations of the pattern with a different ‚Äúoperator‚ÄĚ (and special associated rules for the null element).

And although I really (ab-)use this feature in C++, I’m not entirely sure whether this sort of thing wouldn’t be more suited to a macro(-ish) system than trying to tie it to generics? That said, of course expansion has to be possible inside Generic<Pack …>, but I don’t see why it wouldn’t be.

- Why is this a separate thing from Tuple itself? It feels so similar; I can convert between them, so why do I need this other thing?

There are a couple of issues with implementing this using only tuples:
- Using tuples for everything requires functions written to be used with variadic generics to specifically take a single tuple as an argument, or to bring back a redesigned version of the magical tuple splat functionality (https://github.com/apple/swift-evolution/blob/master/proposals/0029-remove-implicit-tuple-splat.md). A value pack isn’t a tuple and doesn't have to worry about whether or not argument labels should match up with tuple member labels, etc.

I’d think something like (explicit) splat at the call-site with what I’d imagine would be a few different variants would be the cleanest:
- #anonymous_splat: takes tuple with or without labels and expands according to pattern ignoring function argument labels
- #named_splat: takes tuple with or without labels and an optional second tuple type (default to the type of the first tuple) of matching size from which it takes the names and expands the values in the first tuple as the names (labels) from the second type.
- …?

- Tuples don’t allow for generic functions that take a varying number of arguments, unless you want to write them as functions that take a variably sized tuple (see the "foo()" example above).

Yeah, the expansion from tuple to args has to happen at the call site, I think.

Is it possible to have a Tuple containing an `inout` reference (i.e. I want reference behaviour for this tuple member)?

  Daniel.

···

On 29 May 2016, at 02:33, Austin Zheng <austinzheng@gmail.com> wrote:

(Matthew Johnson) #14

I significantly rewrote the proposal to take into account as much feedback as I could. (Many things, like syntax, haven't been changed yet, but will be in a forthcoming version.)

What I did change:

- Renamed 'packs' to 'vectors'

What is the rationale here? Vector makes some sense for the parameter packs because they only consist of types and are thus homogenous. But value packs and argument packs will consist of values or arguments that might all have different types. They are heterogeneous. So vector doesn't seem like the right term. It's not a huge deal, but something to consider anyway.

By the way, the multiMap example is basically the same as the applicative functor for ZipList in Haskell (http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors). You can probably find several more good examples by looking at other applicative functors.

Still thinking about more robust function forwarding but not making much progress...

···

Sent from my iPad

On May 29, 2016, at 7:36 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

- Discussed variadic typealiases a bit, including things like "variadic String" for holding the results of vector computations
- There's a "every variadic associated type must be equal" constraint that can be defined now
- I added a section discussing a "fold" operation, to reduce a value pack/value vector into a single scalar with the help of a user-defined function.
- I changed the proposal so that making a tuple out of a vector now requires surrounding the vector with #tuple(), to get rid of the 'implicit' rules that plx brought up
- I added a section briefly discussing how this feature might be implemented.

Some thoughts:

- Things like indexing into a value vector by an integer value would be extremely powerful. But as far as I can tell they'd require a great deal of macro-like functionality to go along with them. A way to define constant expressions would be required, so we could define "#index = #count(T...)" or something. Then we'd need ways to manipulate that value (increment or decrement) if we wanted to work with the previous or next elements in a chain, we'd need compile-time conditional checking so that a variadic generic could behave correctly for the first or last item in a vector, and so forth. Omitting these expensive features is going to limit the number of uses variadic generics have; is this tradeoff going to be worth it? Could we push off those features to a later date, if/when Swift gets an actual compile time metaprogramming design?

- The more I think about things, the more I'm leaning towards the idea that tuples are the only construct necessary. We could get rid of most of the features of value packs/vectors, and allow them to only serve two roles: defining a variadic generic function, and spreading out a tuple in order to call a variadic generic function. (I think I prefer a spreading operator to bringing back the magic compiler tuple splat functionality.) They could also be "spread out" to define or specialize a different variadic generic type. Thoughts?

- With the existence of 'fold', might it be worth it to remove #tail() (and maybe #head), at least from v1? This would represent a slight loss of expressive power for common use cases in exchange for a considerable decrease in complexity.

Alternatively, some tuple-based designs might make this point obsolete. Imagine something like this:

func head<T, ...U>(input: (T, U...)) -> T { ... }
func tail<T, ...U>(input: (T, U...)) -> (U...) { ... }

Again, any comments are welcome. I hope to continue evolving this proposal as the community decides what they want and don't want to see.

On May 28, 2016, at 1:03 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(plx) #15

I’ll keep this quick since I see upthread you have already revised the proposal.

…something like the above is definitely a "nice to have", but not having it will close off certain use cases.

Oh, this is interesting. So a way to specify an equality relationship between "adjacent" sets of associated types?

Right, that was what I had in mind, and I can think of uses for such neighbor-to-neighbor type relationships.

There may be uses for other relationships‚ÄĒboth beyond equality and beyond neighbor-to-neighbor‚ÄĒbut I can‚Äôt think of any offhand.

One other pack-level constraint came to mind:

- can you enforce (T‚Ķ) is *exactly* (T,T,T,‚Ķ) N times? (e.g. T0 == T1, etc., not just "conforms to same protocols‚ÄĚ or ‚Äúhave identical associated types‚ÄĚ)

‚Ķalong with some ‚Äúpack-to-pack‚ÄĚ constraints:

- if you have e.g. 2+ packs, can you enforce (T…) and (U…) have the same arity?
- if you have e.g. 2+ packs, could you enforce e.g. T.Foo… == U.Bar ?

…as always nice-to-have, but throwing them out there for consideration.

I'll write something up.

for index in 0..<#count(T…) {
    if let v = tables[index][key] {
        valueCache[key] = v
      return v
    }
}

I assume this is all compile time code generation (unroll the loop in the source #count(T...) times for each arity that T... is instantiated as, with a different 'tables' pack member value for each unrolled loop iteration).

I’d assume so too, but thinking it through I think it needs some alternative way of being expressed.

If you look @ the ‚Äúobvious‚ÄĚ implementation for the above as written, it unrolls into something like this:

  if let v = tables[0][key] { … } // assume returns out of here on success
  if let v = tables[1][key] { … } // assume returns out of here on success
  //…etc...

…but b/c tuples aren’t directly subscriptable, those `tables[index][key]` expressions themselves would perhaps get expanded into the equivalent of, e.g.:

  private func __subscriptTables(index index: Int, key: K) -> V? {
    switch index {
       case 0: return tables.0[key]
       case 1: return tables.1[key]
       // etc...
¬†¬†¬†¬†¬†¬†¬†default: fatalError(‚ÄúInvalid subscript into variadic‚Ķblah blah‚ÄĚ)
    }
  }

…and so the original expansion would be more like:

  if let v = __subscriptTables(index:0, key: key) { … } // assume returns out of here on success
  if let v = __subscriptTables(index:1, key: key) { … } // assume returns out of here on success
  //…etc...

‚Ķ.which repeats the switch at each line. In theory the optimizer can know to inline `__subscriptTables`, notice `index` is known at compile-time, replace the switch with direct access, and arrive at the code you ‚Äúreally want‚ÄĚ:

  if let v = tables.0[key] { … } // assume returns out of here on success
  if let v = tables.1[key] { … } // assume returns out of here on success

…but that’s obviously putting a lot of pressure on the compiler to convert the `for index in #count(tables) { … }` code into something equivalent-but-reasonable.

I’ll be sure to look @ at the proposed `fold` in this light.

This is interesting. Might it be possible with to accomplish this with existentials (this is sort of a cross-reference to a different proposal from the generics manifest)? An existential type as described below would work for any pack where all the elements were constrained in the same way. Not sure if it could be made to work in the case where the types in the pack are related to each other (as proposed earlier).

struct ChainSequenceIterator<E, S… where S:Sequence, S.Iterator.Element == E> {

  // A single variable that contains each iterator in turn; specific type doesn't matter as long as the element is E
  private var iterator : Any<Iterator where .Element == E>?

  // ...
}

Actually yes, I hadn’t thought of that and you could make it work in this case (although perhaps with some indirection overhead? and it seems also with some additional state tracking to know which iterator you actually have).

Where I‚Äôm not as sure is for something like a `ChainCollectionIndex` (same `stuff from A, then stuff from B, etc‚ÄĚ concept, but for A, B collections, and so on).

That’s more clearly a case where what you *want* ideally is something like this:

  struct ChainCollection2<A:Collection,B:Collection> {
    let a: A; let b: B
  }

  struct ChainCollectionIndex2<A:Comparable,B:Comparable> {
    private var sourceIndex: Sum2<A,B> // e.g. (A | B)
  }

…since to implement the APIs you need A and A.Index and B and B.Index to "match up". It’s probably possible here to do something like this instead:

  struct ChainCollectionIndex2<A:Comparable,B:Comparable> {
    private var boxedIndex: Box<Any> // actually either Box<A> or Box<B>
    private var whichIndex: AOrB // (E.G. enum ilke IndexFromA | IndexFromB)
  }

…with a lot of casting and so on, and perhaps also with existentials (and/or casting and open-as), but it’d be *cleaner* with the sum, still.

Either way you’re right that e.g. existentials and similar + state flags can cover a lot of these uses.

D: Make Parameter-Packs Named

I understand the appeal of the `…T`-style syntax, but I’d at least consider giving parameter-packs a more-concrete existence, e.g. something like this:

  // strawman declaration syntax:
  struct Foo<I,J,K#ParameterPack> {

    // `K` here will refer to the variadic parameter-pack itself;
    // cf the `typealias` below , but basically K ~ the tuple of its types

    typealias KValueTuple = #tuple(K) // == tuple of values of type K.0, K.1, etc.)
    typealias KTypeTyple - #typeTuple(K) // == tuple of types like K.0, K.1
    typealias FirstK = #first(K)
    typealias LastK = #last(K)
    static var kArity: Int { return #count(K) }
    // and so on

  }

  // straw man point-of-use syntax, can be adjusted of course:
  let concreteFoo = Foo<I,J,K:(K0,K1,K2,…,Kn)>

…which complicates the grammar, but IMHO feels a lot nicer than having a lot of "implicit rules" about what `…` means and so on.

I think it makes sense to make pack usage explicit. I think the dots at site of declaration don't really cause trouble, though, and are a little nicer to read than T#ParameterPack.

I agree #ParameterPack is awful and that T… at the declaration site is not a big deal.

What I don‚Äôt like is not having a way to refer to the pack itself other than via its ‚Äúplaceholder type‚ÄĚ with some dots.

It also seems nicer to express things like a pack fusion with names for packs, but again in fairness it’s not terrible:

  struct Foo<T…> {
  }

  func +++<T…,U…>(lhs: Foo<T…>, rhs: Foo<U…>) -> Foo<#fuse(T…,U…)>

…so I’m not sure what I think on this.

···

On May 29, 2016, at 12:36 PM, Austin Zheng <austinzheng@gmail.com> wrote:

On May 28, 2016, at 3:03 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello swift-evolution,

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Matthew Johnson) #16

Austin,

One very useful possibility opened up by variadic generics that you don‚Äôt mention is the ability to write extensions for structural types (tuple, function, maybe union in the future), including conforming them to protocols. This would be a separate proposal building on the capability of variadic generics but might be worth mentioning in ‚Äúfuture directions‚ÄĚ.

Matthew

···

On May 29, 2016, at 7:36 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

I significantly rewrote the proposal to take into account as much feedback as I could. (Many things, like syntax, haven't been changed yet, but will be in a forthcoming version.)

What I did change:

- Renamed 'packs' to 'vectors'
- Discussed variadic typealiases a bit, including things like "variadic String" for holding the results of vector computations
- There's a "every variadic associated type must be equal" constraint that can be defined now
- I added a section discussing a "fold" operation, to reduce a value pack/value vector into a single scalar with the help of a user-defined function.
- I changed the proposal so that making a tuple out of a vector now requires surrounding the vector with #tuple(), to get rid of the 'implicit' rules that plx brought up
- I added a section briefly discussing how this feature might be implemented.

Some thoughts:

- Things like indexing into a value vector by an integer value would be extremely powerful. But as far as I can tell they'd require a great deal of macro-like functionality to go along with them. A way to define constant expressions would be required, so we could define "#index = #count(T...)" or something. Then we'd need ways to manipulate that value (increment or decrement) if we wanted to work with the previous or next elements in a chain, we'd need compile-time conditional checking so that a variadic generic could behave correctly for the first or last item in a vector, and so forth. Omitting these expensive features is going to limit the number of uses variadic generics have; is this tradeoff going to be worth it? Could we push off those features to a later date, if/when Swift gets an actual compile time metaprogramming design?

- The more I think about things, the more I'm leaning towards the idea that tuples are the only construct necessary. We could get rid of most of the features of value packs/vectors, and allow them to only serve two roles: defining a variadic generic function, and spreading out a tuple in order to call a variadic generic function. (I think I prefer a spreading operator to bringing back the magic compiler tuple splat functionality.) They could also be "spread out" to define or specialize a different variadic generic type. Thoughts?

- With the existence of 'fold', might it be worth it to remove #tail() (and maybe #head), at least from v1? This would represent a slight loss of expressive power for common use cases in exchange for a considerable decrease in complexity.

Alternatively, some tuple-based designs might make this point obsolete. Imagine something like this:

func head<T, ...U>(input: (T, U...)) -> T { ... }
func tail<T, ...U>(input: (T, U...)) -> (U...) { ... }

Again, any comments are welcome. I hope to continue evolving this proposal as the community decides what they want and don't want to see.

On May 28, 2016, at 1:03 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Matthew Johnson) #17

Thank you for reading through the proposal!

These are some very good and clearly articulated examples. Great work! This section is important because variadics are somewhat complicated and it is important to show people why we want them and what problems they can solve.

Any more practical use cases you can come up with (preferably ones that are distinct from the few we have now) would be greatly appreciated.

My thinking is that it's best to keep the feature as described in this proposal as lightweight as possible, proposing only enough expressiveness so that most reasonable use cases can be expressed. There are two reasons for that:

- Design and implementation burden relative to benefit. This is not a top-priority feature in the manifesto, and will be competing with at least two or three other features for resources. It's also quite complicated, as-is. It will affect how Swift handles resilience. [*]
- This proposal should not become a variadic generics proposal with a half-thought-out compile time metaprogramming scheme hanging off it. What Swift gets in terms of macros, code generation, or compile-time expressions deserves a conversation of its own eventually.

Very much agree with the comments about compile time meta programming here. I'm really looking forward to that but we can do far better than C++ here.

More concretely, D has a "static if" construct (https://dlang.org/variadic-function-templates.html). It looks really nice - you could write a n-arity function that generates a `print("Hello, Matthew")` only if its arity is 3. I'm sure there are many use cases for it. Is building something similar worth spending time for during the Swift 3.x timeframe? Probably not, especially if it could be implemented in the future and the existing variadic generic semantics seamlessly extended to work with it.

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

As far as I can tell, the way you are approaching `apply` would not allow the default arguments of the function passed as `function` to be used when calling `apply`. Arguments would have to be provided for all parameters when the function is invoked through apply.

Yes. There are a lot of issues right now with the idea of using a value pack or a tuple to call a function, and most of them apply to the tuple splat discussion that took place a few months ago. Namely, the idea of a tuple or 'vector' of values does not map cleanly to Swift's function parameter conventions. You have inout params, params with default values, argument labels, and other stuff that tuples can't represent cleanly or at all.

I know that this difficulty is not directly related to variadic generics, but it does demonstrate a limitation of this approach to forwarding.

I have already run into a use case where I would like to accept a function and a pack of arguments, store the arguments, be able to compare them for equality, and later invoke the function with them. However, in order for this approach to make sense in my use case it would be essential that the user *not* need to explicitly provide arguments for parameters with defaults.

I bring this up in hopes that we might try to explore designs that would support this use case, and at least give it some consideration. I’m trying to think of ways to make this work but haven’t come up with anything obvious yet.

I do want to explore designs in this space, and I think we will need to figure it out at some point.

If a good solution cannot present itself in the time frame, I'd be willing to punt for the purposes of this proposal.

I am ok with that as long as we can see a path forward to a more robust forwarding solution that can sit beside the variadic generics feature. It would be unfortunate if we move ahead and later find out that we did something that makes more robust forwarding more difficult to design for one reason or another.

My idea of a (sad, awful) fallback solution is to prohibit apply on functions with inout params, require an argument for every argument in the formal parameter list, and allow a fully qualified function reference to be called without re-specifying the argument labels:

struct Foo {
  func myFunc(x: Int, y: Int) { }
  func myFunc(x: Int, z: Int) { }
}

let x = Foo()
let theFunc = x.myFunc(_:y:)
// Cannot do this now
x.myFunc(_:y:)(1, 2)
// Have to do this:
x.myFunc(_:y:)(1, y: 2) // but 'y' is redundant on right; this was discussed during the tuple splat thread

I haven't tried this. It actually surprised me. I thought the unlabeled tuple would implicitly work where a labeled tuple with the same sequence of member types was required.

// In the future...
x.someFunc(_:y:z...:)(1, 2, myPack...)

-Matthew

[*] On a tangential topic, how is Swift going to handle generics across module boundaries in the future? People are complaining that their library generics code is too slow because specialization is impossible, and specialization only happens on stdlib generic types because of some hacks. https://github.com/lorentey/BTree#generics notes that @_specialize might be exposed as an attribute for library author use in the future. It might be the case that every variadic generic type might need to be @_specialize by default, because I can't imagine a variadic equivalent to the dynamic-dispatch solution currently used to implement regular generics without specialization.

Agree that cross module specialization (and WPO generally) is very important. When modules have a nontrivial performance cost (inability to specialize generics) their use is discouraged to some degree.

···

Sent from my iPad

On May 29, 2016, at 1:22 AM, Austin Zheng <austinzheng@gmail.com> wrote:

On May 28, 2016, at 7:41 PM, Matthew Johnson <matthew@anandabits.com> wrote:

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #18

- I have an argument pack. How would I apply a function taking a single argument to each element in the pack? Go via the tuple?

This is definitely something that needs to be worked out.

The C++ pack expansion rules http://en.cppreference.com/w/cpp/language/parameter_pack in the most basic case expand out and separate with commas, e.g.

  pack = (a, b, c)
  foo(pack …) => foo(a, b, c)

But then pattern (i.e. the part to the left of …) may also be more complicated, e.g.

  foo(pack++) … => foo(a++), foo(b++), foo(c++)

The fold expressions then ‚Äúonly‚ÄĚ replace the commas separating instantiations of the pattern with a different ‚Äúoperator‚ÄĚ (and special associated rules for the null element).

And although I really (ab-)use this feature in C++, I’m not entirely sure whether this sort of thing wouldn’t be more suited to a macro(-ish) system than trying to tie it to generics? That said, of course expansion has to be possible inside Generic<Pack …>, but I don’t see why it wouldn’t be.

I think single-function application is a common enough case that it should be handled, without the generality of a macro system. Not sure how much further it should be taken, especially in a v1.

- Why is this a separate thing from Tuple itself? It feels so similar; I can convert between them, so why do I need this other thing?

There are a couple of issues with implementing this using only tuples:
- Using tuples for everything requires functions written to be used with variadic generics to specifically take a single tuple as an argument, or to bring back a redesigned version of the magical tuple splat functionality (https://github.com/apple/swift-evolution/blob/master/proposals/0029-remove-implicit-tuple-splat.md). A value pack isn’t a tuple and doesn't have to worry about whether or not argument labels should match up with tuple member labels, etc.

I’d think something like (explicit) splat at the call-site with what I’d imagine would be a few different variants would be the cleanest:
- #anonymous_splat: takes tuple with or without labels and expands according to pattern ignoring function argument labels
- #named_splat: takes tuple with or without labels and an optional second tuple type (default to the type of the first tuple) of matching size from which it takes the names and expands the values in the first tuple as the names (labels) from the second type.
- …?

As I mentioned in my email to Matthew, Swift already has a way to fully qualify a method name, including the "argument labels". if that fully qualified name is used, IMO the parameter labels in the tuple are redundant and should be optional/ignored.

- Tuples don’t allow for generic functions that take a varying number of arguments, unless you want to write them as functions that take a variably sized tuple (see the "foo()" example above).

Yeah, the expansion from tuple to args has to happen at the call site, I think.

Is it possible to have a Tuple containing an `inout` reference (i.e. I want reference behaviour for this tuple member)?

I tried this last night; it doesn't seem to be possible.

···

On May 29, 2016, at 2:39 AM, Daniel Vollmer via swift-evolution <swift-evolution@swift.org> wrote:

On 29 May 2016, at 02:33, Austin Zheng <austinzheng@gmail.com> wrote:

  Daniel.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #19

Sent from my iPad

I significantly rewrote the proposal to take into account as much feedback as I could. (Many things, like syntax, haven't been changed yet, but will be in a forthcoming version.)

What I did change:

- Renamed 'packs' to 'vectors'

What is the rationale here? Vector makes some sense for the parameter packs because they only consist of types and are thus homogenous. But value packs and argument packs will consist of values or arguments that might all have different types. They are heterogeneous. So vector doesn't seem like the right term. It's not a huge deal, but something to consider anyway.

The intended meaning is that a value vector is homogeneous in the sense that all its members are vectors.

That being said, I don't feel much at all about the naming either way. The "rationale" was that maybe changing 'pack' to a different word would help avoid scaring off people still scarred by C++ templates :). Not really a compelling reason to be honest.

Austin

···

On May 29, 2016, at 8:04 PM, Matthew Johnson <matthew@anandabits.com> wrote:
On May 29, 2016, at 7:36 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

By the way, the multiMap example is basically the same as the applicative functor for ZipList in Haskell (http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors). You can probably find several more good examples by looking at other applicative functors.

Still thinking about more robust function forwarding but not making much progress...

- Discussed variadic typealiases a bit, including things like "variadic String" for holding the results of vector computations
- There's a "every variadic associated type must be equal" constraint that can be defined now
- I added a section discussing a "fold" operation, to reduce a value pack/value vector into a single scalar with the help of a user-defined function.
- I changed the proposal so that making a tuple out of a vector now requires surrounding the vector with #tuple(), to get rid of the 'implicit' rules that plx brought up
- I added a section briefly discussing how this feature might be implemented.

Some thoughts:

- Things like indexing into a value vector by an integer value would be extremely powerful. But as far as I can tell they'd require a great deal of macro-like functionality to go along with them. A way to define constant expressions would be required, so we could define "#index = #count(T...)" or something. Then we'd need ways to manipulate that value (increment or decrement) if we wanted to work with the previous or next elements in a chain, we'd need compile-time conditional checking so that a variadic generic could behave correctly for the first or last item in a vector, and so forth. Omitting these expensive features is going to limit the number of uses variadic generics have; is this tradeoff going to be worth it? Could we push off those features to a later date, if/when Swift gets an actual compile time metaprogramming design?

- The more I think about things, the more I'm leaning towards the idea that tuples are the only construct necessary. We could get rid of most of the features of value packs/vectors, and allow them to only serve two roles: defining a variadic generic function, and spreading out a tuple in order to call a variadic generic function. (I think I prefer a spreading operator to bringing back the magic compiler tuple splat functionality.) They could also be "spread out" to define or specialize a different variadic generic type. Thoughts?

- With the existence of 'fold', might it be worth it to remove #tail() (and maybe #head), at least from v1? This would represent a slight loss of expressive power for common use cases in exchange for a considerable decrease in complexity.

Alternatively, some tuple-based designs might make this point obsolete. Imagine something like this:

func head<T, ...U>(input: (T, U...)) -> T { ... }
func tail<T, ...U>(input: (T, U...)) -> (U...) { ... }

Again, any comments are welcome. I hope to continue evolving this proposal as the community decides what they want and don't want to see.

On May 28, 2016, at 1:03 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

(Austin Zheng) #20

Umm...all its members are *values*. Sorry.

···

On May 29, 2016, at 8:14 PM, Austin Zheng <austinzheng@gmail.com> wrote:

On May 29, 2016, at 8:04 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

Sent from my iPad

On May 29, 2016, at 7:36 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I significantly rewrote the proposal to take into account as much feedback as I could. (Many things, like syntax, haven't been changed yet, but will be in a forthcoming version.)

What I did change:

- Renamed 'packs' to 'vectors'

What is the rationale here? Vector makes some sense for the parameter packs because they only consist of types and are thus homogenous. But value packs and argument packs will consist of values or arguments that might all have different types. They are heterogeneous. So vector doesn't seem like the right term. It's not a huge deal, but something to consider anyway.

The intended meaning is that a value vector is homogeneous in the sense that all its members are vectors.

That being said, I don't feel much at all about the naming either way. The "rationale" was that maybe changing 'pack' to a different word would help avoid scaring off people still scarred by C++ templates :). Not really a compelling reason to be honest.

Austin

By the way, the multiMap example is basically the same as the applicative functor for ZipList in Haskell (http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors). You can probably find several more good examples by looking at other applicative functors.

Still thinking about more robust function forwarding but not making much progress...

- Discussed variadic typealiases a bit, including things like "variadic String" for holding the results of vector computations
- There's a "every variadic associated type must be equal" constraint that can be defined now
- I added a section discussing a "fold" operation, to reduce a value pack/value vector into a single scalar with the help of a user-defined function.
- I changed the proposal so that making a tuple out of a vector now requires surrounding the vector with #tuple(), to get rid of the 'implicit' rules that plx brought up
- I added a section briefly discussing how this feature might be implemented.

Some thoughts:

- Things like indexing into a value vector by an integer value would be extremely powerful. But as far as I can tell they'd require a great deal of macro-like functionality to go along with them. A way to define constant expressions would be required, so we could define "#index = #count(T...)" or something. Then we'd need ways to manipulate that value (increment or decrement) if we wanted to work with the previous or next elements in a chain, we'd need compile-time conditional checking so that a variadic generic could behave correctly for the first or last item in a vector, and so forth. Omitting these expensive features is going to limit the number of uses variadic generics have; is this tradeoff going to be worth it? Could we push off those features to a later date, if/when Swift gets an actual compile time metaprogramming design?

- The more I think about things, the more I'm leaning towards the idea that tuples are the only construct necessary. We could get rid of most of the features of value packs/vectors, and allow them to only serve two roles: defining a variadic generic function, and spreading out a tuple in order to call a variadic generic function. (I think I prefer a spreading operator to bringing back the magic compiler tuple splat functionality.) They could also be "spread out" to define or specialize a different variadic generic type. Thoughts?

- With the existence of 'fold', might it be worth it to remove #tail() (and maybe #head), at least from v1? This would represent a slight loss of expressive power for common use cases in exchange for a considerable decrease in complexity.

Alternatively, some tuple-based designs might make this point obsolete. Imagine something like this:

func head<T, ...U>(input: (T, U...)) -> T { ... }
func tail<T, ...U>(input: (T, U...)) -> (U...) { ... }

Again, any comments are welcome. I hope to continue evolving this proposal as the community decides what they want and don't want to see.

On May 28, 2016, at 1:03 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

Hello swift-evolution,

I put together a draft proposal for the variadic generics feature described in "Completing Generics" as a major objective for Swift 3.x. It can be found here:

https://github.com/austinzheng/swift-evolution/blob/az-variadic-generics/proposals/XXXX-variadic-generics.md

It adopts the syntax and semantics that are described in Completing Generics, and attempts to remain as simple as possible while still being useful for certain use cases (although I think there is still room to simplify). The proposal contains sample implementations for four use cases:

- Arbitrary-arity 'zip' sequence
- Arbitrary-arity tuple comparison for equality
- Tuple splat/function application
- Multiple-arity Clojure-style 'map' function

There is a lot of scope for design refinements, and even for alternative designs. With enhanced existentials, there was already an informal consensus that the feature would involve composing some protocols and class requirements, and placing constraints on the associated types, and most everything else was working out the various implications of doing so. That's not true for this feature.

In particular, I'm interested to see if there are similarly expressive designs that use exclusively tuple-based patterns and no parameter packs. I think Rust once considered a similar approach, although their proposal ended up introducing a parameter-pack like construct for use with fn application: https://github.com/rust-lang/rfcs/issues/376

Feedback would be greatly appreciated. Again, be unsparing.

Best,
Austin

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution