[Pitch] Achieving a heterogeneous collection of Equatables

Evolution Pitches
1

Hi all,

We know that as of Swift 2.0, if a protocol uses `Self` (like
Equatable does), it cannot be used in a heterogeneous collection. This
is a pain point, and has been talked about many times (for instance,
in Brent Simmons' Swift Diary: http://inessential.com/swiftdiary\).

I realize that this problem is intertwined with the use of associated
types, but if we forget about associated types for the moment, I
believe we can get a heterogeneous collection of Equatable elements to
work.

## The problem

There's no problem in creating a heterogeneous collection when there's
no `Self`:

    struct Collection<Element> {
    }

    protocol LooseEquatable {
        func isEqualTo(other: LooseEquatable) -> Bool
    }

    let c1 = Collection<LooseEquatable>()

The type characteristics of c1's elements can be deduced at compile
time, so this works.

But when `Self` is used in the protocol:

    protocol StrictEquatable {
        func isEqualTo(other: Self) -> Bool
    }

    let c2 = Collection<StrictEquatable>()

The type characteristics of c2's elements (for example, what are the
signatures of the methods that they should have) are indeterminable at
compile time because `Self` isn't yet "bound" to a type. For this to
work, the `Self` in StrictEquatable might have to bind to different
types at runtime for different subtypes of StrictEquatable.

This, per my understanding, is why Swift errors out. Assuming this
understanding is correct, I'd like to pitch a solution.

## The pitch

What I'm about to suggest is closely related to Joe Groff's suggestion
to use an EquatesWith here:
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002300.html

Let's say we introduce a new keyword called `Subtype` that can be used
when defining a protocol. `Subtype` binds to the closest subtype that
fully *implements* the protocol. (In contrast, `Self` binds to the
non-protocol type at the end of the protocol hierarchy.)

For example:

    // Type hierarchy: P -> Q -> R -> S
    // P, Q, R are protocols; S is a struct.

    protocol P {
        func f1(t: Subtype)
    }
    protocol Q : P {
        func f2()
    }
    protocol R : Q {
    }
    extension R {
        func f1(t: R) { } // Implementing P
        func f2() { } // Implementing Q
    }
    struct S : R {
    }

    let s = Collection<S>() // Okay: P's Subtype is bound to R
    let r = Collection<R>() // Okay: P's Subtype is bound to R
    let q = Collection<Q>() // Error: Subtype cannot be resolved
    let p = Collection<P>() // Error: Subtype cannot be resolved

`Self` can only bind to a non-protocol type like S, but `Subtype` can
bind to either a protocol or a non-protocol type, depending on where
the protocol gets implemented. Here, the P protocol is implemented in
the sub-protocol R, and so the `Subtype` in P binds to R. If `Subtype`
cannot be resolved, it should result in a compilation error.

In the standard library, if we replace all `Self`s in Equatable with
`Subtype`, we still maintain type safety (so `1 == 1.0` won't compile,
like it is now), but we will, at the same time, be able to create
heterogeneous collections of elements conforming to a sub-protocol of
Equatable, thereby fixing problems like this:
http://inessential.com/2015/08/05/swift_diary_9_where_im_stuck

That said, while this conceptually looks good, I have no idea whether
it's practically viable. I'd love to hear the community's and the
compiler team's take on this suggestion.

roop.

2

You wouldn't really need a different protocol keyword to achieve this. You're providing a conformance for the type protocol<R>: P, rather than saying T: P for all T: R, as happens today. That's a property of the conformance rather than the protocol itself. What you're proposing is closer to the other approach I laid out, allowing protocol types to be extended to conform to protocols themselves:

extension protocol<R>: P { // We're extending the protocol *type* to conform, not its conformers
  func f1(t: R) { }
}

-Joe

···

On Dec 21, 2015, at 1:45 AM, Roopesh Chander via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

