An Implementation Model for Rational Protocol Conformance Behavior

Evolution Pitches
62

Can this behavior/problem be changed/fixed without changing the behavior of existing code? (Please let us know if you want to keep the discussion here focused, without non-expert questions like this.)

63

We don't have a solution yet, so we don't know.

Doug

64

Yes, just as today when you take an X value out of a Set<X>, pass it across a boundary where X: Hashable is unknown, and stick it into a Set<X> with distinct type identity (as defined today).

Simpler example; according to your descriptions I think this would work today:

// Module A
public struct X {}

// Module B
extension X: Hashable { ... }
// Module B1
import B
getX() -> X { let b = Set(X()); return b.first! }

// Module C
extension X: Hashable { ... }
// Module C1
import C
setX(_ x: X) -> X { let c = Set(x) }

// Module D
import A
import B1
import C1
setX(getX())

As I understand it, the local variables b in B1 and and c in C1 are distinct types, using different X: Hashable conformances. Yet an X from one set gets returned from B1.getX() and passed into C1.setX(_), where it has a different Hashable conformance. I claim this is fine, because in D, where the passing happens, hashing an X has no meaning, so there's nothing B1.getX() can meaningfully promise to its clients about the thing it returned that would be violated by a different notion of X: Hashable.

I think it does.

  • B.uniqueXs has nominal type identity [X] with a conformance set containing the X: Equatable conformance from B.
  • In C, [X] has a the same nominal type identity, but its conformance set contains the X: Equatable conformance from C.
  • The two conformance sets conflict, so the extension declared for [X] in C doesn't apply to the [X] coming from B, and on the last line of D, B.uniqueXs.doSomething()is a compilation error.
  • B.uniqueXs.containsDuplicates() on the 2nd to last line of D would certainly be fine and return false if we could hide C's X: Equatable conformances (e.g. if it was internal). I think we can also allow it if the conformances are public, but don't hold me to that!

Note that because there are no existentials involved, all this information is available at compile-time, when it needs to be.

Not quite; your example is a little spare, but let me try…

The conformance set is in the type system and used to determine type compatibility, which, for any given types should be determinable at compile time. The conformance table is part of my implementation model—which I'm not sure we really want to discuss, but since you asked—it expresses a superset of what's in the conformance set, both because we probably don't want to be dynamically rebuilding this table every time a type leaves a relevant conformance scope, and so that existential dispatching works “correctly” (per me). You don't “lose” the whole conformance table just because an instance of a type crosses a conformance scope boundary, but conformances that aren't visible on the destination side of that boundary aren't part of the conformance set.

You could say the parts of the table representing hidden conformances become irrelevant to the static type system, and are eligible to be replaced when crossing into a context with conformances that would conflict if the table was interpreted as a conformace set.

I don't think so, but if after reading this you still do, let's dig into the details and figure it out.

1 Like
65

Okay.

Okay, so it's the fact that uniqueXs was defined in module B that makes it such that X: Equatable cannot differ when interacting with uniqueXs.

My example with excessArray only really differs from your example in one way, which is that excessArray is in module A, where there is no notion of X being Hashable. I expected that distinction not to matter, but now it seems that it is very different in your design. Specifically, it means that excessArray can be used/modified/whatever from any module, whether that module has some notion of X being Hashable or not (or sees conflicting notions of Hashable?). Whereas your uniqueXs is only usable from those modules that use B's conformance to Hashable (and don't see a conflicting conformance. Is that correct?

Doug

1 Like
66

Yes, or to be a little more general, it's the fact that uniqueXs was defined where an X: Equatable conformance was in scope.

Yes, just like today.

(or sees conflicting notions of Hashable ?)

Remains to be seen whether that's actually sound, but so far I see no reason to prevent it. X: Hashable is irrelevant in the scope where excessArray is defined.

