[Pitch] Introduce existential `any`

No, the concrete type conforming to P is not preserved in the type system. This confusion is exactly the motivation for this proposal. P is frequently confused with the generic constraint T: P. Many programmers don't understand this until they hit some obscure error message that says "use a generic constraint instead".

EDIT: by "preserved in the type system", I mean statically. You can, of course, dynamic cast an existential type to a concrete type.

This is exactly the confusion that the Any<P> syntax creates. There is no implicit type parameter here. There is no type-level abstraction at all with Any<P>, but the syntax makes it seem like there is.

I don't think P meaning an implicit type parameter is a bad idea. In fact, it's written in the future directions section of this proposal. But in your suggested syntax for existential types, what's in angle brackets is not a type parameter.

That's right. A cast such as x as? P would change to x as? any P under this proposal.

8 Likes

I.

LOVE.

THIS!!

:smiley:

Hi @hborla, it's great to see that you're working on this problem. Of course it is my duty to trot out, briefly, the points I always | bring | up on this topic:

  • We will someday need to represent things like “any Collection whose Element is Int.” The natural way to spell it in Swift is something like “Collection where Element == Int” (I know there's been talk out there about Collection<.Element == Int> but I honestly can't see how angle brackets improve on where).
  • The more constraints you add to an existential, the more of the protocol's declared API becomes available.
  • any P” doesn't read like a thing that's only going to expose part of the API that every P in fact must expose, which has always been my worry about existentials. If every P is declared to have a foo property and I am handling something called “any P,” it's not obvious why it has no foo, any more than it's obvious why P has no foo today.
  • P where _” ain't pretty, but it at least suggests that something is unknown, and you might need to add something.
  • We could add any to the front of these syntaxes, and I don't object to it if people like it… but it isn't adding anything essential once you have ”P where _.”

Phew, duty done :vulcan_salute:

Oh, whoa, I just noticed this:

What's that supposed to mean? IIUC any P is a concrete type in this proposal but you're not allowed to write

func test<T>(_: T) where T == Int // Int is a cocrete type

at least, IIRC.

-Dave

4 Likes

Hah, you're right, the example I wrote doesn't compile with the error Same-type requirement makes generic parameter 'T' non-generic. I'll fix that, thanks for pointing it out!

I don’t have much to add to the discussion here except for something anecdotal:

As I was reviewing some code today in a large project, I realized that I accidentally used a “protocol as an existential” in a function parameter.

I didn’t want it to be existential for good reasons, I wanted it to be a generic method with a parameter constrained to the same protocol, but it was just so easy to accidentally do exactly what I didn’t want to do :weary:

Now I’m searching my project for every occurrence of all of my protocol names just to make sure I didn’t accidentally use them as existentials elsewhere. So I suppose another benefit of having a separate spelling when using a protocol as an existential would also aid in a project scoped text search for existential usage :)

9 Likes

P.self must refer to (any P) type or be invalid, because there is nothing else to refer. The .self construct applies to a type, and bare P is not a type, it is a constraint. Only any P is a type.

Indeed it is confusing for type of (any P).self to be anything but (any P).Type. But I don't think it is an argument for keeping the P.self spelling. Rather it is an argument for (any P).Type being a replacement for P.Protocol.

We might keep both (any P).Type as a replacement for P.Protocol and any (P.Type) as a replacement for P.Type. But the second replacement, IMO, has little value. Can we consider replacing into something distinct from .Type and maybe more verbose - something like P.ConformingType?

Yes, it makes things more clear.

I don't think it is a good reason for making things intentionally obscure. I usually encounter existential meta types in very generic code, which can handle any type at all. Something related to reflection, serialisation, etc. At this level you don't care about witnesses, just want a consistent syntax for type of T.self being T.Type, with (any P).self and (any P).Type being part of the rule, and not an exception.

When talking about T as a formal parameter, then it behaves like a generic formal parameter in the scope of the box contents:

