An Implementation Model for Rational Protocol Conformance Behavior

Thanks, @mattrips. I probably should have called it out more explicitly. If you're not worn out from reading, Backwards-deployable Conformances also talks about how to tackles some of the problems in Retroactive Conformances vs. Swift-in-the-OS, but focusing on libraries shipped with Apple OSs. It's less relevant to the current discussion, but I don't want to leave the impression that there's been no progress on the issues I/we raised originally.

1 Like

[Meta: I've been posting a lot and been (rightfully) called out on my negativity in private, so after this one I'm going to hold off on further replies till the weekend at least.]

This is a good point. Here's how I would summarize (what as I see as) the intent of our current model, ignoring dynamic casts, associated type inference, and the possibility of two conflicting visible conformances (one of Doug's examples):

  1. When a conformance MyType: MyProtocol is declared, the compiler goes through each requirement and asks what function would be called, given what is known at that point in the program:

    // Illustrative purposes only;
    // the compiler does not actually synthesize a function to do this.
    extension MyType {
      func __invoke_doSomething(with argument: Int) {
        self.doSomething(with: argument)
      }
    }
    

    If there are multiple overloads of doSomething(with:), the compiler picks the best one visible, just like it always does. The meaning of "best" is chosen at this point in time, which means that if one of the overloads is in a constrained extension based on a generic parameter of MyType, it won't get picked, because one implementation is picked to work with any MyType, whether it's MyType<Int> or MyType<[MyType<String?>]>. (It can take into account any constraints that are on the actual definition of MyType—perhaps that its argument has to be Equatable—as well as any constraints on the extension adding the conformance, if it's a conditional conformance.)

    All of this is the same (idea) as overload resolution, which does not do dynamic dispatch in Swift. You'll often find me reciting "there are three ways to do type-based dispatch in Swift: invoking a protocol requirement, calling an overridable method on a class, or actually checking the type with a dynamic cast".

  2. When a MyType value is passed to a generic function with a MyProtocol constraint or converted to an existential value, the compiler finds "the" conformance of MyType to MyProtocol, and passes that to the function. (The run-time representation of the conformance is the witness table, which contains all the "witnesses" to the requirements chosen in (1), as well as the associated types, and the conformances for any constraints on the associated types.) Note that this process doesn't look at the generic arguments of MyType except to populate the "associated types" section.

  3. Later on, when a protocol requirement is invoked (through a generic argument or an existential value), the "witness" found in the table in (2) is called.

That's the model as I understand it. You and Doug have already called out a weak point in (2)—"what should happen if two conformances are visible?"—compounded (in SR-12513) by leaky import visibility that lets the compiler find extension members and see conformances from an import that's in another file in the same module. And there's also the weak point in (1)—"requirements are resolved at the point where the conformance is declared"—which caused the problem with DefaultIndices in SR-12881.

(1) and (2) are also the places Doug called out as places to run a "decision procedure"—either the witness chosen in (1) would be a compiler-synthesized function that picked the best overload when invoked, or the fetching of the witness table in (2) could pick the best overload when created.


But your original point stands. Why is it hard for users to think about generic dispatching? I'd guess that it's the same reason many users have trouble with this code:

extension Collection {
  func whatAmI() { print("Collection") }
}
extension Array {
  func whatAmI() { print("Array") }
}
func whatIsIt<C: Collection>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array
  whatIsIt(x) // Collection
}

For better or worse, most people's model of what generic code ought to do seems to match up with what C++ actually does: it should pick the best option based on the value you pass. It's only us Swift implementers who can look at that and say "that's overload resolution at run time", and shrink away because we've designed a language where overload resolution is non-trivial.

Changing this particular case to "work" doesn't even require a conformance table; it "just" means checking that the concrete type is an Array. There are many reasons why even this concerns me from a performance and code size perspective. But even putting those aside, is that really the interpretation we want for the code above? For Swift, I don't think it is—it's too ad hoc. Nothing links the various whatAmI operations but their names.

(EDIT: But of course, that's all that links the choices in overload resolution too, so this may not mean much.)

5 Likes

I found your example compelling, but then thought about how it utilizes a non-required protocol method. Let's consider how using a required protocol method would change the result.

protocol P {
  func whatAmI()
}
extension P {
  func whatAmI() { print("P") }
}
extension Array: P {
  func whatAmI() { print("Array") }
}
func whatIsIt<C: P>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array
  whatIsIt(x) // Array
}

