SE-0309: Unlock existential types for all protocols

[Avi]

It appears that the compiler simply does not allow it.

protocol P { func moo(p: Self) }
struct S: P { func moo(p: S) { } }

func f() -> some P { S() }

let p: P = f() // Protocol 'P' can only be used as a generic constraint because it has Self or associated type requirements

It's an interesting hole in the design. The compiler has no problem with the function declaration, but doesn't allow callers.

[edit]

If the explicit type is removed:

let p = f()

it works fine. Presumably because the compiler knows the static type of the func, even though it's hidden from the caller. For example, you can't call moo(p:) on the return value, because the compiler forces you to act as if the concrete type is unknown. However (p as! S).moo(p: S()) works, because dynamic casts are allowed.

[hassila (Joakim Hassila)]

I’m not envious of the person who gets to document this in an understandable manner…

(to be on topic, the reflection is that careful conceptual documentation explaining this with clear examples is likely super important, given the sprawling discussions)

[sighoya]

That's the reason why I'm asked for documenting the terms mentioned in the proposal in the type spec.

[Jumhyn (Frederick Kellison-Linn)]

@Avi

Opaque types require the caller to always treat the return value as the existential.

An opaque requires the caller to only use members of the API defined by the protocol, but that's not the same as treating the return value as an existential—in the language model, it is treated as some unknown concrete type which conforms to the specified protocol. That's why you can do this:

func foo<T: P>(_: T) {}
foo(f()) // OK, 'some P' is known to be a type which conforms to 'P'

but not this:

foo(f() as P) // Upcast from 'some P' to 'P' succeeds, but existential 'P' does not conform to 'P'

@Avi

For example, you can't call moo(p:) on the return value, because the compiler forces you to act as if the concrete type is unknown.

Actually, you can call moo as follows:

let p = f()
p.moo(p: f())

IMO, this is where the @_opaqueReturnTypeOf SIL annotation is illuminating. Back when opaque types were first introduced, there were discussions around giving a language-level spelling for this annotation, such as #returnType(of: p.moo) which would allow the user to express "the opaque type returned by p.moo, whatever it is."

Currently, no such spelling exists, but the example above shows that such behavior is currently available in the language model, it’s just somewhat difficult to access. An opaque type is inherently bound to a declaration, and the compiler allows the user to observe the fact that the opaque type's identity is stable across all uses of that declaration—you're just not permitted to observe the actual identity of that type beyond "some type that conforms to P" (modulo dynamic casts, of course).

[Avi]

Thank you for explaining it so coherently.

[Joe_Groff]

@1oo7

I really hope this "suite of attributes for controlling optimizer behavior" can soon be added to Swift, because the most legitimate complaint I've heard about Swift recently from our principal engineer (who is primarily a Java/Kotlin dev) relates to the fact that Swift has unpredictable/inconsistent treatment of how it resolves which overloaded generic method should get called.

Their expectation is that the most specialized method should always get called, since allows you to write code that is "closed for modification but open for exetnsion".

You see, if the consumer of a module can add more specialized methods in extensions, which overload less specialized methods in the base implementation, then they can extend and modify its behavior as if it were an open class and they were overriding its methods with a subclass. Except now you don't have the limitations of class inheritance to worry about—it's all protocols.

However currently we can't really do this in Swift, and clearly we'd need something like an open protocol to accomplish it. And of course if we're doing an open protocol then people will likely want a sealed protocol too.

I'm not sure what you mean by "open protocols"—protocols today are already "open". Overloading in Swift is not meant for generic specialization, and optimization will never change how overload resolution works. Type-specific overloads will never be picked in generic code because Swift will pick one overload for any call site in source code—you can "jump to definition" on any call site and it will have one declaration to jump to. If you want to provide specialized behavior for certain types, you need to make that declaration be a protocol requirement, and have your types with specialized behavior conform to the protocol.

[filip-sakel]

I think there’s quite a lot of confusion surrounding protocols’ dynamic dispatch, where programmers may assume that a member declared in a protocol extension can be “overridden". Perhaps, a compiler warning could be emitted on declarations of conforming types that match declarations of the protocol extension:

protocol Being {}
extension Being {
  var isHuman: Bool { true }
}

struct Pet: Being {
  var isHuman: Bool { false } 
      ^~~~~~~~
  ⚠️ Declaration matches non-protocol-requirement ‘isHuman' of protocol
  ‘Being’ and will only be invoked on instance of type ‘Pet'; calling
  from a generic context requires that ‘isHuman’ be a requirement.
}

[Karl]

@filip-sakel

