SE-0353: Constrained Existential Types

Hi everyone. The review of SE-0353: Constrained Existential Types begins now and runs through May 18, 2022.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to me as the review manager by email or by direct message. When emailing directly, please keep the proposal link at the top of the message.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

Joe Groff
Review Manager

19 Likes

FYI This links to the wrong proposal. The correct link is swift-evolution/0353-constrained-existential-types.md at main · apple/swift-evolution · GitHub

1 Like

Fixed, thanks.

The proposal states:

It is worth noting that this feature requires revisions to the Swift runtime and ABI that are not backwards-compatible nor backwards-deployable to existing OS releases.

So how will deployment of this feature be handled? While we'll be able to mark functions we create with availability, how will the compiler handle attempts to use any Collection<String> when the deployment target is too old? Implicit availability from the compiler?

Additionally, what's the overload logic here? Compiler prefers the most specified of -> any Collection and -> any Collection<String>? What about if we have different availability? I could imagine an alternative to eraseToAnyPublisher returning any Publisher<Value, Error> on newer systems but wanting to keep the concrete type on older ones. Is that possible?

1 Like

Wouldn’t a future implementation prefer some Publisher, which keeps the concrete return type but hides its identity from the caller?

While we extensively use the term "existential types" among compiler developers, and to a lesser degree in the evolution community, the official language term has always been "protocol types". Should that be reflected in the name of this proposal?

4 Likes

Yes, the compiler will know the availability of the Swift runtime support. This is similar to how availability checking works for opaque result types, which require the Swift 5.1 runtime.

Generally, overload ranking uses subtype relationships to determine which overload is "more specialized". So, overload resolution will prefer any Collection<String> because it's a subtype of any Collection. However, this ranking does not apply to result types in general, so calls to an overloaded function that returns any Collection and any Collection<String> will be ambiguous.

Overload resolution will only consider overloads that are available in the context of the caller.

Personally, I think the term "protocol type" and "protocol as a type" should be phased out and replaced with some other term that indicates the boxing or type erasure going on. I think the term "protocol type" has been a contributing factor to folks being confused about why a protocol type doesn't behave like a normal supertype, why a protocol type can't conform to protocols, etc.

Of course, that is a separable question to what we should call the proposal right now to help people understand what it is given their current knowledge.

11 Likes

It is worth noting that this feature requires revisions to the Swift runtime and ABI that are not backwards-compatible nor backwards-deployable to existing OS releases.

This seems severely limiting in the context of library developers and end users of these libraries (app developers) that have to support old versions.

If a feature is only available on the latest runtime, library developers are either forced to stay behind, or force out the app developers that cannot raise their deployment target.
Oftentimes, app developers are constrained to a deployment target by their employer policy and this has profound effect on their quality of life.

While the use of some keyword has been limited to iOS 13 an up, one could say it wasn't particularly load-bearing in libraries since the underlying type could be expressed in a different, more verbose way.

To contrast, the Concurrency feature, which provides quality-of-life benefits for all developers, was originally intended for iOS 15 only. There was massive pushback against this limitation and the Swift team has put in much work to lift it.

I believe having more general availability of existentials benefits all developers as well. I can point to numerous occurrences in my codebase where this is the case, and our deployment target is still iOS 12 (hoping to go to 13 soon).

I believe in this case the Swift team needs to look in to increasing the general availability of existentials down to at least iOS 13.
I don't know why the actual implementation on older targets is difficult, but I still think it merits serious consideration.

4 Likes

Note on variance:

Variance

One primary use-case for constrained existential types is their the Swift Standard Library’s Collection types. The Standard Library’s concrete collection types have built-in support for covariant coercions. For example,

func up(from values: [NSView]) -> [Any] { return values }

At first blush, it would seem like constrained existential types should support variance as well:

func up(from values: any Collection<NSView>) -> any Collection<Any> { return values }