Our two examples, set side by side, reflect a fundamental difference in behavior. I suppose "many users have trouble" with your example due to this difference in behavior. But, I don't want to get this conversation hung up on subtleties of how things currently work.

I want to stay focussed on the question you pose about how we think it ought to work: "Is that really the interpretation we want?" I suppose my answer is, I could go either way on the interpretation. But, whatever the interpretation, I think it ought to apply the same way to both your example and my example.

1 Like

Having read a prior thread on the same subject, I kept thinking, and continue to think: Why isn't this a compile-time error?

Now, I understand your intent to be that this is and should be a compile-time error, but the compiler has a difficult time diagnosing it. If it is an error, do we need to consider it any further for purposes of talking about what the model should be?

I think this should be a compile-time error.

If there are two modules in scope that both supply a type called X, I believe it should be a compile-time error to use X without disambiguating. My answer doesn't change depending upon which module defines the function. If the reference to type X is ambiguous, it is an error.

In all of these cases, shouldn't the user be required to disambiguate the type-name collision at the point of use by prefixing the typename with the applicable module name?

1 Like

It depends on which "this" you're referring to:

  • It is not wrong for either B or C to declare a conformance of X to Hashable. Retroactive conformances are allowed in the language, but they're tricky. No compile-time error here.
  • A program may very well import both modules B and C, perhaps in separate modules that don't even know about each other. You can't really produce a compile-time error without seeing B and C in the same place, and you probably don't want to: B might be some hidden dependency, and bringing it into your program shouldn't cause your program to be wrong just by its existence.
  • The module D in the example should produce a compile-time error somewhere. The correct place, in my opinion, is on the use of ==: the == for Set only works when the two Set types are the same, and these Set<X> types are different because they involve different X: Hashable conformances.

For me, it depends on what modules have been imported. If we only have

import A

func test(any: Any) {
  if let setOfX = any as? Set<X> { ... }
}

then I agree that this must be a compile-time error, because X does not conform to Hashable.

However, I would say that

import A
import B

func test(any: Any) {
  if let setOfX = any as? Set<X> { ... }
}

is correct. Moreover, it should match the type produced by getBSet() but not by getCSet().

There's a similar case for the function if defined in a module that imports A and C.

However, I expect a compile-time error if both conformances of X to Hashable are visible:

import A
import B
import C

func test(any: Any) {
  if let setOfX = any as? Set<X> { ... }  // error: multiple conformances of X to Hashable
}

There is only a single type X here, which is defined in module A. If modules B and C are both included in your program, then at runtime we have to decide what any as? Hashable should do, given that (for example) the two X: Hashable conformances might have different hash values. There are a few options here:

  1. Crash the program, because we've hit an ambiguity and ambiguities are fatal at compile-time
  2. Arbitrarily select one of the conformances; optionally warn the user what we did
  3. Try to rank the conformances in some manner to give a well-defined answer, e.g., by using some information about the module in which the as? occurs
  4. Refuse to choose a specific conformance, and return nil instead so the program can continue

Doug

6 Likes

In your example, when Array conforms to P, the Array version of whatAmI() is the most specialized already, so you get the right answer. Add this to your example and it will better parallel @jrose's:

extension Array where Element: P {
  func whatAmI() { print("Array<P>") }
}
extension Int: P {
  func whatAmI() { print("Int") }
}

The output will be:

Array<P>
Array

That's the one that bothers me most. A protocol requirement is meant to be a point of dynamic dispatch, where you jump to a version of the code that's been customized for the concrete type... but we don't actually get all of the customization we want (or expect).

I'm less bothered by @jrose's example because I don't feel like a call to a function that is neither an overridable method in a class or a protocol requirement should allow different behavior with different types at runtime.

I appreciate that we're gathering a corpus of examples and opinions. One needs those to evaluate designs.

Doug

4 Likes

Doug, thank you for your time and patience. My first pass was a bit sloppy.

I now see in your example that getBSet() and getCSet() inherently provide disambiguation. So, there is no error at that stage. I agree that the error should occur upon use of == with two different types.