I think there’s quite a lot of confusion surrounding protocols’ dynamic dispatch, where programmers may assume that a member declared in a protocol extension can be “overridden".

It would be even better if we could create protocol extension members that were dynamically dispatched and could be overridden.

Today, I can add dynamically-dispatched members on a type by adding a retroactive conformance to a protocol I define. So conceptually, if I added the dynamic members to a new protocol I define, and was able to say “all conformers to Collection also conform to MyCollectionExtensionsProtocol”, I would be able to create a dynamically-dispatched protocol extension method.

According to the generics manifesto, we shouldn’t add this kind of retroactive protocol refinement because:

it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

But I don’t think that applies for fake protocols that are really just bags of extension methods. They wouldn’t have an utterable type for you to use with dynamic casting.

This is just a kind of mental model to explain how it could be implemented. I’m sure if it were implemented, it would be possible to do something cleaner than fake protocols containing bunches of extension members (or maybe it would be modelled in the runtime similarly to a protocol, with some kind of “extension witness table” or something).

[sighoya]

@Karl

“all conformers to Collection also conform to MyCollectionExtensionsProtocol ”

Maybe it suffices to provide:

extension MyCollectionExtensionsProtocol where Self == any Collection

for custom extension methods.

Additionally, you just need to implement the type any Collection for MyCollectionExtensionsProtocol.

This is the same in Rust with dyn Trait implementing Trait, maybe this is the computationally better solution to retroactive protocols.

[Dmitriy_Ignatyev]

It is mentioned in proposal: "Allow constraining existential types, i.e. let collection: any Collection<Self.Element == Int> = [1, 2, 3]".

What about opaque type? The question is not directly connected to the proposal, but anyway.
Will it be possible in Swift 5.5 to write
let collection: some Collection<Self.Element == Int> = [1, 2, 3] ?

[Avi]

@Dmitriy_Ignatyev

What about opaque type? The question is not directly connected to the proposal, but anyway.
Will it be possible in Swift 5.5 to write
let collection: some Collection<Self.Element == Int> = [1, 2, 3] ?

I don't see how that could work. Which concrete type is that supposed to be? How would the compiler choose? The array literal initializer has to invoke a constructor, but you've given the compiler no way to choose the intended implementation.

[ensan-hcl (ensan)]

@Avi

I don't see how that could work. Which concrete type is that supposed to be? How would the compiler choose? The array literal initializer has to invoke a constructor, but you've given the compiler no way to choose the intended implementation.

In Swift5.4, this works fine.

let collection: some Collection = [1, 2, 3]
print(type(of: collection)) // Array<Int>

Therefore, even if it were with constraint <Self.Element == Int>, perhaps it would still have type Array<Int>. I've never heard of such a constraint being enabled in Swift 5.5, though.

[sighoya]

@Avi

I don't see how that could work. Which concrete type is that supposed to be? How would the compiler choose? The array literal initializer has to invoke a constructor, but you've given the compiler no way to choose the intended implementation.

The literal itself has a type, the compiler just need to check if this type conforms to protocol Collection with associated type Element=Int

[jayton (Jens Ayton)]

The “ Improving the UI of generics” design document/submanifesto discusses this kind of constraint, with the syntax some Collection<.Element == Int>, but it’s not part of SE-0309 or any other pitch that’s been made so far, so nobody can say “yes, it will be available in <some version number>”.

[Moximillian (Mox)]

First of all, although not directly part of SE-0309, the deeper discussion about existentials (and opaque types) has been extremely interesting to me, as it has views from both swift insiders and from outside. And it is relevant for the future features for existential, which were also highlighted in SE-0309. So thanks to all who have contributed.

@Joe_Groff

@Dmitriy_Ignatyev

In first case instance of SomeProtocol can have different underlying types. In second case Type is known at compile time.

Neither of these statements is always true. If you pass a value of known static type into an existential, then the compiler can see that and still specialize the function based on the type going in. Similarly, if you call the generic function with a dynamic type, the compiler does not necessarily know what that type is, and may not be able to specialize.

@Joe_Groff

There is an "existential specializer" pass that turns some functions with existential arguments into their generic forms, which allows generic specialization passes to further optimize them. You could maybe use @inline(never) to suppress specialization, but there still isn't a fully designed and developed suite of attributes for controlling optimizer behavior.

Now this is interesting. Since it's the compiler, not the developer who makes the decisions about performance characteristics (speed vs code size, for example), then to me it's actually no longer important to advocate for "correct" choice to be made regarding generics vs. existentials, which for me was one important reason for "any P"... Especially now that SE-0309 has been accepted.

So I guess where "any P" (as one of the possible solutions), would be still be potentially relevant are the places where:

