[swift-evolution] [Idea] Generic associated types
John McCall
rjmccall at apple.com
Tue Mar 14 13:47:32 CDT 2017
> On Mar 14, 2017, at 2:42 PM, Karl Wagner <razielim at gmail.com> wrote:
> I was thinking of making a new thread for this, but since this discussion’s basically over I thought I’d ask a quick question about generic closures.
>
> Basically, I would like to express something like the following (without type-erasing via AnyCollection):
>
> func vendsGenericBytes(callback: <T: Collection>(_: T) -> Void where T.Iterator.Element == UInt8) {
> callback([1, 2, 3, 4, 5])
> callback(DispatchData.empty)
> callback(UnsafeRawBufferPointer(start: nil, count: 0))
> }
>
> // type of vendsGenericBytes is "(<T>(T)->Void where ...)->Void"
>
> func takesGenericBytes<T: Collection>(_: T) where T.Iterator.Element == UInt8 {
> // ...
> }
> // type of takesGenericBytes is: "<T>(T)->Void where …”
> vendsGenericBytes(takesGenericBytes)
>
>
> vendsGenericBytes {
> if let idx = index(where: { $0 == 0x04 }) {
> //...
> }
> }
>
>
> For functions and closures, you sometimes want to refer to them as an unbound generic because you intend to invoke them with a multitude of types within the same scope, and you want to invoke a specialised function/closure for each type of argument.
>
> For example, vendsGenericBytes might decide to call the callback with a ReversedCollection (if the bytes are coming in reverse), or a LazyMapCollection, FilterCollection or any other kind of collection of UInt8s. You can write a generic function which handles that, but you can’t use it as a callback.
>
> Would this kind of thing ever be supported in Swift? If so, could I (or somebody) add it to the generics manifesto so we don't forget?
"Higher-rank polymorphism". You can already express something similar via generic methods, e.g.
protocol GenericBytesFunction {
func invoke<T: Collection>(collection: T) where T.Iterator.Element == UInt8
}
You just don't get the convenience of using a closure.
I'd be interested in supporting higher-rank generics directly, but it's one of those "you have to be very cautious" things because (IIRC) type reconstruction is not fully decidable.
John.
>
> - Karl
>
>> On 13 Mar 2017, at 17:50, John McCall <rjmccall at apple.com <mailto:rjmccall at apple.com>> wrote:
>>
>>> On Mar 12, 2017, at 5:00 PM, Matthew Johnson via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>>> On Mar 12, 2017, at 3:23 PM, Karl Wagner <razielim at gmail.com <mailto:razielim at gmail.com>> wrote:
>>>>
>>>>
>>>>> On 12 Mar 2017, at 14:32, Matthew Johnson <matthew at anandabits.com <mailto:matthew at anandabits.com>> wrote:
>>>>>
>>>>> This is a really important feature IMO, but as others have pointed out it basically amounts to higher-kinded types. I would love to be wrong about this but I am reasonably sure this is out of scope for Swift 4 (otherwise I would be working on a proposal already).
>>>>>
>>>>> Sent from my iPad
>>>>>
>>>>
>>>> I’m not an expert on this stuff, but are they still higher-kinded types if we don’t express a relationship between Self and the associated type? I don’t think it’s quite the same conceptual leap as HKT.
>>>
>>> I’m no expert either but it sure seems to me like it enables the things usually discussed in the context of higher-kinder types. Maybe someone from the core team can comment on whether there is a meaningful difference
>>
>> Yes, it's a way of getting some of the behavior of higher-kinded types. Kind of a well-known trick in a number of languages. It's significantly simpler to handle in the type system because the higher-kinded entities stay "second class" — you don't necessarily have to deal with, say, higher-kinded type variables in the constraint solver or in type inference. Of course, that limits some of the code you can write, or at least the simplicity of that code.
>>
>>> and whether this is something that could fit into Swift 4.
>>
>> No.
>>
>> John.
>>
>>>
>>>>
>>>> Consider that every associated type must be backed by a typealias (explicit or inferred) in the conforming type. We can already have generic typealiases. This would be a more targeted thing which required those associatedtype-implementing-typealiases to contain generic parameters. It would also extend the constraints from SE-0142 to allow constraints to refer to those parameters and bind them to other associated types.
>>>>
>>>> The workaround is basically to erase and dynamic-cast your way out:
>>>
>>> Yes, there are workarounds, none of which are desirable.
>>>
>>> I ran into a case last year where there was a significant performance impact caused by the need to perform type erasure as a workaround. The type erasing wrapper required an allocation and type information that could have been used by the optimizer was lost. This was frustrating and convinced me that we definitely need HKT in Swift eventually. There are very useful generic libraries that cannot be implemented efficiently without them.
>>>
>>>
>>>>
>>>> //NOTE: dynamic type of ScanPromise.Result *must* be same as closure result. No static enforcement though :(
>>>>
>>>> extension Scanner where ScanPromise.Result == Any? {
>>>> func scan<T>(from f: Offset, until u: (Offset, Item) -> T?) -> T? {
>>>> return withoutActuallyEscaping(u) { _u -> T? in
>>>> return promiseScan(from: f, until: _u).await() as? T // downcast from Any? to T?
>>>> }
>>>> }
>>>> }
>>>>
>>>> class MyPromise<R>: Promise {
>>>> typealias Result = R?
>>>> let offset: Offset
>>>> let block: (Offset, Item) -> R?
>>>> }
>>>>
>>>> class MyScanner: Scanner {
>>>> typealias ScanPromise = MyPromise<Any> // want this to be “typealias ScanPromise<X> = MyPromise<X>"
>>>>
>>>> func promiseScan<T>(from: Offset, until: @escaping (Offset, Item) -> T?) -> ScanPromise {
>>>> return MyPromise(offset: from, block: until) // upcast from T? to Any?
>>>> }
>>>> }
>>>>
>>>> - Karl
>>>>
>>>>> On Mar 11, 2017, at 11:49 PM, Karl Wagner via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>>>>
>>>>>> I have a model like this:
>>>>>>
>>>>>> protocol Promise {
>>>>>> associatedtype Result
>>>>>> }
>>>>>>
>>>>>> protocol Scanner {
>>>>>> associatedtype ScanPromise: Promise
>>>>>>
>>>>>> func promiseScan<T>(from: Offset, until: (Offset, Item) -> T?) -> ScanPromise // where Result == T?
>>>>>> }
>>>>>>
>>>>>> The thing that I’m trying to express is: whichever type implements the associated type ‘ScanPromise’ must be generic, and that parameter must be its result (i.e. something it got as a result of calling the “until” closure).
>>>>>>
>>>>>> Even with SE-0142, this kind of constraint would not be possible. What I would like to write is something like this:
>>>>>>
>>>>>> protocol Promise {
>>>>>> associatedtype Result
>>>>>> }
>>>>>>
>>>>>> protocol Scanner {
>>>>>> associatedtype ScanPromise<T>: Promise // now generic. [SE-0142]: where Result == T
>>>>>>
>>>>>> func promiseScan<T>(from: Offset, until: (Offset, Item) -> T?) -> ScanPromise<T>
>>>>>> }
>>>>>>
>>>>>> Thoughts?
>>>>>>
>>>>>> - Karl
>>>>>> _______________________________________________
>>>>>> swift-evolution mailing list
>>>>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>>>>
>>>
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170314/8d4a2661/attachment.html>
More information about the swift-evolution
mailing list