[Pitch] Constrained Existential Types

Hello, Swift evolution!

@codafi has been working on the following pitch for primary associated type constraints on existential types, and we'd love your feedback! This pitch is applying SE-0346: Lightweight same-type requirements for primary associated types to existential types.

Note that discussion of generalized existential type constraints is happening over here: Generalized opaque and existential type constraints

Please let us know your questions, thoughts, and other constructive feedback!

-Holly


Constrained Existential Types

Introduction

Existential types complement the Swift type system’s facilities for abstraction. Like generics, they enable a function to take and return multiple possible types. Unlike generic parameter types, existential types need not be known up front when passed as inputs to a function. Further, concrete types can be erased (hidden behind the interface of a protocol) when returned from a function. There has been a flurry of activity in this space with SE-0309 unblocking the remaining restrictions on using protocols with associated types as existential types, and SE-0346 paving the way for a lightweight constraint syntax for the associated types of protocols. Building directly upon those ideas, this proposal seeks to re-use the syntax of lightweight associated type constraints in the context of existential types.

any Collection<String>

In essence, this proposal seeks to provide the same expressive power that SE-0341 gives to some types to any types.

Motivation

Though SE-0309 provides the ability to use protocols with associated types freely, it does not leave any room for authors to further constrain the associated types of those protocols, creating a gap in expressiveness between generics and existentials. Consider the implementation of a type-erased stack of event producers and consumers:

protocol Producer { 
  associatedtype Event
  
  func poll() -> Self.Event?
}

protocol Consumer {
  associatedtype Event
  
  func respond(to event: Self.Event)
}

If a hypothetical event system type wishes to accept an arbitrary mix of Producers and an arbitrary mix of Consumers, it is free to do so with existential types:

struct EventSystem {
  var producers: [any Producer]
  var consumers: [any Consumer]
  
  mutating func add(_ producer: any Producer) { self.producers.append(producer) }
}

However, we run into trouble when trying to compose producers and consumers with one another. As any given Producer yields data of an unspecified and unrelated Event type when poll’ed, Swift will (rightly) tell us that none of our consumers can safely accept any events. One solution would be to make EventSystem generic over the type of events and require Producer and Consumer instances to only return those events. As it stands, this also means restricting the producers and consumers to be concrete, with the added downside of requiring us to homogenize their types - ad-hoc type erasure strikes again:

struct EventSystem<Event> {
  var producers: [AnyProducer<Event>]
  var consumers: [AnyConsumer<Event>]
  
  mutating func add<P: Producer>(_ producer: P)
    where P.Event == Event
  { 
    self.producers.append(AnyProducer<Event>(erasing: producer)) 
  }
}

In this example, we have sacrificed quite a lot for type safety - and also have to maintain two extra type erasing wrappers for producers and consumers. Really, what is missing is the ability to express the fact that the producer and consumer types don’t matter (existential types) but the data they operate on does (generic constraints). This is where constrained existential types shine. When combined with the power of primary associated types from SE-0346, it allows us to write the code we wanted to in the first place:

struct EventSystem<Event> {
  var producers: [any Producer<Event>]
  var consumers: [any Consumer<Event>]
  
  mutating func add(_ producer: any Producer<Event>) { 
    self.producers.append(producer) 
  }
}

Proposed solution

Existential types will be augmented with the ability to specify constraints on their primary associated types. When an existential type appears with such constraints, they will be converted into same-type requirements.

protocol P<T, U, V> { }

var xs: [any P<B, N, J>] // "Equivalent" to [any P] where P.T == B, P.U == N, P.V == J

Detailed design

The syntax of existential types will be updated to accept constraint clauses. Type inference procedures will be updated to apply inference rules to generic parameters appearing as part of parameterized existential types.

The Swift type system and runtime will accept casts from parameterized existential types to non-parameterized existential types and vice versa, as well as casts that refine any constrained primary associated types. Upcasts and downcasts to, from, and between existential types will be updated to take these additional constraints into account:

var x: any Sequence<T>
_ = x as any Sequence // trivially true
_ = x as! any Sequence<String> // requires examining Sequence.Element at runtime
_ = x as! any Sequence<Int> & Collection<String> // an impossible type, but we have to prove that at runtime

Effect on ABI stability

As constrained existential types are an entirely additive concept, there is no impact upon ABI stability.

Alternatives considered

Aside from the obvious of not accepting this proposal, we could imagine many different kinds of spellings to introduce same-type requirements on associated types. For example, a where-clause based approach as in:

any (Collection where Self.Element == Int)

Syntax like this is hard to read and use in context and the problem becomes worse as it is made to compose with other existential types and constraints. Further it would conflict with the overall direction that generic constraints in Swift are taking as of SE-0346. Generalized constraint syntaxes are out of scope for this proposal and are mentioned later as future directions.

Future directions

Generalized Constraints

This proposal intentionally does not take a position on the generalized constraint syntax considered during the review of SE-0341. To take one spelling:

any Collection<.Index == String.Index>

Though when and if such a syntax is available we expect it to apply to constrained existential types. Possible designs for generalized constraints on existential types are discussed in Generalized opaque and existential type constraints.

Opaque Constraints

