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

**URL:** <https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589>\
**Category:** Discussion\
**Tags:** generics\
**Created:** [March 17, 2020, 3:46am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589 "2020-03-17T03:46:02Z")\
**Posts on this page:** 20\
**Page:** 3

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [April 6, 2020, 9:54pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/41 "2020-04-06T21:54:34Z")

</div>

> [@dabrahams](#):
>
> Could you show an example of what you mean here, Joe? It seems entirely reasonable to me that, to keep the last assertion from firing in my example, the extensions of `P` and the conditional conformance of `Array` to `Equatable` would all have to be visible in the scope where `Array<Int>` was bound to a `P` -constrained generic parameter, i.e. at the point of the last `isEquatable` call. It is the context of that scope in which I expect the lookups to happen.

You aren't declaring the conformance for `Array<Int>`, though, you're declaring the conformance for `Array` for all `Element`s, in a context that may be independent of any other conditional conformances on `Array` or conditionally-eligible default implementations for `P`. If you declared `extension Array: P where Element == Int`, we would in fact pick up the most specific available methods to satisfy the requirements for P for `Array<Int>`.

> [@dabrahams](#):
>
> That's what I've always thought the intended semantics _should_ be. It's never been clear to me that anyone else—particularly those putting intentions into code—had the same semantics in mind, though. And absent an implementation, there doesn't seem to be any mechanism for establishing an official consensus.

The Swift runtime implements the semantics I described. It just needs a suitably correct compiler to feed it the right inputs.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 22, 2020, 4:01pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/42 "2020-04-22T16:01:00Z")

</div>

Responding to @Paul_Cantrell's post from another thread here, because it's really this topic IMO:

> [@Test if a type conforms to a non-existential protocol](https://forums.swift.org/t/test-if-a-type-conforms-to-a-non-existential-protocol/35479/27):
>
> In Dave’s example in that second link, this dynamically dispatched code:
> 
> ```swift
> extension P {
> static var isEquatable: Bool { false }
> }
> 
> ```
> 
> …is something that the value itself knows — “I am not equatable” — whereas this statically dispatched code (which if I understand correctly is a shadow, not an override):
> 
> ```swift
> extension P where Self : Equatable {
> static var isEquatable: Bool { true }
> }
> 
> ```
> 
> …is tied to something the calling context knows — “if _you_ think I implement the `Equatable` protocol, then I guess I’m equatable!” Dave’s example goes haywire because the local assumptions (the static types) that could expose this `isEquatable` implementation don’t travel around with the value itself.

It's much worse than that, unfortunately. Whether that second extension acts as a shadow or an override depends on the concrete type it applies to:

```swift
struct X : P, Equatable {...} // override
struct Y<T> : P, Equatable { ... } // override
struct Z<T> : P {}
extension Z : Equatable where T: SomeProtocol { ... } // shadow!

```

> [@Test if a type conforms to a non-existential protocol](https://forums.swift.org/t/test-if-a-type-conforms-to-a-non-existential-protocol/35479/27):
>
> Back to the problem at hand: I don’t think you can get things to make sense again here without doing some kind of runtime test based on metadata that lives with the value itself. Whether that’s an expensive type metadata search with `is` or the vtable lookup I sketched, it has to be dynamic.

I don't want to disagree exactly, but I'd like to draw a distinction between programs that are _semantically static_ and those that are _semantically dynamic_, because that's an entirely different question than whether the program happens to be implemented using dynamic dispatching. A **semantically static** program is one in which, if the whole program is visible to the compiler, all dynamic dispatching based on types could be optimized away by specialization. ¹

In Swift, all unoptimized generic code is _implemented_ with dynamic dispatching, but the code is _semantically static_ as long as no existentials or non-final classes (the basic type-erasing mechanisms) are involved. ² (at the point where these erased types are created the semantically static information is captured and, as you say, “lives with the value itself”). IMO it's hugely valuable that generic code is always semantically static, and the semantics I have in mind for getting “this to make sense” preserve that property.

* * *

¹ I invented these terms AFAIK; if there are established words for this distinction, let's use those instead.  
² Closures with captures can be viewed as another type erasing mechanism. I'm not overlooking those, and if you want to fold them into this discussion, we can, but it will complicate things.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 28, 2020, 4:41am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/43 "2020-04-28T04:41:41Z")

</div>

Wow, I'm back here again. Sorry to keep picking at this one, but the model we have just seems really broken. This example shows how algorithms on conditionally-conforming collections can end up having the wrong complexity:

> <https://gist.github.com/dabrahams/fef7cf8ff6946477ffecc129867c19e3>

With great regret: [[SR-12692] Conditional conformance of generics and specialized algorithms is broken. · Issue #55136 · apple/swift · GitHub](https://bugs.swift.org/browse/SR-12692)

---

<div class="post-metadata">

**Author:** ![Jens](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jens/32/12903_2.png) [@Jens](https://forums.swift.org/u/Jens)\
**Post date:** [April 29, 2020, 7:14am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/44 "2020-04-29T07:14:09Z")

</div>

I might be asking about something obvious here but isn't this what is explained in [this](https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md#overlapping-conformances) and [this](https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md#overloading-across-constrained-extensions) section of SE-0143, ie:

> As noted in the section on [multiple conformances](https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md#multiple-conformances), Swift already bans programs that attempt to make the same type conform to the same protocol twice. This proposal extends the ban to cases where the conformances are conditional.
> 
> /.../
> 
> For these reasons, this proposal _bans overlapping conformances_ entirely.
> 
> /.../

* * *

> Conditional conformances may exacerbate existing problems with overloading behaving differently with concrete types vs. in a generic context. For example, consider:
> 
> /.../
> 
> This is not a new problem to Swift. We can write a similar example using a constrained extension and non-conditional conformances:
> 
> /.../
> 
> That said, the introduction of conditional conformances might increase the likelihood of these problems surprising developers.

?

* * *

If so, I keep making mistakes having to do with this, even though I understand it every time I read it. It seems like I can't truly internalize it.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 29, 2020, 4:33pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/45 "2020-04-29T16:33:21Z")

</div>

> [@Jens](#):
>
> I might be asking about something obvious here but isn't this what is explained in [this](https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md#overlapping-conformances) and [this](https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md#overloading-across-constrained-extensions) section of SE-0143  
> ?

It is. I just never quite realized until recently how serious the consequences are for generic programming. Namely, you have to learn one or both of these lessons:

1. You can't reliably provide a specialized implementation of a base protocol requirement in a derived protocol extension. It will seem to work in many scenarios, but will break down in corners as described here:
2. Conditionally conforming a generic type to a more refined protocol than the one it already conforms to doesn't work if any of the base protocol's requirements have been specialized in the more refined protocol. Those specializations become shadowing overloads that are not used in all contexts.

> [@](#):
>
> If so, I keep making mistakes having to do with this, even though I understand it every time I read it. It seems like I can't truly internalize it.

Me too; I think if you do any algorithm specialization mistakes are unavoidable (unless you resort to beautiful/horrifying hacks like the one described by @Nevin [here](https://forums.swift.org/t/test-if-a-type-conforms-to-a-non-existential-protocol/35479/49), which don't currently optimize well). My take on it is:

- Protocol extensions as they exist today are an inappropriate mechanism for specialization of public protocols in libraries.

- You can use them for requirement specialization privately if you're very careful about the lessons cited above

- To avoid changing the semantics of existing code, fixing this will require:

Fortunately I have been advised that there's room in the ABI for the things needed to fix the problem, so there's hope for the future at least. I think any reasonable solution to these problems could easily also address [this one](https://forums.swift.org/t/dynamically-dispatched-protocol-extension-members/32566).

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 30, 2020, 3:12am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/46 "2020-04-30T03:12:40Z")

</div>

Here's a mystery/challenge related to this problem: [these lines](https://gist.github.com/dabrahams/fef7cf8ff6946477ffecc129867c19e3#file-conditionalconformanceofgenerics-swift-L89-L99) demonstrate how a conditionally-conforming collection implementation may exhibit the wrong behavior (not just efficiency): it actually traps. Why doesn't the same problem occur when `x1` is one of the standard library's conditionally conforming types, like `FlattenSequence`?

```swift
// Try this definition instead.
let x1 = repeatElement(0...9, count: 10).joined()

```

Endless bragging rights for the dev who explains that (I don't know the answer).

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [April 30, 2020, 4:45am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/47 "2020-04-30T04:45:19Z")

</div>

> [@dabrahams](#):
>
> Here's a mystery/challenge related to this problem: [these lines](https://gist.github.com/dabrahams/fef7cf8ff6946477ffecc129867c19e3#file-conditionalconformanceofgenerics-swift-L89-L99) demonstrate how a conditionally-conforming collection implementation may exhibit the wrong behavior (not just efficiency): it actually traps. Why doesn't the same problem occur when `x1` is one of the standard library's conditionally conforming types, like `FlattenSequence` ?
> 
> ```swift
> // Try this definition instead.
> let x1 = repeatElement(0...9, count: 10).joined()
> 
> ```
> 
> Endless bragging rights for the dev who explains that (I don't know the answer).

The stdlib collection types implement `index(_:offsetBy:)` unconditionally (or at least, with no condition beyond `Collection`).

If you move `index(_:offsetBy:)` from the conditional extension into either the main body of `CountSteps1` or an unconditional extension thereof, then it will work.

The reason your example crashes is twofold. First, `offsetEnd(by:)` is written in an extension of `Collection`. So within its body, all the compiler knows statically is that `Self: Collection`.

The call to `index(_:offsetBy:)` resolves to the function which satisfies the conformance of `Self` to the `Collection` protocol. And for `CountSteps1` that is the default implementation from the stdlib, which traps on negative offsets.

Second, the conditional extension on `CountSteps1` does not take part in its conformance to `Collection`, so the methods therein are not implementations of `Collection` requirements. (They are, however, implementations of `BidirectionalCollection` and `RandomAccessCollection` requirements.)

By moving those implementations out of the conditional extension and into an unconditional one (or the main body of the type), then they become part of the `Collection` conformance.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 30, 2020, 3:09pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/48 "2020-04-30T15:09:06Z")

</div>

> [@Nevin](#):
>
> The stdlib collection types implement `index(_:offsetBy:)` unconditionally (or at least, with no condition beyond `Collection` ).

Oh, I see now: the standard library just gives up on performance guarantees for its conditionally-conforming `RandomAccessCollections` ☹. That is really sad. I never would have allowed `FlattenRandomAccessCollection` to be collapsed in this way until we had a way to prevent that.

> The reason your example crashes is twofold…

Yeah, I know why my example crashes; I designed it to show how the existing system is broken.

> [@](#):
>
> By moving those implementations out of the conditional extension and into an unconditional one (or the main body of the type), then they become part of the `Collection` conformance.

[Edit: The following is all wrong; see below]

The point is that if the type (`CountSteps1`) were a legit wrapper over its base, it would use the base's index to implement its own, and those operations wouldn't be available to it in the main body of the type, making the problem completely unfixable short of beautiful/awful existential hacks.

> <https://github.com/apple/swift/issues/55154>
>
> | | |
> |------------------|-----------------|…
> |Previous ID | SR-12709 |
> |Radar | None |
> |Original Reporter | @dabrahams |
> |Type | Bug |
> |Status | Closed |
> |Resolution | Invalid |
>         
> \<details\>
> \<summary\>Additional Detail from JIRA\</summary\>
> 
> | | |
> |------------------|-----------------|
> |Votes | 0 |
> |Component/s | Standard Library |
> |Labels | Bug |
> |Assignee | None |
> |Priority | Medium |
> 
>    
> 
> md5: 433866332d6171ff5820a201ec099db7
> 
> \</details\>
> 
> 
> 
> 
> 
> \*\*Issue Description:\*\*
> 
> 
> \`\`\` swift
> /// The total number of single-hop index steps made in our test collections.
> var totalSteps = 0
> /// A collection that tracks the number of single-hop index steps executed.
> struct CountSteps0 : RandomAccessCollection {
> init(count: Int) { self.count = count }
> var count: Int
> var startIndex: Int { 0 }
> var endIndex: Int { count }
> func index(after i: Int) -\> Int { 
> totalSteps += 1
> return i + 1
> }
> func index(before i: Int) -\> Int { 
> totalSteps += 1
> return i - 1
> }
> subscript(i: Int) -\> Range\<Int\> { return 0..\<9 }
> }
> extension Collection {
> func midPoint() -\> Index { 
> index(startIndex, offsetBy: count / 2, limitedBy: endIndex)!
> }
> }
> let x0 = CountSteps0(count: 900)
> \_ = x0.midPoint()
> print("steps:", totalSteps) // 0
> \_ = x0.joined().midPoint()
> print("steps:", totalSteps) // 1350
> \`\`\`
> 
> Due to \<https://bugs.swift.org/browse/SR-12692\> this is impossible to fix using protocol extensions. Hacks like \[this\](https://forums.swift.org/t/test-if-a-type-conforms-to-a-non-existential-protocol/35479/49) are needed.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [April 30, 2020, 3:25pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/49 "2020-04-30T15:25:03Z")

</div>

> [@dabrahams](#):
>
> Oh, I see now: the standard library just gives up on performance guarantees for its conditionally-conforming `RandomAccessCollections` ☹. That is really sad. I never would have allowed `FlattenRandomAccessCollection` to be collapsed in this way until we had a way to prevent that.

I believe that is not correct. The conditionally-conforming types provide their own implementations of `Collection` requirements, which forward to the base collection. Therefore, if the base provides performant random-access guarantees, then so does the wrapper.

(Where possible that is—of course `LazyFilterCollection` can only provide `Bidirectional`, not `RandomAccess`, whereas `LazyMapSequence` can do both.)

> [@dabrahams](#):
>
> The point is that if the type ( `CountSteps1` ) were a legit wrapper over its base, it would use the base's index to implement its own, and those operations wouldn't be available to it in the main body of the type, making the problem completely unfixable short of beautiful/awful existential hacks.

If `CountSteps1` were a legit wrapper over its base, it would use the base’s index to implement its own, and it would forward `index(_:offsetBy:)` to its base, and that operation _would_ be available to it in the main body of the type, making the problem entirely nonexistent.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [April 30, 2020, 3:29pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/51 "2020-04-30T15:29:28Z")

</div>

> [@Nevin](#):
>
> > [@dabrahams](#):
> >
> > Oh, I see now: the standard library just gives up on performance guarantees for its conditionally-conforming `RandomAccessCollections` ☹. That is really sad. I never would have allowed `FlattenRandomAccessCollection` to be collapsed in this way until we had a way to prevent that.
> 
> I believe that is not correct. The conditionally-conforming types provide their own implementations of `Collection` requirements, which forward to the base collection. Therefore, if the base provides performant random-access guarantees, then so does the wrapper.

My bad; `FlattenCollection` can't be random access. Sorry for the noise.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [April 30, 2020, 3:58pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/52 "2020-04-30T15:58:39Z")

</div>

> [@dabrahams](#):
>
> My bad; `FlattenCollection` can't be random access. Sorry for the noise.

But it _can_ be improved:

[This](https://github.com/apple/swift/blob/adaf0651f15edab6e44e1e78e97ee7432dfc907a/stdlib/public/core/Flatten.swift#L340-L349) is its implementation of `index(_:offsetBy:)`, which is indeed only conditioned on `T.Element: Collection`. (The `limitedBy` version is a few lines down. The following applies to both, as well as `distance(from:to:)` and maybe some other stuff.)

Currently, its `index(_:offsetBy:)` method works by repeatedly stepping the index one position at a time. But it could be rewritten to “hop”, by checking the `count` of each outer element in turn. (The first one of course would check the distance from the starting point to whichever end is in the proper direction.)

When the outer elements are `RandomAccess`, this means it would not have to walk the inner elements at all. It would happily hop along the outer elements, subtracting their counts until the distance remaining to travel reaches (or crosses) zero. Then it would drop into the correct outer element, and hop to the desired position.

The tradeoff here is that in the non-`RandomAccess` case it would go more steps than necessary, because it would have to find `count` for whichever outer element contains the destination, rather than stopping immediately when it reaches the destination.

That could probably be rectified through some cleverness, since it does know the remaining distance ahead of time.

Basically, we would want something like `index(_:offsetBy:limitedBy:)` that returns a tuple of `(indexReached: Index, actualDistanceTraveled: Int)`. Or alternatively, `distance(from:to:butNotMoreThan:)` with a similar return type.

---

<div class="post-metadata">

**Author:** ![Douglas\_Gregor](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/douglas_gregor/32/1362_2.png) [@Douglas\_Gregor](https://forums.swift.org/u/Douglas_Gregor)\
**Post date:** [May 7, 2020, 9:48pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/53 "2020-05-07T21:48:22Z")

</div>

> [@dabrahams](#):
>
> Fortunately I have been advised that there's room in the ABI for the things needed to fix the problem, so there's hope for the future at least. I think any reasonable solution to these problems could easily also address [this one](https://forums.swift.org/t/dynamically-dispatched-protocol-extension-members/32566).

This really needs some elaboration, because this is an area where implementation constraints have a significant impact on what is possible with the language design. The current implementation model is that a protocol conformance is described by a "witness table", which is a mapping of each protocol requirement to its "witness", i.e., the one declaration that satisfied that particular requirement. With generic types, that witness has to be one that works for any generic arguments. To get a different witness for different generic arguments, which is fundamentally what this thread is about, requires the Swift runtime to inspect the capabilities of the actual argument types dynamically, and perform some decision procedure to pick the best witness. There are effectively two places where we can introduce a decision procedure that works with the current runtime:

- Within the implementation of a function itself. For example, if a single function had multiple bodies (e.g., each with a different `where` clause), the decision procedure would be at the beginning of the witness function.
- When the witness table for a concrete type's conformance to a protocol is realized (e.g., `Array<Int>` conforming to `P` in @dabrahams's example). Here, the decision procedure would be in some runtime hooks we have during witness table realization. We can make decisions for each protocol requirement (independently).

Now, the fact that this decision process occurs at runtime implies a few things about our design constraints:

- The process should be fast. We'll have to accept some dynamic lookups (e.g., does `Int` conform to `Equatable`?), but we probably have to avoid global lookups that produce an unknown set of potential candidates to rank.

- The process should never fail. Overload resolution and similar ranking metrics have ambiguities. We should either define away those ambiguities (i.e., there is always a single best answer) or we need some kind of fallback (warn and pick at random? pick what today's language picks?).

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 7, 2020, 10:59pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/54 "2020-05-07T22:59:40Z")

</div>

> [@Douglas\_Gregor](#):
>
> - The process should be fast. We'll have to accept some dynamic lookups (e.g., does `Int` conform to `Equatable` ?), but we probably have to avoid global lookups that produce an unknown set of potential candidates to rank.

If we take the "multiple bodies with different where clauses" approach, it seems to me like we could bubble up the information in those where clauses to the conformance, so that we know statically that the conformance needs to take added conditional arguments in order to instantiate the witness table, so that we could still pass down the `Int: Equatable` conformance (or lack thereof) at the point of instantiation for the witness table instead of doing a global search.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [May 7, 2020, 11:57pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/55 "2020-05-07T23:57:35Z")

</div>

Thanks for your post, Doug!

> [@Douglas\_Gregor](#):
>
> Now, the fact that this decision process occurs at runtime implies a few things about our design constraints:
> 
> - The process should be fast. We'll have to accept some dynamic lookups (e.g., does `Int` conform to `Equatable` ?), but we probably have to avoid global lookups that produce an unknown set of potential candidates to rank.
> - The process should never fail. Overload resolution and similar ranking metrics have ambiguities. We should either define away those ambiguities (i.e., there is always a single best answer) or we need some kind of fallback (warn and pick at random? pick what today's language picks?).

Would you be open to thinking differently about how this can work? I've always had in mind a system where these determinations can be made at compile time (while still allowing separate compilation of course). I've always thought viewing something that's [semantically static](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/42) through a dynamic lens has been limiting our implementation choices, and I think there are other possibilities.

Whether we can even begin that conversation depends on whether you agree that generics should/could be semantically static. If not, the options are indeed much more limited.

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 8, 2020, 12:15am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/56 "2020-05-08T00:15:42Z")

</div>

I don't think it's just about viewing the problem through a "dynamic lens". The important property I think we want to maintain in the generics system is modularity. That allows us to implement generics with semantically equivalent dynamic and static implementations, but that's not the only benefit; it also allows for separate compilation and analysis, avoids introducing fundamental compiler performance problems, and minimizes side effects from adding additional packages to a system.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [May 8, 2020, 3:07am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/57 "2020-05-08T03:07:11Z")

</div>

Of _course_ we want modularity, motherhood, 🍎 🥧 and all other good things 😉

I don't know why you think that's related to what I brought up. What I have in mind is modular and preserves all of the properties you listed _except_ possibly the thing about semantically equivalent static and dynamic implementations—depending on what you mean by that—whose value I am inclined to question.

I _think_ what I have in mind could even improve the modularity story, but it's hard to tell because you haven't been very precise about the properties you listed. It would be really helpful if you could unambiguously describe the semantics you think are crucial, ideally with examples that illustrate the differences between the results you want and those you would like to prevent, so we can evaluate both those judgements and any proposals that may arise from this thread.

Thanks,  
Dave

---

<div class="post-metadata">

**Author:** ![Douglas\_Gregor](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/douglas_gregor/32/1362_2.png) [@Douglas\_Gregor](https://forums.swift.org/u/Douglas_Gregor)\
**Post date:** [May 8, 2020, 3:38am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/58 "2020-05-08T03:38:51Z")

</div>

> [@Joe\_Groff](#):
>
> If we take the "multiple bodies with different where clauses" approach, it seems to me like we could bubble up the information in those where clauses to the conformance, so that we know statically that the conformance needs to take added conditional arguments in order to instantiate the witness table, so that we could still pass down the `Int: Equatable` conformance (or lack thereof) at the point of instantiation for the witness table instead of doing a global search.

In cases where we know it statically, yes, and that's a common case I bet we can optimize. In the general case, we won't know until runtime that the type will be `Int`, and someone will have to do the dynamic lookup.

Doug

---

<div class="post-metadata">

**Author:** ![Douglas\_Gregor](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/douglas_gregor/32/1362_2.png) [@Douglas\_Gregor](https://forums.swift.org/u/Douglas_Gregor)\
**Post date:** [May 8, 2020, 4:53am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/59 "2020-05-08T04:53:46Z")

</div>

> [@dabrahams](#):
>
> I _think_ what I have in mind could even improve the modularity story, but it's hard to tell because you haven't been very precise about the properties you listed. It would be really helpful if you could unambiguously describe the semantics you think are crucial, ideally with examples that illustrate the differences between the results you want and those you would like to prevent, so we can evaluate both those judgements and any proposals that may arise from this thread.

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](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589). The parts relevant to my examples are these:

```swift
// (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:

```swift
// (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:

```swift
  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`:

```swift
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`:

```swift
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:

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

```

we end up getting an ambiguity error:

```swift
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):

```swift
// (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:

```swift
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

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [May 8, 2020, 5:30am UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/60 "2020-05-08T05:30:02Z")

</div>

> [@Douglas\_Gregor](#):
>
> I don't know what you have in mind, but I can spell out what I know is implementable (relatively) efficiently

I appreciate the extensive reply, and I will dig into it in detail, but can we please first answer my earlier question of whether you consider it acceptable to say that all programs without existentials or non-final classes are semantically static? My definition of that term is simple: a semantically static program can be implemented without type-based dynamic dispatching provided all the sources are available to the compiler.

There's a whole class of backward-compatible ways you might extend Swift generics (or to "fix" things that are broken today, such as cross-module dispatching) that would make the semantics of some such programs dynamic. I want to know if you consider any of those points in the design space essential destinations for the language. The answer determines both how I understand the possible futures of Swift's generics system, and whether my ideas are worth discussing at all in this forum.

---

<div class="post-metadata">

**Author:** ![Joe\_Groff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/joe_groff/32/1929_2.png) [@Joe\_Groff](https://forums.swift.org/u/Joe_Groff)\
**Post date:** [May 8, 2020, 4:32pm UTC](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589/61 "2020-05-08T16:32:37Z")

</div>

> [@Douglas\_Gregor](#):
>
> In cases where we know it statically, yes, and that's a common case I bet we can optimize. In the general case, we won't know until runtime that the type will be `Int` , and someone will have to do the dynamic lookup.

I think the important thing is not whether the type is `Int`, but whether the conformance's behavior is conditional on the availability of other conformances on the type or its associated types. Since we don't have any way currently of abstracting over constraints, the set of conditional arguments to a conformance seems to me like it should always be statically knowable.

[Previous page](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589.md?page=2)

[Next page](https://forums.swift.org/t/ergonomics-generic-types-conforming-in-more-than-one-way/34589.md?page=4)