1. you have to use generics, existentials wouldn't simply work. I guess SE-0309 implementation already has some error messages related to this, nudging you to the right direction?
2. you have to use existentials, generics simply wouldn't work (the obvious one being heterogenous collections). Is there a way to better inform developers about this?
3. future new features around existentials, and how to make syntax for those new features more understandable so that people get them right more often than wrong. One key place in my mind would be extension syntax for describing existential conformance to its protocol, which might be needed for protocols with associated types... if such thing makes sense:

extension any SomeProto: SomeProto { ... }

In a way I now find it understandable that the core team wants to defer the syntax change decisions to the proposals where new features would be introduced to existentials and then discuss the syntax in conjuction to those changes:

@Joe_Groff

We also know that the existential syntax will have to be expanded to allow for where constraints on associated types, and we don't want to prematurely introduce a new existential syntax without knowing how that new syntax will accommodate other necessary extensions.

The current situation is not perfect, but at least we got rid of the overly eager firewalls in SE-0309

[CrystDragon (Lincoln Wu)]

I haven’t seen anything related to dynamic casting or conformance checking is mentioned in the proposal, neither about existential metatypes.

Can someone clarify it for me, that if this feature is implemented, will we be allowed to write these codes:

let a = someObj is Hahsable
let b = someObj as? Hashable

let t = Hashable.self
let u: Hashable.Type
let v: Hashable.Protocol

Thanks a lot.

[filip-sakel]

Yes, these examples will work.

[anthonylatsis]

@CrystDragon

Can someone clarify it for me, that if this feature is implemented, will we be allowed to write these codes:

let a = someObj is Hahsable
let b = someObj as? Hashable

let t = Hashable.self
let u: Hashable.Type
let v: Hashable.Protocol

@filip-sakel

Yes, these examples will work.

Yeah, the proposal allows any protocol to be used as a type, and that is exactly how protocols are used in these examples (apparently, we should mention this explicitly).

[CrystDragon (Lincoln Wu)]

Thanks a lot!!
Really appreciate you guys' work.

[anthonylatsis]

Regarding the discussion around terminology

I think the practical meaning lies in understanding the differences rather than trying to break down the terms. Perhaps the reason the term "existential" refers primarily to protocol types and their values in surface-level Swift is the dualism between protocol types, which are formally defined via existential quantification (there exists...), and generic types, formally defined via universal quantification (for all...). The term seems to be somewhat historically tied to protocol-like types, although some types and generic parameter types may also be defined via existential quantification.

A value of protocol type is just a run-time container that can store anything as long as it conforms to the protocol. The whole point of this run-time container indirection is that the type of its contents may change at run-time, and nothing is known aside from the existence of a conformance of the underlying (dynamic) type to the protocol (the identity of the underlying type is erased). As such, two distinct values of the same protocol type may simultaneously conceal values of different conforming types, as well as a single value of protocol type may conceal values of different conforming types at different points in time. The only thing that defines a protocol type is the protocol (the constraint that is imposed on the contents of the existential container).

// These are two values of the exact same protocol type, storing values
// of different conforming types. 
let int: Equatable = 0
var string: Equatable = ""

// The type of the contents can change dynamically.
string = true 

Consequently, it makes little to no sense to use a value of protocol type when the underlying type is known at compile time or the value is not expected to or cannot change (as in the case of int above or a function parameter).

---

some types are a purely compile-time concept. This means the underlying type is always known at compile time by design, eliminating the need for a run-time indirection. Despite the syntax, the identity of a some type goes beyond just the specified protocol and also captures the introducing declaration and any generic parameters of the surrounding context, thus preserving the identity of the underlying type.

func global1() -> some Equatable { 0 }
func global2() -> some Equatable { 0 }

func global3<T>(_: T) -> some Equatable { 0 }

// These are two values of *different* opaque types. 
// 'some1' has type 'opaqueResultTypeOf(global1)' (pseudo).
// 'some2' has type 'opaqueResultTypeOf(global2)'.
let some1: some Equatable = global1()
let some2: some Equatable = global2()

// These are two values of *different* opaque types. 
// 'some3' has type 'opaqueResultTypeOf<Int>(global3)'.
// 'some4' has type 'opaqueResultTypeOf<Bool>(global3)'.
let some3: some Equatable = global3(0)
let some4: some Equatable = global3(true)

The mapping from existential types to underlying types can be seen as a one-to-many relationship (every existential type corresponds to every conforming type), while the mapping from some types to underlying types can be seen as a one-to-one many-to-one relationship (every some type corresponds to a single conforming type).