any<T> Dictionary<KeyWrapper<T>, ValueWrapper<T>> where T: Something
//     \-------------------+--------------------/
//                         \- type T is statically substituted in this scope.

T as an actual parameter is not applicable here. You never see in code T replaced with an actual parameter.

In a way this is similar to the signature of the AnyView.init(): <V> (V) -> AnyView where V : View. Once you erase Text to AnyView, you don't write AnyView<Text> in code anywhere. Concrete value of V is statically substituted on the call site while erasing and does not exist afterwards.

This signature is the main piece of information describing what AnyView does. There is 1:1 mapping between the generic signature of initializer of nominal hand-written AnyView and an equivalent existential in suggested syntax:

<V> (V)  -> AnyView where V :  View

vs

any<V> V where V: View

Similarly, if I would provide a hand-written type-erasing wrapper for the example above, it would be something like this:

struct AnyWrappedDictionary {
    init<T>(_ value: Dictionary<KeyWrapper<T>, ValueWrapper<T>>) where T: Something { ... }
}
2 Likes

I've always had problems with the whole existential/associated types thing in Swift so anything that helps clarify it and avoid problems seems like it should be a good idea. That said, I think the pitch could maybe help clarify things a bit more for dummies like me?

I just want to be totally sure I'm understanding at least a tiny bit of the concept here. The example given in the motivation section is this:

protocol P {
  associatedtype A
  func test(a: A)
}

func generic<ConcreteP: P>(p: ConcreteP, value: ConcreteP.A) {
  p.test(a: value)
}

func useExistential(p: P) {
  generic(p: p, value: ???) // what type of value would P.A be??
}

I've run into this situation many times in the past where I get to a place like the commented line and suddenly realize I didn't have the "full" type that I thought I had so I appreciate any attempt to preemptively fix this.

What I'm not sure I understand is, how is adding "any" in here going to help prevent me from writing this code and getting too far down the rabbit hole before noticing?

Presumably, if I understand correctly, if after this change was implemented, the only difference is I would be required to add the any keyword before I could even get an empty version of the useExistential() function to even compile, right? So let's say I add in the any keyword to make Xcode happy and now I have this:

protocol P {
  associatedtype A
  func test(a: A)
}

func generic<ConcreteP: P>(p: ConcreteP, value: ConcreteP.A) {
  p.test(a: value)
}

func useExistential(p: any P) {
  generic(p: p, value: ???) // now what? 
}

So it seems to me that all we've gained here is that we've maybe traded one error string for another - I still don't have access to type of P.A within the useExistential() function, correct? I'll still probably end up googling that error and ending up on StackOverflow where someone will have to explain how I've been a dummy again. What has been gained? This code still won't work and nothing helped prevent me from writing it - unless I'm totally missing something here (and I might be - and if so, I suspect I'm not the only one).

11 Likes

This is incorrect: .self is an identity operator that applies to everything, not just types. You can write 42.self or, for that matter, 42.self.self.self. You can even shadow the name Int with a variable of the same name (like this: let Int = 42) and write Int.self.self.self instead of 42.

2 Likes

True, it works with values as well. But .self on a bare protocol-as-a-constraint is still non-sensical. It is not a meta-type. It might be something like a meta-protocol or meta-constraint, but currently such entities do not exist, and AFAIU, introducing them is not a goal of this proposal.

P.self is a value of type P.Protocol and my understanding is that this pitch proposes to make no change to it. I’m not sure what’s nonsensical about it.

What about arrays of existentials? Is it legal to spell:

let x = [any P]

Can an existential be used in a generic slot at all like this?

Updated: I intended to write;

let x: [any P] = …

As you have written this, it's not legal.
That's because of the same reason, that also makes the following examples illegal:

let x = [Int]
let y = Int

Maybe you meant

let x = [any P]()

or

let x: [any P]

?

In this case, yes that will be possible, exactly as

let x = [P]()

is possible today.

1 Like

This proposal is concise and simple, yet answers all my questions and provides great arguments why it should be accepted. It also goes well with SE-0309. I would really like to see it happen, hopefully as proposed in the proposal by allowing it in Swift 5.6.

