SE-0309: Unlock existential types for all protocols

The fundamental difference between some and any is what happens when that code is compiled. Just as with e.g. structs and classes, a very similarly looking code has very different behaviour. In case of structs and classed you end up in a very different place behaviour wise, when you make a copy of it.

In case of generics (i.e. some) you end up with only the concrete type in the resulting compiled code. There's no "generics" to be found anymore, it's been replaced by that concrete type everywhere. And this means when code is compiled, the P is locked to single type, e.g. Int. So all values in this case are "Int", not a "generic value" or "protocol value".

In case of existentials (i.e. any), you have abstracted code even after it has been compiled, and if you want to know the real concrete type, you have to explicitly query for it. This means when you use existential as a function parameter, you can "open" it to reveal the instance of the concrete type that actually is being stored in there. Existential itself isn't really a value, it's merely a box that contains a concrete type value which can be one of many. So after compile, any P still can be any of Int, String, ..., whatever type that complies with the rules of P.

Holds only for return type position and is as I said an implementation detail.

I've heard that this is also true for some P types in some cases.

Existentials relate to the variable or more concretely to the instance behind the variable which isn't the same as the value.

I already said it upthread, I don't consider existentials tied to the term box or dynamic/runtime, existentials exists outside these concepts.
For me, an existential is an instance of an existential type, which some P is.

I don't think the definitions in Swift programming language agree with your view of the term "existential" and also Opaque types, as currently implemented in Swift 5.4, which use the "some P" as their syntax, do not have anything to do with existentials (as defined by Swift), but are instead implemented using generics, as far as I know. Generics uses protocols (as constraints) as much as existentials do, but generics does not use protocols as a type, they instead replace the constrained type with the real concrete type. The keywords protocol and existential cannot be used interchangeably.

This all feels like it has very little to do with reviewing the proposal. If the definition of "existential" is in question, perhaps that discussion can be had in a separate thread?

16 Likes

It's not merely an implementation detail. It's a compiler-enforced rule. That is, the rule that all returned values must be of the same type logically allows the compiler to treat the method as-if it had been declared to return the concrete type.

Usage of some P in argument position would seem to make no sense. At that point, it's not hiding anything from the caller, and one can hide the concrete type from the callee today, by using generics.

This is a circular definition. What is an existential type?

In Swift a protocol type, whatever this means. Generally, a type which steal literals/values from other types, usually base types like integer, structs ... .

The discussion about that has moved to reverse-generics-for-argument-type

By that definition, some P isn't existential. some P is shorthand, with the added benefit of hiding the real type from the caller. But that's all a compiler trick. some P is a stand-in from the perspective of the developer, never the compiler.

some P behaves like the following:

// magic modifier to hide the real type from everyone else.
private(type) typealias HiddenP = Int

public func f() -> HiddenP {}

One would not consider HiddenP to be an existential, and some P is nothing more than Swift's actual implementation of my made-up typealias modifier.

4 Likes

It’s also very confusing for an average Swift user (like myself). I’m completely lost now. The waters have been very muddled and my understanding of this topic has regressed. I’m silently hoping for one of the more recognisable names to “lay down the law” here and declares what is what to get back on solid ground.

Now it might not matter whether I understand all the little details here since I can’t offer any sensible contribution anyway. I can only hope that in the end this feature and its nuances will be explainable and understandable to the average user.

2 Likes

I'm sorry for this. A new topic was opened for further discussion on the topic opaque types.
Our discussion about existentials vs opaque types hasn't changed the proposal yet, so you can ignore it.

1 Like

I'm in the same boat as you. I can't follow all the nuance and detail because I don't have a solid computer science background. But don't consider your contributions to be worthless or insensible. Swift has to be approachable by ordinary app developers, and not just language theorists and compiler devs. Any time you ask a question, even out of ignorance, you're signaling that something is not quite right.

Of course, there's a time and place. In the middle of a very technical discussion might not be the best place. But I think a Review post is -- it's the last time you and I get a voice unless and until an amendment is proposed in the future.

3 Likes

So, I believe that this side discussion is fundamentally about a disagreement over the definition of "existential".

