[swift-evolution] [Review] SE-0143: Conditional Conformances

[Dave Abrahams]

on Fri Sep 30 2016, Douglas Gregor <dgregor-AT-apple.com> wrote:

>> On Sep 30, 2016, at 1:41 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>> 
>> 
>> on Fri Sep 30 2016, Douglas Gregor <dgregor-AT-apple.com> wrote:
>> 
>
>>>> On Sep 29, 2016, at 10:16 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>> 
>>>> 
>>>> Obviously I'm a huge +1 for this feature, but I have some concerns and
>>>> questions about the particulars.
>>> 
>>>> 
>>>> on Wed Sep 28 2016, Joe Groff <swift-evolution at swift.org> wrote:
>>>> 
>>>>> Conditional conformances also have a run-time aspect, because a
>>>>> dynamic check for a protocol conformance might rely on the evaluation
>>>>> of the extra requirements needed to successfully use a conditional
>>>>> conformance. For example:
>>>>> 
>>>>> ```swift
>>>>> protocol P {
>>>>> func doSomething()
>>>>> }
>>>>> 
>>>>> struct S: P {
>>>>> func doSomething() { print("S") }
>>>>> }
>>>>> 
>>>>> // Array conforms to P if it's element type conforms to P
>>>>> extension Array: P where Element: P {
>>>>> func doSomething() {
>>>>>   for value in self {
>>>>>     value.doSomething()
>>>>>   }
>>>>> }
>>>>> }
>>>>> 
>>>>> // Dynamically query and use conformance to P.
>>>>> func doSomethingIfP(_ value: Any) {
>>>>> if let p = value as? P {
>>>>>   p.doSomething()
>>>>> } else {
>>>>>   print("Not a P")
>>>>> }
>>>>> }
>>>>> 
>>>>> doSomethingIfP([S(), S(), S()]) // prints "S" three times
>>>>> doSomethingIfP([1, 2, 3])       // prints "Not a P"
>>>>> ```
>>>>> 
>>>>> The `if-let` in `doSomethingIfP(_:)` dynamically queries whether the
>>>>> type stored in `value` conforms to the protocol `P`. In the case of an
>>>>> `Array`, that conformance is conditional, which requires another
>>>>> dynamic lookup to determine whether the element type conforms to `P`:
>>>>> in the first call to `doSomethingIfP(_:)`, the lookup finds the
>>>>> conformance of `S` to `P`. In the second case, there is no conformance
>>>>> of `Int` to `P`, so the conditional conformance cannot be used. The
>>>>> desire for this dynamic behavior motivates some of the design
>>>>> decisions in this proposal.
>>>> 
>>>> Whether a dynamic evaluation is required at this point seems to depend
>>>> on how you represent conformance.  Saying “Array conforms conditionally”
>>>> treats Array as a type, but it might be simpler to treat Array as a
>>>> family of concrete types.
>>> 
>>> This is already the case in the runtime; we specialize the metadata for generic types.
>>> 
>>>> I always envisined it this way: at the moment
>>>> a module using the concrete type Array<Foo> comes together with an
>>>> extension (either in that module or in another) that makes Array<T>
>>>> conform to Equatable depending on properties of T, that extension is
>>>> evaluated and Array<Foo> is marked as conforming or not.
>>> 
>>> If the protocol, Array, and Foo all come from different modules, this
>>> process happens at runtime. Yes, the optimizer could specialize the
>>> conformance at compile time in many common cases, but you can’t see
>>> every possible specialization without whole-program analysis, so it
>>> doesn’t change the model.
>>> 
>>>> Then asking
>>>> about a type's conformance is always a simple thing.  But I suppose
>>>> which approach wins is dependent on many factors, and the other way can
>>>> be thought of as adding lazy evaluation to the basic model, so if this
>>>> adds nothing to your thinking please excuse the static.
>>> 
>>> Without whole-program information, you need to have the runtime
>>> capability (or disallow the use of this feature in runtime
>>> queries). Static specialization can be considered an optimization to
>>> this model.
>> 
>> I know it has to happen at runtime in the worst case.  I was suggesting
>> it could happen at load time rather than as a complication of the
>> dynamic cast machinery.  In principle all the load-time information can
>> be usefully cached on-disk.
>
> You can’t compute it at load time, either. There might be sane cases, but here’s a fun one involving existential metatypes:
>
> 	protocol P { 
> 	  static func makeArray() -> [Self] { return [self] }
> 	}
>
> 	extension Int: P { }
>
> 	extension Array: P where Element: P { }
>
> 	func thwartLoadTime(kind: String) {
> 		let meta: P.Type
> 		if kind == “Int” { meta = Int.self }
> 		else { meta = String.self }
>
> 		let array: [Any] = meta.makeArray() // Sweet, now I have an array of … something.
> 		print(array is P)         // true or false?
> 	}

