[swift-evolution] Variadic generics discussion
Austin Zheng
austinzheng at gmail.com
Sun May 29 12:36:22 CDT 2016
This feedback is great.
> On May 29, 2016, at 9:00 AM, plx via swift-evolution <swift-evolution at swift.org> wrote:
>
> Thanks for getting the discussion started with such a thorough initial writeup.
>
> My overall concern is this:
>
> - on the one hand, I *very much* understand—and support—the idea of starting simple and adding functionality later
> - on the other hand, this is *already* a rather complicated proposal syntactically, semantically, and probably also in implementation
> - on the gripping hand, I’m concerned that despite being so complicated, it’s perhaps too limited to pay for itself as-proposed
>
> Or, put differently, if you believe there’s an optimal point on the complexity/functionality for a v1, I worry a bit after reading it that it’s buying too little practical functionality for the complexity it’ll bring, and that something a *little* more complex might provide a *lot* more practical utility.
>
I agree. There is definitely work to be done to find the optimal complexity/benefit point.
> To that end, I’ve provided some concrete-ish examples of things it’d be nice to be able to do via variadics and the additional features they would either *need* or at least *benefit* from having available.
Excellent!
>
> All of these are very much “nice to have” features that need not be included in a first version, but they each illustrate one possible complexity/capability trade-off.
>
> A.1: Support for uniform variadic-parameter associated-type constraints?
>
> Consider trying to write a variadic form of this sequence:
>
> // given sequences a, b, provides a sequence equivalent-to
> // zip(a,b).lazy.map() {
> // ( min($0.0,$0.1), max($0.0,$0.1) )
> // }
> struct ExtremaSequence<A:Sequence,B.Sequence where A.Iterator.Element == B.Iterator.Element, A.Iterator.Element: Comparable> {
> private let a: A; private let b: B
> }
>
> struct ExtremaIterator<A:Iterator,B.Iterator where A.Element == B.Element, A.Element:Comparable> {
> private var a: A?
> private var b: B?
>
> mutating func next() -> (A.Element,A.Element)? {
> guard let nextA = a?.next() else {
> a = nil; b = nil;
> return nil
> }
> guard let nextB = b?.next() else {
> a = nil; b = nil;
> return nil
> }
> if nextA < nextB {
> return (nextA,nextB)
> } else {
> return (nextB,nextA)
> }
> }
>
> }
>
> …would it be necessary to write the type’s generic parameters like this:
>
> struct VariadicExtremaSequence<E:Comparable,S… where S:Sequence, S.Iterator.Element == E>
>
> …or would there be some way of writing a constraint like “all `S.Iterator` must have same `.Element`?”?
Yes. Right now the way the feature is written up implies:
- You can make all the pack members conform to the same protocols/subclass requirements
- You can make all the associated types conform to the same protocols/subclass requirements
- You can make all the associated types forced to be the same concrete type
The missing constraint(s) are:
- All the associated types must be equal across pack members (i.e. "all S.Iterator.Element's are equal")
- anything else?
>
> A.2: Support for non-uniform "parameter-to-parameter” constraints
>
> As an example:
>
> protocol ValueTransformer {
> associatedtype Input
> associatedtype Output
>
> func transformedValue(for input: Input) throws -> Output
>
> }
>
> // how to express this (if possible), mock syntax below
> struct LoggingValueTransformerApplier<
> T:ValueTransformer
> where
> …T[i],T[j]… => T[i].Output == T[j].Input> : ValueTransformer {
>
> typealias Input = #first(T…).Input
> typealias Output = #last(T…).Output
>
> private let (transformers) = (T...)
>
> func transformedValue(for input: Input) throws -> Output {
> // evaluate incrementally, logging input => (output | error) step-by-step
> }
>
> }
>
> …something like the above is definitely a "nice to have", but not having it will close off certain use cases.
Oh, this is interesting. So a way to specify an equality relationship between "adjacent" sets of associated types?
>
> B: Integer-Based Indexing
>
> I see it’s been brought up already, but I’d *strongly* suggest making support for integer-based “indexing” into variadic packs a priority.
>
> What concerns me is that without support for that, I suspect a lot of code would have to get "written twice” if using the “recursive” API on parameter packs.
>
> Here’s a mock example:
>
> // a “weaker” dictionary-like protocol
> protocol LookupTable {
> associatedtype Key: Hashable
> associatedtype Value
>
> subscript(key: Key) -> Value? { get }
>
> }
>
> /// Does a cascading search for values through a possibly *heterogeneous*
> /// collection of backing lookup tables…caching results to avoid subsequent searches
> struct HeterogeneousCascadingLookupTable<K:Hashable,V,T…
> where
> T:LookupTable,
> T.Key == K,
> T.Value == V> : LookupTable {
>
> private let (tables): (T…)
> private var valueCache: [K:V] = [:]
> private var missingKeys: Set<K> = []
>
> // implementation *with* integer-based indexing:
> subscript(key: K) -> V? {
> get {
> guard !missingKeys.contains(key) else { return nil }
> if let cached = valueCache[key] { return cached }
> for index in 0..<#count(T…) {
> if let v = tables[index][key] {
> valueCache[key] = v
> return v
> }
> }
> missingKeys.insert(key)
> return nil
> }
> }
>
> // implementation without integer-based indexing (or equivalent mechanism):
> subscript(key: K) -> V? {
> get {
> guard !missingKeys.contains(key) else { return nil }
> if let cached = valueCache[key] { return cached }
> if let value = self.lookupValue(for: key, in: self.tables) {
> valueCache[key] = value
> return value
> } else {
> missingKeys.insert(key)
> return nil
> }
> }
> }
>
> // recursive lookup implementation (necessary b/c our type itself
> // isn’t defined by recursively-nesting itself)
> private final func lookupValue<U…
> where
> U…: LookupTable,
> U.Key == K,
> U.Value == V>(for key: K, in tables: U…) -> V? {
> return #first(tables)[key] ?? self.lookupValue(for: key, in: #rest(tables))
> }
>
> }
>
> …which isn’t the end of the world, but having to write a separate recursive implementation of each method that needs to step-through the variadic parameters would spread things out a bit, it’d seem.
I'll write something up.
for index in 0..<#count(T…) {
if let v = tables[index][key] {
valueCache[key] = v
return v
}
}
I assume this is all compile time code generation (unroll the loop in the source #count(T...) times for each arity that T... is instantiated as, with a different 'tables' pack member value for each unrolled loop iteration).
>
> (Yes, this specific thing could be written today w/out variadics, but it illustrates the tradeoff here).
>
> C: “Variadic-Sum” / Structural-Union?
>
> I mentioned this before in a response to the manifesto email, but will reiterate it here: there’s a fair amount of useful things you could do with variadic generics *if* there was also some similar way to get a “structural union”.
>
> A simple motivating example is something like a `Chain` sequence (analogous to `Zip`); e.g. something for which `chain(a,b)` is the sequence of ‘the elements in `a`, then the elements in `b`.
>
> Although the proposed variadics make the sequence itself easy to write:
>
> // for now I'd assume we need the `E` as a separate type parameter here,
> // but recall the previous point
> struct ChainSequence<E,S… where S:Sequence, S.Iterator.Element == E> {
> private let (…sequences): (S…)
> init(…arguments: S…) { … }
> }
>
> …the iterator is a bit more complicated. Without “structural unions” you’d probably wind up with something like this for a variadic implementation:
>
> struct ChainSequenceIterator<E,I… where I:Iterator, I.Element == E> {
>
> private var (…iterators): (I?…) // <- I hope this works
>
> mutating func next() -> E? {
> // find first non-nil iterator, try to get next element from it;
> // if next is non-nil, return that, otherwise nil it out and
> // find the *next* non-nil iterator, etc….
> }
>
> }
>
> …which could be made to work, but is wasteful in some ways (you have space to store n iterators…). You can make it a little cleaner if you have some way of doing integer-based indexing into the variadic parameters, but that doesn’t change the space requirements (it’s still going to need room for all `n` iterators + bookkeeping).
>
> If, however, you have some variadic-compatible structural unions, you can write it as (roughly):
>
> struct ChainSequenceIterator<E,S… where S:Sequence, S.Iterator.Element == E> {
> private let source: ChainSequence<E,S…>
> private var iterator: (S.Iterator |…) // (meant to be ~ `(S1.Iterator | S2.Iterator | S3.Iterator | …. | SN.Iterator)` )
> private var done: Bool = false
>
> mutating func next() -> E? {
> // if not `done`, try `next` on current iterator in `iterator`
> // if non-nil, return, otherwise advance to next iterator, etc., ...
> }
> }
>
> …(how much space this actually saves depends on the size of `source` vs the size of the iterators, but it’s *possible* to save space this way).
>
> Variadic generics *can* be added w/out structural unions — they’re a pure "nice-to-have" — but having support for variadic "product types" w/out corresponding variadic "sum types" is going to complicate-or-prevent certain constructs.
This is interesting. Might it be possible with to accomplish this with existentials (this is sort of a cross-reference to a different proposal from the generics manifest)? An existential type as described below would work for any pack where all the elements were constrained in the same way. Not sure if it could be made to work in the case where the types in the pack are related to each other (as proposed earlier).
struct ChainSequenceIterator<E, S… where S:Sequence, S.Iterator.Element == E> {
// A single variable that contains each iterator in turn; specific type doesn't matter as long as the element is E
private var iterator : Any<Iterator where .Element == E>?
// ...
}
>
> D: Make Parameter-Packs Named
>
> I understand the appeal of the `…T`-style syntax, but I’d at least consider giving parameter-packs a more-concrete existence, e.g. something like this:
>
> // strawman declaration syntax:
> struct Foo<I,J,K#ParameterPack> {
>
> // `K` here will refer to the variadic parameter-pack itself;
> // cf the `typealias` below , but basically K ~ the tuple of its types
>
> typealias KValueTuple = #tuple(K) // == tuple of values of type K.0, K.1, etc.)
> typealias KTypeTyple - #typeTuple(K) // == tuple of types like K.0, K.1
> typealias FirstK = #first(K)
> typealias LastK = #last(K)
> static var kArity: Int { return #count(K) }
> // and so on
>
> }
>
> // straw man point-of-use syntax, can be adjusted of course:
> let concreteFoo = Foo<I,J,K:(K0,K1,K2,…,Kn)>
>
> …which complicates the grammar, but IMHO feels a lot nicer than having a lot of "implicit rules" about what `…` means and so on.
I think it makes sense to make pack usage explicit. I think the dots at site of declaration don't really cause trouble, though, and are a little nicer to read than T#ParameterPack.
>
>> On May 28, 2016, at 3:03 PM, Austin Zheng via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>
>> Hello swift-evolution,
>>
>
> _______________________________________________
> 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/21219071/attachment.html>
More information about the swift-evolution
mailing list