Variadic generics discussion

[anandabits (Matthew Johnson)]

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

Makes sense when you look at just the fact that they are values and don't consider what kind of value I guess.

···

Sent from my iPad

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

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> wrote:

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 (Functors, Applicative Functors and Monoids - Learn You a Haskell for Great Good!). 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> 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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]

A few more comments inlined now that I’ve read it.

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

Seems the answer is yes iff there’s a `T.Foo... == U.Bar…` style relationship, but no way to just request same-arity by itself?

- if you have e.g. 2+ packs, could you enforce e.g. T.Foo… == U.Bar ?

Missed this either before or you added it, sorry either way.

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

I'll write something up.

I like the `fold` construct but feel like for this use it needs a few more options-or-variants.

The first one is some more-explicit support for “early exit”.

EG for the cascading-lookup example, you can convert it to this `#fold`:

  private func lookupKey(key: K) -> V? {
    return fold(
      start: nil,
      reducer: {
        (table, value)
        in
        return value ?? table[key]
      },
      values: tables
    )
  }

…but unless the compiler is very savvy you are going to have a bunch of unneeded stuff even after your “success” (it won’t do another lookup, but it just seems wasteful and could be wasteful in other contexts).

Relatedly, that `#fold` is only going to work if the compiler can infer a proper type for the `table` argument to the `reducer`.

If you have to specify the types explicitly via a helper function, it seems like this won’t work:

  func lookupIfNecessary<T:LookupTable where T.Key == K, T.Value == V>(table: T, key: K, value: V?) -> V? {
     return value ?? table[key]
  }

…b/c the signature isn’t right for the reducer, and it seems like this might work:

  func createLookupFunction<T:LookupTable where T.Key == K, T.Value == V>(key: K) -> (T, V?) -> V? {
     return { (t,v) in return v ?? t[key] }
  }

  private func lookupKey(key: K) -> V? {
    return fold(
      start: nil,
      reducer: createLookupFunction(key), // <- should work…I hope...
      values: tables
    )
  }

…but it seems a bit convoluted; perhaps there’s a trick here? Or perhaps a variant with an adjusted signature like so:

  // perhaps inout K ? or as an option?
  #foldWithContext(context: K, start: U, reducer:(#requirements,U,K) -> U, values: (T…)) -> U

Relatedly, having `#fold` variants like the above that include the current index could address a lot of the uses for integer-based indexing:

  #indexedFold(start: U, reducer:(#requirements,U,Int) -> U, values: (T…)) -> U

…(the above can be done w/out dedicated support, but dedicated support might be more compiler-friendly on this one).

Finally, after reading it over again I really find the `…` confusing beyond the initial declaration sites (as you can perhaps tell since I’ve been mis-using it in my replies).

I can’t come up with an alternative that isn’t a major regression for simple declarations, but if a more-explicit syntax could be invented I’d highly prefer it.

···

On May 30, 2016, at 7:44 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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Austin (Austin Zheng)]

(inline, again)

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

Yes, this makes sense. #allequal(T...), maybe?

…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 ?

Yes, an explicit "same length" constraint makes sense. Otherwise, if a pack
is derived from another pack they are implied to have the same length.

I think the second constraint should be possible already? I'll double-check.

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