It's Equatable in that example, but yes. The uniqueness is part of uniqueXs API contract and that is defined in terms of B's X: Equatable conformance.

The principle is that:

  • When conformances conflict, it means they (potentially) describe distinct semantics.
  • Every API has a contract that describes its semantic requirements and guarantees.
  • Conformances that are unknown on either side of an API boundary can't reasonably show up in the API's contract so cannot cause a semantic problem (see internal protocols).
  • It's no problem for a type to effectively gain or lose conformances when crossing an API boundary (internal protocols again).
  • The problem occurs when an API contract is written in terms of a conformance and the two sides of the API boundary (potentially) disagree about the semantics of that conformance.

Make sense?

1 Like
67

So, I can see how your rules as described get you to that set of conclusions.

We're inferring that X: Equatable is part of uniqueXs API contract based on the presence of X: Equatable in B---or, more generally, in B or any module it depends on---even though there's no evidence of this being part of the contract. uniqueXs might not ever care about Equatable, and we've made reasonable code ill-formed.

That's one of my complaints about his approach: uniqueXs is not written in terms of a conformance, so why should it be subject to additional constraints on X: Equatable? It's based on the fact that X: Equatable is known to module B, but how far does this go? Does the fact that Y: Equatable is known to module B also have an impact on uses of uniqueXs? It seems like it has to, because Y could include some values of type X in it and compare them with ==?

More than before, but not really. I can work through small examples (sorta), but I haven't a clue how I would explain it to someone. More importantly, I don't think I can come up with examples that show why this improves code overall---if your uniqueXs example is an improvement, but my very similar excessArray example sees no improvement, have we fixed a systemic issue? Which one?

Doug

68

No, I was stating that it was part of the API contract based on the documentation written just above it. I was not trying to show you how to “think like the compiler,” but how an API contract can be broken by a conflicting conformance.

This is about encapsulation and API contracts.

Once a module such as B creates an A.X: Equatable conformance that notion of equatability becomes part of what X “means” to all the code in B. B may not depend on that conformance today, but it has a right to start depending on it at any time. The same is true if a module imported by B exposes a public A.X: Equatable conformance (the only possibility today outside of A, where X is defined, and the standard library, where Equatable is defined),

Sorry, I'm unable to guess what kind of impact you have in mind, but I don't see any way in which Y: Equatable could affect uses of uniqueXs. Maybe you could be more explicit?

That's ironic, because as far as I can tell what I've proposed is a model that can be explained, not just in terms of mechanics, but also in terms of principles, both of which I think I've laid out unambiguously in this thread. As for the status quo, while I understand its rules mechanically, they seem more based on a couple of examples than on principles, and are nonuniform and thus hard for me to reason about.

My biggest complaint about the status quo is that it violates what I'll call “Abrahams' first law of systems design:” thou shalt not create a system where blame can't be assigned. To elaborate, it has to be possible for programmers to define rules for using components, and if everybody follows the rules, code has to work. When something goes wrong, it has to be possible to point to some code and describe what the mistake is in terms of things the author should have reasonably known and been able to account for. My problem is that I can't explain which module author made the mistake in the uniqueXs example. Whenever that happens, it's time for the compiler to step in and force things to be straightened out, or we don't have a sustainable programming model.

I'm confused; what improvement you expect for the excessArray example? It doesn't have any problems that need fixing as far as I can tell. Given that you're saying my proposed response to the uniqueXs example is too restrictive, I'd have thought you would at least have no complaints with this one.

69

Making progress.

May I suggest that someone else (@jrose @Jens or anyone else) go through the (perhaps academic) exercise of applying the proposed model to some other examples, both standard cases and edge cases? There may be insights and understanding to be gained from it.

70

Sure, so is the existing model, but the existing model is based on what conformance you try to use as a client rather than what conformances were provided by the implementation. The former is the subset that is directly relevant; I'm asking for cases where we need the additional information.

