[Pitch] Introduce existential `any`

While I think I understand you, I had the impression that when we make the proper split between the singleton and existential metatypes we will also be able to express the compiler magic function type(of:) natively in Swift.

func type<T>(of instance: T) -> any T.Type // SE-0096

If that's still the case, what does type(of: Int(42)) return, when not any Int.Type which boxes Int.Type?

More than fair, thank you for providing some clarification on this.

The proposal does not change the split between singleton and existential metatypes. There is no new any Int.Type; that is ill-formed. The signature of type(of:) will still not be expressible in the type system because of its special behavior for expressions statically typed as existential.

The proposal introduces a distinction between naming a protocol or protocol composition as a constraint (which can be turned into an existential with the any keyword) or as an existential type (with the any keyword).

2 Likes

Forgive me for my persistence on this, I'm just confused right now. What if we actually allowed such any Int.Type boxes regardless of their usefulness? Would type(of:) function then be natively expressible in Swift? My brain still cannot process what the return type of the todays version of the same function is. Is that an Either like special type no one told us about? I always had the impression that it was a form of any T.Type where you could substitute T with any other type or constraint, even back then when @beccadax helped us polishing the related proposal.

:confused:

protocol P {}
struct Foo: P {}

let fooAsP: /* any */ P = Foo()

// existential metatype (any P.Type) boxing the
// singleton metatype Foo.Type
let a: /* any */ P.Type = type(of: fooAsP)

let b: /* any ??? */ Int.Type = type(of: Int(42))

If it's not the 'existential metatype', then type(of:) returns multiple different types? o.O
What is my misunderstanding here? :thinking:

It seems like you're saying that type(of:) only applies any to the return type when the passed parameter type itself has any, but why do we want that behavior? Is it that tremendously bad permitting any T.Type boxes where T can be anything?

To me this would significantly simplify the mental model here.

class C1 {}
class B1 {}
actor AnActor {}

let b1AsC1: C1 = B1()

let c: /* any */ C1.Type = type(of: b1AsC1) // boxes singleton B1.Type

let d: /* any */ AnActor.Type = type(of: AnActor())

let d: /* any */ (x: Int, y: Int).Type = type(of: (x: 0, y: 1))

I personally don't see any harm with this? If there's a potential performance issue, can't we somehow optimize this issue away still!?

I'm really scratching my head right now. :thinking:

type(of:) has different behavior when the operand is statically of existential type (including existential metatypes). To express the behavior of the function, you would have to overload it (infinitely, because existential metatypes can be infinitely nested) and introduce genericism over constraints:

func type<T>(of: T) -> T.Type // only eligible when T is not existential
func type<C: protocol>(of: any C) -> any C.Type
func type<C: protocol>(of: any C.Type) -> any C.Type.Type
func type<C: protocol>(of: any C.Type.Type) -> any C.Type.Type.Type // ad infinitum

That's just what it does. There is no spelling for this type relationship in Swift.

That's exactly my point of this "issue". Why cannot we not say that we permit the existence of a "box type" aka. the metatype existential for any type?

// singleton `Int.Type` is now boxed inside the box / existential metatype `any Int.Type`
let exitentialMetatype: any Int.Type = Int.self

This would make us need a single signature for type(of:):

func type<T>(of instance: T) -> any T.Type

We could even tackle other things in the future with such model:

func subtype<T>(of type: T.Type, named: String) -> (any T.Type)? { ... }

If you haven't ever had the chance to scan our old but polished proposal, I kindly invite you and everyone else to read trough it (including the abstract examples inside the "Visual metatype relationship example (not a valid Swift code)" and "Some examples" spoilers): LINK

Note: Replace every occurrence of Type<T> with T.Type and AnyType<T> with any T.Type while reading.

I just realize that you written this out by flattening the signature, but why? :thinking:

I'd rather have expected the following scenario:

protocol P {}
struct Foo: P {}
let box: /* any */ P.Type = Foo.self
let c: /* any */ (/* any */ P.Type).Type = type(of: box)

Unless you are talking about changing the behavior of type(of:), that does not work and cannot work. There is no type expression that can possibly represent "the type produced by type(of:) on a T", because type(of:) does not respect generic substitution.

Suppose that such an expression existed. To try to avoid any confusion about any, let me spell it TypeOf<T>.

  • TypeOf<any Printable> is any Printable.Type, the existential metatype.
  • In a context generic over U, TypeOf<U> is U.Type.
  • If I substitute U=any Printable into U.Type, I get (any Printable).Type, the non-existential metatype.

