SE-0309: Unlock existential types for all protocols

[Joe_Groff]

If an associated type is inherited from a parent protocol, then it is not distinct. If P and Q were independent protocols that each declared an associated type with the same name, then in the composition P & Q, the associated types are formally independent.

[sighoya]

Ah I see, this is even the case in the proposal, thanks.

[filip-sakel]

@Syre

Maybe I just don't get it, can someone explain to me the benefit in this example compared to:

let collection: Collection<Self.Element == Int> = [1, 2, 3]

With compiler optimizations and the constraints on existential types, like that in your example, I see how generics and existentials may seem like the same abstraction mechanism. However, they offer quite different capabilities.

Adding any will hopefully discourage overuse of existentials, as the some generics counterpart will have the same syntactic weight, yet it will guarantee consistent performance. Of course, existentials are useful for heterogeneous collections and dynamicity. However, generics are a very capable abstraction that taps into Swift's rich type system and covers most of our needs. Therefore, trying to optimize existentials to make them act like generics would solve quite a limited problem, while still being a complex feature to implement.

In your example, if we were required to use any but instead opted for some, we would benefit from more predictable and consistent performance.

[GarthSnyder]

I'm really happy to see this issue being worked on. It's been resting in the "eventually" bucket for a long time!

This is a thorough and thoughtful proposal. From a technical perspective, SE-0309 looks pretty effective at squeezing out as much of the latent potential of existentials as possible while avoiding both performance degradation and fundamental or incompatible changes to the language.

However, it involves so many type-theoretical limitations and edge cases that I'm skeptical this scheme can be explained in language comprehensible to the average Swift programmer. It's far beyond the complexity of, e.g., generics.

I'm wary of the C++ effect, where every generation of the language seems to introduce a slew of patch-over features and special cases designed to overcome limitations introduced by previous versions of the language. I would hate to see Swift go down that road, and this proposal feels like something of a wrong turn in that regard.

There's a section of the proposal that floats the idea of provider-side marking of APIs to delineate functions that are known to be accessible through generalized existentials. It's not clear to me based on a first reading whether all functions can be so simply categorized (I would guess not). But in any case, I'd like to see this idea explored in more detail as part of the base proposal.

Am I correct in thinking that the current intention is to allow any old protocol to be treated as a generalized existential? Any given use of a GE might be rejected by the compiler with a cryptic error message, but there's no barrier to attempting to access arbitrary protocols as GEs. If so, this seems like a recipe for developer frustration because understanding the real issues underlying the errors is likely to be nontrivial.

Requiring protocols to be explicitly GE-enabled would go a long way toward shifting the need to understand the details of the GE implementation onto API developers. It might be worth considering this as a usability issue even though there doesn't appear to be any particular technical reason for it.

[CTMacUser (Daryle Walker)]

@aerobounce

Thanks for taking your time.

@sighoya

• ABI constraints for the old syntax (without any ) exist

• any P seems to be a nice dual to some , simply writing the protocol name make it hard to know which kind of existential we mean here ( some or any )
• a protocol is theoretically not a type, just a constraint/predicate, but with this proposal we would also refer to the existential type (the protocol as type), instead this should be disambiguated with additional syntax to make the distinction more clear

@Karl

IMO, the benefit of having new syntax would be if it could clearly distinguish type erasure from generic code.

Those totally make sense!

I think in an older thread, someone said that Rust had the same problem. The type for existential boxes over a trait(?) was spelled the same way as referencing the trait directly. They moved to an introducer ("impl"?) too.

[cukr]

@CTMacUser

Introduce Any<P> as a better way of writing existentials

At one point in history rust language was in the same place as swift now - they found out that using just the name of the trait (protocol) to denote the trait object (existential) is a bad idea. Their solution was to use the word dyn which is similar to impl (their equivalent of some) https://doc.rust-lang.org/edition-guide/rust-2018/trait-system/dyn-trait-for-trait-objects.html I think we should use any (or maybe another short word) to preserve the symmetry, just like rust did dyn Foo - imp…

[anthonylatsis]

@xAlien95

In Swift, until now, type erasing has been an explicit action made by the user. An heterogeneous array results in an error instead of a warning

let array = [1, "two"]
// error@-1: Heterogeneous collection literal could only be inferred to '[Any]';
//           add explicit type annotation if this is intentional
// [fix-it]  Insert ' as [Any]'

and you need to explicitly add as [Any] in order to be able to compile your code. I would like the same treatment for associated types.

Also, there is a subtle distinction between the two: whereas such a heterogeneous array literal may still be explicitly ascribed to another sensible type, an unconstrained associated type can really only be represented as Any.

@xAlien95

As a general rule (and under the assumption of expanding opaque types to be available also in non-return positions and as a tool for expressing unnamed generic parameters), I wouldn't distinguish between covariant and contravariant positions and would indiscriminately replace Self and associated types with opaque types of their upper bounds.

