Generalized Type Erasure (Existential Types)

Evolution Pitches
1

This idea comes from GHC's ExistentialQuantification extension to the Haskell Language. My original pitch was horribly unclear, and suggested a confusing syntax, so if you read it in its original form, find it revised below:

Context

Let's start with a simplified version of the IteratorProtocol protocol from the standard library, restricted to iterating only over Int values:

protocol IteratorOverInt {
    mutating func next() -> Int?
}

It is completely valid to store instances of types conforming to IteratorOverInt, without needing to know the concrete type at compile time. So we could very well have something like:

struct ContainsIntIterator {
    var iterator: IteratorOverInt
    ... // Other fields
}

This struct declaration is completely valid, and its type is completely independent of the concrete (runtime) type of iterator. But now say we are using the IteratorProtocol from the standard library:

struct ContainsIntIterator {
    var iterator: ... // What do we do?
    ...
}

Outside of its generics system, Swift has no built-in way to express what we would like iterator to be: an instance of a type conforming to IteratorProtocol, where the Element associated type in the conformance is Int. We could solve the problem by making ContainsIntIterator generic:

struct ContainsIntIterator<I: IteratorProtocol> where I.Element == Int {
    var iterator: I
    ...
}

This allows us to specify the type of iterator exactly as we want it, but in doing so we must parameterize the ContainsIntIterator struct by the concrete type of I. In some cases this makes sense, but in others, it may simply complicate code: what if a user of ContainsIntIterator has no reason to care about the contained iterator's concrete type?

You can apply targeted solutions per protocol, such as the standard library's AnyIterator<Element>, but I pitch a new language feature that would provide first-class support for this and other use-cases.

The Pitch

What if Swift brought all the features of generics to stored properties and variables? What if we could write this:

struct ContainsIntIterator {
    var iterator: (forall<I: IteratorProtocol> I where I.Element == Int)
    ...
}

So what would this mean? iterator would be an instance of some unknown (at compile time) type I, with constraints given in the familiar where syntax. The forall would exist to introduce new type variables, just as generics do, but would not allow them to escape beyond the forall context.

Within this struct's methods, you would be able to use iterator exactly as you would in the generic-struct version; the difference is that ContainsIntIterator no longer "leaks" the concrete type of iterator, because neither it nor any of its consumers actually care what that is.

Importantly, I am not suggesting anything similar to C++'s templated variables (where a template parameter would be provided at each usage site).

Other Use Cases

Admittedly the above example was quite contrived. As something more concrete (and as something which I do not know how to express at all in current Swift), I present a Parser protocol for a parser-combinator I'm working on:

protocol Parser {
    associatedtype Result
    func parse<C: Collection>(_ input: C) throws -> Result where C.Element == Character
}

A Parser is a type that knows how to parse a collection of characters into some Result. It should not care about the concrete type of the selection, and so the required parse method is generic over all Collections.

Since my parsers will be constructed from a large number of re-usable and generic sub-parsers, their concrete types will be quite large. I would like a way to completely erase the type of a parser while maintaining its functionality, primarily to return parsers from functions, but also to support arrays of parsers with my combinators.

I set out to write an AnyParser<Result>, but there is no way to erase the generic type of parse; there is no way to store a generic closure. Of course, I could make an AnyParser<Result, C: Collection>, but now AnyParser is not a Parser!

With my pitch, I would not need any such AnyParser type; if I wanted a function foo that returned any kind of parser for an Int, I could write its signature as:

func foo(...) -> (forall<P: Parser> P where P.Result == Int)
1 Like
2

Sounds quite complicated — at least compared to "protocol Sequence<T>"
which would also allow us to get rid of AnySequence.
But maybe your proposal has a higher chance to be accepted...
[string escaping can be really hard :)]

3

You mean

protocol Baz { ... }
protocol Bar { associatedtype Qux }

protocol Foo {
    associatedtype B: Bar where B.Qux: Baz

    var field: B
}

which is possible as you see...

5

I think this only defers the problem; I cannot simply pass around a Foo if it is a protocol with an associated type like that.

It is true that if we had erasure simply for protocols with associated types (and without support for arbitrary constraints), I could implement my above existential type signature with a dummy protocol like Foo, but this seems like boilerplate that obscures the intent of the code.

6

Declaring a type and a property isn't the same thing. Are you sure you can declare such properties in Haskell? How do you plan on using such a property? You will access it specifying a parameter? What if I access it with a different one? What should it even return, not to mention what will I mutate if I try to?

let a = A()
a.field<Int>.something
a.field<Bool>.something

a.field<SomeOtherSuitableType>.something = something
7

If protocols were generic you could write:

protocol Foo<B> where B.Qux: Baz {
    var field: B
}

Which I find easier to read.

1 Like
8

Universally parametrizing protocols is a non-starter, at least for Swift 5.

It's easier to write

struct Foo<B: Bar> where B.Qux: Baz {
    var field: B
}

if you want it directly in a struct (non-protocol oriented way).

Actually you can if you don't need to store it as Foo. Generic methods to the rescue.

9

