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

There are already many ways to cause that to happen in Swift. Here's one I whipped up in a few minutes; just add a conformance of X to P. I don't know what you mean by “breaking”; this one causes a compilation error, but causing a semantic change is even easier.

protocol P {}
extension P {
  func foo(_: Int?) {  }
}
protocol Q {}
extension Q {
  func foo(_: String?) {  }
}
struct X : Q {}

// ============== Downstream ============

X().foo(nil)

Thanks! I may do so, but if so I'll start a separate thread and cc you, since this is about the language design.

Sure, thanks for the small example. That said, I think you'll agree that there's a difference between the likelihood of accidental name collision versus a language feature that is hard to use without creating the same problem. :slight_smile:

I understand this sentiment of wanting to express something and be willing to accept some limitations it might come with. However, I think there are many drawbacks to potentially adding a language feature expanding the functionality of protocols which you can only use in an app context. Protocols are used extensively throughout the Swift ecosystem, be it apps, frameworks or SwiftPM packages. If we add a language feature that you can only use in an app, it means that frameworks and SwiftPM packages cannot make use of this feature. It also prevents people from lifting out common code across their apps into a common framework/package.

There is a less ergonomic solution today that you can use -- enums. Enums precisely model a closed-world, although changing code that is relying on protocol-based patterns to use an enum is not straightforward.

I’m too tired to have really thought this through, but it seems like that wouldn’t be an issue if the compiler has access to the library’s/package’s source code. If they’re statically linked, anyway... not sure about dynamic linking. Either way, though, I can’t really think of a scenario where you wouldn’t have access to your own library’s source code, and I think most SwiftPM packages are hosted on GitHub.

Indeed, and as you say, this is less ergonomic. For one thing, it requires a kind of "guts-out" design (in that the calling code is responsible for "tagging" the value) that sets my teeth on edge. Encapsulation and information hiding isn't just good for public module API. In a large project, it can be essential in organizing internal code.

Alas, Swift doesn't have the best story in this arena, as I've mentioned before :pensive:

Right, we only have compiler-automated picking today, but we ought to also have a mechanism by which a conformance could be specified directly. This is why we have a lot of the paranoid restrictions around conformances today, like "no overlapping conformances", "no private conformances", and so on, because they would make it easier to end up in a situation where the compiler can't make a consistent automated choice, and we'd need "named" conformances or something to let source code direct it.

Overlapping conformances might get you somewhat closer to what you're looking for, since it would let you describe different conformances for different constraints:

protocol P {
    static var isEquatable: Bool { get }
}

extension P {
    static var isEquatable: Bool { false }
}

extension P where Self : Equatable {
    static var isEquatable: Bool { true }
}

// strawman syntax `named <identifier>` to name a conformance
extension Array: P named AnyArrayP {}

extension Array: P named EquatableArrayP where Element: Equatable {}

func foo<T: P>(x: T) { print(x.isEquatable) }

// strawman syntax `using <identifier>` to pick a specific conformance
foo(x: [1, 2, 3] using AnyArrayP) // prints false
foo(x: [1, 2, 3] using EquatableArrayP) // prints true

but that still has the issue where, in a generic context where you have a T without an Equatable constraint, you could only pick the AnyArrayP conformance.

Given a conformance, the set of witnesses it uses is the same across all generic arguments. We effectively look up the witnesses in the context of the place where the X: P conformance is declared, based on its set of generic constraints. We only generate witness tables to instantiate different associated types, or to handle protocol resilience when an ABI-stable library introduces new protocol requirements with default implementations that need to be injected into existing binaries.

The main problem with "looking it up" is that there isn't a good way to guarantee a good answer because of the possibility of multiple conformances, and the ability for dynamic code loading to change the behavior of lookup at runtime. All of our generics features thus far avoid depending on global lookup.

One possibility might be to add formal optional constraints to the language, so that you can write P as:

protocol P where Self ?: Equatable { ... }

This would give the type system enough information to try to collect an Equatable conformance up front when forming a P conformance, and plumb that information through witness table instantiation so that we know it's dependent on Equatable conformance.

As far as #2 goes, I think the design of traits and type classes in Rust, Haskell, and other languages would be informative. In those languages, default implementations are explicitly declared as such, and protocol conformances are established in dedicated declarations. This makes it possible to diagnose up front when declarations fail to fulfill their roles. We've been using warnings to softly nudge users in the direction of using one-extension-per-conformance, which gives better near-miss diagnostics, but we don't currently really have a good way of guaranteeing good diagnostics in the face of potentially surprising behavior.

3 Likes