I'm not sure if 'fold' as currently expressed is powerful enough to do
something like this. I suppose a variant of fold that took its parameter
'inout' would work, especially if your 'fold' type was a (isFinished,
desiredValue) tuple (or maybe even just "desiredValue?" as an optional).

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 ==
> {

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

I think union types (the A | B | C anonymous type commonly requested) would
naturally complement this sort of functionality. You could have something
like #union(T...), which is a scalar value whose type is T1 | T2 | ... | Tn.

Like you said, a lot of things are possible with even the simple model,
when dynamic casting is taken into account. It's just more difficult to
read and possibly slower to execute.

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.

I'll keep on thinking about this.

···

On Mon, May 30, 2016 at 5:44 AM, plx via swift-evolution < swift-evolution@swift.org> wrote:

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> wrote:

Hello swift-evolution,

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

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

[L_Mihalkovic]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

···

On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

Matthew

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

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

[Lmpessoa (Leonardo Pessoa)]

I hate C++ generics. Just thought about sharing this.

···

On 29 May 2016, at 9:00 am, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

Sent from my iPad

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

Thank you for reading through the proposal!

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

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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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. GitHub - attaswift/BTree: Fast sorted collections for Swift using in-memory B-trees 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.

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

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

[Austin (Austin Zheng)]

(more inline)

A few more comments inlined now that I’ve read it.

I like the `fold` construct but feel like for this use it needs a few more
options-or-variants.

The first one is some more-explicit support for “early exit”.

EG for the cascading-lookup example, you can convert it to this `#fold`:

  private func lookupKey(key: K) -> V? {
    return fold(
      start: nil,
      reducer: {
        (table, value)
        in
        return value ?? table[key]
      },
      values: tables
    )
  }

…but unless the compiler is very savvy you are going to have a bunch of
unneeded stuff even after your “success” (it won’t do another lookup, but
it just seems wasteful and could be wasteful in other contexts).

Relatedly, that `#fold` is only going to work if the compiler can infer a
proper type for the `table` argument to the `reducer`.

If you have to specify the types explicitly via a helper function, it
seems like this won’t work:

  func lookupIfNecessary<T:LookupTable where T.Key == K, T.Value ==
>(table: T, key: K, value: V?) -> V? {
     return value ?? table[key]
  }

…b/c the signature isn’t right for the reducer, and it seems like this
might work:

  func createLookupFunction<T:LookupTable where T.Key == K, T.Value ==
>(key: K) -> (T, V?) -> V? {
     return { (t,v) in return v ?? t[key] }
  }

Yes, the fundamental problem here is that a user might need to pass an
arbitrary number of additional, non-pack-dependent arguments into the
reducer.

One possible solution might be an "AdditionalInfo" parameter representing
some constant always passed into the reducer function. This would
effectively do the same thing as a closure closing over some common state,
but maybe be a little less horrific to the user?

fold(start: U, constantData: V, reducer: (#requirements, U, V) -> U,
values: T...)

(I ran into this issue some time ago as an app developer where I needed to
connect two APIs. One of them took fewer arguments than the other, and we
needed to preserve the additional context. The offending API was also
vended by a 3rd-party library, so it couldn't be changed. I remember an
elegant solution using multiple argument list currying, a feature which is
now gone from Swift...)

  private func lookupKey(key: K) -> V? {
    return fold(
      start: nil,
      reducer: createLookupFunction(key), // <- should work…I hope...
      values: tables
    )
  }

…but it seems a bit convoluted; perhaps there’s a trick here? Or perhaps a
variant with an adjusted signature like so:

  // perhaps inout K ? or as an option?
  #foldWithContext(context: K, start: U, reducer:(#requirements,U,K) -> U,
values: (T…)) -> U

Relatedly, having `#fold` variants like the above that include the current
index could address a lot of the uses for integer-based indexing:

  #indexedFold(start: U, reducer:(#requirements,U,Int) -> U, values: (T…))
-> U

…(the above can be done w/out dedicated support, but dedicated support
might be more compiler-friendly on this one).

Here's a revised signature for fold(), taking in account the things you
requested (which are good points, the Objective-C "BOOL*" arguments on
enumeration blocks and the .enumerate() method on Swift collections attest
to that):

#fold<...T, U>(start: U, reducer: (#requirements, Int, U) -> (U, Bool),
values: T...) -> U

The reducer takes in an Int which is provided as the index into the pack.
It returns a tuple, (U, Bool), which can be used to specify early exist.
There could be "sugared" versions of fold which don't provide the index
and/or the early return functionality; those wouldn't be too difficult to
design.