I've rewritten my proposal; it was admittedly very unclear, and hopefully it is more clear now.

I'm not trying to suggest something like C++'s templated variables; rather, I'm suggesting the ability to have "boxes" for instances of unknown-but-constrained-at-compile-time types, where you could only use something from such a box to the extent you could if its type were a generic parameter.

Assignment and mutation would work similarly; you could assign anything to such a box if its type fit within the box's constraints, and it would replace the original value.

I also agree that generics, as they are currently, account for the vast majority of use cases, but for the cases where tracking generic parameters becomes a chore that only satisfies the type checker, I think this would be a godsend.

10

Personally I really want this feature. If I understand you proposal correctly, I think you are proposing something similar to this?

3 Likes
11

But you can't inherit from struct, therefore you need a protocol or something else.

As an aside none of this is going to happen anytime soon, therefore probably optimum use of discussion time to design the best version of the feature whilst Swift 5 is bedded down.

1 Like
12

Yah, that's exactly what I'm thinking of. Guess it would have done me well to check there first.

13

Aha, now this makes more sense. Somewhat covered in the rationale @Justin_Jia linked.

14

Generalized Existentials get tricky, e.g. from the manifesto:

protocol Equatable {
  func ==(lhs: Self, rhs: Self) -> Bool
  func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = ...
let e2: Equatable = ...

if let storedInE1 = e1 openas T {     // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T {      // is e2 also a T?
    if storedInE1 == storedInE2 { ... } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

This is much easier with a generic protocol:

protocol Equatable { // Type is: Equatable<T> where T = Self
  func ==(lhs: Self, rhs: Self) -> Bool
  func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = 1 // Type is Equatable<Int>
let e2: Equatable = 2 // Type is Equatable<Int>

if e1 == e2 { ... } // OK: also verified at compile time not runtime - which is nice.
15

If you put a static == constraint on Self, then it's not really an existential type anymore; you're (perhaps inadvertently) specifying the concrete type, which is what existential types allow you to avoid.

16

You can still write a function that accepts Equatable<Int> and pass it any Equatable<Int>. Maybe what you are driving at is that you can't write a function that accepts Equatable<Any> (note Any) and pass it an Equatable<Int> (note Int). But that is a seperate issue, variance in generics.

17

But if Equatable<Int> requires that Self == Int (which is what I parse from your example), then you are requiring Self to be Int. So then yes, you could pass any Equatable<Int>, but there is only one type that is Equatable<Int>: Int.

18

The compiler wouldn't allow that anyways (Same-type requirement makes generic parameters 'T' and 'Self' equivalent). The correct way would be

protocol Equatable<T> { 
  func ==(lhs: T, rhs: T) -> Bool
  func !=(lhs: T, rhs: T) -> Bool
}

which the compiler still wouldn't allow though (operator requirements must have at least one argument of type Self)

This would make the protocol universal, but it still remains existential being a protocol. (If we consider existentially quantified types without parameters can be called existentials. Otherwise, they are simply abstract types)

19

Yeah Equatable as written doesn't work (I chose it because that is what the manifesto used as an example), but you would change Equatable to something like:

protocol Equatable<T> {
    var valueToEquate: T { get }
    func equals(_ other: T) -> Bool
    static func ==(lhs: Equatable<T>, rhs: Equatable<T>) -> Bool
    static func !=(lhs: Equatable<T>, rhs: Equatable<T>) -> Bool
}

extension Equatable {
    static func ==(lhs: T, rhs: T) -> Bool { return lhs.equals(rhs.valueToEquate) }
    static func !=(lhs: T, rhs: T) -> Bool { return !lhs.equals(rhs.valueToEquate) }
}

You could then write classes/structs that were Equatable<Int>, e.g.:

struct BoxInt: Equatable<Int> {
    let value: Int
    var valueToEquate: Int { return value }
    func equals(_ other: Int) { return value == other }
}
20

Protocols with associated types are generic protocols, but using a different syntax. Conceptually they are the same, so we are talking about the same thing here.

We can still do something like this if generalized existentials are supported:

typealias Equatable<Int> = Equatable where Element == Int
21

When I think generic protocols, I think of something analogous to generic traits in Rust, or multi-parameter type classes in Haskell, which are a very different concept indeed. In both those languages, associated types still exist, and behave as they do in Swift; there is exactly one concrete specification of each associated type for each conformer-protocol pair; in other words, a protocol with one or more associated types can only be conformed to once.

Meanwhile, with generic protocols, every specialization of the protocol would be considered a unique protocol itself, i.e. Equatable<Int> and Equatable<Double> would be considered entirely different protocols. This would in turn allow what looked like multiple-conformance, i.e. a type that conformed to both Equatable<Int> and Equatable<Double>.

In the Rust world, this is used for traits (Rust's equivalent to protocols) that describe relationships between a Self and one or more other types. For instance, the + operator is provided by a conformance to the Add<RHS> trait, which defines what happens for Self + RHS.

I would definitely like to see generic protocols come to Swift at some point, though since Swift has ad-hoc overloading, they're a less critical feature than they are in Rust or Haskell (neither of which have such a thing).

2 Likes