Ergonomics: generic types conforming "in more than one way"

Evolution Discussion
59

I don't know what you have in mind, but I can spell out what I know is implementable (relatively) efficiently and where I see things as becoming problematic. Let's revisit your original example. The parts relevant to my examples are these:

// (A) Definition
protocol P {
    static var isEquatable: Bool { get }
}

// (B) Default implementation
extension P {
    static var isEquatable: Bool { false }
}

// (C) More-constrained default implementation
extension P where Self : Equatable {
    static var isEquatable: Bool { true }
}

// (D) Conformance
extension Array : P {}

What we get today is that, at the point (D) where Array is stated to conform to P, the compiler looks at both implementations (B) and (C). For this case, (C) is not applicable because the Array<Element> for an arbitrary Element is not guaranteed to be Equatable. Therefore, the compiler chooses (B) and we get the surprising behavior.

Now, we could imagine a different, conditional conformance of Array to P that only works for Element types that are themselves Equatable (and, thus, the Array is Equatable). Let's call it D' because I've always wanted to be a mathematician:

// (D') Alternative, conditional conformance
extension Array : P where Element: Equatable {}

Now, because we know that Array<Element> will be Equatable, both of the isEquatable implementations (B) and (C) are usable (their requirements are met), so we have to make a choice---should it be (B) or should it be (C)? Well, (C) is more specialized, i.e., it has additional requirements on top of (B), and therefore is assumed to be better (faster, more accurate, etc.), so we pick that one. That's what happens, as expected.

Now, what we want is to get (C) for when the Element type happens to be Equatable, and (B) when it is not Equatable. By looking at (B) and (C), we can encode a decision procedure here, and it's pretty easy. At the point where we know the Element type---whether it happens in the compiler's type checker, optimizer, or at runtime, we'd prefer that it not matter, as @Joe_Groff points out---we want to effectively do this check:

  if Element is Equatable {
    use implementation (C)
  } else {
    use implementation (B)
  }

I believe that's completely implementable. The compiler, seeing both (B) and (C), can emit that if/else block to determine which function to use for the witness of the conformance, so conformance (D) has the behavior we want.

But, there are limitations, so let's see where the model breaks.

First of all, there can be ambiguities. Let's extend the example with another protocol Q and another implementation of isEquatable:

protocol Q { }

// (E) Another constrained implementation
extension P where Self : Q {
    static var isEquatable: Bool { true }
}

// (F) Array conditionally conforms to Q
extension Array: Q where Element: Q { }

Now, conformance of Array to P has three potential implementations of isEquatable to consider: (B), (C), and (E). (C) is more specialized than (B), and (E) is more specialized than (B), but (C) and (E) can't really be ordered. So if we have a type like this that conforms to both Equatable and Q:

struct X: Equatable, Q { }

What happens for the conformance of Array<X> to P? All of (B), (C), and (E) apply, so I think this must be an error. If we model this case today by extending the conformance of Array to P with both conditions on its Element type, like this:

// (D'') conformance with an ambiguity
extension Array : P where Element: Equatable, Element: Q {}

we end up getting an ambiguity error:

t2.swift:2:16: note: multiple matching properties named 'isEquatable' with type 'Bool'
    static var isEquatable: Bool { get }
               ^
t2.swift:6:16: note: candidate exactly matches
    static var isEquatable: Bool { false }
               ^
t2.swift:10:16: note: candidate exactly matches
    static var isEquatable: Bool { true }
               ^
t2.swift:19:16: note: candidate exactly matches
    static var isEquatable: Bool { true }
               ^

I consider that to be the correct behavior here, because there is no "best" answer. I would be fine with the original conformance of Array to P (marked (D) at the beginning) becoming ambiguous and triggering an error at compile time. I think it would be a major problem with the design if this ambiguity could happen at run time.

To be clear, the fix here is not too complicated, and could possibly even be suggested by the compiler. You effectively need to provide another constrained implementation that is more specialized than both (C) and (E):

// (G) Yet another constrained implementation, better than the others!
extension P where Self : Equatable, Self: Q {
    static var isEquatable: Bool { true }
}

That fixes the problem, and we still have a (relatively simple) decision algorithm:

switch (Element is Equatable, Element is Q) {
  case (true, true): use implementation (G)
  case (true, false): use implementation (C)
  case (false, true): use implementation (E)
  case (false, false): use implementation (B)
}

This depends on having the complete set of potential witnesses visible at the point where the conformance is declared. If we were to move the definition of the protocol Q and the corresponding protocol P extension implementation (E) into another module, we'd lose the ability to select implementation (E) because it's not visible to us at build time. I consider that a good thing, but I could certainly imagine it causing some confusion when factoring code into a different module changes the overall behavior. And it's not something that I consider fixable, because even if you take the performance hit of doing a runtime lookup to find all of (B), (C), and (E), you've lost the ability to ensure (prior to runtime) that there can never be an ambiguity.

Doug

11 Likes