Generalized Type Erasure (Existential Types)

Those interested in pursuing this topic should familiarize themselves with the proposal @Austin worked on a couple years ago with guidance from @Joe_Groff and @Douglas_Gregor . It quite thoroughly explores generalized existentials and proposes a very nice design for Swift. I believe the latest draft is still found here: swift-evolution/XXXX-enhanced-existentials.md at az-existentials · austinzheng/swift-evolution · GitHub.

2 Likes

That is a really good explanation of what they are thinking of doing with improvements over the manifesto.

Comments on enhanced existentials:

  1. Does not allow equivalent of struct S: Equatable<Int>, Equatable<Double> { ... }, which can be a pain (it is frequently requested for Java for example which has generic interfaces with the generic type erased - like Haskell).

  2. The syntax is long winded, the draft even suggests typealias AnyCollection<Int> = Collection where .Element == Int; ironic when comparing to generic protocols (which they weren't, but in the context of this discussion it is).

  3. There would be associated types and generics with much the same capability, why not unify on one or the other? Or as Scala does allow either/both in all contexts. (Scala allows the equivalent of associated types and generics to be freely mixed over their equivalent of protocols, structs, and classes.)

There's been a lot of good feedback since that draft proposal was composed. If we do ever get to the stage where we can advance generalized existentials for review, and if the draft proposal is still useful at that point, I'd be happy to rewrite it to incorporate whatever insights have been gleaned in the meantime.

I'm not sure if you've seen it, but the generics manifesto calls generic protocols "unlikely" because the number of use cases for wanting generic protocols---beyond what generalized existentials can do---seems fairly limited.

Generic protocols aren't a very good match for, e.g., Collection, because even though it would be nice to be able to say Collection<String>, that would still need to be a generalized existential because Collection has associated types for Index and SubSequence.

As I see it, generalized existentials are the right solution to the problem of having to write type-erased wrappers for protocols with associated types, which fit well within the language. Generic protocols could be another feature on top that would allow one to express some extra patterns (e.g., protocol ConvertibleFrom<Source>), but don't displace generalized existentials.

Doug

3 Likes

Personally, I think it's worth nudging the proposal forward. I expect there's a lot of design iteration to be done before it comes up for a review (and that pesky issue of an implementation appearing).

Doug

2 Likes

I have been playing with possible designs for language-level support for actor model concurrency and other server side stuff (proxies, IoC, composable services, etc). A lot of those things almost mandate generalized existentials. I can't wait to see it happen.

But the few use-cases generic protocols do support are very compelling like generalising type conversions ala Rust's From, Into, TryFrom, TryInto

2 Likes

Please do! Let me know if you need any help, I'm very motivated in participating pushing this forward.

What are the parts of Austin's proposal which require more design attention?

1 Like

Isn't this a circular argument? If you had generic protocols you wouldn't need Index, SubSequence, etc. as associated types since Index<T>, SubSequence<T>, etc. would be types. You see these spurious associated types in many places in the standard library, they just complicate everything! Collection would be:

protocol Collection<T> {
    var firstIndex: Index<T> { get }
    subscript(bounds: Range<Index<T>>) -> SubSequence<T> { get }
    ...
}

Turn this around another way, what do associated types get you that generics don't? To answer my own question there is one area; types that don't need to be explicitly specified (particularly private types). EG the Java standard library protocol Collector (Collector is a fancy often parallel version of reduce) exposes the intermediate container type it uses to accumulate the results, ideally Collector would be:

protocol Collector<ElementType, ResultType> {
    private associatedtype AccumulatorType
   ...
}

That is why Scala allows both associated types and generic types, however associated types are rare compared to generic types (a non-private associated type is the same as a generic type in Scala). If you could only have one, surely you would pick generics! Also of note is that Swift doesn't support private associated types, so part of the above argument is moot anyway.

1 Like

I am also willing to help with work on the proposed design and proposal text in any way I can.

forall<I: IteratorProtocol> I where I.Element == Int

What about:

func f(x: T where T:Protocol && T.assoc==Int) {...}

@Slava_Pestov, @Joe_Groff
What about involving introspection in this and expanding semantics of where?

protocol StandartEquatable {
    func ==(lhs: Self, rhs: Self) -> Bool where lhs.Type == rhs.Type
}
protocol CustomEquatable {
    func ==(lhs: Any, rhs: Any) -> Bool where lhs.contains(function(named: "==", withArgumentSignature: (lhs.Type, rhs.Type))) && rhs.contains(function(named: "==", withArgumentSignature: (lhs.Type, rhs.Type)))
}
let a: StandartEquatable = 1
let b: StandartEquatable = 2
a == b //OK, types are identical
let c: CustomEquatable = SomeObject()
let d: CustomEquatable = AnotherObject()
c == d //OK, they both implement custom comparing against each other
let e: HeterogeneousCollection<Element: CustomEquatable> = [Type1(), Type2(), Type3()] //etc
let f: HomogeneousCollection<Element: StandartEquatable> = [Type(), Type(), Type()]