[swift-evolution] [swift-evolution-announce] [Review] SE-0174: Change `filter` to return an associated type
Howard Lovatt
howard.lovatt at gmail.com
Wed May 3 03:57:46 CDT 2017
@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
>>>>
>>>> <https://github.com/apple/swift-evolution#what-goes-into-a-review-1>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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170503/0215bda2/attachment.html>
More information about the swift-evolution
mailing list