[Pitch] Introduce existential `any`

Ah, right it's the .Protocol one here. :man_facepalming: Thank you.

Existential types in Swift are harmful because folks often reach for them by accident, or because they appear to be easier to use when they're really not the best tool for the job, not because existential types aren't a valuable language feature. And pragmatically, completely removing a widely used language feature is a nonstarter.

Existential types provide the ability to store values of any underlying concrete type that meets the given constraints dynamically. This is a different kind of abstraction than generics that allows for values with different concrete types to be used interchangeably as the same static type. One common use case for this is heterogeneous collections.

There's a more in-depth explanation of the difference between existentials and generics in the Type-level and value-level abstraction section of Improving the UI of generics


Heterogeneous collections are a common use of existential contains today, but there have been other features floated to solve the problem of heterogenous collections. For example, I once wanted to implement a map of [<S: SomeProtocol>.Type : [S : S.AssocType]], and was frustrated about the need to type the storage as [ObjectIdentifier : [Any : Any]]. @Joe_Groff suggested it might be worth supporting path-dependent types as a first-class language feature, which would eliminate the need for existential types here.

But that’s a hypothetical feature, whereas existentials already exist. And they can be used in combination with generics to build type-safe heterogeneous collections. I wound up hiding the type-erased map and writing new generic accessors around it.

Perhaps existentials will always have a place as a building block with which more sophisticated type-safe systems can be built.

type(of:) is an interesting case, and it finally helped me to understand what @DevAndArtist means.

TL;DR Syntax that @DevAndArtist is proposing is more related to generalised subtyping than to this proposal, and is still not sufficient to solve the challenge of type(of:).

My initial understanding was that proposed any Int.Type means any<> Int.Type, which makes no sense. But now I realise that actually @DevAndArtist means any<T: Int> T.Type, which makes sense, under assumption that there is generalised subtyping relation in Swift.

As @Joe_Groff explained, this won't help to express the existing behaviour of the type(of:), and nothing will. But may help to fix the behaviour of the type(of:).

I assume that current behaviour of type(of:) is not desired, but rather a limitation of the type system expressiveness. Desired behaviour is, I assume, the one of func type<P: protocol>(of: any P) -> any P.Type.

To have the same behaviour in the case of func type<T>(of: T) -> ???<T>, there needs to be a type expression ???<T> that resolves into any P.Type when substituting any P for T.

I think such type expression can be constructed, using 4 tools:

  1. Generalised subtyping <T: U>, or at least subtyping relation between type and protocol existential - <T: any P>
  2. Generalised existentials (any<T> T.Type where T: any P), or at least existential for subtyping relation, as @DevAndArtist is suggesting - any (any P).Type.
  3. Constraint for type being concrete, not an existential - using protocol <T: Concrete> or a keyword <T: concrete>. With generalised existentials this and a previous one allow us to write any<T> T.Type where T: any P, T: Concrete. Shortcut syntax probably would be any ((any P) & Concrete).Type.
  4. Knowledge that T: any P, T: Concrete => T: P built into compiler. Note that if generalised subtyping allows arbitrary value transformations, this may be false.

Now signature of type(of:) will look like this:

func type<T>(of: T) -> (any<U> U.Type where U: T, U: Concrete)

Note that U: Concrete part is important! Without it (any P).self is also a valid return value, and converting to any P.Type is not valid.

protocol P {}
protocol Q: P {}
struct R: P {}
struct S: Q{} 

// May return (any P).self, (any Q).self, R.self, S.self
func f() -> (any<U> U.Type where U: any P)

// May return only R.self, S.self
func g() -> (any<U> U.Type where U: any P, U: Concrete)

Now, if we substitute T = any P into the signature above, we get:

func type(of: any P) -> (any<U> U.Type where U: any P, U: Concrete)

That's not the same as

func type(of: any P) -> (any<U> U.Type where U: P)

And the two return types probably have different binary representation. Both need to store the type metadata and witness tables. The type metadata parts are binary compatible, but witness for U: any P is not the same as witness U: P. Not sure if U: Concrete needs a witness table. It may provide something which needs to be passed into witness for U: any P to obtain witness for U: P.

But if the only way concrete type can be a subtype of a protocol existential is by conforming to the protocol, then the two types encode identical sets of values, and thus are the same type. So compiler is allowed to perform implicit cast from one binary representation to another, and replace (any<U> U.Type where U: any P, U: Concrete) with simpler (any<U> U.Type where U: P).

Edit: if Never ever becomes a true bottom type, then it will break #4 - it is a concrete type, as a bottom type it is a subtype of every existential, but it does conform to every protocol.