Right. There is no error unless both B and C are imported. If both are imported, the error is triggered when the function ambiguously refers to Set<X>.

Why do you say there is only a single type X? We get two different types of Set<X>, "because they use different conformances of X: Hashable." So, shouldn't the two different X: Hashable also be considered as two different types? And, then, when the program attempts to instantiate an X without disambiguation, shouldn't that result in a compile-time error?

Thanks again. Good stuff.

1 Like

There is a single type X, defined in A. It has a unique identity that is unchanged by it's conformances.

We have two different types spelled Set<X> in the source code because one is Set<X where X:Hashable comes from module B> and the other is Set<X where X: Hashable comes from module C>. One X, two Set<X>, because required conformances are part of type identity for uses of generic types.

X is not ambiguous. Trying to form the type Set<X> where two different conformances of X to Hashable are visible should be a compile-time error.

Doug

2 Likes

Hmm. In Jordan's example, why shouldn't the Array version of whatAmI() be afforded the most "specialized" treatment?

Yuck.

When I further amend the example by removing the requirement that protocol P have a whatAmI() method, the output becomes:

// Array<P>
// P

Is there a semantic model underlying why we have different behavior depending upon whether or not a protocol-provided implementation is a requirement of the protocol?

To me it feels natural that a change in the concrete type could change behavior. But, I'm troubled by the idea that a function could produce different behavior depending upon whether or not it happens to be a protocol requirement.

Got it. Thank you.

Can the existence of the duplicate Hashable conformances reasonably be detected at compile time at the point at which an X is instantiated, for instance as part of constructing the witness table for X? If so, should the conflicting conformances be considered an error?

Just to add my reaction as a humble user. For this particular example, my mental model of Swift's generics (which took a while to develop) allows me to not get surprised or confused. This example is in my opinion not showcasing any of the really-hard-to-understand parts. I include the example here again for completeness:

protocol P {
  func whatAmI()
}

extension P                      { func whatAmI() { print("P")        }  }
extension Array: P               { func whatAmI() { print("Array")    }  }
extension Array where Element: P { func whatAmI() { print("Array<P>") }  }
extension Int: P                 { func whatAmI() { print("Int")      }  }

func whatIsIt<C: P>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array<P>
  whatIsIt(x) // Array
}
test()

By looking at this program I can predict (and not get surprised) by the output. The generic function whatIsIt has a typeparameter C which is constrained only by C: P which means that the compiler knows nothing about C except what it knows about P. That is, it knows about P's requirement whatAmI() and can call that required method (as implemented by various particular Cs), but it does so without knowing anything about eg Element or Array, it cannot get any information from any if its call sites, it's just its signature that matters.

The only way to make whatIsIt print "Array<P>" too (which I guess might be what some would expect?) would be to rewrite the example in a way that lets the compiler know more/enough about C. As the example is currently written, it is clear that within the body of whatIsIt, the compiler has no idea about Element: P or that C can sometimes be an Array. It only knows that some C conforms to P and if that C happens to implement P's requirement rather than use a default implementation, it will call C's implementation.


That said, there are many other things I get confused by in Swift's generics, like this example which @dabrahams linked to in the OP. (Note that I do not have a clear expectation about what the intended/best/fixed behavior should be in that example, especially so when taking @Nevin's "fun fact" into account.)

But perhaps my confusion there is just caused by the same rules I claim to understand here, I haven't thought about it enough to know if that might be the case.

4 Likes

@Douglas_Gregor said “A protocol requirement is meant to be a point of dynamic dispatch“ and I completely agree. Also in you example the method that is declared conditionally when the Array’s Element conforms to P, I don’t see why the final output would be correct. For example, we could write:

protocol P { func whatIAm() }

...

extension Array: P {
    func whatIAm() { print(“Array”) }
    
    func whatIAm() where Element: P 
        { print(“Array<P>”) }
}

When written this way, I think the user’s expectation would be that since the second method is more specific it will be called instead of the first one, especially when considering that whatIAm() is a protocol requirement.

That will not compile:

protocol P { func whatAmI() }

extension Array: P {
  func whatIAm() { print("Array") }

  func whatIAm() where Element: P { // ERROR: 'where' clause cannot be attached to a non-generic declaration
    print("Array<P>")
  }
}