And some people think Swift isn't dynamic enough?! ;-)

>>> But, yes, you’re right that (e.g.) overloading across
>>> differently-constrained extensions and protocol extensions means
>>> dealing with divergent interfaces… and it’s been a problem for type
>>> checker and humans both.
>> 
>> But that's not going away, so what's the point in bringing it up?
>
> I don’t want us to introduce new features that make the problem worse, which allowing overlapping conformances would.
>
>>>> 
>>>> Doesn't this break, then?
>>>> 
>>>>  protocol Equatable { ... }
>>>>  protocol Comparable : Equatable { ... }
>>>>  protocol Hashable : Equatable { ... }
>>>> 
>>>>  extension Array : Comparable where T : Comparable {}
>>>>  extension Array : Hashable where T : Hashable {}
>>>> 
>>>> I hope not, beause personally, I don't see how breaking the ability to
>>>> do things like that could be acceptable.  The protocols such as
>>>> Equatable et al. that form the components of “Regular” types are *going*
>>>> to be inherited by many other protocols, so this isn't just going to
>>>> happen in a nice localized context, either.
>>> 
>>> The above is ill-formed as written, because we can’t associate
>>> ‘Equatable’ with either conformance without excluding the other—and
>>> putting it in both places would create an overlapping conformance. 
>> 
>> (like we said in your office) I don't think the key issue is the
>> association of conformances here, but where the Equatable *requirement*
>> is getting satisfied.
>
> Yes, that’s true in the user-facing model.
>
>> 
>>> 
>>> So, the fix is to explicitly spell out the Equatable conformance:
>>> 
>>> 	extension Array: Equatable where T: Equatable { } okay! this is the Equatable conformance for Array
>> 
>> This isn't a terrible answer.
>
> I think it’s actually a rather good answer: this implementation of
> Equatable is more general/more reusable than either the Comparable or
> Hashable versions.

Excellent point; that changes my view of this quite a bit, actually.

>> If we could know that no extensions related to the Comparable or
>> Hashable conformance were supplying the Equatable requirement, I think
>> we could allow it to be omitted, though.  I bet you're going to tell me
>> we can't know that, but isn't it enough to use the information we have
>> statically at the time we see the above extensions?
>
> The question you would have to answer is, effectively, “is there a
> single == to satisfy Equatable that works for all of the constrained
> extensions?” If you have find declarations to satisfy all of the
> requirements of the protocol in question, such that each of the
> constrained extensions can use that one set of declarations to satisfy
> the same protocol, then maybe it’s plausible… but the result won’t
> necessarily be as general as “extension Array: Equatable where T:
> Equatable”.
>
> It’s also another “global” solver, because it needs to satisfy *all*
> of the requirements of the protocol and *all* of the conditional
> conformances that imply conformance to that protocol simultaneously to
> come up with a correct answer. For example, we might have several
> implementations of == that might work:
>
> extension RangeReplaceableCollection where Element: Equatable {
> 	static func ==(lhs: Self, rhs: Self) -> Bool { /*use ==*/ }
> }
>
> extension RangeReplaceableCollection where Element: Comparable {
> 	static func ==(lhs: Self, rhs: Self) -> Bool { /*use < and > because we can */ }
> }
>
> The second == is the better one for "extension Array : Comparable
> where T : Comparable" but is inapplicable for "extension Array :
> Hashable where T : Hashable”, so we have to choose the first…
>
> That falls apart if the overlapping conditional conformances are in
> different modules, of course, because if we only see the "extension
> Array : Comparable where T : Comparable”, we’ll pick the second ‘==‘…
> and whoever comes up with "extension Array : Hashable where T :
> Hashable” in another module will get a failure. The explicit solution
> of requiring "extension Array: Equatable where T: Equatable” addresses
> this problem by getting the user involved in creating the appropriate
> generalization.
>
>> 
>>> Note that this conformance is less-specialized than both the “Array:
>>> Comparable” and “Array: Hashable” conformances, which is important:
>>> one cannot satisfy “Hashable” (or “Comparable”) without satisfying
>>> “Equatable”, so that Equatable conformance has to exist and has to be
>>> usable from the Hashable and Comparable conformances.
>> 
>> Suppose I had written:
>> 
>> extension Array where T: Equatable {
>>    static func ==(x: Array, y: Array) -> Bool { ... }
>> }
>> 
>> Why isn't that enough to allow me to avoid writing the Equatable
>> conformance?  I'm not asking because I think it's important to avoid it
>> once I've written all of the above.  I'm just trying to probe/understand
>> the model.
>
> If you allowed the above to fix the problem, the answer to the
> question “when does Array<T>” conform to Equatable?” is still “if T is
> Hashable or T is Comparable”, which isn’t what we want. We want “it’s
> Equatable”.