@GarthSnyder

I'm wary of the C++ effect, where every generation of the language seems to introduce a slew of patch-over features and special cases designed to overcome limitations introduced by previous versions of the language. I would hate to see Swift go down that road, and this proposal feels like something of a wrong turn in that regard.

The concept of path-dependent types is what we envision interfacing with existentials to land at eventually, and we were careful to make sure the current proposal in all its intricacies does not interfere with a source-compatible future transition. But I doubt things can sort themselves out by making use of opaque types, which are still dependent on and invariant in the generic parameters of the enclosing context (Self in our case).

[anthonylatsis]

@GarthSnyder

Am I correct in thinking that the current intention is to allow any old protocol to be treated as a generalized existential? Any given use of a GE might be rejected by the compiler with a cryptic error message, but there's no barrier to attempting to access arbitrary protocols as GEs.

I am not exactly sure what you meant there. The solution allows any protocol to be used as a type, but a member access on a value of protocol type may still be rejected with an error message showcased in the Diagnostics section. The latter can already happen today with protocol extension members. In other words, we are getting rid of the artificial type-level limitation in favor of the already-existing value-level limitation, which is a type safety barrier we can sometimes reasonably set aside with the help of type erasure.

[Syre]

Thanks for the explanation Filip, I now understand the motivation. Still, I think users will probably just learn that "any P" is the path of least resistance. However, I also don't have a better solution to offer at the moment.

[ryansobol]

@Syre

Still, I think users will probably just learn that "any P" is the path of least resistance. However, I also don't have a better solution to offer at the moment.

There’s certainly some truth to the saying that when you only have a hammer, everything looks like a nail. However, there’s also some seriously talented teachers in the Swift community, which hopefully counts for something.

Take, for instance, my favorite article on this very subject–A Protocol-Oriented Approach to Associated Types and Self Requirements in Swift by Khawer Khaliq. Though the article will need a few updates if this proposal is accepted, it meticulously demonstrates a variety of techniques to completely avoid compiler errors that are common when misusing associated types and self requirements in protocols.

Not to sound too hyperbolic, but it will kind of fall to all of us in the Swift community to follow exemplars like Khawer. In short, we will need to teach precisely when and when not to reach for the hammer if the any P construct is accepted into the language.

[Alejandro (Alejandro Alonso)]

I am a huge +1 on this.

I'm somewhat disappointed that this didn't go the extra mile and include any P as well, but I can see the rationale to break it up into parts. My only concern now is that we won't get to any P quick enough and people are going to start using existentials more and more making the day that we introduce any P more of a headache. I would like to see any P tackled on the same Swift version that this is introduced (I know none of the proposal authors have a say into that) so that when people use this proposal it's coupled with any P.

Overall, I'm extremely happy this is finally going through and huge props to the proposal authors for an amazing writeup!

[dabrahams (Dave Abrahams)]

@GarthSnyder

However, it involves so many type-theoretical limitations and edge cases that I'm skeptical this scheme can be explained in language comprehensible to the average Swift programmer. It's far beyond the complexity of, e.g., generics.

I happened to be browsing by, just out of nostalgia. I'll add that this is an effect I have always worried the addition of generalized existentials would have. I'm disappointed to see that the proposal doesn't seem to include a careful examination of these implications along with proposing mitigation strategies.

Requiring protocols to be explicitly GE-enabled would go a long way toward shifting the need to understand the details of the GE implementation onto API developers. It might be worth considering this as a usability issue even though there doesn't appear to be any particular technical reason for it.

That was one of my earliest proposals for a mitigation strategy. Is it enough? I'm not sure. To me it seems like it helps with the surprising-API-non-availability problem, but maybe less so the language complexity effects.

More broadly, my concern here has always been that in an eagerness to “just get past the restriction already,” we'd brush away the downsides and fail to do an enthusiastic investigation of just what they are, how bad they might be, and how we might counteract them. The sense I get from the proposal is, “we thought about a couple things but decided not to do anything,” which I'm not sure is really adequate, especially after such a thorough exploration of the space from @Joe_Groff.

FWIW-ly y'rs,
Dave

[wowbagger (冀卓疌)]

I find myself somewhat confused while reading the discussions about the variances in Swift's types. Is there a general guide/rule somewhere that I can read up on what positions are considered by the type constructor as covariant, invariant, and contra-variant?

[anthonylatsis]

@wowbagger

Is there a general guide/rule somewhere that I can read up on what positions are considered by the type constructor as covariant, invariant, and contra-variant?

These four should serve the purpose:

• Tuple types are covariant in their element types.
• Generic types are invariant in their generic parameters except for a select few Standard Library types (Optional, Array, Set and Dictionary), which are covariant.
• inout types are invariant in their underlying type.
• Function types are contravariant in their parameter types and covariant in their result type.