But this turns out to be quite a technical feat. There is a naive implementation of this coercion that recasts the input collection as an Array of the appropriate type, but this would be deeply surprising and would bake the fact that Array is always returned into the ABI of the standard library forever.

Constrained existential types will behave as normal generic types with respect to variance - that is, they are invariant - and the code above will be rejected.

This is not a brilliant example, because in the specific case of erasure to Any, this is equivalent to simply dropping the Element constraint. In other words, if the existential function returned any Collection instead of any Collection<Any>, the code should work.

Existentials are different to generic types in that you can choose whether or not to specify even basic parameters like the collection's Element type. You can't create an Array<?> or Set<?>, where the value has its true type behind the scenes but is presented with an erased Array or Set interface, but you can with existentials.

Sometimes, developers reach to heterogenous collections in these cases - so, an Array<Any> or Set<AnyHashable>. This gives you the expected interface, where the Array's elements have been erased of their static types, but comes at quite a performance cost. In the example, creating a new Array with individually boxed elements is an O(n) operation which might allocate a lot of memory. By contrast, going from any Collection<NSView> to any Collection is a no-op.

When the compiler rejects the above code, specifically involving a same-type constraint to Any, I think it would be valuable to emit a targeted diagnostic suggesting the constraint be dropped. It can be easy to overuse angle brackets, and developers might forget about this unique feature of existentials.

--

When it comes to non-Any constraints, of course you can't simply drop the constraint. Consider a non-Any example: returning a collection of integers as a collection of numerics:

func up(from values: any Collection<Int>) -> any Collection<Numeric> { values }

With the recent changes to generics syntax, it should be clearer about why this must fail today - because Numeric is being used in a (conceptually, not syntactically) ambiguous way. There are two options for what the developer might be looking to express:

  • any Collection<any Numeric> (heterogenous collection)

    This expresses a very different concept to Collection<Int>, and the problem here is more contravariance than covariance. Because <any Numeric> is a same-type constraint, it implies that mutating methods also accept any Numerics, even though a collection of Int clearly doesn't.

    As noted, this could theoretically be implemented by copying to a different collection (e.g. an Array<any Numeric>) and boxing every element in individual existential boxes. But a lot of the point of using existentials is because you want a particular, specialised implementation, while presenting a convenient interface to clients that hides those details. I don't think people would be happy if the data could so easily be implicitly copied to an Array.

    At the very least, I think it's a good idea for this to involve some kind of explicit Array initialiser call.

  • any Collection<some Numeric> // any Collection<.Element: Numeric> (erasure)

    Theoretically you should be able to represent an any Collection<Int> using either of these forms, and just like dropping the constraint, it should come at no cost.

    But you can't express either these things right now anyway, and both the some form and possible future generalised constraint shorthands are out of scope for this proposal.

So, to summarise: same-type constraints to Any (or any looser type boundaries) are really for actual heterogeneous collections, not for erasure. If you want to erase types which are part of an existential, you can simply loosen the existential's constraints.

I think there is still room to solve this; the main issue with respect to this proposal is that it only adds same-type constraints, which are insufficient for the erasure cases where implicit coercion makes the most sense.

My reading of the proposal seems to suggest that it is some kind of failure or odd quirk, but IMO invariance is the only logical thing given the limited constraints being added here, and there is plenty of room to develop this as we add support for the latter syntax described above.

1 Like

The term "existential type" is acknowledged in The Swift Programing Language, though "protocol type" is clearly preferred:

Protocols as Types

Protocols don’t actually implement any functionality themselves. Nonetheless, you can use protocols as a fully fledged types in your code. Using a protocol as a type is sometimes called an existential type, which comes from the phrase “there exists a type T such that T conforms to the protocol”.

Off-topic question: where should I go to report errors in TSPL? "Nonetheless, you can use protocols as a fully fledged types in your code" has a grammatical error in it. Would the "Swift Website" category of these forums be the appropriate place?

1 Like

Very much in favor of this! This will be really great for redux-style architectures that return asynchronous sequences of actions, for example (e.g., TCA).