IIUC, your definition of "existential" is similar to:

a value of an existential of protocol P is a value v for which there exists a type T, such that v is of type T and T conforms to P.

Under this definition the value boxed in any P and both possible extensions of some P are existentials.


However, IIUC the definition of "existential" in general use in the Swift community is similar to:

a value of an existential of protocol P is a value b which contains a value v for which there exists a type T, such that v is of type T and T conforms to P, and b contains proofs of those statements about v.

Under this definition, any P, but not the value boxed in it, is an existential, but some P is not, because the proofs for some P are not stored in the value, but in the context.

4 Likes

Thanks everyone for participating in the review! The proposal has been accepted.

20 Likes

First of all congratulations on the proposal acceptance! I think this is a great step forwards for Swift as a language.

Now let me please try to clear up some of the above confusion about opaque types vs. existentials.

Using "some" with "any" would be confusing because "some Foo" is a placeholder for static type information known at compile-time, whereas "any Foo" would be a placeholder for dynamic type information only known at runtime.

Since Swift is a statically-typed language, and its type abstractions always refer to statically-known type information. We should keep it that way.

For details see below. (Warning, it's long.)

Definitions

  • existential container type (noun): the statically-known, but invisible to the programmer, type of the value/object that contains an instance of a value/object of a non-statically-known type that conforms to the protocol associated with the existential container. AKA "protocol-type". An instance of this would be a "protocol-type object".
  • existential type (noun): the dynamically-known type of the value/object contained within an existential container. This is NOT the type of the protocol-type object, it's the type of what's inside it. This type can only be determined via type-casting, is, or calling type(of:) at runtime. (Protip: In some cases, the protocol-type object must first be cast to Any to "open the container" before the dynamic existential type can be accessed.)
  • existential (noun): this is used in confusing ways. When referring to something at runtime, "an existential" could be used to refer to a specific value or object whose static type is a protocol-type. When referring to something at compile-time, it usually refers to the existential container type itself.
  • opaque type (noun): the statically-known, but invisible to the programmer or consuming code, return type of a function or property type of a variable. This type is not a container of some type—it is that type. In a static sense, the opaque type is merely a placeholder to be replaced by a specific type at compile-time. An opaque type is a protocol name prefixed by "some".
  • generic type (noun): the statically-known, visible to the programmer, parameter type or return type of a function, or property type of a variable. This acts very similarly to an opaque type except that consuming code will know exactly what the type is, at compile time.
  • associated type (noun): a placeholder in a protocol for a specific type that must be declared (or be able to be inferred) on any type that conforms to the protocol; very often, this requirement can be satisfied by a generic type parameter via a typealias. In current Swift, an associated type can never be opaque but it can be a self-conforming existential.
  • self-conforming (adjective): describes an existential container type that is statically known to conform to the same protocol that's also conformed to by the dynamic, existential type of its contents. A value/object of a self-conforming protocol-type will forward all member access to its contents.
  • static (adjective): when referring to type information, it means type information that's known at compile time. When referring to a protocol requirement, it means a requirement that specifies a static var, static func, or init method.
  • dynamic (adjective): when referring to type information, it means type information that's known only at runtime. This can be determined with type-casting (as/is), reflection, or functions like type(of:). When used as a declaration modifier, e.g. dynamic var foo it grants some Obj. C runtime features to that property.
  • protocol requirements (noun): in Swift, a protocol is just a set of requirements. Every func, var, and associatedtype in a protocol, is a requirement. For static protocol requirement, see the definition of static above.
  • protocol-type (noun): see existential container type

Swift is a Statically-Typed Language

When reading a novel, it's confusing if the character whose point-of-view the story is being told from, keeps randomly changing every other sentence, or if we keep jumping around from a past-tense to a future-tense, etc.

To avoid this problem, Swift tells the broad strokes of its story entirely from the static point-of-view. As a statically-typed language, Swift keeps its explicit, declarative syntax abstractions squarely in the static perspective. Its declarative abstractions are all placeholders for static type information that will be determined at compile-time: generics, opaque types, associated types, protocol-types, etc.

Meanwhile, Swift handles dynamic type information in a totally imperative manner, always using dynamic type-casting like as, is, or functions like type(of:) to make it clear which type information is dynamically determined—that which requires some lines of code to actually run before it will be accessible in code.

This is why the future direction of "any" just does not work for Swift, because it would make a declaration func foo() -> any Bar sound like "any Bar" is a placeholder for static type information, which it simply isn't.

Opaque Types can be Existential Protocol-Types

Incorrect. As explained above in the thread, an opaque type can be an existential container type as long as the protocol is one of the three kinds of protocols in Swift whose protocol-type objects can self-conform:

  • @objc protocols that don't have any static or initializer requirements
  • the new @_marker protocols
  • compiler-known protocols (such as Swift.Error—there's a short list of protocols built into Swift that are allowed to self-conform despite not fitting any of the above categories, because they have special witness tables created in advance to facilitate self-conformance)

See this part of the Swift compiler code, thanks to @anthonylatsis for linking it above.

Existential container types are known at compile time so they can indeed qualify as "some"/opaque type that conforms to their own protocol—as long as the compiler agrees they can conform to their own protocol (self-conformance).

However the existential type of the value/object contained inside an instance of a given existential container type is not known at compile time. Whether or not a given type is an existential container type is irrelevant to the question of whether it can conform to its own protocol and therefore be used with generics/opaque types.

Swift's Static vs. Dynamic Type Information Is Confusing

The fact that opaque types and existential container types seem related in the minds of people who don't understand them is not a bad reason to clarify the language, but we should be very careful that whatever changes we make don't further confuse the issue about what type information is dynamically known vs. what type info is statically known.

Ideally we can add syntax that stays true to declarative = static, imperative = dynamic distinction that Swift has.

However the proposed future direction for syntax "any" would make an existential seem like a placeholder for static type info, as if the compiler has been upgraded to where now I can do:

protocol Bar {
    associatedtype X
    static var x: X
}

func bar() -> any Bar { ... }

struct Foo<T: Bar> {
    var bar: T
}

let foo = Foo(bar: bar()) 
// this can never compile because `bar`'s return type
// is not statically known to conform to `protocol Bar`
// (meanwhile it would be, if this was `some Bar`)

That's why the opaque type feature is extremely different from the feature of existentials. The fact that people could get these concepts mixed up we can do a better job of educating Swift developers and that "some" might not have been the best word for opaque types.

"Opaque type" is not a very self-explanatory term, and "some" is extremely vague. It makes sense if you already know what it means, but if you don't, it gives you no clues about what is meant.

Opaque types are types that are statically known by the compiler at build-time, but are purposefully hidden from the consumers of the API. It probably should have been called something more descriptive, like a "concealed type" with "concealed" used instead of "some", like:

var body: concealed View // compiler knows what type this is, not you

Meanwhile, the concept of existential containers is totally different. The container type is statically known, but what goes inside is a purely dynamic behavior. The underlying type of a given protocol-type object is not known at compile time.

Future Directions to Clarify Swift

I won't pretend to know what will make the dynamic vs. static aspects of Swift less confusing for most developers, because everyone's brain works differently and this is a very abstract and arcane aspect of the language to understand.

Personally I'm a visual thinker and I like the principle of least surprise. For someone like me, I think it would hep if there was a visual aid combined with an explicit, unambiguous, plain-English keyword, which makes it clear that an existential container is a box whose type is statically known but whose contents' type is only known at runtime. We already have a word, "variable", which means "something that's known at runtime." So we could combine that with a visual aid in the form of | characters to make it clear what's meant:


struct Thing {
    typevariable FooType: Foo
    var foo: |FooType|
    // foo's type is a container type whose contents are of a variable type
    // that's only known at runtime
}

... but for someone whose brain works differently than mine, I'm not sure this would be less confusing than the existing behavior. YMMV

6 Likes

Those are two different things. Just because the type referred to by some P can be an existential does not mean that every some P is an existential.

That claim would be the same as saying that since some P can refer to Int, all some P refer to Int.

4 Likes

I don't understand why this would be the case. Would the compiler not verify that bar() is actually returning a type that conforms to Bar?

:+1:t2: I never said they were the same. I said "can be" ... that means they are different, but not mutually exclusive, concepts.

That claim would be the same as saying that since some P can refer to Int , all some P refer to Int

... what claim?

My point was just that this earlier statement of yours is inaccurate:

It's not an existential because the concrete type must be known to the compiler at build time

This is an inaccuracy because certain existentials can indeed count as concrete types at compile-time, whereas your statement makes it sound like if the compiler knows a concrete type therefore it must not be an existential.

Maybe that's what you meant though? I could be misreading.

1 Like

Do you mean concrete type? I think of associated types as generic types, but not as a placeholder for a generic type.

This is what I would think of as a placeholder for a generic type:

protocol P {
    associatedtype T: Hashable
    func f(a: T)
}

struct S: P {
    // this doesn't fulfil the protocol requirement and
    // there's no way to alias T = U
    func f<U: Equatable>(a: U) {}
}

Or this: https://github.com/apple/swift/blob/main/docs/GenericsManifesto.md#generic-associatedtypes :point_left: Generic associatedtypes

irrelevant point

In my mind the only question here is: does Bar conform to itself? That can be statically known, right? Edit: just realized that Bar (or any protocol for that matter) will never conform to itself - oops!

As someone who liked the any P syntax, I have to admit this a compelling argument against it.

This seems too verbose to me and the |FooType| looks too similar to [FooType]. I would rather have a syntax like protocol<Foo> over that. Maybe capitalize it so it looks more like a type: Protocol<Foo>

3 Likes

The point is that Bar in this example has associated type and static requirements, which means, an existential of type Bar cannot conform to Bar because the compiler will have no way to know what the associated type actually is, or where the implementations of the static methods are to be found.

struct Foo<T: Bar> requires some type T that conforms to Bar, but existentials of Bar can never conform to Bar. Therefore let foo = Foo(bar: bar()) can never compile.

That's why the "any" syntax doesn't seem viable to me, because any Bar makes it sound like the compiler statically knows that this function returns an existential container whose type is statically known to conform to Bar, which it doesn't and can't because Bar has associated type and static requirements.

With the expanded rules about existentials, perhaps we could have a protocol-type object of type Bar (the existential container type), however that object can't enjoy self-conformance because the compiler can't infer the existential type within the existential container at compile-time. It's a logical impossibility sadly.

The usual kind of proof that's given for this is a reduction to absurdity. (Forgive me if I butcher this)

Given:

protocol Bar {
    associatedtype X
    static var x: X { get }
    init()
}

class A: Bar {
    typealias X = Int
    static var x: Int = 42
    init() {}
}

class B: Bar {
    typealias X = String
    static var x: String = "blah"
    init() {}
}

... and a function that returns "any Bar" ...

func bar() -> any Bar { .random() ? A() : B() }

If the statically known type "any Bar" conforms to Bar protocol, then we reach absurdity:

struct Foo<T: Bar> {
    var bar: T
}

let bar = Foo(bar: bar()).bar // what's the static type of bar?

func impossible<T: Bar>(_:T) { print(T.x) }

impossible(bar)
// what gets printed, according to the compiler? 

But I probably butchered it. I think there was a better example given by @xwu on this thread: Very confused about some compiler warnings related to protocols—bugs or intended?

1 Like

Good point. It would have been more accurate for me to say that it's a placeholder that must resolve to a specific type at compile time. This is often satisfied via a typealias to a generic type parameter but it doesn't have to be. I'll update the post. Thanks.

Hmm, if what you're asking is, "does (the protocol-type object) Bar conform to Bar"? You're correct that it can be statically known whether or not a given protocol is able to have a protocol-type object that enjoys self-conformance, because there are rules about this in Swift's compiler. The example I gave would be totally fine if Bar was an @objc protocol with no static or initializer requirements. However, in my example, Bar has both an associated type and a static requirement, which means a protocol-type object for Bar cannot conform to Bar.

1 Like

I think we know statically that any Bar can't exist, yet?
But maybe with more features integrated, it could?