Rationale: any Any and any AnyObject are redundant. Any and AnyObject are already special types in the language, and their existence isn’t nearly as harmful as existential types for regular protocols because the type-erasing semantics is already explicit in the name.

In a previous thread, I suggested protocol composition as a backwards-compatible alternative:

  • Use Any & P instead of any P
  • Use Any & P & Q instead of any (P & Q) or any P & Q

Existential metatypes:

  • Use (Any & P).Type instead of any P.Type
  • Use (Any & P & Q).Type instead of any (P & Q).Type

With this alternative, the any Value and any Object renaming wouldn't need to be considered, and the required parentheses would be easier to predict.

Confusion with the protocol metatype would remain, but I don't think the proposed any P.Type versus (any P).Protocol spelling helps much either.

1 Like

The pitch mentions that existentials are a performance problem relative to generics, because of dynamic dispatch. I'm wondering if someone can explain, or point me to an explanation, about why that is the case.

With typical dynamic dispatch you have the pointer indirection to the "vtable" of function pointers.

If you have a generic like:

func foo<X: SomeInterface>(x: X) {  ... }

How could it be any different? If the body needs to find the functions of SomeInterface on x, doesn't it need some kind of table of function pointers? I figured that was the "protocol witness table" I've seen mentioned.

Is Swift compiling multiple copies of foo for different types? I didn't think so. ?

1 Like

Roughly, yes. If the compiler can, and in most cases it can, it will create specialized implementations for each type that is used so that it can directly reference the type's definitions instead of going through the "vtable".

1 Like

Oh man. I didn’t think the old P.Protocol discussion would get dragged out here. My main response to that is that it’s the least important part of this proposal and that if it remains weird, that’s at least not a regression.

But if we want to talk about it…

We care about types because they specify what operations work on what values. So what values are we talking about?

  1. An instance of a generic parameter T constrained to P. Type: T
  2. The type(of:) such a value. Type: T.Type
  3. The value representing T itself, which you can call static members of P on. Type: also T.Type

(2) and (3) are the same because that matches how concrete types work: String.init() and type(of: "").init() do the same thing and have the same static type.

  1. The value representing the protocol P itself. This has exactly one supported use in Swift today besides ===: Objective-C’s conformsToProtocol: / conforms(to:) method. This is the value you get when you say P.self today, and its type is spelled P.Protocol.

  2. An instance of an existential, where you can invoke the instance members of P. Type currently spelled P but this proposal plans to change it to any P.

  3. The type(of:) such a value, which is the concrete type. The static type of this is currently spelled P.Type.

  4. The existential value where you can invoke the static members of P. This is also currently spelled P.Type.

Like the generic case, these two are spelled the same because you get the same behavior: (String.self as P.Type).init() and type(of: "" as P).init()

  1. The value representing the type of a stored property or variable with existential type. You can’t actually get this with type(of:), but you can get it out of Mirror. I believe the value you get back is === to P.self, but Swift could have made a different decision about this. Because there’s no static way to get it, there’s not exactly a static type other than Any.Type, though in practice you can successfully downcast that to P.Protocol. There’s no equivalent static type today for, say, P & Q.

So what could (any P).Type mean? It could be (6), by analogy with (2). Or it could be (8), by analogy with uses of Mirror on concrete types.

And what could any (P.Type) mean? It could be (7), by analogy with (3). And…actually that’s the only one I can reasonably argue for.

So yes, it’d be nice to have a more regular spelling for P.Protocol…but that really is a niche type, and I wouldn’t use that to argue that (any P).Type is wrong, or that we can’t have any P.Type.

7 Likes

For what it's worth, in the abstract I agree with the idea that (any P).Type probably ought to be the concrete metatype of the existential type and any P.Type ought to be the existential metatype. P.Type has always been a rather fast-and-loose syntax because it isn't a simple composition of a type and an operator upon it. If we'd always had any, that would be easy to clear up.

