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

Douglas Gregor dgregor at apple.com
Fri Sep 30 18:10:38 CDT 2016

> 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?

>> 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.

> 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”.

>>>> 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.

>>>> 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.

>>>> 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.

	- Doug

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

More information about the swift-evolution mailing list