Let's revisit that uniqueXs example in full, now that we've learned something more about your proposal and about the existing module, in particular with different conformances. The only thing I've change are the comments on the last two lines, which I've annotated with the current language semantics:

// Module A
extension Array where Element: Equatable {
   /// Returns the index of `x` if present in `self`, and `nil` otherwise.
   func containsDuplicates() -> Bool { ... }
}

struct X {}

// Module B
import A
extension X: Equatable { 
  static func == (a: X, b: X) -> Bool {…}
}
/// Some Xs with no duplicate values, per equality as defined here.
public let uniqueXs: [X] = Array(Set( … ))

// Module C
import A
extension X: Equatable { 
  static func == (a: X, b: X) -> Bool {…} // Different equality
}

extension Array where Element: Equatable {
   /// - Requires: `!self.containsDuplicates()`
   func doSomething() { precondition(!self.containsDuplicates()) }
}

// Module D
import A
import B
import C

print(B.uniqueXs.containsDuplicates()) // ERROR: ambiguous conformance X: Equatable (found conformances in both B and C)
B.uniqueXs.doSomething()               // ERROR: ambiguous conformance X: Equatable (found conformances in both B and C)

As noted, the compiler is broken here and won't emit that error message, but the language model we've been designing for---i.e., the one that the runtime representation is built around--- is that you look up the conformances you need at the point where you call from concrete code into generic code (or form a specialization of a generic type), with only those conformances that you need to satisfy the requirements. For example, to satisfy the requirements of containsDuplicates() or doSomething(), we look up the conformance of X to Equatable so the witness table can be passed in the function. This affects type identity when the conformances are part of the type's generic requirements (Hashable conformances affect Set<X> identity, but not [X] identity). If there's an ambiguity, the compiler should produce an error. The model is consistent, but the implementation is buggy.

So, the current model rejects the last two lines. Let's compare that with your comments on your model:

We agree to reject the last line. The existing model rejects the second-to-last line (X: Equatable is needed to make the call, and it is ambiguous), but perhaps your model accepts? (I'm not supposed to hold you to your answer, but I kinda want to know).

So, where is the meaningful difference in behavior with your model?

Doug

[EDIT: I had Hashable originally in two places that should have been Equatable; this has been fixed]

71

In the uniqueXs example, is the extension in Module B public or internal? Based on the substance of the discussion, I assume it is meant to be public. If it is internal to Module B, then it is invisible in C and thus the [X] received in C from uniqueXs arrives without B's conformance to Equatable, right?

So, if a method's generic constraint calls for a Collection, and the passed concrete type expressly conforms to RandomAccessCollection (thus implicitly conforming to Collection) and that type has a method declared for distance(from:to:) that customizes it conformance to RandomAccessCollection, will that method be treated as part of the implicit conformance to Collection or will it be disregarded as constituting an irrelevant conformance to a requirement of RandomAccessCollection?

Why is Hashable needed to satisfy the requirements of containsDuplicates() or doSomething?

72

I assumed public. If it were internal (something that doesn't exist today, but could), then there would be no ambiguity in D because B's conformance would not be visible in D.

Conformance to RandomAccessCollection implies conformances to Collection; only the Collection conformance is considered because only Collection is needed. And whatever distance(from:to:) implementation satisfied that requirement in Collection will be used. (I don't think Dave's proposal changes anything about this).

It isn't; I meant Equatable there and have fixed the post.

Doug

73

Right. Regrettably, I was unaware of this bit from the documentation:

You can’t provide an explicit access-level modifier for an extension if you’re using that extension to add protocol conformance. Instead, the protocol’s own access level is used to provide the default access level for each protocol requirement implementation within the extension.

I suppose this circles back to a fundamental question that continues to bother me: Should Swift allow a module to vend a retroactive conformance as part of the module's public API? I suppose there must be a good use case for it, but I'm not aware of it.

74

I believe part of the motivation behind this thread is to define and document the model so that users are able to make this sort of judgment for themselves.

As things stand, now, we have multiple sources of truth: (1) StackOverflow answers, (2) blog posts, (3) WWDC videos, (4) reading between the lines in The Swift Programming Language, (5) asking questions in the Using Swift part of this forum, and (6) whatever the compiler does.

That last one is a special one. The common wisdom seems to be that the compiler defines the language. If the compiler let's you do something, then that something is allowed (unless someone from the Core Team or at Apple says otherwise). But that really isn't true, and shouldn't be true.

This is not meant as a complaint. Rather, it is intended as a call to please continue down the path this thread already is on.

2 Likes
75

Well, you can have a module whose role is to adapt the data structures of one module to work with the algorithms of another module, by making the data structures for the former conform to the protocols of the latter. My favorite hypothetic example is a linear algebra library providing Matrix data structures being adapted to conform to the Graph protocols in a graph-theory library, because "of course" a matrix is just a graph in a different representation, yet these are two separate domains.

Doug

4 Likes
76

But, as I've been saying, what conformances were provided by the implementation is not the basis of my model. It's what conformances were visible on both sides of an API boundary, and whether they are in conflict.

Let's revisit that uniqueXs example in full, now that we've learned something more about your proposal and about the existing module,

Sorry, what existing module? I just want to understand. [Edit: oh, you meant “model!”]

First, let me note that our definitions of “current” or “semantics” must be very different if you think the statements quoted above are not internally contradictory. We don't have this documented, AFAIK, so all the rest of us have to go on is the implementation, which as you say doesn't emit that error message. I'm not saying this to yank your chain or to pick nits, but because if we can't agree on the meanings of these terms it's going to be really hard to make progress.

Second, when you wrote “your example shows unexpected and bad behavior in the presence of multiple conformances,” without following it up with “but that's a bug (SR-XXX) and not part of the intended model,” I assumed (fairly, I think) that you were saying that both the current implementation and the intended model fails to deal correctly with that example. What you're saying now is very different from that interpretation.

I think it might be understandable, based on the above, if it turns out that what I'm proposing is effectively the same as your intended model, because you've been pretty hard to pin down. So I ask you to take pity on a poor, literal-minded person, who's just trying to understand, and be a bit more consistent and unambiguous.

So the errors you say should be there above point to the uses of containsDuplicates and doSomething (and not B.uniqueXs), because both of those things depend on the X: Equatable conformance, which is ambiguous in the context where they are invoked, correct?

Just to keep everybody honest—especially myself—I built the uniqueXs example out into a Swift package at GitHub - dabrahams/UniqueXs. The code as written in my earlier postings, even if all the ellipses were filled in, wouldn't compile, mostly because public conformances demand more definitions to be public. While we could overlook that, what's visible to whom is kind of central to this debate, so I don't want to gloss over it.

It would be really helpful if we could do the same for any other examples we get into in detail, I think. In particular, we never saw more than one line of code for your excessArray example, so if we get into it more I'd like to know exactly what we're supposed to be discussing.

Sorry again: when you say “where you… form a specialization of a generic type” do you mean “where you first encounter each distinct set of concrete type arguments—and presumably, relevant conformances?” (the way “specialization” is often used around C++) or do you mean “generate specific code for the specific set of generic generic parameters” (the way we usually hear it used around Swift)?

The answer actually makes a big difference to me, because I think it determines whether “generic types conform in one way” is an intended part of the model or not.

So, the current model rejects the last two lines. Let's compare that with your comments on your model:

Fair enough.

We can't allow the call based on the fact that the conformance set coming from B (where uniqueXs is defined) is compatible with the the conformance set in A to allow the call, because in a similar program control flow can make that information dynamic.

There are only two remotely reasonable behaviors here, AFAICS:

  1. Reject the program because uniqueXs is flowing directly into a context with a conflicting notion of X: Equatable.

  2. Reject the program because at the point where containsDuplicates—which depends on X: Equatable—is called, the conformance is ambiguous.

I think if I'm being honest about the intent behind my proposal, it would have to be #1, because D has C's X: Equatable conformance, which conflicts with the one from B, where uniqueXs was defined.

Now, the fact that D has two notions of X: Equatable in its conformance set (B's and Cs) instead of just one, complicates thinking about this a bit, because you can view D as a context where no X: Equatable is available, which would sort of make it OK. But in today's language definition, conflicts always manifest this way, within a single conformance set, but I was thinking about a way to formalize scoped conformances, where you could have singular conflicting conformances across an API boundary (e.g. B and C have their own internal X: Equatables—should they be allowed to directly exchange Xs)? Again being honest, I'm completely fried at the moment and and not thinking very clearly, so I don't know the answer, but that doesn't seem like a problem to me where I stand right now.

Great question. Now that you've clarified the intended model it might be nothing. I'll have to sleep on it.

77

As cool as retroactive conformance is, I've found that I usually, eventually, want to go to the trouble to create adapting wrappers for these purposes. Otherwise, the resulting public APIs can get huge and diffuse. Personally, I've never seen retroactive conformance as creating much of a problem, but also don't know of any circumstances in which it's essential. If retroactive conformance is ever essential, it would be very worthwhile to clearly define the kinds of things it enables.

3 Likes
78

Starting by re-asking these questions because I don't see any answers yet:

So the errors you say should be there above point to the uses of containsDuplicates and doSomething (and not B.uniqueXs ), because both of those things depend on the X: Equatable conformance, which is ambiguous in the context where they are invoked, correct?

Sorry again: when you say “where you… form a specialization of a generic type” do you mean “where you first encounter each distinct set of concrete type arguments—and presumably, relevant conformances?” (the way “specialization” is often used around C++) or do you mean “when you generate specific code for the specific set of generic generic parameters” (the way we usually hear it used around Swift)?

The answer actually makes a big difference to me, because I think it determines whether “generic types conform in one way” is an intended part of the model or not.

Having slept on it, the difference is captured by this change to the example, which you can get by checking out the drop-one-equatable branch.

If I understand correctly, in your intended model, the call to containsDuplicates() would fail to compile, but the call to doSomething() would compile and trigger the precondition failure. A program that contained just the last line would be legal, but the code would be broken. So what rules of your programming model were broken, and by whom? The only rule that I can imagine leaves it up to the programmer to track the source of each set of related X instances and ensure it doesn't travel into a context with a conflicting conformance. Is that a manageable programming model?

79

Doug, thank you for that example regarding retroactive conformance.

When conforming a type in module B to a protocol from module A, is there any means available for the author of module B to make the conformance internal to module B? It seems like that would be a desirable feature.

80

Yes, that's correct.

Each time you encounter a use of a generic entity, there is a set of generic parameters for which you must provide generic arguments, and a set of conformance constraints for which you must provide conformances. If there is an ambiguity in the choice of conformance for any of those conformance constraints, the program is ill-formed.

Yes.

You have multiple different definitions of Equatable running around for a type. It was going to bite you eventually.

I think it's reasonable, and I think your proposal doesn't actually address it either. As I understand it, the extra "conformance table" in your model is only carried through generics and existentials, but this isn't generic any more:

extension Array where Element == X {
   /// - Requires: `!self.containsDuplicates()`
   public func doSomething() { precondition(!self.containsDuplicates()) }
}

Even if we disagree about whether the above counts as "generic", it seems like one need only "launder" the uniqueXs instance through another non-generic function to have the same problem:

func launder(xs: [X]) {
  xs.doSomething()
}

launder(xs: B.uniqueXs)

Doug

81

There is no way to do this. I agree that it is a reasonable feature, but we need a semantic model of how as? will work to make that feature useful.

Doug