This might be rather dense, but the formal understanding here is that a protocol type P (under this proposal, any P) is the existential type ∃ T:P . T, which you can read as "there exists a type T that conforms to P such that this is a T". For example, if I have an Int, I can convert it to Encodable:

  • Encodable as a type means ∃ T:Encodable . T ("there exists a type T that conforms to Encodable such that this is a T")
  • Int is a type that conforms to Encodable, so it's a valid substitution for T
  • The open formula in my existential is just T, and if I substitute T=Int into that, I get Int
  • So I can make a value of the existential type if I can provide an Int

In principle, this can be arbitrarily generalized. For example, ∃ K:Hashable,V:Encodable . [K: V] means "there exists a type K that conforms to Hashable and another type V that conforms to Encodable such that this a dictionary from K to V". I can make a value of this type from, say, a value of type [String: Int] by assigning K=String, V=Int. This existential type would be usefully different from e.g. [AnyHashable: Encodable] because it expresses that all the keys have the same type and all the values have the same type. But Swift doesn't allow this kind of unrestricted existential, for a variety of reasons.

What Swift does allow is the specific case of an "existential metatype". Swift interprets the syntax P.Type to mean ∃ T:P . T.Type, which is to say, "there exists a type T that conforms to P such that this is a T.Type". Therefore, for example, you can form an Encodable.Type with a value of Int.Type by letting T=Int.

This is not a compositional interpretation of that syntax. Taking the components independently, you would expect P.Type to be (∃ T:P . T).Type, i.e. the metatype of the existential type, which is a singleton type (it has exactly one value). But we wanted to allow this existential metatype to be written, and we felt the existential metatype was much more likely to be useful than the singleton metatype of the existential, and we felt that programmers would often reach for it first and be surprised if it didn't work. So we stole the syntax for this purpose.

The any operator really cannot be totally compositional: it doesn't apply to an arbitrary type, or even to most types, and it essentially rewrites its operand. So building this extra metatype thing into its rewrite rule isn't particularly strange. But the any operator also acts almost like an qualifier, in that you could naturally think of it as "containing" the rewrite and producing a normal type that you would expect to behave compositionally. Compositionally, (any P).Type would be the metatype of the existential, and so different from any P.Type. That's weird, but not that weird.

Unfortunately, I'm not sure we can get away with making that change, because I think it might have weird implications for typealiases. typealias MyP = P is something that people can write today, and MyP.Type is the existential metatype, not the metatype of an existential. Do we disallow this somehow? Does it change behavior if someone rewrites it to typealias MyP = any P, so that whether a protocol (or protocol composition) typealias is "any-ed" changes the semantics? This might be too much for people to understand.

13 Likes

Could you please elaborate?

RHS of the typealias must be a type, so typealias MyP = P is not valid, only typealias MyP = any P. But there are still use case for bare P. I think, following the idea of separating protocol-as-type from protocol-as-constraint we should also separate usage of typealias - let’s call a keyword for that a constraint:

constraint MyPQ = P & Q
struct S<T: MyPQ> {} // OK
class C: MyPQ {} // OK
let x: MyPQ // error
let y: any MyPQ // ok
1 Like

It is an interesting point you made here. I think we don't have to touch typealias at all, because it's simply an additive side effect from the introduction of the any keyword.

protocol P {}
typealias MyP1 = P // should remain valid
typealias MyP2 = any P // new, but further constrained than `MyP1`

let p1: P // error -> should be `any P`
let p2: any P // as proposed
let p3: MyP1 // error -> should be `any MyP1`
let p4: MyP2 // new, okay 

// ignore the redundancy error for the sake of the example
extension Int: P {} // nothing changes here
extension Int: any P {} // error
extension Int: MyP1 {} // okay, similar to `Int: P`
extension Int: MyP2 {} // error, similar to `Int: any P` 

If we were to allow MyP2 then we should also allow typealias MyP3 = some P. Then the typealias can always act as a substitute for a type at the context of usage.