Or in terms of values, if I have something I know statically is an any Printable, type(of:) will produce the dynamic type of the value in the existential, packaged as an existential metatype. If I have something that I don't know statically is an any Printable, but has an opaque type that dynamically happens to be any Printable, type(of:) will produce the singleton metatype value (any Printable).Type.

If Swift gains a different feature for extracting the dynamic type which respects generic substitution, then we could also add a type expression for its result type. However, I think it would be exceptionally confusing to spell that something like any T.Type, because it makes a very subtle distinction between very similar-looking types, and because the transformation it performs is subtly bound up with the any type operator.

I think in my mental model I have to disagree with this and again highlight the previous discussions regarding a potential "true" singleton P.Type but distinct from (any P).Type (previously known as P.Protocol).

In that sense I see this as:

  • TypeOf<Printable> is any Printable.Type , the existential metatype of the protocol (constraint), which stores some singleton T.Type where T: Printable.
  • TypeOf<any Printable> is any (any Printable).Type , the existential metatype of the protocol existential, which stores some singleton T.Type where T: any Printable.
  • In a context generic over U , TypeOf<U> is still another box, hence any U.Type .
  • If I substitute U=any Printable into any U.Type , I get any (any Printable).Type , the existential metatype of the protocol existential.
  • If I substitute U=Printable into any U.Type , I get any Printable.Type , the existential metatype of the protocol (constraint).

Here's the relationship I envision between metatypes. Let's look at this (non-valid) syntax as if singleton metatypes where modeled by a pseudo "meta" final class and existential metatypes by a pseudo "meta" protocol.

protocol Foo { 
  static func foo() 
  func instanceMethodFoo()
}

protocol Boo : Foo { 
  static func foo()
  static func boo() 
  func instanceMethodFoo()
  func instanceMethodBoo()
}

class A : Foo { 
  static func foo() { ... } 
  func instanceMethodFoo() { ... }
}

class B : A, Boo { 
  static func boo() { ... } 
  func instanceMethodBoo() { ... }
}

/// Swift generates metatypes along the lines of:
///
/// Syntax: `meta protocol /* any */ T.Type` - only metatypes can conform to these meta protocols
/// Syntax: `final meta class T.Type` - metatype
/// Note: `CapturedType` represents `Self` of `T` in `any T.Type`

// For Any:
meta protocol /* any */ Any.Type: meta class {
  var `self`: Self { get }
}

final meta class Any.Type: /* any */ Any.Type {
  var `self`: Any.Type { ... }
}

// For Foo:
meta protocol /* any */ Foo.Type: /* any */ Any.Type {
  var `self`: Self { get }
  func foo()
  func instanceMethodFoo(_ `self`: CapturedType) -> (Void) -> Void
}

final meta class Foo.Type: /* any */ Any.Type {
  var `self`: Foo.Type { ... }
  func instanceMethodFoo(_ `self`: Foo) -> (Void) -> Void { ... }
}

// For Boo:
meta protocol /* any */ Boo.Type: /* any */ Foo.Type {
  var `self`: Self { get }
  func boo()
  func instanceMethodBoo(_ `self`: CapturedType) -> (Void) -> Void
}

final meta class Boo.Type: /* any */ Any.Type {
  var `self`: Boo.Type { ... }
  func instanceMethodFoo(_ `self`: Boo) -> (Void) -> Void { ... } 
  func instanceMethodBoo(_ `self`: Boo) -> (Void) -> Void { ... } 
}

// For A:
meta protocol /* any */ A.Type : /* any */ Foo.Type {
  var `self`: Self { get }
  func foo()
  func instanceMethodFoo(_ `self`: CapturedType) -> (Void) -> Void
}

final meta class A.Type: /* any */ A.Type {
  var `self`: A.Type { ... }
  func foo() { ... }
  func instanceMethodFoo(_ `self`: A) -> (Void) -> Void { ... }
}

// For B:
meta protocol /* any */ B.Type: /* any */ A.Type, /* any */ Boo.Type {
  var `self`: Self { get }
  func foo()
  func boo()
  func instanceMethodFoo(_ `self`: CapturedType) -> (Void) -> Void
  func instanceMethodBoo(_ `self`: CapturedType) -> (Void) -> Void
}

final meta class B.Type: /* any */ B.Type {
  var `self`: B.Type { ... }
  func foo() { ... }
  func boo() { ... }
  func instanceMethodFoo(_ `self`: B) -> (Void) -> Void { ... }
  func instanceMethodBoo(_ `self`: B) -> (Void) -> Void { ... }
}