Yep.

>>>>> However, in cases where there is a reasonable ordering between the two
>>>>> constrained extensions (i.e., one is more specialized than the other),
>>>>> the less specialized constrained extension should "win" the implied
>>>>> conformance. 
>>>> 
>>>> “Less specialized wins” is surprising at the very least!  I've only ever
>>>> seen the opposite rule (e.g. in overload resolution).  What's the
>>>> rationale for this approach?
>>> 
>>> You need the most-general implementation so that conformance can be
>>> used by other constrained extensions, the way the ‘Array: Equatable’
>>> gets used by ‘Array: Hashable’ and ‘Array: Comparable’.
>> 
>> Are you sure we don't want the most specialized common ancestor of all
>> the constrained extensions?
>
> Yes, that’s correct.

We do or don't want that?

>>>>> Continuing the example from above:
>>>>> 
>>>>> ```swift
>>>>> protocol S: R { }
>>>>> 
>>>>> struct X5<T> { }
>>>>> 
>>>>> extension X5: S where T: S { }
>>>>> 
>>>>> // This last extension "wins" the implied conformance to P, because
>>>>> // the extension where "T: R" is less specialized than the one
>>>>> // where "T: S".
>>>>> extension X5: R where T: R { }
>>>>> ```
>>>>> 
>>>>> Thus, the rule for placing implied conformances is to pick the *least
>>>>> specialized* extension that implies the conformance. If there is more
>>>>> than one such extension, then either:
>>>>> 
>>>>> 1. All such extensions are not constrained extensions (i.e., they have
>>>>> no requirements beyond what the type requires), in which case Swift
>>>>> can continue to choose arbitrarily among the extensions, 
>>>> 
>>>> Surely that can't be the right long-term design?
>>> 
>>> When all of the extensions are unconstrained, it still doesn’t matter
>>> to the user where the conformance goes. In truth, this rule extends to
>>> groups of extensions that have the *same* constraints—it doesn’t
>>> matter which one we pick.
>> 
>> Seems to me it does if they define different semantics!  What am I
>> missing?
>
> If they have the same constraints, they’ll have the same
> overload-resolution behavior when picking declarations to satisfy
> requirements.

Ya lost me here.

>> 
>>>>> or
>>>>> 
>>>>> 2. All such extensions are constrained extensions, in which case the
>>>>> program is ill-formed due to the ambiguity. The developer can
>>>>> explicitly specify conformance to the protocol to disambiguate.
>>>> 
>>>> I'm really concerned about the understandability of this model.  It
>>>> doesn't seem rational or consistent with other choices in the
>>>> language. Now maybe I'm missing something, but in that case I think you
>>>> haven't given a clear/precise enough description of the rules.  But the
>>>> next section looks like it might clear things up for me...
>>>> 
>>>> ...(I'm sorry to say it didn’t)
>>> 
>>> While the exposition can be improved somewhat, placement of implied
>>> conformances is fairly tricky and low-level. It will surface to the
>>> user in cases where the user writes something like your
>>> Comparable/Hashable example:
>>> 
>>>>  extension Array : Comparable where T : Comparable {}
>>>>  extension Array : Hashable where T : Hashable {}
>>> 
>>> and the compiler needs to complain about the inability to place
>>> ‘Equatable’ in a way that directs the user to the correct answer
>>> without exposing them to the entire chain of reasoning we’re going
>>> through. The diagnostic would need some thought:
>>> 
>>> 	error: ‘Array' requires an explicit conformance to ‘Equatable’
>>> 	due to conflicting implied conformances (from ‘Comparable’ and
>>> 	‘Hashable’)
>> 
>> If we're not making this illegal:
>> 
>>      extension Foo : Comparable { ... }
>>      extension Foo : Hashable { ... }
>>      // extension Foo : Equatable { ... }
>> 
>> I think it's going to be tough for people to understand why the
>> overlapping implied conformances are a problem in the other case.
>
> Given the negative feedback we got when I tried to require this
> before, I don’t think it’s wise to require it except in those cases
> where it is necessary for conditional conformances. And, of course, it
> would be a source-breaking change to go back and require this for
> non-conditional conformances.

I'm not saying we should make the above illegal!  I'm saying we need a
better way to explain why the conditional case doesn't work.

-- 
-Dave