Synthesizing Equatable, Hashable, and Comparable for tuple types

[Mike_Kluev]

can you outline how extensions and protocol conformances might look
for structural types? to compare the ugliness of both approaches.

Mike

···

on Date: Tue, 21 Nov 2017 22:54:21 -0800 Douglas Gregor <dgregor@apple.com> wrote:

On Nov 21, 2017, at 10:48 PM, David Hart <david@hartbit.com> wrote:
>
> On 22 Nov 2017, at 07:41, Douglas Gregor via swift-evolution < > swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
>>
>> I think it’s straightforward and less ugly to make structural types
allow extensions and protocol conformances.
>
> Can somebody explain to me what is less ugly about that? I would have
naturally thought that the language would be simpler as a whole if there
only existed nominal types and all structural types were just sugar over
them.

See Thorsten’s response with, e.g.,

              Function<Double, InoutParam<String>, Param<Int>>

which handles “inout” by adding wrappers around the parameter types (which
one would have to cope with in any user of Function), but still doesn’t
handle argument labels. To handle argument labels, we would need something
like strings as generic arguments. We’d also need to handle calling
conventions and anything else we invent for function types.

[Douglas_Gregor]

There are some examples at

  https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#extensions-of-structural-types

e.g., making all tuples of Equatable elements Equatable (which also mixes in conditional conformances and variadic generics):

  extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type "(Elements...)" to be Equatable
}

One could imagine adding a “curry” operation to function types:

  extension<Param1, Param2, Result> (Param1, Param2) -> Result {
    var curried: (Param1) -> (Param2) -> Result {
      return { (arg1: Param1) in { (arg2: Param2) in self(arg1, arg2) } }
    }
  }

Or perhaps making metatypes Hashable so they can be used as keys into a Dictionary:

  extension<T> T.Type: Hashable {
    var hashValue: Int {
      return ObjectIdentifier(self).hashValue
    }

   static func ==(lhs: T.Type, rhs: T.Type) -> Bool { /* standard library magic */ }
  }

  - Doug

···

On Nov 22, 2017, at 2:59 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

on Date: Tue, 21 Nov 2017 22:54:21 -0800 Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

> On Nov 21, 2017, at 10:48 PM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:
>
> On 22 Nov 2017, at 07:41, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org> <mailto:swift-evolution@swift.org <mailto:swift-evolution@swift.org>>> wrote:
>
>>
>> I think it’s straightforward and less ugly to make structural types allow extensions and protocol conformances.
>
> Can somebody explain to me what is less ugly about that? I would have naturally thought that the language would be simpler as a whole if there only existed nominal types and all structural types were just sugar over them.

See Thorsten’s response with, e.g.,

              Function<Double, InoutParam<String>, Param<Int>>

which handles “inout” by adding wrappers around the parameter types (which one would have to cope with in any user of Function), but still doesn’t handle argument labels. To handle argument labels, we would need something like strings as generic arguments. We’d also need to handle calling conventions and anything else we invent for function types.

can you outline how extensions and protocol conformances might look for structural types? to compare the ugliness of both approaches.

[Chris_Lattner]

One could imagine adding a “curry” operation to function types:

Right, having non-nominal types participate in the generics system would be undoubtably awesome! :)

Or perhaps making metatypes Hashable so they can be used as keys into a Dictionary:

  extension<T> T.Type: Hashable {

Ok, so you just happened to pick a simple one: what is the benefit of plumbing knowledge of metatypes through the entire generics system, rather than define a “Swift.Metatype” type, and defining stuff against it?

-Chris

···

On Nov 24, 2017, at 3:47 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

    var hashValue: Int {
      return ObjectIdentifier(self).hashValue
    }

   static func ==(lhs: T.Type, rhs: T.Type) -> Bool { /* standard library magic */ }
  }

  - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[Mike_Kluev]

that's already the case.. (all tuples of equatable elements are equatable).
no?

Mike

···