Thanks for all the replies, everybody! I've had a busy end-of-week, but I'll try to respond in the next few days.

Oh sorry, I was compiling on 5.3. Nonetheless, It's the same as what you wrote. The point I wanted to make is that the expectation of the user when seeing the code written this way - I think - would be that the more specialised method (the second one) be called.

Ah, I didn't know that was supported in 5.3, Here is the complete program with your modification, which compiles with Swift 5.3:

protocol Q { func whatAmI() }

extension Int: Q {
  func whatAmI() { print("Int") }
}

extension Array: Q {
  func whatAmI() { print("Array") }
  func whatAmI() where Element: Q { print("Array<P>") }
}

func whatIsIt<C: Q>(_ value: C) { value.whatAmI() }

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array<P>
  whatIsIt(x) // Array
}
test()

The result is the same, and FWIW it's still what I'd expect from that code, for the same reasons as before:

(P being Q in this modified example.)


I can see the point, and I remember having to go through a phase of "relearning" (because I was so used with C++ templates). The thing is that in the context of whatIsIt<C: Q>(…), C cannot get more specialized than that; the compiler's knowledge stops at C: Q, and Q says nothing about C having an Element.

This is so funny. My reaction of "Yuck" was because I would want to see a result of either P or Array<P>, but definitely not the middle ground of Array.

When you say, "it does so without knowing anything about eg Element or Array, it cannot get any information from any if its call sites, it's just its signature that matters," I don't understand what you mean. If that were so, how does whatIsIt know enough to call Array's implementation of whatAmI, but not enough to call Array<P>'s implementation of whatAmI?

All of this is getting a bit deep in the weeds. That may be my fault. I'd like to steer back towards the central point of the pitch:

2 Likes

Then I suppose we could at least do what I've proposed for constrained generics, e.g. by tucking the information into (a copy of) the first witness table. If there's truly no way to extend the information passed to unconstrained generics, it would mean…

I hope this is irrelevant because of what I've learned below about distinct types

making the semantics of dynamic downcasting a value of generic parameter type to a protocol existentials inconsistent with those of generic dispatching in some cases. We'd have the option to limit the inconsistency to cases where the generic parameter is unconstrained. Happy to elaborate more if this isn't obvious to you. I'm still hoping there's a way out of this jam, but I don't think it's fatal to the idea.

I must admit I'm a bit confused as to why several people have posted in this thread about addressing that bug via compiler changes, since it has a fix in the library. If it's because you think the existing standard library code should work as written, then that's news(!) to me and we're into new territory in two dimensions:

  1. We'd have an opportunity to describe the rules that make that code work
  2. We'd be changing the semantics of existing code