One particularly interesting construction is the composition of opaque types and constrained existential types. This combo allows for a particularly powerful form of type abstraction:

any Collection<some View>

This type describes any value that implements the Collection protocol but whose element type is an opaque instance of the View protocol. Today, Swift’s generics system lacks the ability to express same-type constraints with opaque types as an operand.

Even More Generalized Existentials

Constraints on existing primary associated types are hardly the only thing existential types can express. Swift’s type system can be given the ability to open arbitrary (constrained) type parameters into scope via an existential. This enables not just top-level usages as in

any<T: View> Collection<T>

But also nested usages as in

any Collection<any<T: Hashable> Collection<T>>

Essentially enabling ad-hoc abstraction over generic types of any shape at any point in the program.

38 Likes

Assuming SE-0346 is adopted, this is a very logical direction. Treating some and any as duals and building out features that work with both wherever they make sense is, IMO, actively desirable.

As to future directions, any Collection<any<T: Hashable> Collection<T>> is a doozy.

17 Likes

Could you elaborate on why this would have to be proven at runtime? Couldn’t the compiler look at the constraints of the two protocols and come up with a compile-time diagnostic?

4 Likes

Looks very promising!

Does this allow the ability to return multiple types from a function as long as they conform to the giver protocol with the necessary associated type? E.g,

func getCollection(from someEnum: MyEnum) -> any Sequence<String> {
  switch someEnum {
  case .first: return [“a”, “c”, “c”, “a"]
  case .second: return [“a”, “b”, “c”] as Set<String>
  case .third: return [3, 4, 5].lazy.map(String.init)
  case .fourth: return CollectionOfOne(“hey”)
  }
}
1 Like

In this sentence:

In essence, this proposal seeks to provide the same expressive power that SE-0341 gives to some types to any types.

might it be clearer instead to link to SE-0346 (which actually provides the associated type constraints feature for opaque types)? I was initially confused by the comparison to SE-0341, until I realized that the link was specifically to a "future direction" anchor.

1 Like

Here's one thing that feels very odd to me after scanning this particular pitch.

If you're going to permit same-type requirement on existentials via any P<Foo>, why is there no mention on the same functionality through a typealias? I would at least expect that after this proposal I'll be able to write typealias SomeP<T> = P where P.Assoc == T and then any SomeP<Foo>.

2 Likes

P.Assoc isn’t actually the name of a type, because the protocol type itself doesn’t have member types. You’d need some sort of P where .Assoc == T, and at that point you’re just inventing the more general syntax for SE-0346. When we have that syntax, we should be able to use it for existentials as well.

2 Likes

I think in this case it probably would be provable statically that this is an invalid constraint, the same way that a generic function can’t constrain the same associated type to different things.

2 Likes

I think this pitch needs a section like the following in the detailed design.

Equality of constrained protocol types

The language must define when two types that are derived differently in code are in fact the same type. In principle, it would make sense to say that two constrained protocol types are the same if and only if they have exactly the same set of possible conforming types. Unfortunately, this rule is impractical in Swift’s type system for complex technical reasons. This means that some constrained protocol types which are logically equivalent to each other will be considered different types in Swift.

The exact rule is still being determined, but for example, it is possible that the type any P & Q<Int> might be considered different from the type any P<Int> & Q even if the associated types of these protocols are known to be equal. Because these types have equivalent logical content, however, there will be an implicit conversion between them in both directions. As a result, this is not expected to pose a large practical difficulty. [Obviously the rule should be precisely described in the actual proposal.]

Substitutions of constrained protocol types written with the same basic “shape”, such as any P<Int> and any P<T> in a generic context where T == Int, will always be the same type.

[I think the complex technical reasons might be out of scope for the proposal document, but I can get into them in the pitch if people are interested.]

10 Likes

+1. I can't wait for this. Very exciting.

These recent improvements around existential are very welcome :tada:

1 Like

I am unredeemably biased here, but to me this is the obvious "capstone" proposal that ties together the sequence of SE-0309, SE-0341, and SE-0346 to address a longstanding pain point with Swift.

Doug

16 Likes

I got chill bumps all up my arms :clap:.
I can't wait to watch you will present this, and all the rest that is happening around generics/existentials at the upcoming WWDC.

2 Likes

I think the introduction and the motivation sections are extremely well written! However, I got a bit confused trying to understand the example code.

Initially, in the type-erasing example the add function looks like this:

Based on SE-0341, I would translate this to a function with an opaque parameter some Producer<Event>.

mutating func add(_ producer: some Producer<Event>)

Instead, later on it was rewritten as one with any Producer<Event>:

Can I also insert generic parameter of type P into [any Producer]? How is the interoperability between these 2 features?

This is listed as a future direction, but would the spelling any Collection<some Hashable> be possible with your proposal? Or would that also be a future direction?

What about some Collection<any Hashable>?

I seem to remember that some Collection<some Hashable> is already allowed after SE-0341 so it feels like these should already compose in some way.

Yes, it does. It's no different than returning any other existential, for example if your return type was any Sequence without the constraint (which already works in 5.7 snapshots).

1 Like

In case anyone missed it, this proposal is now under review over here:

Please ask further questions over on the review thread!

1 Like