(I didn't include the additionalInfo feature mentioned above, but it
wouldn't be too hard to munge it in.)

Finally, after reading it over again I really find the `…` confusing
beyond the initial declaration sites (as you can perhaps tell since I’ve
been mis-using it in my replies).

I can’t come up with an alternative that isn’t a major regression for
simple declarations, but if a more-explicit syntax could be invented I’d
highly prefer it.

The syntax is desperately in need of improvement. Even I had to read over
my examples a few times to make sure I was using everything correctly.

I'm thinking about a more tuple-oriented approach that would eliminate the
distinction between packs and tuples everywhere except when calling or
defining a generic function or defining a generic type, which might
eliminate some of the confusion.

···

On Mon, May 30, 2016 at 6:30 AM, plx via swift-evolution < swift-evolution@swift.org> wrote:

[anandabits (Matthew Johnson)]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

···

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Matthew

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'
- 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[L_Mihalkovic]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

the two sections are linked. My point is just to keep in mind what they say about the conformances that can be established at compile time, versus the scenarios that wind-up hitting the runtime reflection system to resolve a question (dynamic casts).

···

On May 31, 2016, at 4:26 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Matthew

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'
- 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[anandabits (Matthew Johnson)]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

the two sections are linked. My point is just to keep in mind what they say about the conformances that can be established at compile time, versus the scenarios that wind-up hitting the runtime reflection system to resolve a question (dynamic casts).

There are no performance concerns noted in Doug’s manifesto. Extensions, including conformances for structural types is listed under “minor extensions”, not “maybe” or “unlikely”. Providing extensions and conformances for structural types shouldn’t be any more difficult than doing so for any other variadic type.

···

On May 31, 2016, at 10:17 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On May 31, 2016, at 4:26 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Matthew

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'
- 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[L_Mihalkovic]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

the two sections are linked. My point is just to keep in mind what they say about the conformances that can be established at compile time, versus the scenarios that wind-up hitting the runtime reflection system to resolve a question (dynamic casts).

There are no performance concerns noted in Doug’s manifesto. Extensions, including conformances for structural types is listed under “minor extensions”, not “maybe” or “unlikely”. Providing extensions and conformances for structural types shouldn’t be any more difficult than doing so for any other variadic type.

Good... my moment of doubt came from reading the code involved in the differed initialization og metadata for the case of non fixed size tuples. I will play more with the compiler and see if I can trigger it.

···

On May 31, 2016, at 5:29 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 10:17 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On May 31, 2016, at 4:26 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:
On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

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> 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[anandabits (Matthew Johnson)]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

the two sections are linked. My point is just to keep in mind what they say about the conformances that can be established at compile time, versus the scenarios that wind-up hitting the runtime reflection system to resolve a question (dynamic casts).

There are no performance concerns noted in Doug’s manifesto. Extensions, including conformances for structural types is listed under “minor extensions”, not “maybe” or “unlikely”. Providing extensions and conformances for structural types shouldn’t be any more difficult than doing so for any other variadic type.

Good... my moment of doubt came from reading the code involved in the differed initialization og metadata for the case of non fixed size tuples. I will play more with the compiler and see if I can trigger it.

It sounds like you’re more familiar with the implementation than I am. I don’t know how much work has been done to support general variadic types yet. It’s possible there is still a lot of work to be done. But I can’t imagine any reason variadic conformance would be more difficult for built-in structural types than it is for user-defined variadic types.

···

On May 31, 2016, at 10:46 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com> wrote:
On May 31, 2016, at 5:29 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

On May 31, 2016, at 10:17 AM, L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

On May 31, 2016, at 4:26 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Matthew

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'
- 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[L_Mihalkovic]

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

It might be worth reading again the generics manifesto’s comment about how the runtime cost of chasing up the protocol chain might turn it into a performance nightmare.

Are you talking about providing conditional conformance in a protocol extension: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions ?

That is not what I was talking about. I was talking about extensions of structural types: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

the two sections are linked. My point is just to keep in mind what they say about the conformances that can be established at compile time, versus the scenarios that wind-up hitting the runtime reflection system to resolve a question (dynamic casts).

There are no performance concerns noted in Doug’s manifesto. Extensions, including conformances for structural types is listed under “minor extensions”, not “maybe” or “unlikely”. Providing extensions and conformances for structural types shouldn’t be any more difficult than doing so for any other variadic type.

Good... my moment of doubt came from reading the code involved in the differed initialization og metadata for the case of non fixed size tuples. I will play more with the compiler and see if I can trigger it.

It sounds like you’re more familiar with the implementation than I am. I don’t know how much work has been done to support general variadic types yet. It’s possible there is still a lot of work to be done. But I can’t imagine any reason variadic conformance would be more difficult for built-in structural types than it is for user-defined variadic types.

Hmm. Not sure what you call variadic types. As far as I can tell types have a fixed layout that the compiler is even able to compute. The only exception seemed to be these variable sized tuples that differ layout definition until runtime. But that is still not a variadic type. It is not that the struct is variadic, it is its parameter list that is variadic. That influences the cardinality of certain properties, but not the overall shape. What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

···

On May 31, 2016, at 5:52 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 10:46 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On May 31, 2016, at 5:29 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 10:17 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On May 31, 2016, at 4:26 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On May 31, 2016, at 9:16 AM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:
On May 31, 2016, at 3:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

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> 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: Draft RFC: variadic generics · Issue #376 · rust-lang/rfcs · GitHub

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

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

[Austin (Austin Zheng)]

How so? I'm interested in anything that can get us away from having to
generating code at compile-time.

···

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic < laurent.mihalkovic@gmail.com> wrote:

What's interesting about the code in the manifesto is that it looks very
much like "..." is a runtime construct, as opposed to trying the get the
compiler to do the heavy lifting.

[Austin (Austin Zheng)]

AFAICT compile-time code generation suffers from the C++ templates problem
- my understanding is that if you don't have access to the definition of
the template you can't specialize. A Swift (regular, non-variadic) generic
function can be called with any conforming type without need for
specialization through dynamic dispatch, with specialization still existing
as an optimization. Having the same apply to variadic generics would be a
significant advantage.

···

On Tue, May 31, 2016 at 11:08 AM, David Sweeris <davesweeris@mac.com> wrote:

Out of curiosity, why?

- Dave Sweeris

On May 31, 2016, at 12:59 PM, Austin Zheng via swift-evolution < > swift-evolution@swift.org> wrote:

How so? I'm interested in anything that can get us away from having to
generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic < > laurent.mihalkovic@gmail.com> wrote:

What's interesting about the code in the manifesto is that it looks very
much like "..." is a runtime construct, as opposed to trying the get the
compiler to do the heavy lifting.

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

[David_Sweeris]

Out of curiosity, why?

- Dave Sweeris

···

On May 31, 2016, at 12:59 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

How so? I'm interested in anything that can get us away from having to generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

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

[anandabits (Matthew Johnson)]

AFAICT compile-time code generation suffers from the C++ templates problem - my understanding is that if you don't have access to the definition of the template you can't specialize. A Swift (regular, non-variadic) generic function can be called with any conforming type without need for specialization through dynamic dispatch, with specialization still existing as an optimization. Having the same apply to variadic generics would be a significant advantage.

I believe there has been some discussion of packaging SIL (or something like that) with modules for at least some generic constructs to allow specialization across module boundaries.

···

On May 31, 2016, at 1:11 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

On Tue, May 31, 2016 at 11:08 AM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:
Out of curiosity, why?

- Dave Sweeris

On May 31, 2016, at 12:59 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

How so? I'm interested in anything that can get us away from having to generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

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

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

[L_Mihalkovic]

well there is no macro system, and for the moment a clear statement from chris that this is not on the table in the short term. the code in the example looked like run-of-the-mill swift, except for the “…". so that leaves us with swift looking code that would be executed by the compiler, but with nothing particular to tell which parts to and which not. just a thought.

···

On May 31, 2016, at 7:59 PM, Austin Zheng <austinzheng@gmail.com> wrote:

How so? I'm interested in anything that can get us away from having to generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

[L_Mihalkovic]

what I mean is I think it is perfectly doable as a runtime thing, without much apparent magic (the compiler support code is a different story), but it looks like a clean runtime story.

···

On May 31, 2016, at 7:59 PM, Austin Zheng <austinzheng@gmail.com> wrote:

How so? I'm interested in anything that can get us away from having to generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

[Chris_Lattner]

well there is no macro system, and for the moment a clear statement from chris that this is not on the table in the short term. the code in the example looked like run-of-the-mill swift, except for the “…". so that leaves us with swift looking code that would be executed by the compiler, but with nothing particular to tell which parts to and which not. just a thought.

Lets be clear though: variadic generics are not in scope for Swift 3 either.

I definitely don’t speak for the rest of the core team, nor have I discussed it with them… but IMO, this whole feature seems like a better fit for a macro system than it does to complicate the generics system. Unlike C++’s template system, our generics system inherently has runtime / dynamic dispatch properties, and I don’t think that shoehorning variadics into it is going to work out well.

-Chris

···

On May 31, 2016, at 12:17 PM, L Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

On May 31, 2016, at 7:59 PM, Austin Zheng <austinzheng@gmail.com <mailto:austinzheng@gmail.com>> wrote:

How so? I'm interested in anything that can get us away from having to generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

What's interesting about the code in the manifesto is that it looks very much like "..." is a runtime construct, as opposed to trying the get the compiler to do the heavy lifting.

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

[Austin (Austin Zheng)]

This is pretty much where my thinking about the topic has led me as well.
I'll resign this topic to pursue some other, hopefully more relevant work,
although anyone who wants to continue the discussion is welcome to.

···

On Tue, May 31, 2016 at 12:49 PM, Chris Lattner <clattner@apple.com> wrote:

On May 31, 2016, at 12:17 PM, L Mihalkovic via swift-evolution < > swift-evolution@swift.org> wrote:

well there is no macro system, and for the moment a clear statement from
chris that this is not on the table in the short term. the code in the
example looked like run-of-the-mill swift, except for the “…". so that
leaves us with swift looking code that would be executed by the compiler,
but with nothing particular to tell which parts to and which not. just a
thought.

Lets be clear though: variadic generics are not in scope for Swift 3
either.

I definitely don’t speak for the rest of the core team, nor have I
discussed it with them… but IMO, this whole feature seems like a better
fit for a macro system than it does to complicate the generics system.
Unlike C++’s template system, our generics system inherently has runtime /
dynamic dispatch properties, and I don’t think that shoehorning variadics
into it is going to work out well.

-Chris

On May 31, 2016, at 7:59 PM, Austin Zheng <austinzheng@gmail.com> wrote:

How so? I'm interested in anything that can get us away from having to
generating code at compile-time.

On Tue, May 31, 2016 at 10:04 AM, L. Mihalkovic < > laurent.mihalkovic@gmail.com> wrote:

What's interesting about the code in the manifesto is that it looks very
much like "..." is a runtime construct, as opposed to trying the get the
compiler to do the heavy lifting.

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