[Pitch] Introduce existential `any`

Jumhyn · December 7, 2021, 3:21pm

Yeah, MetatypeExistential was not meant to be a serious suggestion, just an illustration of the sort of change I was talking about. AFAIU, we make an effort not to use the 'existential' terminology almost at all—it receives only a single mention in TSPL as an aside. Something like ConformingType is a better serious suggestion.

hborla · December 7, 2021, 5:32pm

No, using P.Type as a conformance constraint in a generic signature does not fall out of being able to use it with any. Conceptually it might make sense, but today, existential types are not modeled in the implementation with generic signatures (they should be, because that would also allow for other constraints on existential types, e.g. any Collection<Int>, but that will require generalization of their representation in the type system).

John_McCall · December 7, 2021, 10:03pm

No. As I discussed above, the existential metatype for a generic type constraint Constraint is the type ∃ τ : Constraint . τ.Type. It does not apply (does not result in a well-formed formula) to things that are not known to be a generic type constraint, and since Swift does not allow abstraction over generic type constraints (e.g. struct A<Constraint: protocol> { func foo<T: Constraint>(t: T) }), that means it only applies to concretely named constraints. A concrete type like Int or NSObject or what have you only has a concrete metatype (which in the case of classes and class metatypes can also store subtypes).

Douglas_Gregor · December 7, 2021, 11:47pm

As has been noted, having a representation of the "true" P.Type in the type system doesn't open up the ability to express new generic constraints, so I don't think we're actually unlocking a new set of generic algorithms. The only use cases I've been able to think up are around the idea of having a value of this "true" protocol metatype and doing a runtime check to see if a given type conforms to that protocol, sort of like as? does but without turning the result into an existential. However, as soon as I do that, I start wanting to use that "true" protocol metatype as a generic constraint.

It's not orthogonal to the proposal. If I understand correctly, it's not in conflict with this proposal, either. Rather, this proposal opens to the door for "true" P.Type as a potential follow-on, because it vacates the P.Type and P.self syntax, leaving it ill-formed in a future late version. That syntax could either remain ill-formed, or a subsequent proposal---with its own motivation---could use that newly-available syntax to do some of the things you describe.

Is that a fair characterization?

Doug

DevAndArtist · December 8, 2021, 5:19am

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.

John_McCall · December 8, 2021, 5:33am

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).

DevAndArtist · December 8, 2021, 5:39am

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.

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?

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.

John_McCall · December 8, 2021, 5:58am

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.

DevAndArtist · December 8, 2021, 6:06am

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.

DevAndArtist · December 8, 2021, 6:21am

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

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)

John_McCall · December 8, 2021, 6:22am

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 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.

DevAndArtist · December 8, 2021, 6:49am

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

DevAndArtist · December 8, 2021, 8:01am

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:

(NSString, NSString).Type is a subtype of any (NSObject, NSObject).Type

Metatypes of functions are a little bit more special (the subtyping relation on functions flips around for parameter types):

((Any) -> Void).Type is a subtype of any ((Int) -> Void).Type etc.

((Void) -> Int).Type is a subtype of any ((Void) -> Any).Type

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.

ksluder · December 8, 2021, 5:31pm

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:

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:

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

Moximillian · December 8, 2021, 8:12pm

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.

Douglas_Gregor · December 8, 2021, 8:43pm

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

Doug

Douglas_Gregor · December 8, 2021, 9:11pm

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

DevAndArtist · December 9, 2021, 5:04am

@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.

ksluder · December 9, 2021, 5:06am

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?

hborla · December 9, 2021, 5:21am

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.