Unlike with conversions, note that the part about Optional, Array, Set and Dictionary being covariant does not fully apply in our case (the covariant relations are listed at the end of the Proposed Solution).

[xwu (Xiaodi Wu)]

@anthonylatsis

note that the part about Optional , Array , Set and Dictionary being covariant does not fully apply in our case

Was the omission of Set from the corresponding proposal text deliberate?

[anthonylatsis]

@xwu

Was the omission of Set from the corresponding proposal text deliberate?

Yes, covariant type erasure in generic parameter position can cause us to run into the self-conformance problem when there is a conformance requirement.

[wowbagger (冀卓疌)]

Thanks!

Is there an explanation or rationale behind these 4 subtyping rules as well? Sorry if I'm asking too much. I want to understand the rules instead of just memorising them.

[suyashsrijan]

There's a nice article by Mike Ash that talks about the basics - mikeash.com: Friday Q&A 2015-11-20: Covariance and Contravariance and there are some forum posts about it w.r.t generics here and here.

[anthonylatsis]

@wowbagger

Is there an explanation or rationale behind these 4 subtyping rules as well?

Subtyping rules are generally determined via the Liskov substitution principle, and then variance comes in for compound types to describe how subtyping in a component can relate to subtyping in the compound.

Following the substitution principle, it so happens that the parameter types of f2 must be supertypes of those of f1 and the result type of f2 must be a subtype of that of f1 for f2 to be a subtype of f1. Tuple types are just arrays of element types, and we can prove by induction that subtyping relations in components are propagated out to the tuple. A similar reasoning can be applied to the few Standard Library collections that are covariant by means of hardcoded built-in conversions. Other generic types are invariant in their generic parameters because the compiler does not know how to convert from one specialization to another in the general case. Regarding inout types, I think the reason they are invariant is that deep down, they resemble a generic pointer type like UnsafePointer, but I can't speak to whether UnsafePointer itself is deliberately kept invariant.

[Paul_Cantrell]

+1 to this, and hooray! Long awaited, much needed. Heterogenous [P] collections remain a vexing wall inside the maze of Swift, and this would easy some of the pain. So pleased to see this line of work proceeding at last.

Is there a snapshot build I can use to experiment with this? (Apologies if I missed the link.)

Two questions…er, well, question clusters:

---

First, is there any value in exposing non-covariant Self as Never rather than making the method disappear altogether? For example, the Equatable existential type would have:

static func == (lhs: Never, rhs: Never) -> Bool

I can imagine one might want to deal generically with method references — reflection, say, or generating diagnostics — without actually needing to call the method. I admit that I don’t have a specific compelling use case for this, and the harm it would do to the already-confusing diagnostic messages would be substantial. Still, worth asking.

I can also imagine that there might be situations where the compiler might be able to determine a better lower bound than Never from generic constraints etc. Does such a situation exist? (For example, the compiler might be able to deduce a less-restrictive bound for a private protocol, where all possible implementing types are known at compile time.)

---

The second question really just amounts to, “Do I understand the proposal correctly? If so, great!”

Tim Ekl’s nice post on this proposal got me thinking about this limits of this proposal. He considers this example:

protocol Shape {
    func duplicate() -> Self
    func matches(_ other: Self) -> Bool
}

Even with this proposal, the following doesn’t work:

func assertDuplicateMatches(s: Shape) {
    let t = s.duplicate() // t could be any Shape, not nec same as s
    assert(t.matches(s))  // ❌
    assert(s.matches(t))  // ❌
}

…which makes sense, because we need to guarantee to the type checker that s and t actually have the same type:

func assertDuplicateMatches<SpecificShapeType: Shape>(s: SpecificShapeType) {
    let t = s.duplicate() // t also has type SpecificShapeType
    assert(t.matches(s))  // ✅
    assert(s.matches(t))  // ✅
}

(Aside: I like the spelling any Shape better every time I see it in context. It would make the problem with the first version of assertDuplicateMatches much easier to see.)

However, if I understand correctly, the following code still won’t work even if this proposal is accepted:

let testShapes: [Shape] = […]
for shape in testShapes {
    assertDuplicateMatches(shape)
}

…because the compiler can’t determine a non-existential SpecificShapeType for the call to assertDuplicateMatches. Do I have that right?

Given that, I take it this implies the Shape existential does not actually conform to the Shape protocol? The proposal doesn’t say this explicitly, but it must be so. (Given that, what is the error message here? Seems like one that requires extra-special care.)

Given the above, I take it that this future direction in the proposal:

Make existential types "self-conforming" by automatically opening them when passed as generic arguments to functions. Generic instantiations could have them opened as opaque types.

…would make the code above work as written?