SE-0353: Constrained Existential Types

Evolution Proposal Reviews
#6

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

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

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

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

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

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

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?

#13

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

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

#15

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

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

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.

#18

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

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

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.

#21

We’ve realized that, if we can allow constrained existential types to be stored directly in structs without back-deployment constraints, you can effectively do almost anything you want with them, just with some minor inconvenience. You can’t back-deploy an Array<any Collection<Int>>, but you can back-deploy an Array<MyAnyCollection<Int>>, where that’s simply a struct wrapping any Collection<T>. And you can dynamically cast from an any Collection<T> by converting it to Any first. The only hard restrictions will be that reflection won’t work and dynamic casts to these types won’t work.

We still cannot promise that you’ll be able to do that, however.

11 Likes
[Accepted] SE-0353: Constrained Existential Types
#22

Strong +1 on this.

Oh yes. This feature has been highly requested since the earliest days of Swift, and has always been on the "someday we'll get to this" checklist.

It does now that we've worked out the whole story of generics ergonomics, simplifying generics (e.g., with some Collection<String>) and extending support for existentials via SE-0309.

I've been involved with the design of this feature, so I'm not unbiased here.

I do have one request. SE-0309 specifies that we cannot call a member of an existential value if the result type of that member uses any of the associated types in an invariant position. That prevents code like this from working:

extension Collection {
  func doSomething() -> some Collection<Element> { ... }
}

func test(strings: any Collection<String>) {
  let otherStrings = strings.doSomething() // error: result type uses Element in an invariant position
}

We don't have to prevent this, and indeed we want this call to succeed and produce an any Collection<String>. I believe the change is straightforward, allowing same-type requirements on primary associated types and inferring an existential where those primary associated types are bound appropriately. However, I'd prefer that this change be documented as part of this proposal, because I'd like any expansion of the expressivity of existentials to coincide with a change to this rule set out by SE-0309.

Doug

13 Likes
[Accepted] SE-0353: Constrained Existential Types
#23

... backing up my comment with a pull request with the requested change: SE-0353: Add "Covariant Erasure with Constrained Existentials" by DougGregor · Pull Request #1649 · apple/swift-evolution · GitHub

Doug

2 Likes
#24

Thanks Doug. The core team has discussed the review up to this point, and we've agreed to extend the review by another week in order to give the community time to review this revision.

#25

The core team has decided to accept this proposal including the above revision.

3 Likes