On 24 November 2017 at 23:47, Douglas Gregor <dgregor@apple.com> wrote:

e.g., making all tuples of Equatable elements Equatable

[xwu (Xiaodi Wu)]

No, tuples do not conform to any protocols. There are hardcoded
implementations of `==` up to some arity in the stdlib to partially
mitigate the lack of protocol conformance.

···

On Fri, Nov 24, 2017 at 9:08 PM, Mike Kluev via swift-evolution < swift-evolution@swift.org> wrote:

On 24 November 2017 at 23:47, Douglas Gregor <dgregor@apple.com> wrote:

e.g., making all tuples of Equatable elements Equatable

that's already the case.. (all tuples of equatable elements are
equatable). no?

[Douglas_Gregor]

One could imagine adding a “curry” operation to function types:

Right, having non-nominal types participate in the generics system would be undoubtably awesome! :)

Or perhaps making metatypes Hashable so they can be used as keys into a Dictionary:

extension<T> T.Type: Hashable {

Ok, so you just happened to pick a simple one:

Yup. Try to make a nominal type to describe labeled tuples.

what is the benefit of plumbing knowledge of metatypes through the entire generics system,

That’s not how one would implement this in the compiler. Most of the compiler doesn’t care whether the subject of a protocol conformance is a nominal type or not, and those scattered (but numerous) places that do care should be straightforward to generalize to include structural types. It’s not metatype-specific work.

rather than define a “Swift.Metatype” type, and defining stuff against it?

It would be a nominal type in name only (pun intended!), with special cases throughout the compiler and ABI—like we have with Optional, except with poorer test coverage. Worse, unlike the generalization I discuss above, where one generalization refactoring makes all structural types work, we’d have to put in all of the not-really-nominal hacks for each currently-structural type on a case-by-case basis.

  - Doug

···

Sent from my iPhone

On Nov 24, 2017, at 4:06 PM, Chris Lattner <clattner@nondot.org> wrote:

On Nov 24, 2017, at 3:47 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

-Chris

   var hashValue: Int {
     return ObjectIdentifier(self).hashValue
   }

  static func ==(lhs: T.Type, rhs: T.Type) -> Bool { /* standard library magic */ }
}

   - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[Mike_Kluev]

to me as a user the end result is the same...
probably we need a better convincing example of what users may want that
doesn't have a workaround now.

speaking of ugliness, the ellipsis on the left of names is quite ugly:

     extension<...Elements : Equatable> (Elements...) : Equatable

Mike

···

On 25 November 2017 at 03:12, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Fri, Nov 24, 2017 at 9:08 PM, Mike Kluev via swift-evolution < > swift-evolution@swift.org> wrote:

On 24 November 2017 at 23:47, Douglas Gregor <dgregor@apple.com> wrote:

e.g., making all tuples of Equatable elements Equatable

that's already the case.. (all tuples of equatable elements are
equatable). no?

No, tuples do not conform to any protocols. There are hardcoded
implementations of `==` up to some arity in the stdlib to partially
mitigate the lack of protocol conformance.

[Chris_Lattner]

Ok, so you just happened to pick a simple one:

Yup. Try to make a nominal type to describe labeled tuples.

People keep talking about adding integer values to generics, why not strings too? ;-)

what is the benefit of plumbing knowledge of metatypes through the entire generics system,

That’s not how one would implement this in the compiler. Most of the compiler doesn’t care whether the subject of a protocol conformance is a nominal type or not, and those scattered (but numerous) places that do care should be straightforward to generalize to include structural types. It’s not metatype-specific work.

Sure, I can buy that. The thing that you’re leaving out is that you have to also generalize those (numerous) places to handle all the complexities of those non-nominal types. The system has to handle keywords, inout arguments, etc somehow, and therefore the complexity to handle them needs to go somewhere.

The question is only whether one design or the other produces a lower energy state of complexity. Given that I don’t know this code at all, if you think that your way is the best way to model it, then I’ll happily believe you. :-)