We know that as of Swift 2.0, if a protocol uses `Self` (like
Equatable does), it cannot be used in a heterogeneous collection. This
is a pain point, and has been talked about many times (for instance,
in Brent Simmons' Swift Diary: http://inessential.com/swiftdiary\).

I realize that this problem is intertwined with the use of associated
types, but if we forget about associated types for the moment, I
believe we can get a heterogeneous collection of Equatable elements to
work.

## The problem

There's no problem in creating a heterogeneous collection when there's
no `Self`:

   struct Collection<Element> {
   }

   protocol LooseEquatable {
       func isEqualTo(other: LooseEquatable) -> Bool
   }

   let c1 = Collection<LooseEquatable>()

The type characteristics of c1's elements can be deduced at compile
time, so this works.

But when `Self` is used in the protocol:

   protocol StrictEquatable {
       func isEqualTo(other: Self) -> Bool
   }

   let c2 = Collection<StrictEquatable>()

The type characteristics of c2's elements (for example, what are the
signatures of the methods that they should have) are indeterminable at
compile time because `Self` isn't yet "bound" to a type. For this to
work, the `Self` in StrictEquatable might have to bind to different
types at runtime for different subtypes of StrictEquatable.

This, per my understanding, is why Swift errors out. Assuming this
understanding is correct, I'd like to pitch a solution.

## The pitch

What I'm about to suggest is closely related to Joe Groff's suggestion
to use an EquatesWith here:
[swift-evolution] protocol can only be used as a generic constraint because it has Self or associated type requirements

Let's say we introduce a new keyword called `Subtype` that can be used
when defining a protocol. `Subtype` binds to the closest subtype that
fully *implements* the protocol. (In contrast, `Self` binds to the
non-protocol type at the end of the protocol hierarchy.)

For example:

   // Type hierarchy: P -> Q -> R -> S
   // P, Q, R are protocols; S is a struct.

   protocol P {
       func f1(t: Subtype)
   }
   protocol Q : P {
       func f2()
   }
   protocol R : Q {
   }
   extension R {
       func f1(t: R) { } // Implementing P
       func f2() { } // Implementing Q
   }
   struct S : R {
   }

   let s = Collection<S>() // Okay: P's Subtype is bound to R
   let r = Collection<R>() // Okay: P's Subtype is bound to R
   let q = Collection<Q>() // Error: Subtype cannot be resolved
   let p = Collection<P>() // Error: Subtype cannot be resolved

`Self` can only bind to a non-protocol type like S, but `Subtype` can
bind to either a protocol or a non-protocol type, depending on where
the protocol gets implemented. Here, the P protocol is implemented in
the sub-protocol R, and so the `Subtype` in P binds to R. If `Subtype`
cannot be resolved, it should result in a compilation error.

In the standard library, if we replace all `Self`s in Equatable with
`Subtype`, we still maintain type safety (so `1 == 1.0` won't compile,
like it is now), but we will, at the same time, be able to create
heterogeneous collections of elements conforming to a sub-protocol of
Equatable, thereby fixing problems like this:
inessential: Swift Diary #9: Where I’m Stuck

That said, while this conceptually looks good, I have no idea whether
it's practically viable. I'd love to hear the community's and the
compiler team's take on this suggestion.

3

I like it! Extend an arbitrary existential (and it’s conforming types?) with additional conformances. That is pretty cool!

···

On Dec 22, 2015, at 10:48 AM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 21, 2015, at 1:45 AM, Roopesh Chander via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

We know that as of Swift 2.0, if a protocol uses `Self` (like
Equatable does), it cannot be used in a heterogeneous collection. This
is a pain point, and has been talked about many times (for instance,
in Brent Simmons' Swift Diary: http://inessential.com/swiftdiary\).

I realize that this problem is intertwined with the use of associated
types, but if we forget about associated types for the moment, I
believe we can get a heterogeneous collection of Equatable elements to
work.

## The problem

There's no problem in creating a heterogeneous collection when there's
no `Self`:

  struct Collection<Element> {
  }

  protocol LooseEquatable {
      func isEqualTo(other: LooseEquatable) -> Bool
  }

  let c1 = Collection<LooseEquatable>()

The type characteristics of c1's elements can be deduced at compile
time, so this works.

But when `Self` is used in the protocol:

  protocol StrictEquatable {
      func isEqualTo(other: Self) -> Bool
  }

  let c2 = Collection<StrictEquatable>()

The type characteristics of c2's elements (for example, what are the
signatures of the methods that they should have) are indeterminable at
compile time because `Self` isn't yet "bound" to a type. For this to
work, the `Self` in StrictEquatable might have to bind to different
types at runtime for different subtypes of StrictEquatable.

