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

[Dave Abrahams]

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.

>>> Note that, for an arbitrary type `T`, there are four potential answers to
>>> the question of whether `SomeWrapper<T>` conforms to `Equatable`:
>>> 
>>> 1. No, it does not conform because `T` is neither `Equatable` nor
>>> `HasIdentity`.
>>> 2. Yes, it conforms via the first extension of `SomeWrapper` because
>>> `T` conforms to `Equatable`.
>>> 3. Yes, it conforms via the second extension of `SomeWrapper` because
>>> `T` conforms to `HasIdentity`.
>>> 4. Ambiguity, because `T` conforms to both `Equatable` and
>>> `HasIdentity`.
>> 
>> Arguably in this case you could say yes it conforms and it doesn't
>> matter which extension you use because there's only one sensible
>> semantics for Equatable.
>
> Sure, we know the semantics of these protocols: === should imply ==.
>
>>  Other protocols are less obvious, though
>> (c.f. Int's conformance to Monoid with +/0 vs */1).
>
> Right.
>
>>> 2. It is no longer possible to uniquely say what is required to make a
>>> generic type conform to a protocol, because there might be several
>>> unrelated possibilities. This makes reasoning about the whole system
>>> more complex, because it admits divergent interfaces for the same
>>> generic type based on their type arguments. 
>> 
>> I'm pretty sure we already have that.  Array<T> would have hashValue if
>> T were hashable, and < if T were comparable, and never the twain shall
>> meet.
>
> The first sentence of (2) meant “to a *given* protocol”, not just “to
> any protocol." 

I don't think I misunderstood that.

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

>>> At its extreme, this invites the kind of cleverness we've seen in the
>>> C++ community with template metaprogramming, which is something Swift
>>> has sought to avoid.
>>> 
>>> 3. All of the disambiguation machinery required at compile time (e.g.,
>>> to determine whether one conditional conformance is more specialized
>>> than another to order them) also needs to implements in the run-time,
>>> as part of the dynamic casting machinery. One must also address the
>>> possibility of ambiguities occurring at run-time. This is both a sharp
>>> increase in the complexity of the system and a potential run-time
>>> performance hazard.
>>> 
>>> For these reasons, this proposal *bans overlapping conformances*
>>> entirely. While the resulting system is less flexible than one that
>>> allowed overlapping conformances, the gain in simplicity in this
>>> potentially-confusing area is well worth the cost. Moreover, this ban
>>> follows with existing Swift rules regarding multiple conformances,
>>> which prohibit the same type from conforming to the same protocol in
>>> two different ways:
>>> 
>>> ```swift
>>> protocol P { }
>>> 
>>> struct S : P { }
>>> extension S : P { } // error: S already conforms to P
>>> ```
>> 
>> I think that's the real answer to “why don't we want to allow it?”
>> 
>> Also, these overlapping constraints are effectively equivalent to “or”
>> constraints, which I think we know are trouble, from a type checking
>> POV.
>
> Right.
>> 
>> [By the way, what is the status of our enforcement of this rule across
>> modules?  I do think that library interop will eventually oblige us to
>> allow different overlapping conformances to appear in separate modules
>> that don't also define the conforming type].
>
> IIRC, we get runtime failures for overlapping conformances across
> modules.

Ick.  Not that I know of a better answer...

>>> ### Implied conditional conformances 
>>> 
>>> Stating conformance to a protocol implicitly states conformances to
>>> any of the protocols that it inherits. This is the case in Swift
>>> today, although most developers likely don't realize the rules it
>>> follows. For example:
>>> 
>>> ```swift
>>> protocol P { }
>>> protocol Q : P { }
>>> protocol R : P { }
>>> 
>>> struct X1 { }
>>> struct X2 { }
>>> struct X3 { }
>>> 
>>> extension X1: Q { }  // implies conformance to P
>>> 
>>> extension X2: Q { }  // would imply conformance to P, but...
>>> extension X2: P { }  // explicitly-stated conformance to P "wins"
>> 
>> What difference does it make which one “wins?”  Even if P had
>> requirements and we were fulfilling them in these extensions, my mental
>> model has always been that they get thrown into a big soup and we let
>> overload resolution sort it out (or declare ambiguity).  So I've never
>> had any idea that “winning” was happening.
>
> In Swift 3, it doesn’t actually matter who “wins”: it’s just an
> implementation detail whose only user-visible effect right now is on
> the near-miss diagnostics for @objc optional requirements. My obtuse
> way of saying this in the proposal was to point out that, with
> conditional conformances, now it *does* matter to the user model,
> because overload resolution would get different answers depending on
> which extension is asking the question.
>
>>> extension X3: Q { }  // implies conformance to P
>>> extension X3: R { }  // also implies conformance to P
>>>                     // one will "win"; which is unspecified
>>> ```
>>> 
>>> With conditional conformances, the question of which extension "wins"
>>> the implied conformance begins to matter, because the extensions might
>>> have different constraints on them. For example:
>>> 
>>> ```swift
>>> struct X4<T> { }
>>> 
>>> extension X4: Q where T: Q { }  // implies conformance to P
>>> extension X4: R where T: R { }  // error: implies overlapping conformance to P
>>> ```
>>> 
>>> Both of these constrained extensions imply a conformance to `P`, but
>>> the actual `P` implied conformances to `P` are overlapping and,
>>> therefore, result in an error.
>> 
>> 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.

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

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?

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

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

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

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

> We can easily produce a Fix-It to create the skeleton of the
> conformance:
>
> 	extension Array: Equatable {
> 	  // … 
> 	}
>
> With some heroics involving, e.g., intersecting the requirements, we might be able to have the Fix-It put in a guess at the ‘where’ clause:
>
> 	extension Array: Equatable where T: Equatable {
> 	  // … 
> 	}
>
> but that might not be necessary.
>
> Now, I do think it’s important to note that neither of the Comparable
> or Hashable conformances we’ve shown actually has what Equatable
> needs—it doesn’t provide an ‘==‘ operator. The problems become clearer
> if we try to write that in both places:
>
> 	extension Array: Comparable where T: Comparable {
> 	  static func ==(lhs: Self, rhs: Self) -> Bool { … }
> 	}
>
> 	extension Array: Comparable where T: Comparable {
> 	  static func ==(lhs: Self, rhs: Self) -> Bool { … }
> 	}
>
> Which ‘==‘ makes Array Equatable? The answer depends on the
> capabilities of ’T’.

Yes, but we weren't discussing that scenario.  Can't we treat these
cases differently?

>>> ### Overloading across constrained extensions
>>> 
>>> One particularly important aspect of the placement rule for implied
>>> conformances is that it affects which declarations are used to satisfy
>>> a particular requirement. For example:
>>> 
>>> 
>>> ```swift
>>> protocol P {
>>>  func f()
>>> }
>>> 
>>> protocol Q: P { }
>>> protocol R: Q { }
>>> 
>>> struct X1<T> { }
>>> 
>>> extension X1: Q where T: Q {           // note: implied conformance to P here
>>>  func f() {
>>>    // #1: basic implementation of 'f()'
>>>  }
>>> }
>>> 
>>> extension X1: R where T: R {
>>>  func f() {
>>>    // #2: superfast implementation of f() using some knowledge of 'R'
>>>  }
>>> }
>>> 
>>> struct X2: R {
>>>  func f() { }
>>> }
>>> 
>>> (X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
>>> X1<X2>().f()        // calls #2, which is preferred by overload resolution
>>> ```
>>> 
>>> Effectively, when satisfying a protocol requirement, one can only
>>> choose from members of the type that are guaranteed to available
>>> within the extension with which the conformance is associated. 
>> 
>> AFAICT, this is the first time that an extension's association to a
>> conformance has ever been visible in the user model, and I am not sure
>> that we want to expose it.  I'm *not* saying we *don't* want to; I'm
>> saying it isn't obvious why we should.
>
> I guess it’s technically been visible in cross-module cases—you can
> see where the implied protocols ended up in the generated interface of
> a compiled module—but nobody noticed or cared, so it’s not really part
> of the model. It might be that we don’t need to make this concept
> visible at all—we just need to tell users when we require them to
> write an explicit conformance. We could even omit the “why” from the
> diagnostic.
>
>> 
>>> In this case, the conformance to `P` is placed on the first extension
>>> of `X1`, so the only `f()` that can be considered is the `f()` within
>>> that extension: the `f()` in the second extension won't necessarily
>>> always be available, because `T` may not conform to `R`. 
>> 
>> I don't see how that's any different from the `f()` in the first
>> extension, which won't necessarily always be available because `T` may
>> not conform to `Q`.
>
> If you’re looking from the point of view of the first extension, T
> does conform to P. That’s the “placement” part: when you say that a
> conformance is placed on a particular extension, it’s requirements are
> satisfied based on the constraints of that extension.

Oh, I see, you're explaining the effects of your chosen semantics, not
justifying them, here.

>> 
>>> Hence, the call that treats an `X1<X2>` as a `P` gets the first
>>> implementation of `X1.f()`. When using the concrete type `X1<X2>`,
>>> where `X2` conforms to `R`, both `X.f()` implementations are
>>> visible... and the second is more specialized.
>>> 
>>> Technically, this issue is no different from surprises where (e.g.) a
>>> member added to a concrete type in a different module won't affect an
>>> existing protocol conformance. 
>> 
>> Let me be absolutely clear that I'm *not* questioning this scheme on
>> those grounds.  I think it makes sense for static and dynamic (or
>> generic) behaviors of the same spelling to differ sometimes, and it's
>> even a useful design tool (c.f. someCollection.lazy).  However, the fact
>> that it arises in some situations and is even sometimes the best design
>> choice doesn't mean that's the way *this* feature should act in *this*
>> situation.  I can't tell whether you're suggesting:
>> 
>> a) type safety demands this behavior
>> b) it's the only behavior that's efficiently implementable
>> c) it's actually the best behavior for the common use cases, or
>> d) something else
>
> It’s weakened forms of (a)-(c):
>
> aa) It’s guaranteed to provide type safety, without the possibility
> for run-time ambiguities or other failures
> 
> bb) It’s efficiently implementable and fits well into the existing
> model. I know of partial solutions that allow some late resolution
> here that are efficiently implementable and can maintain a lack of
> run-time failures, but they require nontrivial engineering effort and
> I don’t know how to generalize them 
>
> cc) I suspect that the vast majority of use cases don’t need this kind
> of late resolution
>
>>> 2. Eliminating repetition: the `lazy` wrappers described in the
>>> [motivation](#motivation) section could be collapsed into a single
>>> wrapper with several conditional conformances. A similar refactoring
>>> could also be applied to the range abstractions and slice types in the
>>> standard library, making the library itself simpler and smaller. All
>>> of these changes are potentially source-breaking and ABI-breaking,
>>> because they would remove types that could be used in Swift 3
>>> code. However, there are mitigations: generic typealiases could
>>> provide source compatibility to Swift 3 clients, and the ABI-breaking
>>> aspect is only relevant if conditional conformances and the standard
>>> library changes they imply aren't part of Swift 4.
>> 
>> I think the description “eliminating repetition” does a disservice to
>> the actual impact of this feature.  It will result in a massive decrease
>> in API surface area, which simplifies the implementation of the library,
>> yes, but also makes it far more accessible to users.
>
> Okay, fair point.
>
>> 
>>> Aside from the standard library, conditional conformances have an
>>> impact on the Swift runtime, which will require specific support to
>>> handle dynamic casting. If that runtime support is not available once
>>> ABI stability has been declared, then introducing conditional
>>> conformances in a later language version either means the feature
>>> cannot be deployed backward or that it would provide only more
>>> limited, static behavior when used on older runtimes. 
>> 
>> It would also mean carrying forward all that implementation and API
>> complexity for the forseeable future.
>
> Yup.
>
>> 
>>> Hence, there is significant motivation for doing this feature as part
>>> of Swift 4. Even if we waited to introduce conditional conformances,
>>> we would want to include a hook in the runtime to allow them to be
>>> implemented later, to avoid future backward-compatibility issues.
>>> 
>>> ## Effect on Resilience
>>> 
>>> One of the primary goals of Swift 4 is resilience, which allows
>>> libraries to evolve without breaking binary compatibility with the
>>> applications that use them. While the specific details of the impact
>>> of conditional conformances on resilience will be captured in a
>>> more-complete proposal on resilience, possible rules are summarized
>>> here:
>>> 
>>> * A conditional conformance cannot be removed in the new version of a
>>> library, because existing clients might depend on it.
>> 
>> I think that applies to all conformances.
>
> Yes, it does.
>
>> 
>>> * A conditional conformance can be added in a new version of a
>>> library, roughly following the rules described in the [library
>>> evolution
>>> document](https://github.com/apple/swift/blob/master/docs/LibraryEvolution.rst#new-conformances). The
>>> conformance itself will need to be annotated with the version in which
>>> it was introduced.
>> 
>> Presumably this is an ABI-preserving but potentially source-breaking
>> change, because of the implied conformance ambiguity issues you
>> mentioned earlier... and because of changing overload resolution, etc.?
>
> Yeah, the issue here is that the conditional conformance would overlap
> existing concrete conformances, so you would need to remove those
> concrete conformances… except when using an old version of the
> library.
>
>>> * A conditional conformance can be *generalized* in a new version of
>>> the library, i.e., it can be effectively replaced by a (possibly
>>> conditional) conformance in a new version of the library that is less
>>> specialized than the conditional conformance in the older version of
>>> the library. For example.
>>> 
>>>  ```swift
>>>  public struct X<T> { }
>>> 
>>>  // Conformance in version 1.0
>>>  public extension X: Sequence where T: Collection { ... }
>>> 
>>>  // Can be replaced by this less-specialized conformance in version 1.1
>>>  public extension X: Sequence where T: Sequence { ... }
>>>  ```
>>> 
>>>  Such conformances would likely need some kind of annotation.
>> 
>> Ditto?
>
> Yup.
>
>> 
>>> ## Alternatives considered
>>> 
>>> The most common request related to conditional conformances is to
>>> allow a (constrained) protocol extension to declare conformance to
>>> a protocol. For example:
>>> 
>>> ```swift
>>> extension Collection: Equatable where Iterator.Element: Equatable {
>>>  static func ==(lhs: Self, rhs: Self) -> Bool {
>>>    // ...
>>>  }
>>> }
>>> ```
>>> 
>>> This protocol extension will make any `Collection` of `Equatable`
>>> elements `Equatable`, which is a powerful feature that could be put to
>>> good use. Introducing conditional conformances for protocol extensions
>>> would exacerbate the problem of overlapping conformances, because it
>>> would be unreasonable to say that the existence of the above protocol
>>> extension means that no type that conforms to `Collection` could
>>> declare its own conformance to `Equatable`, conditional or otherwise.
>> 
>> ...which is part of why I think we need better rules about overlap than
>> the ones proposed here.  I anticipate a repetition of the pattern we
>> have today, where Array provides == and != but can't conform to
>> Equatable, just on a different level.  That has always felt wrong.  Now
>> we'll do the same thing with Collection, so *at least* you don't have to
>> write the == operator when you write the conditional conformance.
>
> Yes, there will be repetition. To be concrete, one would end up with this:
>
> extension RangeReplaceableCollection where Iterator.Element: Equatable {
>   static func ==(lhs: Self, rhs: Self) -> Bool {
>     // implement == efficiently...
>   }
> }
>
> but each type that forms to Collection will still have to state its
> conformance to Equatable, even though it will often be empty, e.g.,
>
> 	extension Array: Equatable where Element: Equatable { }
>
> We are still in a better place than we were in Swift 3, where there
> was *no* way to make Array conform to Equatable, but in these cases
> it’ll still feel boilerplate-y.

Yes, a step forward is a step forward.

Thanks!

-- 
-Dave