-Chris

···

On Nov 24, 2017, at 9:20 PM, Douglas Gregor <dgregor@apple.com> wrote:

[xwu (Xiaodi Wu)]

e.g., making all tuples of Equatable elements Equatable

that's already the case.. (all tuples of equatable elements are
equatable). no?

No, tuples do not conform to any protocols. There are hardcoded
implementations of `==` up to some arity in the stdlib to partially
mitigate the lack of protocol conformance.

to me as a user the end result is the same...
probably we need a better convincing example of what users may want that
doesn't have a workaround now.

The workaround substantially bloats the standard library, and the result is
nothing close to the same because your type is still not Equatable. This
means that it cannot benefit from any generic algorithms. For example, an
array of such tuples cannot be Equatable in turn.

speaking of ugliness, the ellipsis on the left of names is quite ugly:

     extension<...Elements : Equatable> (Elements...) : Equatable

Seems perfectly fine to me.

···

On Sat, Nov 25, 2017 at 06:35 Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 03:12, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Fri, Nov 24, 2017 at 9:08 PM, Mike Kluev via swift-evolution < >> swift-evolution@swift.org> wrote:

On 24 November 2017 at 23:47, Douglas Gregor <dgregor@apple.com> wrote:

[David_Sweeris]

Agreed.

Speaking of which, have we started designing the syntax & semantics of the variadic generics/tuples system yet? I’ve been away from my computer a lot lately, and I tend to miss threads when subject lines gets truncated to “[swift-evolution][pitch] Some subj” on my phone.

- Dave Sweeris

···

On Nov 25, 2017, at 08:05, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Sat, Nov 25, 2017 at 06:35 Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 03:12, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Fri, Nov 24, 2017 at 9:08 PM, Mike Kluev via swift-evolution <swift-evolution@swift.org> wrote:

On 24 November 2017 at 23:47, Douglas Gregor <dgregor@apple.com> wrote:

e.g., making all tuples of Equatable elements Equatable

that's already the case.. (all tuples of equatable elements are equatable). no?

No, tuples do not conform to any protocols. There are hardcoded implementations of `==` up to some arity in the stdlib to partially mitigate the lack of protocol conformance.

to me as a user the end result is the same...
probably we need a better convincing example of what users may want that doesn't have a workaround now.

The workaround substantially bloats the standard library, and the result is nothing close to the same because your type is still not Equatable. This means that it cannot benefit from any generic algorithms. For example, an array of such tuples cannot be Equatable in turn.

speaking of ugliness, the ellipsis on the left of names is quite ugly:

     extension<...Elements : Equatable> (Elements...) : Equatable

Seems perfectly fine to me.

[Mike_Kluev]

The workaround substantially bloats the standard library, and the result
is nothing close to the same because your type is still not Equatable. This
means that it cannot benefit from any generic algorithms. For example, an
array of such tuples cannot be Equatable in turn.

i see. then the current workaround is not deep enough.

speaking of ugliness, the ellipsis on the left of names is quite ugly:

     extension<...Elements : Equatable> (Elements...) : Equatable

Seems perfectly fine to me.

i haven't encounter this notation before so it looks strange and requires
some effort to decipher. if it was e.g. in this form:

extension (Equatable...) : Equatable

then it would be immediately obvious what it means, IMHO

Mike

···

On 25 November 2017 at 16:04, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

[xwu (Xiaodi Wu)]

That reads to me like you are extending a tuple of type `(Equatable...)`.
This is not the same as extending a tuple of type `(E...) where ...E :
Equatable`.

···

On Sat, Nov 25, 2017 at 4:30 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 16:04, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

The workaround substantially bloats the standard library, and the result
is nothing close to the same because your type is still not Equatable. This
means that it cannot benefit from any generic algorithms. For example, an
array of such tuples cannot be Equatable in turn.

i see. then the current workaround is not deep enough.