I kept the any keyword near the protocol keyword just for the sake of the example, but it's redundant. It would only be needed when you want to create the 'existential metatype' from the 'meta protocol', therefore meta protocol T.Type as a type would become any T.Type.

And the converted examples from our old proposal:

// Types:
protocol Foo {}
protocol Boo : Foo {}
class A : Foo {}
class B : A, Boo {}
struct C : Foo {}

// Metatypes:
let a1: A.Type = A.self           //=> Okay
let p1: Foo.Type = Foo.self       //=> Okay
let p2: Boo.Type = C.self         //=> Error -- `C` is not the same as `Foo`

let any_1: any Any.Type = A.self   //=> Okay
let any_2: any Any.Type = Foo.self //=> Okay

let a_1: any A.Type = A.self       //=> Okay
let p_1: any Foo.Type = A.self     //=> Okay
let p_2: any Foo.Type = Foo.self   //=> Error -- `/* final meta class */ Foo.Type` is not a subtype of `/* meta protocol /* any */ */ Foo.Type`

// Generic functions:
func dynamic<T>(type: any Any.Type, `is` _: T.Type) -> Bool {
  return type is any T.Type
}

func dynamic<T>(type: any Any.Type, `as` _: T.Type) -> (any T.Type)? {
  return type as? any T.Type
}

let c1: C.Type = C.self

dynamic(type: c1, is: Foo.self)    //=> true
dynamic(type: c1, as: Foo.self)    //=> an `Optional<any Foo.Type>`

To put it on other words, I seem to pursue away from your pseudo re_any model with implicit flattening behavior into a single and simple generically expressible world.

// yours
func type<T>(
  of instance: optional_any T
) -> re_any (flat_map_existential_metatype T).Type

// mine: just create an existential box and store the dynamic type there
func type<T>(of instance: T) -> any T.Type

I took a few minutes and updated our proposal text to further amplify what I'm aiming here for all along.

  • T.Type is the concrete type of T.self. A T.Type only ever has one instance, T.self; even if T has a subtype U, U.Type is not a subtype of T.Type.

  • any T.Type is the supertype of all _.Types whose instances are subtypes of T, including T itself:

    • If T is a struct or enum, then T.Type is the only subtype of any T.Type.
    • If T is a class, then T.Type and the _.Types of all subclasses of T are subtypes of any T.Type.
    • If T is a protocol, then the _.Types of all concrete types conforming to T are subtypes of any T.Type. T.Type is not itself a subtype of any T.Type, or of any any _.Type other than any Any.Type.
  • Structural types follow the subtype/supertype relationships of their constituent types. For instance:

In this new notation, some of our existing standard library functions would have signatures like:

func unsafeBitCast<T, U>(_: T, to type: U.Type) -> U
func ==(t0: (any Any.Type)?, t1: (any Any.Type)?) -> Bool
func type(of instance: T) -> any T.Type // SE-0096

That last example, type(of:), is rather interesting, because it is actually a magic syntax rather than a function. We propose to align this syntax with _.Type and any _.Type by correcting the return type to any T.Type. We believe this is clearer about both the type and meaning of the operation.

let anInstance: NSObject = NSString()
let aClass: any NSObject.Type = type(of: anInstance)

print(aClass) // => NSString

More details:

  • Every static or class member of T which can be called on all subtypes is an instance member of any T.Type. That includes:

    • Static/class properties and methods
    • Required initializers (as methods named init)
    • Unbound instance methods
  • The T.Type of a concrete type T has all of the members required by any T.Type, plus non-required initializers.

  • The T.Type of a protocol T includes only unbound instance methods of T.

  • If T conforms to P, then any T.Type is a subtype of any P.Type, even if T is a protocol.

  • The type of (any T.Type).self is (any T.Type).Type.

  • The type of T.Type.self is (T.Type).Type, which is not a subtype of any type except any (T.Type).Type. There is an infinite regress of (...(T.Type)).Types.

  • any _.Types are abstract types similar to class-bound protocols; they, too, support identity operations.

  • _.Types are concrete reference types which have identities just like objects do.

Int.self === Int.self // true
Int.self === Any.self // false

When the proposal text says something like T.Type is a subtype of any T.Type it means that in the terms of the previously presented abstract model which uses 'final meta classes' and 'meta protocols'. In reality they are only pseudo-subtypes because T.Type would be valid to be boxed inside an existential box any T.Type.