Others will disagree I know, but I'm not at all opposed to #2. In fact think it is necessary in some areas of the generics system (whether for SR-12881 remains to be seen). I'm an enthusiastic supporter of #1, which, it seems to me, is obviously a precondition for #2. Also before we move on to #2 I'd like to talk about how the rules of #1 line up with the solutions to other problems in the generics system that seem closely related to me. In particular:

  • Problems with algorithm specialization and conditional conformances.
  • Problems with conformances in multiple modules (edit: good news—I see this one might almost be considered fixed if someone would just document how it's supposed to work!)
  • The inability of anyone other than the owner of a protocol to extend the set of specializable algorithms that operate on models of the protocol.

I believe that it's possible to resolve all three of those within the implementation model I'm pitching here, which is part of why I pitched it. If you'd rather talk about it in terms of programming models, that would be great. As I noted at the beginning of the thread I've had some trouble making headway with that tack, but I'm happy to try again.

Thanks for asking, but I'm a bit bewildered by the question. I filed SR-12881 to report that library components aren't working properly. As I'm sure you know, I've filed plenty of bugs about the generics system recently, but that isn't one of 'em. Mostly though, I don't have any grasp on how what you've described generalizes or what rules would govern the semantic change going into effect. Obviously, I'm not interested in a compiler change that just affects that one example, and I'm pretty sure that's not what you mean to propose, but please can you describe the programming model or the implementation model in a way that tells me more than just how you expect the compiler to deal with one or two pieces of code?

I'm aware.

You mean, it already does that? That's wonderful! I suppose one can square this with Jordan's assertion that type metadata is unique for a given type because they're considered different types, but that's actually just what I'd like to see happen with scoped conformances and basically would allow the conformance table I've pitched in my implementation model to be stashed in the value witness table.

I hate to ask, but is any of this (and the implications for program semantics) written down somewhere?

I'm totally fine with that (not the runtime crash, but that multiple overlapping conformances affects type identity).

Great question! This sounds tricky at first but the more I think it through, the more obvious the answer becomes: the cast fails (produces nil) unless the type metadata for Set<X> at the point of the cast matches the type metadata pointer for any, i.e. unless the X used to form any conforms to Hashable the same way that an X instance would if it were created locally. Simply put, if the type of any and the local meaning of Set<X> are distinct, the cast fails.

This one is easy; I expect the semantics laid out in the scoped conformances pitch. The cast succeeds iff a conformance of X to Hashable was visible in the scope where X was first bound to a generic parameter or the X instance was converted to an existential. The Hashable existential instance behaves according to that conformance.

Yes please! I just want to start by getting to a common language for describing the semantics we want. Having previously failed to have the discussion from an abstract programming model POV, I pitched an implementation model here that

  • I could easily understand
  • Seemed consistent with your stated intent
  • Was flexible enough to express the semantics I want, if deployed in one particular way
  • Seemed implementable (and apparently it is?) so would not immediately draw fire on that score (#FAIL!)

No surprise; I didn't lay out any semantics in this pitch, because every time I try to describe the semantics I want—and I promise I'm not pointing any fingers here—it feels to me like someone more familiar than me with the current implementation either:

  • declares the semantics unimplementable and out of the question, or
  • proceeds from the current implementation as a given in a way that closes off discussion of possible semantics.

By pitching a possible implementation model, I was trying to set up a basis for the discussion that wouldn't immediately lead to a dead end.

Sorry I couldn't answer the first question; I just don't have the context I need to do so yet. I think I answered the other questions pretty solidly, though. But my actual goal here was to lay the groundwork for any kind of productive discussion of semantics at all. In the thread you referenced, I asked you many direct questions to try to get a handle on your design intent. When the reply tersely declined to address most of them I decided that maybe I needed to try a different angle. I'm very glad that we seem to be engaging productively on this topic now!

Amen to that, brother! I've just been trying to unlock the semantic decisions from the brain of the person I presume to have made them. And small examples are definitely necessary, but as a means of illustrating semantics that can be described more generally.

4 Likes

Looking at the overall protocol system, the behavior of non-required methods declared in protocol extensions is the source of much confusion about which available version of a method will be called in a given situation.

For instance, see Paul Hudson's discussion of this aspect of the protocols system. After noting the surprise that it causes, he explains:

By declaring a [required] method in the protocol you’re allowing conforming types to override it; if you don’t [i.e., if you declare the method only in an extension of the protocol], they can’t [override that method] unless they have a specific type.

The bracketed portions are my additions to provide context.

Unless I'm mistaken, the intention is: a protocol's non-required method is not overridden by a conforming type when that type is used as an existential. That behavior is a feature. Hudson explains that the purpose of the feature is to provide uniform, non-overrideable behavior for types that conform to a protocol.

However, that non-overriding feature exists only when the conforming type is treated as an existential type. If the conforming type is used as itself, it is able to override the method otherwise supplied by the protocol extension.

All of this contributes towards what is a pretty complicated mental model as to which version of a given method will be called in a given context.

Unfortunately, the conformance behavior of non-required methods declared in protocol extensions is not formally documented (AFAIK). In fact, there isn't even a formal name for these non-required protocol methods (AFAIK).

Also, please see this proposal regarding the user having more control over how this aspect of protocol conformance is handled.

There are a variety of other macro aspects of the system that have similar impacts on the mental model, such as the interplay between the class-subclass hierarchy and protocol conformance. Perhaps someone else could offer a discussion of that aspect of the matter.

1 Like

I agree that the system is complicated. It took me a lot of time, questions and experimentation to build a (mostly) working mental model, and I often see people on these forums struggle with the same issues as I once had. I also agree that the system (its intended behavior) really needs to be documented and explainable in a way that is accessible, terse and complete.

3 Likes