speaking of ugliness, the ellipsis on the left of names is quite ugly:

     extension<...Elements : Equatable> (Elements...) : Equatable

Seems perfectly fine to me.

i haven't encounter this notation before so it looks strange and requires
some effort to decipher. if it was e.g. in this form:

extension (Equatable...) : Equatable

then it would be immediately obvious what it means, IMHO

[Mike_Kluev]

and if Equatable is not a type but a protocol then the practical difference
is what ?

Mike

···

On 25 November 2017 at 22:38, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sat, Nov 25, 2017 at 4:30 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

i haven't encounter this notation before so it looks strange and

requires some effort to decipher. if it was e.g. in this form:

extension (Equatable...) : Equatable

then it would be immediately obvious what it means, IMHO

That reads to me like you are extending a tuple of type `(Equatable...)`.
This is not the same as extending a tuple of type `(E...) where ...E :
Equatable`.

[xwu (Xiaodi Wu)]

Not sure what you’re asking. Equatable is a protocol.

For a protocol P, (P, P) is a concrete type with two elements each of
existential type P. For a type T : P, a tuple of type (T, T) is not a tuple
of type (P, P). If we can extend tuples, you can write a generic algorithm
that works with any type (T, T) where T : P, and/or you can write an
algorithm that works with concrete type (P, P). Note that there is no
overlap between these two because existential type P does not conform to
protocol P.

···

On Sat, Nov 25, 2017 at 16:44 Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 22:38, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sat, Nov 25, 2017 at 4:30 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

i haven't encounter this notation before so it looks strange and

requires some effort to decipher. if it was e.g. in this form:

extension (Equatable...) : Equatable

then it would be immediately obvious what it means, IMHO

That reads to me like you are extending a tuple of type `(Equatable...)`.
This is not the same as extending a tuple of type `(E...) where ...E :
Equatable`.

and if Equatable is not a type but a protocol then the practical
difference is what ?

[Mike_Kluev]

Not sure what you’re asking. Equatable is a protocol.

that's the point. i mean, if user writes this:

extension (Equatable, Equatable) : Equatable

what *else* could he mean other than this:

extension <T: Equatable, R: Equatable> (T, R) : Equatable

and if it is indeed the only reasonable meaning we can think of - i'd say
the first notation is nicer.

For a protocol P, (P, P) is a concrete type with two elements each of
existential type P.

this part i do not understand. protocol is not an existential type. or is
it?

For a type T : P, a tuple of type (T, T) is not a tuple of type (P, P). If
we can extend tuples, you can write a generic algorithm that works with any
type (T, T) where T : P, and/or you can write an algorithm that works with
concrete type (P, P). Note that there is no overlap between these two
because existential type P does not conform to protocol P.

Mike

···

On 25 November 2017 at 23:07, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

[xwu (Xiaodi Wu)]

Not sure what you’re asking. Equatable is a protocol.

that's the point. i mean, if user writes this:

extension (Equatable, Equatable) : Equatable

what *else* could he mean other than this:

extension <T: Equatable, R: Equatable> (T, R) : Equatable

No, it would mean extending the concrete type `(Equatable, Equatable)`
(which has other roadblocks to becoming possible because Equatable has Self
requirements).

and if it is indeed the only reasonable meaning we can think of - i'd say
the first notation is nicer.

For a protocol P, (P, P) is a concrete type with two elements each of
existential type P.

this part i do not understand. protocol is not an existential type. or is
it?

Ah. You seem to be unfamiliar with protocol existentials. Protocols
(currently, only those without Self or associated type requirements, for
various implementation reasons) are themselves types. For example, you can
write:

protocol P { }
extension Int : P { }
let x: P = 42

In this example, x is of type `P`, not of type `Int`. Let's clarify the
difference:

extension Array where Element == P {
  func hi() {
    print("Hello")
  }
}

extension Array where Element : P {
  func hi() {
    print("World!")
  }
}

let y: [P] = [x]
let z: [Int] = [x as Int]