I made an example a couple years ago demonstrating how to conflicting conformances were able to slip past the compiler. The code doesn't seem to build anymore, instead it fails with a linker error. Do you know if that linker error might be related to the conflicting conformances?

@dabrahams you may find it interesting to look at the example: GitHub - anandabits/Incoherence: An example demonstrating the "incoherent instances" problem in Swift.

Probably a bug relating to them, yeah.

Quite. I am no fan of negated or disjunctive constraints.

And requires explicit disambiguation at the use site. I'm trying to allow declaration sites to be more explicit/clear/expressive about what's going to happen at use sites having no explicit interventions.

[Just for my general edification, could you give an example of the former?]

Regardless of where it happens today, it seems like, if we can afford to generate witnesses dynamically for the purposes of ABI-stable library evolution, we can probably also afford to do it (if necessary) to enable other capabilities of ABI-stable libraries. Of course I'd rather avoid it…

I've always taken a “scoped concept map” view of how conformance lookup should work, in which what gets “passed down” is the scope where the generic parameters are bound to concrete types, and conformances are “looked up” in that scope. That model, AFAICT, prevents dynamic loading from having any effect on the semantics of generics.

I'd like to hear more about what problem you see with multiple conformances, and whether or not that could be addressed the same way.

Now, that begins to get at what I'm aiming for! It seems as though there's something about the complete independence of the conformance declarations that, at least in this case, is at odds with the intention of the author of P (uh, me). I was thinking of that code as a “system” when I wrote it, but it doesn't quite act that way. Syntactically, maybe it would make sense to have a way to group these conformances together so they can be considered as one, which I presume would make the ?: Equatable thing unnecessary as it could be deduced from the other conformances in the group. Another approach would be to grant special status to file or module boundaries, gather all the conformances within them, and consider them together.

Yeah, that's a good point; I'll do some digging. You're a polyglot, Joe; any other specific recommendations of languages to look at?

That sounds similar to how Swift protocol conformances try to work, by capturing concept/protocol conformance information from their environment at instantiation time. It seems like with the "scoped concept map" concept you would still have the issue where, outside of up front declaration of the relationship between P and Equatable, you'd be required to grab information "out of scope" in order to fulfill the conditional witness to isEquatable. Having a way of declaring up front the conditional aspects of P conformance with ?: or something similar might be enough to fix that problem.

I think Rust's model is probably the closest to Swift, though they do allow specialization as an experimental feature (with the drawbacks that that does rely on global coherence of conformances and whole-program information, which are not really options for Swift's compilation model). I think the way Rust handles impl conformance declarations and default implementations is a good model, though.

2 Likes

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.

Having a way of declaring up front the conditional aspects of P conformance with ?: or something similar might be enough to fix that problem.

Not having the up-front declaration is obviously more work for the compiler, but it doesn't seem like a requirement. I'm not dead-set against doing that up-front declaration, but unless I'm missing something important, it's something we should decide to require or not based on what makes the best language design for users.

I think Rust's model is probably the closest to Swift, though they do allow specialization as an experimental feature (with the drawbacks that that does rely on global coherence of conformances and whole-program information, which are not really options for Swift's compilation model). I think the way Rust handles impl conformance declarations and default implementations is a good model, though.

I'll spend some time playing with that and see what I can learn, thanks.

Thanks, I took a look. I've always assumed that because Swift tries to make protocol conformance “truly, semantically, dynamic,” it would have to (at best) pick an arbitrary conformance in some situations… But I created a simpler example so I could do some experimentation, which seems to demonstrate it's much worse than that, and this part of the compiler is nondeterministic, if not insane.

https://bugs.swift.org/browse/SR-12513

1 Like

We are well aware that the implementation is not very robust in the face of multiple conformances, because there are many places in the compiler where it ought to carry conformance information forward but gives up and does global lookup again. The intended semantics should be that you get the one conformance that's visible at the point of use (or else an ambiguity if there are more than one), and that generics with protocol requirements which get instantiated with different conformances end up instantiating different types.

3 Likes

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.

You aren't declaring the conformance for Array<Int>, though, you're declaring the conformance for Array for all Elements, 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>.

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

3 Likes

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

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:

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

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.

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:

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

5 Likes

I might be asking about something obvious here but isn't this what is explained in this and this section of SE-0143, ie:

As noted in the section on 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.

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.

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, 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:

    • New language features to describe requirement specializations explicitly
    • Warnings to be issued whenever something in a protocol extension could match a requirement from a less-refined protocol.
    • An annotation that you can add to such a protocol extension to denote, “yes, that's OK, I intended to shadow that requirement and I know it's not going to provide an implementation of the requirement”

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.

3 Likes