[swift-evolution] Variadic generics discussion
plx
plxswift at icloud.com
Sun May 29 11:00:57 CDT 2016
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 at 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 <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 <https://github.com/rust-lang/rfcs/issues/376>
>
> Feedback would be greatly appreciated. Again, be unsparing.
>
> Best,
> Austin
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160529/4027c12a/attachment.html>
More information about the swift-evolution
mailing list