[swift-evolution] [swift-evolution-announce] [Review] SE-0174: Change `filter` to return an associated type
Anders Ha
hello at andersio.co
Wed May 3 04:51:35 CDT 2017
> On 3 May 2017, at 5:32 PM, Anders Ha via swift-evolution <swift-evolution at swift.org> wrote:
>
> So a bit of correction: generic protocol had been dismissed in the Generic Manifesto specifically for sequences and collections, because it would permit multiple conformances of a certain type to the same protocol with different types of elements, and it is considered wrong.
>
> `Self` in a protocol refers not to the unbound generic type, but to the specialized one, e.g. `Array<T>` where T is bound, instead of `Array`. For your code snippets to work, the compiler would need to explicitly “unspecialize” the specialised `Self` and parameterise it with a different type. This notion is called higher-kinded types.
>
> https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#higher-kinded-types
>
> For example, using the potential syntax in the manifesto:
>
> extension RangeReplaceableCollection {
> func filter<Filtered>(_ isIncluded: (Element) -> Bool) -> Filtered where Filtered ~= Self, Filtered.Element == Element
> func map<Mapped>(_ transform: (Element) -> Mapped.Element) -> Mapped where Mapped ~= Self
> }
>
> Let’s say `Self` is `Set<Int>`, the compiler would need to be instructed to “unspecialize” it and parameterise it again, so that it still knows the resulting collection statically. Then at this point, yes, it can be statically dispatched.
>
> But for now, higher-kinded types do not seem to be on the radar at all. So to achieve the same result, there are only two options:
>
> 1. Type-erased wrappers, e.g. `AnyCollection<T>`, or generalised existential, e.g. `Collection where .Element == T`. This means dynamic dispatch.
> 2. Associated type, i.e. the proposal.
>
> Another important constraint you’ve missed is that only `RangeReplaceableCollection` implies the collection can be explicitly constructed. So a default of `[Element]` is necessary.
Perhaps I should rephrase this for clarity:
Another important constraint missed is that `Sequence` and derived protocols do not imply constructibility and manipulability. These capabilities belong to standalone protocols like `RangeReplaceableCollection` and `SetAlgebra`.
So a default of `[Element]` for `Sequence.filter` is inevitable, even with we have higher-kinded types.
>
> Regards
> Anders
>
>> On 3 May 2017, at 4:57 PM, Howard Lovatt <howard.lovatt at gmail.com> wrote:
>>
>> @Anders,
>>
>> I think you can eliminate the dynamic dispatch for a struct. Using the generic parameterised syntax rather than the where clause syntax (because it is more compact and clearer):
>>
>> protocol Sequence<T> {
>> func filter(_ isIncluded: (T) -> Bool) -> Self<T> // Note: returns Self<T>
>> ...
>> }
>> extension Sequence {
>> func filter(_ isIncluded: (T) -> Bool) -> Self<T> { // Note: returns Self<T>
>> var result = Self<T>
>> for element in self {
>> if isIncluded(element) { result.append(element) }
>> }
>> return result
>> }
>> ...
>> }
>> struct Set<T>: Sequence<T> { ... } // Inherits filter from extension
>>
>> For struct `Set<T>` `Self<T>` is `Set<T>` (obviously, that is what Self means), therefore the compiler can for both code and type checking purposes generate:
>>
>> struct Set<T>: Sequence<T> {
>> func filter(_ isIncluded: (T) -> Bool) -> Set<T> { // Note: returns Set<T>
>> var result = Set<T>
>> for element in self {
>> if isIncluded(element) { result.append(element) }
>> }
>> return result
>> }
>> ...
>> }
>>
>> This is an intermediate step for the compiler since `Set` is still generic, in `T`. When a specific `Set` is instantiated, e.g. `let s = Set<Int>`, the compiler can generate both for code and type checking purposes:
>>
>> struct Set<Int>: Sequence<Int> {
>> func filter(_ isIncluded: (Int) -> Bool) -> Set<Int> { // Note: returns Set<Int>
>> var result = Set<Int>
>> for element in self {
>> if isIncluded(element) { result.append(element) }
>> }
>> return result
>> }
>> ...
>> }
>>
>> When you call `s.filter` there is no dynamic dispatch because `filter` is final within a struct and the compiler also knows that this version of `filter` returns a `Set<Int>` and therefore no dynamic dispatch on the returned value if in a chain of calls either.
>>
>> Have I made a mistake in the above?
>>
>> -- Howard.
>>
>> On 3 May 2017 at 17:27, Anders Ha <hello at andersio.co> wrote:
>> Returning `Self<T>` requires higher kinded type. Note that parameterized protocols are not the same as higher kinded types, since for the former generic protocol parameters are already bound at conformance of the static `Self` like associated types, while the later is about having a generic static `Self`.
>>
>> IOW you cannot do `Self<T>` statically without higher kinded type. The best you can get is generalized existential, e.g. `filter` returning a `Collection where .Element == T` or `Collection<T>` if protocols can be parameterized.
>>
>> The compiler cannot eliminate virtual dispatching for existentials, because this is what existential is by definition — knowing how to manipulate it at static time, but not the type which varies at runtime. All non-class existentials are dispatched through their associated protocol witness tables.
>>
>> Regards
>> Anders
>>
>> On 3 May 2017, at 09:05, Howard Lovatt <howard.lovatt at gmail.com> wrote:
>>
>>> My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.
>>>
>>> I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.
>>>
>>> -- Howard.
>>>
>>> On 2 May 2017, at 8:57 pm, Anders Ha <hello at andersio.co> wrote:
>>>
>>>> I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.
>>>>
>>>> Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.
>>>>
>>>> Regards
>>>> Anders
>>>>
>>>> On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
>>>>
>>>>> Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.
>>>>> On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt at gmail.com> wrote:
>>>>> Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.
>>>>>
>>>>> As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:
>>>>>
>>>>> protocol Equatable {
>>>>> static func ==(lhs: Self, rhs: Self) -> Bool
>>>>> ...
>>>>> }
>>>>> struct Int: Equatable { ... }
>>>>> let e1: Equatable = 1
>>>>> let e2: Equatable = 2
>>>>> if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type
>>>>>
>>>>> I would replace this with:
>>>>>
>>>>> protocol Equatable<T> { // Use T instead of Self
>>>>> static func ==(lhs: T, rhs: T) -> Bool
>>>>> ...
>>>>> }
>>>>> struct Int: Equatable<Int> { ... }
>>>>> let e1: Equatable<Int> = 1
>>>>> let e2: Equatable<Int> = 2
>>>>> if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>
>>>>>
>>>>> As an aside on the aside, even better:
>>>>>
>>>>> protocol Equatable<T = Self> { // T defaults to Self
>>>>> static func ==(lhs: T, rhs: T) -> Bool
>>>>> ...
>>>>> }
>>>>> struct Int: Equatable { ... } // T is Int, the default is Self
>>>>> let e1: Equatable = 1 // T is Int, the default is Self
>>>>> let e2: Equatable = 2 // T is Int, the default is Self
>>>>> if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>
>>>>>
>>>>> Everything I am suggesting is done in other languages and from my personal experience works out better.
>>>>>
>>>>>
>>>>> -- Howard.
>>>>>
>>>>> On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>>>> Howard, take a look at the generics manifesto section on generic protocols:
>>>>>
>>>>> https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md
>>>>>
>>>>> It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.
>>>>>
>>>>> On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution at swift.org> wrote:
>>>>>> review of SE-0174 "Change `filter` to return an associated type"
>>>>>>
>>>>>> • What is your evaluation of the proposal?
>>>>> I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:
>>>>>
>>>>> 1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
>>>>> 2. Allow Self to accept a generic argument, so that you can write Self<T>
>>>>>
>>>>> With these to, admittedly much more major changes, you can then write:
>>>>>
>>>>> protocol Sequence<T> {
>>>>> func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
>>>>> func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
>>>>> }
>>>>> extension RangeReplaceableCollection {
>>>>> func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
>>>>> var result = Self<T>()
>>>>> for element in self {
>>>>> if try isIncluded(element) {
>>>>> result.append(element)
>>>>> }
>>>>> }
>>>>> return result
>>>>> }
>>>>> func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
>>>>> var result = Self<M>()
>>>>> for element in self {
>>>>> try result.append(mapper(element))
>>>>> }
>>>>> return result
>>>>> }
>>>>> }
>>>>>
>>>>> Which I think both reads better and is more powerful since it allows map to be written also.
>>>>>
>>>>>> • Is the problem being addressed significant enough to warrant a change to Swift?
>>>>> Yes, return an array is a real pain
>>>>>
>>>>>> • Does this proposal fit well with the feel and direction of Swift?
>>>>> Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.
>>>>>
>>>>>> • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
>>>>> Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.
>>>>>
>>>>>> • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
>>>>> Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.
>>>>>
>>>>> -- Howard.
>>>>>
>>>>> On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor at apple.com> wrote:
>>>>>
>>>>>> Hello Swift community,
>>>>>>
>>>>>> The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:
>>>>>>
>>>>>> https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
>>>>>> Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at
>>>>>>
>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>>> or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:
>>>>>>
>>>>>> Proposal link:
>>>>>>
>>>>>> https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
>>>>>> Reply text
>>>>>> Other replies
>>>>>> What goes into a review?
>>>>>>
>>>>>> The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:
>>>>>>
>>>>>> • What is your evaluation of the proposal?
>>>>>> • Is the problem being addressed significant enough to warrant a change to Swift?
>>>>>> • Does this proposal fit well with the feel and direction of Swift?
>>>>>> • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
>>>>>> • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
>>>>>> More information about the Swift evolution process is available at
>>>>>>
>>>>>> https://github.com/apple/swift-evolution/blob/master/process.md
>>>>>> Thank you,
>>>>>>
>>>>>> -Doug Gregor
>>>>>>
>>>>>> Review Manager
>>>>>>
>>>>>> _______________________________________________
>>>>>> swift-evolution-announce mailing list
>>>>>> swift-evolution-announce at swift.org
>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution-announce
>>>>> _______________________________________________
>>>>> swift-evolution mailing list
>>>>> swift-evolution at swift.org
>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>>
>>>>> _______________________________________________
>>>>> swift-evolution mailing list
>>>>> swift-evolution at swift.org
>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
More information about the swift-evolution
mailing list