This, per my understanding, is why Swift errors out. Assuming this
understanding is correct, I'd like to pitch a solution.

## The pitch

What I'm about to suggest is closely related to Joe Groff's suggestion
to use an EquatesWith here:
[swift-evolution] protocol can only be used as a generic constraint because it has Self or associated type requirements

Let's say we introduce a new keyword called `Subtype` that can be used
when defining a protocol. `Subtype` binds to the closest subtype that
fully *implements* the protocol. (In contrast, `Self` binds to the
non-protocol type at the end of the protocol hierarchy.)

For example:

  // Type hierarchy: P -> Q -> R -> S
  // P, Q, R are protocols; S is a struct.

  protocol P {
      func f1(t: Subtype)
  }
  protocol Q : P {
      func f2()
  }
  protocol R : Q {
  }
  extension R {
      func f1(t: R) { } // Implementing P
      func f2() { } // Implementing Q
  }
  struct S : R {
  }

  let s = Collection<S>() // Okay: P's Subtype is bound to R
  let r = Collection<R>() // Okay: P's Subtype is bound to R
  let q = Collection<Q>() // Error: Subtype cannot be resolved
  let p = Collection<P>() // Error: Subtype cannot be resolved

`Self` can only bind to a non-protocol type like S, but `Subtype` can
bind to either a protocol or a non-protocol type, depending on where
the protocol gets implemented. Here, the P protocol is implemented in
the sub-protocol R, and so the `Subtype` in P binds to R. If `Subtype`
cannot be resolved, it should result in a compilation error.

In the standard library, if we replace all `Self`s in Equatable with
`Subtype`, we still maintain type safety (so `1 == 1.0` won't compile,
like it is now), but we will, at the same time, be able to create
heterogeneous collections of elements conforming to a sub-protocol of
Equatable, thereby fixing problems like this:
inessential: Swift Diary #9: Where I’m Stuck

That said, while this conceptually looks good, I have no idea whether
it's practically viable. I'd love to hear the community's and the
compiler team's take on this suggestion.

You wouldn't really need a different protocol keyword to achieve this. You're providing a conformance for the type protocol<R>: P, rather than saying T: P for all T: R, as happens today. That's a property of the conformance rather than the protocol itself. What you're proposing is closer to the other approach I laid out, allowing protocol types to be extended to conform to protocols themselves:

extension protocol<R>: P { // We're extending the protocol *type* to conform, not its conformers
func f1(t: R) { }
}

4

What you're proposing is closer to the other approach I laid out,

allowing protocol types to be

extended to conform to protocols themselves

I couldn't find the thread you've explained this earlier, so I'm going by
what you've described in this thread.

extension protocol<R>: P { // We're extending the protocol *type* to

conform, not its conformers

  func f1(t: R) { }
}

But we *do* want conformers of R to also conform to P (and have func f1's
implementation available in them, by virtue of conforming to R). If we
didn't, then if we apply this solution to the Swift stdlib, and we have the
following type hierarchy when we use it (considering the example from
http://inessential.com/2015/08/05/swift_diary_9_where_im_stuck\):

protocol Equatable (in stdlib)
-> protocol Hashable (in stdlib)
-> protocol Account (in app)
     with a protocol extension:
     extension protocol<Account> : Equatable {
         func isEqual(lhs: Account, rhs: Account) -> Bool { return false }
     }
-> class TwitterAccount (in app)

If I understand your solution correctly, the above setup means that the
Account protocol and the TwitterAccount class don't conform to Equatable -
only that the Account existential type conforms to Equatable. So we can't
do twitterUser1 == twitterUser2, and being able to do that is desirable for
this use case.

What I was proposing can be seen as a variation of your EquatesWith
approach, the difference being that the "where EquatesWith == Drawable"
part is automatically inferred by the compiler based on where the
super-protocol gets implemented in the type hierarchy. It could be
implemented in a class/struct, in which case `Subtype` would behave similar
to `Self`, or it could be implemented in a protocol, in which `Subtype`
would bind to the protocol (like, say, `Drawable`).

roop.

···

On Tue, Dec 22, 2015 at 10:18 PM, Joe Groff <jgroff@apple.com> wrote: