[swift-evolution] [Manifesto] Completing Generics

[David Smith]

> On Mar 2, 2016, at 8:19 PM, Joe Groff <jgroff at apple.com> wrote:
> 
>> 
>> On Mar 2, 2016, at 6:20 PM, David Smith via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>>> 
>>> On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>> 
>>> Hi all,
>>> 
>>> 
>>> Existentials
>>> 
>>> Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.
>>> 
>>> *Generalized existentials
>>> 
>>> The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:
>>> 
>>> protocol IteratorProtocol {
>>>   associatedtype Element
>>>   mutating func next() -> Element?
>>> }
>>> 
>>> let it: IteratorProtocol = …
>>> it.next()   // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element
>>> 
>>> Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):
>>> 
>>> let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]
>>> 
>>> The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):
>>> 
>>> typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
>>> let strings: AnySequence<String> = [“a”, “b”, “c”]
>>> 
>>> 
>>> Opening existentials
>>> 
>>> Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:
>>> 
>>> protocol Equatable {
>>>   func ==(lhs: Self, rhs: Self) -> Bool
>>>   func !=(lhs: Self, rhs: Self) -> Bool
>>> }
>>> 
>>> let e1: Equatable = …
>>> let e2: Equatable = …
>>> if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type
>>> 
>>> One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:
>>> 
>>> 	 
>>> if let storedInE1 = e1 openas T {     // T is a the type of storedInE1, a copy of the value stored in e1
>>>   if let storedInE2 = e2 as? T {      // is e2 also a T?
>>>     if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
>>>   }
>>> }
>>> 
>>> Thoughts?
>>> 
>>> 	- Doug
>>> 
>> 
>> Thanks for sending this out! A lot of the stuff here looks amazingly useful, and I'm excited to see it being discussed.
>> 
>> The choice of Equatable as an example for opening existentials is an interesting one here, because it's one of the few cases I can think of where differing dynamic types is actually fully defined: they're not equal. In ObjC we express that by starting every -isEqual: implementation with if (![other isKindOfClass:[self class]]) { return NO; }, which while clunky and easy to forget, does neatly express the desired semantics with no burden at the callsite. 
>> 
>> My first thought for how to express that in Swift was "ok, provide an == for (Any, Any) that just always says false", but that would defeat the ability to say something just doesn't make sense to compare with ==, which is a nice feature and prevents bugs.
>> 
>> Next thought for expressing it cleanly was:
>> 
>> protocol Equatable {
>>     func ==(lhs: Self, rhs: Self) -> Bool
>>     func !=(lhs: Self, rhs: Self) -> Bool
>>     func ==(lhs: Self, rhs: !Self) -> Bool { return false }
>>     func !=(lhs: Self, rhs: !Self) -> Bool { return true }
>> }
>> 
>> and I guess another equivalent way of writing it that doesn't require a new syntactic construct would be:
>> 
>> protocol Equatable {
>>     func ==(lhs: Self, rhs: Self) -> Bool
>>     func !=(lhs: Self, rhs: Self) -> Bool
>>     func ==<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return false }
>>     func !=<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return true }
>> }
> 
> My thinking is that this could be expressed as extending the existential type to conform to the protocol:
> 
> extension Any<Equatable>: Equatable {
>   func ==(lhs: Any<Equatable>, rhs: Any<Equatable>) -> Bool {
>     if let lrhs = rhs as? lhs.Self {
>       return lhs == rlhs
>     }
>     return false
>   }
> }

Oh wow, I did not put 2 and 2 together here and get "you can extend existentials of something without extending that thing itself". That is *so pretty*. Hesitation withdrawn!

	David

> 
>> which would make this idea a minor extension of the "Concrete Same-Type Requirements" section.
>> 
>> However, this still has a similar flaw to the first idea I had, which is that it introduces a valid == operator for things that never make sense to compare, when what we actually want is one that will only be accepted if there's insufficient information to determine whether it's valid (i.e. Equatable existentials). I suppose there's a relatively obvious syntax to express that directly:
>> 
>> protocol Equatable {
>>     func ==(lhs: Self, rhs: Self) -> Bool
>>     func !=(lhs: Self, rhs: Self) -> Bool
>>     func ==<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return false }
>>     func !=<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return true }
>> }
>> 
>> Where "?=" would be read as "might be equal to". It's not clear to me if this sort of "default implementation for non-matching existentials" concept is applicable beyond Equatable though, and if not it seems like a lot of machinery to add for one case.
> 
> The "introducing an == operator for things that never make sense to compare" problem could be avoided by a type system rule that, when we bind a generic parameter from multiple value parameter, we don't upconvert to a type that neither parameter statically has. Since `==` is `<Self> (Self, Self) -> Bool`, that would prevent us from picking `Self == Any<Equatable>` if you called `Int == Float`, but would allow it if one or the other parameter was already Any<Equatable>.
> 
> -Joe

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160302/8f9539b2/attachment.html>