y.hi() // Prints "Hello"
z.hi() // Prints "World!"

Moreover, if we do not write the first `extension Array`, then `y.hi()`
doesn't compile. This helps to illustrate that P does not conform to itself.

For a type T : P, a tuple of type (T, T) is not a tuple of type (P, P). If

···

On Sat, Nov 25, 2017 at 5:21 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 23:07, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

we can extend tuples, you can write a generic algorithm that works with any
type (T, T) where T : P, and/or you can write an algorithm that works with
concrete type (P, P). Note that there is no overlap between these two
because existential type P does not conform to protocol P.

Mike

[Mike_Kluev]

Not sure what you’re asking. Equatable is a protocol.

that's the point. i mean, if user writes this:

extension (Equatable, Equatable) : Equatable

what *else* could he mean other than this:

extension <T: Equatable, R: Equatable> (T, R) : Equatable

No, it would mean extending the concrete type `(Equatable, Equatable)`
(which has other roadblocks to becoming possible because Equatable has Self
requirements).

and if it is indeed the only reasonable meaning we can think of - i'd say
the first notation is nicer.

For a protocol P, (P, P) is a concrete type with two elements each of
existential type P.

this part i do not understand. protocol is not an existential type. or is
it?

Ah. You seem to be unfamiliar with protocol existentials. Protocols
(currently, only those without Self or associated type requirements, for
various implementation reasons) are themselves types. For example, you can
write:

protocol P { }
extension Int : P { }
let x: P = 42

thanks, indeed i was totally unaware of this. can't even find it in the
language reference.

if i decipher this correctly, the above example with Equatable is probably
"fine" (because Equatable has self requirement) but in other cases it won't
be fine.

In this example, x is of type `P`, not of type `Int`. Let's clarify the
difference:

extension Array where Element == P {
  func hi() {
    print("Hello")
  }
}

extension Array where Element : P {
  func hi() {
    print("World!")
  }
}

let y: [P] = [x]
let z: [Int] = [x as Int]

y.hi() // Prints "Hello"
z.hi() // Prints "World!"

Moreover, if we do not write the first `extension Array`, then `y.hi()`
doesn't compile. This helps to illustrate that P does not conform to itself.

thanks for example. too subtle feature imho. i never thought protocol could
be a type on it's own, makes the whole story more complex.

Mike

···

On 25 November 2017 at 23:39, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sat, Nov 25, 2017 at 5:21 PM, Mike Kluev <mike.kluev@gmail.com> wrote:

On 25 November 2017 at 23:07, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

[Alejandro_Martinez]

Ah. You seem to be unfamiliar with protocol existentials. Protocols
(currently, only those without Self or associated type requirements, for
various implementation reasons) are themselves types. For example, you can
write:

A little offtopic, but I've been wanting to ask if it would be
possible to clarify the definition of existentials on the generics
manifesto (or somewhere than can be easily found by newcomers). I'm
sure I'm not the only one that has a vague notion of what it means but
would still appreciate to have a more concrete definition with some
examples. :D

···

protocol P { }
extension Int : P { }
let x: P = 42

In this example, x is of type `P`, not of type `Int`. Let's clarify the
difference:

extension Array where Element == P {
  func hi() {
    print("Hello")
  }
}

extension Array where Element : P {
  func hi() {
    print("World!")
  }
}

let y: [P] = [x]
let z: [Int] = [x as Int]

y.hi() // Prints "Hello"
z.hi() // Prints "World!"

Moreover, if we do not write the first `extension Array`, then `y.hi()`
doesn't compile. This helps to illustrate that P does not conform to itself.

For a type T : P, a tuple of type (T, T) is not a tuple of type (P, P).
If we can extend tuples, you can write a generic algorithm that works with
any type (T, T) where T : P, and/or you can write an algorithm that works
with concrete type (P, P). Note that there is no overlap between these two
because existential type P does not conform to protocol P.

Mike

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Alejandro Martinez

Alexito's World