1 Like

Bit of a bummer about the hard runtime requirement, I guess we'll be living with type erasing wrappers for the next handful of years. I guess there's nothing developers can do about it, like bundle a preferred runtime in their own apps?

Can any migrators be provided for type erasing wrappers types (e.g.: Combine's AnyPublisher / eraseToAnyPublisher) so we can adopt the feature fairly automatically when enough of our user bases are not dependent on the older runtimes?

Dose any Collection<Int> conforms to Collection? Or something like this valid:

func foo<C: Collection>(_ collection: C) { ... }

var bar: any Collection<Int> = ...
foo(bar)
1 Like

Existential seems like a good starting point but it’s quite technical. Perhaps “any-type” could do the job, or maybe “dynamic” to better indicate what’s going on. With “dynamic types,” there would be parity with opaque types since each has its own, distinct keyword (any and some respectively).

The term used in the AnyCollection etc types is ‘type erasing’ or ‘type hiding’ wrappers.

  • some P - opaque type. It’s always a single type - you just can’t see it.

  • any P - erased type. The information about ‘which type it is’ is deliberately erased to allow different types to be used at runtime.

3 Likes

I wanted to ask @John_McCall, @hborla & @codafi if they could, to expand more on the breaking changes to the ABI and its effect on runtime limitations.

Is this solely due to additions to the mangler? I've noticed PR #42563 mention "runtimes with general shape support" - which runtimes are those?

Addititonaly, if a portable symbol mangle isn't possible, perhaps it is possible to add some sort of code generation shim that will be optimized out on newer runtimes, a polyfill of some sort?

1 Like

There are a couple of other terms that ought to be defined:

  • ad-hoc type erasure
  • concrete types can be erased (hidden behind the interface of a protocol)

I know what type erasure is but interface of a protocol is playing tricks with my brain because interface is what other languages refer to the concept of protocols.

any Collection<Int> does not conform to Collection (what would the Index and other associated types be?), however, the code you wrote is still valid thanks to existential opening/unboxing, which is under a second round of review now: SE-0352 (second review): Implicitly Opened Existentials

5 Likes

As a general rule, evolution discussions are forward-looking; we're trying to design the best language we can, and if it takes a few years for everyone to be able to take advantage of new features, that's unfortunate but also the reality of the thing. As a result, we generally ask that you review proposals ignoring back-deployment concerns. Whether platforms with stable ABIs will be able to support features on existing systems is outside the scope of the evolution process.

With that said, I'll try to answer your question on a technical level as best I can. Basic interactions with constrained existential types such as forming existential values by type-erasing a value of concrete type, "opening" existential values to access a type-erased value, and passing existential values around concretely do not rely on runtime support. Runtime support is required when using a constrained existential type as a type argument to a generic function or type, when performing dynamic casts to or from the type, and when doing certain kinds of reflection, e.g. with Mirrors. To answer your specific question, no, the issues here are not primarily about symbol mangling.

It's possible we'll be able to usefully distinguish these cases in code, so that uses of constrained existential types in the former category will not need to be deployment-restricted, but that's not something we're promising. It's also possible that Apple will be able to provide the needed runtime support in a way that works on existing systems, but that is also not something that we are promising. You should assume that neither of these things will happen and that uses of constrained existential types on Apple platforms will have to be availability-restricted to future operating systems.

24 Likes

Thank you for elaborating. I understand that evolution discussions are forward-looking and agree that the primary goal is getting to the best language.

In addition to this, I believe it's reasonable to assume that end users (developers) care a lot about backwards support.

Past evolution decisions about backwards support have sometimes generated controversy (SwiftUI, Concurrency) and I felt that this is better raised now rather than later, when it reaches a wider audience of developers and they realize that they cannot use it due to runtime limitations.

That said, I respect your time and hope you manage to achieve the best backwards compatibility given the real world constraints.

Having first-class existentials is an extremely useful feature and I just hope the most people will have access to it.