Thank you @hborla for including the discussion of Any<> in the Alternatives Considered section.

Much e-ink has been spilled about how to interpret any T.Type, resulting in lengthy dissections of “existential metatypes” and “generic contexts”. And resolving that discussion doesn’t alleviate the possibility of confusion in the future. To wit:

I think this is a very strong indication that any T is not the best spelling for this feature. Any<T> has the built-in benefit of grouping via angle brackets. It is immediately clear that and how Any<T.Type> is distinct from Any<T>.Type. Even if you don’t understand the nuances of metatypes, you can understand that one syntax names a type that wraps a Type object, while the other names a Type object that wraps an Any. If you encounter an error “Any<> cannot be applied to Type objects”, you immediately know you how to fix it: move the .Type outside the angle brackets.

Moreover, Any<T> gives us the opportunity to eliminate the intimidating term “existential” from the programmer’s mental model. Visual Basic has a much simpler name for “existential containers”: Variant. In Swift, Any<T> can be the new name for “existential container”. Thus, I question the relevance of this criticism from the Alternatives Considered section:

  1. A generic type is something programmers can implement themselves. In reality, existential types are a built-in language feature that would be very difficult to replicate with regular Swift code.

Variant is special in Visual Basic, and I think every Swift programmer would be willing to accept Any<T> being special in Swift as well. Any and AnyObject are already very special. I honestly think if you polled even moderately experienced Swift developers, they would collectively shrug at being unable to implement their own version of Any<T>. Like any programming language, there will be parts that it cannot implement itself; a friendly name for an intimidating type-theory concept seems a fine thing to put on the other side of that boundary.

The second criticism of the Any<T> syntax concerns static type information:

  1. This syntax creates the misconception that the underlying concrete type is a generic argument to Any that is preserved statically in the existential type. The P in Any<P> looks like an implicit type parameter with a conformance requirement, but it's not; the underlying type conforming to P is erased at compile-time.

This seems like an implementation-centric view of the feature. Just because the type system preserves the identity of the generic arguments doesn’t make that information useful to the consumer of the generic type. In fact, it can be a hindrance in the very cases that lead developers to write their own type-erasing wrappers. With Any<P>, the language can offer a feature that programmers have been asking for since Swift first arrived: salvation from writing their own AnyFoo type-erasing wrappers. I suspect far fewer Swift developers have been asking for a way to tell at a glance which expressions retain concrete type arguments in their static type signature. In fact, in certain circumstances I think many would class that as a usability anti-feature.

I think it’s a very small subset of developers who would have to deal with possible differences between any T.Type and (any T).Type. One of those spellings would be only needed in a very advanced programming. I don’t think we should design APIs primarily to accommondate those advances use cases where people anyway need to be very knowledgeable.

The angle brackets to me is an indication of generics or similar functionality and I wouldn’t want that to get mixed up with existentials. The point of this any syntax is to disambiguate existentials and angle brackets are not doing that.

3 Likes

No, this proposal does not introduce the ability to overload type names.

Doug

Hi all,

This has been a fantastic discussion, and the pitched proposal has been improved and clarified considerably along the way. While there are still some things under discussion here in the pitch thread, the Core Team feels that the proposal and discussion has converged enough to initiate a review. Those discussions that would directly impact the proposed features (e.g., the alternative Any<P> syntax still under discussion) can certainly move to the review thread, where we'll get opinions from others who follow formal reviews but not pitches. But we should be mindful of scope creep: other discussions around extensions to the proposal model that wouldn't change the meaning of what's proposed (e.g., introducing a new kind of metatype for protocols) can continue here or be handled through other threads as well.

Thanks everyone, I'll launch the review shortly.

EDIT: Review thread is here

Doug

20 Likes

@hborla I have one question for you. What does the following call return after this proposal?

type(of: (any P.Type).self) // `any P.Type.Type` or `any (any P.Type).Type`

From John's explanation it should be the former, but by my intuition I would expect the latter, because after all I would manually probably use any (any P.Type).Type as a type pamaramter where (any P.Type) is a substitution for T in any T.Type.

I don’t think this question belongs in the review thread, so I’ll ask it here: if existentials cause “active harm”, why not propose eliminating them instead of just changing their spelling? What necessary capability do existentials posses that generic types do not?

Today, type(of: P.Type.self) returns type P.Type.Protocol. This proposal only changes the spelling of this type, which becomes (any P.Type).Type, i.e. the singleton metatype of the existential metatype itself.

3 Likes

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

2 Likes

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.