Status of generalized existentials

[dan-zheng]

Hi all,

I'm curious about the status of generalized existentials. From the Generics Manifesto:

Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
  associatedtype Element
  mutating func next() -> Element?
}

let it: IteratorProtocol = ...
it.next()   // if this is permitted, it could return an "Any?", i.e., the existential that wraps the actual element

Generalized existentials would make it easier to work with protocols with associated types (PATs):

• They enable values with a PAT type (e.g. let x: Equatable)
• They can replace the type-erasure pattern for dealing with PATs (e.g. AnyCollection, AnyHashable, etc. can become just Collection, Hashable with minimal support)
  • This reduces the jump in difficulty from working with protocols w/o associated types to PATs.

---

I'm wondering:

• If generalized existentials are on the roadmap for Swift generics
• If people are actively working on generalized existentials
• What's necessary to support generalized existentials
  • Is additional runtime support needed to represent "protocol values"?
  • Do new user-facing features need to be introduced (e.g. opening existentials)?
  • Are there major blockers preventing development?

Thanks!

[nuclearace (Erik Little)]

They’re a highly desired feature. I am curious to know if they need to do be done before ABI is settled. If they can’t be added after ABI stability, I’m seriously worried we may never see them. They’re probably my #1 request.

I think the biggest limiter is that they require pretty good knowledge of multiple parts of the compiler. And that usually means a multi coordinated effort to implement.

[dan-zheng]

If it's possible to create a list of specific tasks for generalized existentials, that would be great for coordinating community effort! I imagine not everything is scoped out, though.

[rxwei (Richard Wei)]

Here's a concrete use case that demonstrates that the design of generalized machine learning APIs is blocked by generalized existentials (while there are other language limitations, GE is a big one).

Given a data structure representing a parameterized model, there needs to be a collection containing all parameters in which each element is partly type-erased but capable of math operations.

typealias AnyFloatingPointTensor = TensorProtocol where Scalar : FloatingPoint

struct MyMLModel {
  var w1, b1, w2, b2: Tensor<Float>
  var w3, b3: Tensor<BFloat16>
  var allParameters: [AnyFloatingPointTensor] {
    return [w1, b1, w2, b2, w3, b3]
  }
}

Then in the optimizer code, the user or library designer can write:

for inout θ in model.allParameters {
  θ -= θ * learningRate
}

Here's some more context:

Swift pointers to value types

In traditional metaprogramming ML frameworks, optimizer APIs have never been a hard problem because an optimizer builder always runs a host language loop to build graph components for each parameter update at runtime. However in Swift for TensorFlow, there is no way to build generalized ML optimizers today because the TensorFlow extension is a "non-metaprongramming ML framework". Beyond synthesizing a computed property setter/getter and supporting inout pattern, we also need the compiler to be …

[Paul_Cantrell]

The lack of generalized existentials is the reason Siesta uses this loosey-goosey conditional casting sugar for getting resource contents, instead of making its central Resource type be a generic Resource<T>.

(For those who don’t know Siesta, the short version is that a core feature that obviously should be generic isn’t.)

I’ve investigated implementing Resource<T> with current Swift, and it is possible, but (1) it leads to an explosion of AnyFoo types with unacceptable levels of duplicate code, and (2) the mental & syntactic burden on clients of the library is just too great.

Along with improved String ergonomics and better reflection, this is one of the few things that keeps Swift from being a fully mature language in my book. I realize that the core team has daunting problems that are far more immediate, but it would be nice if there were a way for the community to help move this along.

[nuclearace (Erik Little)]

If it's possible to create a list of specific tasks for generalized existentials, that would be great for coordinating community effort! I imagine not everything is scoped out, though.

A list would be great. Would be even better is if we can break that list up into specific tickets that could be worked on in pieces instead of a giant monolithic effort. I think we could probably start scoping out the required work now, we'd just need some input from some people who have some idea of what changes would be needed.

@Joe_Groff Do you have input into whether this could be an additive feature post-ABI stability? Or are there some parts of this feature that we should figure out and bake into the ABI now?

[DevAndArtist (Adrian Meister)]

I think we should aim an incremental support for those features with each major Swift release. From my point of view the next step would be to allow the where clause on existentials (and force it to typealias declarations only - I'm not going to discuss in this thread on why).

@hartbit should we revive our plans for drafting a formal proposal for that in the next few weeks? Without raising the hopes, we still would need someone to implement it since it's yet another huge and non-trivial generic feature.

[anandabits (Matthew Johnson)]

should we revive our plans for drafting a formal proposal for that in the next few weeks?

If you do pursue this you might want to start by revisiting the draft @Austin wrote a couple years ago: https://github.com/austinzheng/swift-evolution/blob/az-existentials/proposals/XXXX-enhanced-existentials.md and subset out the relevant parts.

[DevAndArtist (Adrian Meister)]

That was basically the plan, thank you for mentioning it again though.

[Joe_Groff]

Yes, we know we aren't going to implement generalized existentials before ABI stability, and we know we'll need to migrate some standard library type erasers to proper existentials at some point in the future when we do properly support them.

[total_swiftification]

Hi, Joe . I am wondering what happened to this feature : abi is now fixed, and no sings of introduction of GE is in sight. Is this dead?

[andybezaire (andy)]

Is there any interest in reviving this?

I would love to take my:

func stringPublisher() -> AnyPublisher<String, None> {
  Just(5)
    .map { String(describing $0) }
    .eraseToAnyPublisher()
}

and make it be:

type alias AnyPublisher<I, O> = Publisher where .Input = I, .Output = O

func stringPublisher() -> AnyPublisher<String, None> {
  Just(5)
    .map { String(describing $0) }
}

and never need to call .eraseToAnyPublisher() again.

[dan-zheng]

@andybezaire

Is there any interest in reviving this?

I would love to take my: [...] and make it be:

type alias AnyPublisher<I, O> = Publisher where .Input = I, .Output = O

Hi Andy! It seems like you're interested in a language feature I'd call "typealiases with extra syntactic generic requirements", which is a bit different from "generalized existentials".

Check out this thread:

Generic typealiases with additional constraints?

Right, but it would behave like an existential type when used in a generic constraint. If I wrote this today typealias Foo<T> = T where T : Sequence, T.Element == Int Then it is not valid to write func foo<T : Foo>(_: T) {} But presumably, you could do that if you instead wrote typealias Foo = Sequence where .Element == Int So the syntax being proposed here is quite different than a generic typealias. It is more like a shorthand for a protocol type and a where clause to be expanded at th…

For interested compiler hackers, I would say this feature is a medium t-shirt size.

[andybezaire (andy)]

Yes I think I typed it wrong. Thanks for the link. Maybe this is the way I should have typed it:

type alias AnyPublisher<I, O> = Any<Publisher where .Input = I, .Output = O>

func stringPublisher() -> AnyPublisher<String, None> {
  Just(5)
    .map { String(describing $0) }
}

I think we would need to be able to constrain the associated types of the generic that is used by Any<T>

Does that make more sense? Combine is great but I would like to get rid of all of those .eraseToAnyPublisher()'s if possible.

[dan-zheng]

Indeed, that makes sense - thanks. Truly existential (dread and terror)