[Draft] Automatically deriving Equatable and Hashable for certain value types


(Tony Allevato) #1

I was inspired to put together a draft proposal based on an older
discussion in the Universal Equality, Hashability, and Comparability thread
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that
recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not
possible for the Swift 3 timeline, but it's something that would benefit
enough people that I want to make sure the discussion stays alive. If there
are enough good feelings about it, I'll move it from my gist into an actual
proposal PR.

Automatically deriving Equatable andHashable for value types

   - Proposal: SE-0000
   <https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md>
   - Author(s): Tony Allevato <https://github.com/allevato>
   - Status: Awaiting review
   <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
   - Review manager: TBD

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#introduction>
Introduction

Value types are prevalent throughout the Swift language, and we encourage
developers to think in those terms when writing their own types.
Frequently, developers find themselves writing large amounts of boilerplate
code to support equatability and hashability of value types. This proposal
offers a way for the compiler to automatically derive conformance to
Equatable and Hashable to reduce this boilerplate, in a subset of scenarios
where generating the correct implementation is likely to be possible.

Swift-evolution thread: Universal Equatability, Hashability, and
Comparability <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919>
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#motivation>
Motivation

Building robust value types in Swift can involve writing significant
boilerplate code to support concepts of hashability and equatability.
Equality is pervasive across many value types, and for each one users must
implement the == operator such that it performs a fairly rote memberwise
equality test. As an example, an equality test for a struct looks fairly
uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool {
  return lhs.property1 == rhs.property1 &&
         lhs.property2 == rhs.property2 &&
         lhs.property3 == rhs.property3 &&
         ...
}

What's worse is that this operator must be updated if any properties are
added, removed, or changed, and since it must be manually written, it's
possible to get it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type in
a Set or use one as a multi-valuedDictionary key. Writing high-quality,
well-distributed hash functions is not trivial so developers may not put a
great deal of thought into them – especially as the number of properties
increases – not realizing that their performance could potentially suffer
as a result. And as with equality, writing it manually means there is the
potential to get it wrong.

In particular, the code that must be written to implement equality for
enums is quite verbose. One such real-world example (source
<https://github.com/exercism/xswift/blob/master/exercises/poker/PokerExample.swift#L151-L189>
):

func ==(lhs: HandRank, rhs: HandRank) -> Bool {
  switch (lhs, rhs) {
  case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank
, let rSuit)):
    return lRank == rRank && lSuit == rSuit
  case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let rFour)):
    return lFour == rFour
  case (.fullHouse(three: let lThree), .fullHouse(three: let rThree)):
    return lThree == rThree
  case (.flush(let lRank, let lSuit), .flush(let rRank, let rSuit)):
    return lSuit == rSuit && lRank == rRank
  case (.straight(high: let lRank), .straight(high: let rRank)):
    return lRank == rRank
  case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let rRank)):
    return lRank == rRank
  case (.twoPair(high: let lHigh, low: let lLow, highCard: let lCard),
        .twoPair(high: let rHigh, low: let rLow, highCard: let rCard)):
    return lHigh == rHigh && lLow == rLow && lCard == rCard
  case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2,
card3: let lCard3),
        .onePair(let rPairRank, card1: let rCard1, card2: let rCard2,
card3: let rCard3)):
    return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 ==
rCard2 && lCard3 == rCard3
  case (.highCard(let lCard), .highCard(let rCard)):
    return lCard == rCard
  default:
    return false
  }
}

Crafting a high-quality hash function for this enum would be similarly
inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases;
notably, enums with raw values conform toRawRepresentable, Equatable, and
Hashable without the user explicitly declaring them:

enum Foo: Int {
  case one = 1
  case two = 2
}
let x = (Foo.one == Foo.two) // workslet y = Foo.one.hashValue //
also workslet z = Foo.one.rawValue // also also works

Since there is precedent for this in Swift, we propose extending this
support to more value types.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#proposed-solution>Proposed
solution

We propose that a value type be Equatable/Hashable if all of its members are
Equatable/Hashable, with the result for the outer type being composed from
its members.

Specifically, we propose the following rules for deriving Equatable:

···

-

   A struct implicitly conforms to Equatable if all of its fields are of
   types that conform to Equatable – either explicitly, or implicitly by
   the application of these rules. The compiler will generate an
   implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x
   == rhs.x for all fields x in T.
   -

   An enum implicitly conforms to Equatable if all of its associated values
   across all of its cases are of types that conform to Equatable – either
   explicitly, or implicitly by the application of these rules. The compiler
   will generate an implementation of ==(lhs: T, rhs: T) that returns true
   if and only if lhs and rhs are the same case and have payloads that are
   memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

   -

   A struct implicitly conforms to Hashable if all of its fields are of
   types that conform to Hashable – either explicitly, or implicitly by the
   application of these rules. The compiler will generate an implementation of
    hashValue that uses a pre-defined hash function† to compute the hash
   value of the struct from the hash values of its members.

   Since order of the terms affects the hash value computation, we
   recommend ordering the terms in member definition order.
   -

   An enum implicitly conforms to Hashable if all of its associated values
   across all of its cases are of types that conform to Hashable – either
   explicitly, or implicitly by the application of these rules. The compiler
   will generate an implementation of hashValue that uses a pre-defined
   hash function† to compute the hash value of an enum value by using the
   case's ordinal (i.e., definition order) followed by the hash values of its
   associated values as its terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a
multiplicative hash function such as Kernighan and Ritchie or Bernstein is
easy to implement, but we do not rule out other possibilities.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-defaults>Overriding
defaults

Any user-provided implementations of == or hashValue should override the
default implementations that would be provided by the compiler. This is
already possible today with raw-value enums so the same behavior should be
extended to other value types that are made to implicitly conform to these
protocols.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Should it be possible to easily omit certain properties from automatically
generated equality tests or hash value computation? This could be valuable,
for example, if a property is merely used as an internal cache and does not
actually contribute to the "value" of the instance. Under the rules above,
if this cached value was equatable, a user would have to override == and
hashValue and provide their own implementations to ignore it. If there is
significant evidence that this pattern is common and useful, we could
consider adding a custom attribute, such as @transient, that would omit the
property from the generated computations.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be completely
explicit, or should users have to explicitly list conformance with Equatable
and Hashable in order for the compiler to generate the derived
implementation?
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change will have no impact on existing code because it is purely
additive. Value types that already provide custom implementations of == or
hashValue but satisfy the rules above would keep the custom implementation
because it would override the compiler-provided default.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate for
automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.


(Brent Royal-Gordon) #2

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

A word of warning: an earlier proposal on memberwise initializers ran aground because it tried to annotate properties to tell the compiler which ones should be included in the generated initializer. It was ultimately judged too complex a solution for the specialized problem space it was trying to tackle.

In other words, Keep It Simple, Stupid. <https://en.wikipedia.org/wiki/KISS_principle>

···

--
Brent Royal-Gordon
Architechies


(Matthew Johnson) #3

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

A word of warning: an earlier proposal on memberwise initializers ran aground because it tried to annotate properties to tell the compiler which ones should be included in the generated initializer. It was ultimately judged too complex a solution for the specialized problem space it was trying to tackle.

That's not entirely true. The solution the core team was leaning towards in their feedback also included property annotations. The proposal was deferred because a lot of new ideas were discussed during the review period and our understanding of the design space was refined. By the end of the review not even I was convinced that the proposal as written was the right long term solution.

If we're going to derive automatic Equatable and Hashable implementations it is necessary to exclude certain members. We can talk about strategies for doing that, and possibly for minimizing cases where the annotations are used, but we need some kind of control.

The common case where annotations will be required is likely to be for a small number of members relative to those contributing to Equatable and Hashable. An annotation or two are much better than writing out manual implementations. They also scale nicely if we are able to derive implementations of other protocols in the future.

···

Sent from my iPad
On May 25, 2016, at 8:08 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

In other words, Keep It Simple, Stupid. <https://en.wikipedia.org/wiki/KISS_principle>

--
Brent Royal-Gordon
Architechies

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


(Mark Sands) #4

Thanks so much for putting this together, Tony! Glad I was able to be some
inspiration. :^)

···

On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution < swift-evolution@swift.org> wrote:

I was inspired to put together a draft proposal based on an older
discussion in the Universal Equality, Hashability, and Comparability thread
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that
recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not
possible for the Swift 3 timeline, but it's something that would benefit
enough people that I want to make sure the discussion stays alive. If there
are enough good feelings about it, I'll move it from my gist into an actual
proposal PR.

Automatically deriving Equatable andHashable for value types

   - Proposal: SE-0000
   <https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md>
   - Author(s): Tony Allevato <https://github.com/allevato>
   - Status: Awaiting review
   <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
   - Review manager: TBD

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#introduction>
Introduction

Value types are prevalent throughout the Swift language, and we encourage
developers to think in those terms when writing their own types.
Frequently, developers find themselves writing large amounts of boilerplate
code to support equatability and hashability of value types. This proposal
offers a way for the compiler to automatically derive conformance to
Equatable and Hashable to reduce this boilerplate, in a subset of
scenarios where generating the correct implementation is likely to be
possible.

Swift-evolution thread: Universal Equatability, Hashability, and
Comparability
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919>

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#motivation>
Motivation

Building robust value types in Swift can involve writing significant
boilerplate code to support concepts of hashability and equatability.
Equality is pervasive across many value types, and for each one users must
implement the == operator such that it performs a fairly rote memberwise
equality test. As an example, an equality test for a struct looks fairly
uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool {
  return lhs.property1 == rhs.property1 &&
         lhs.property2 == rhs.property2 &&
         lhs.property3 == rhs.property3 &&
         ...
}

What's worse is that this operator must be updated if any properties are
added, removed, or changed, and since it must be manually written, it's
possible to get it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type
in a Set or use one as a multi-valuedDictionary key. Writing
high-quality, well-distributed hash functions is not trivial so developers
may not put a great deal of thought into them – especially as the number of
properties increases – not realizing that their performance could
potentially suffer as a result. And as with equality, writing it manually
means there is the potential to get it wrong.

In particular, the code that must be written to implement equality for
enums is quite verbose. One such real-world example (source
<https://github.com/exercism/xswift/blob/master/exercises/poker/PokerExample.swift#L151-L189>
):

func ==(lhs: HandRank, rhs: HandRank) -> Bool {
  switch (lhs, rhs) {
  case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let rSuit)):
    return lRank == rRank && lSuit == rSuit
  case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let rFour)):
    return lFour == rFour
  case (.fullHouse(three: let lThree), .fullHouse(three: let rThree)):
    return lThree == rThree
  case (.flush(let lRank, let lSuit), .flush(let rRank, let rSuit)):
    return lSuit == rSuit && lRank == rRank
  case (.straight(high: let lRank), .straight(high: let rRank)):
    return lRank == rRank
  case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let rRank)):
    return lRank == rRank
  case (.twoPair(high: let lHigh, low: let lLow, highCard: let lCard),
        .twoPair(high: let rHigh, low: let rLow, highCard: let rCard)):
    return lHigh == rHigh && lLow == rLow && lCard == rCard
  case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let lCard3),
        .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let rCard3)):
    return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 == rCard3
  case (.highCard(let lCard), .highCard(let rCard)):
    return lCard == rCard
  default:
    return false
  }
}

Crafting a high-quality hash function for this enum would be similarly
inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases;
notably, enums with raw values conform toRawRepresentable, Equatable, and
Hashable without the user explicitly declaring them:

enum Foo: Int {
  case one = 1
  case two = 2
}
let x = (Foo.one == Foo.two) // workslet y = Foo.one.hashValue // also workslet z = Foo.one.rawValue // also also works

Since there is precedent for this in Swift, we propose extending this
support to more value types.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#proposed-solution>Proposed
solution

We propose that a value type be Equatable/Hashable if all of its members
are Equatable/Hashable, with the result for the outer type being composed
from its members.

Specifically, we propose the following rules for deriving Equatable:

   -

   A struct implicitly conforms to Equatable if all of its fields are of
   types that conform to Equatable – either explicitly, or implicitly by
   the application of these rules. The compiler will generate an
   implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x
   == rhs.x for all fields x in T.
   -

   An enum implicitly conforms to Equatable if all of its associated
   values across all of its cases are of types that conform to Equatable –
   either explicitly, or implicitly by the application of these rules. The
   compiler will generate an implementation of ==(lhs: T, rhs: T) that
   returns true if and only if lhs and rhs are the same case and have
   payloads that are memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

   -

   A struct implicitly conforms to Hashable if all of its fields are of
   types that conform to Hashable – either explicitly, or implicitly by
   the application of these rules. The compiler will generate an
   implementation of hashValue that uses a pre-defined hash function† to
   compute the hash value of the struct from the hash values of its members.

   Since order of the terms affects the hash value computation, we
   recommend ordering the terms in member definition order.
   -

   An enum implicitly conforms to Hashable if all of its associated
   values across all of its cases are of types that conform to Hashable –
   either explicitly, or implicitly by the application of these rules. The
   compiler will generate an implementation of hashValue that uses a
   pre-defined hash function† to compute the hash value of an enum value
   by using the case's ordinal (i.e., definition order) followed by the hash
   values of its associated values as its terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a
multiplicative hash function such as Kernighan and Ritchie or Bernstein is
easy to implement, but we do not rule out other possibilities.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-defaults>Overriding
defaults

Any user-provided implementations of == or hashValue should override the
default implementations that would be provided by the compiler. This is
already possible today with raw-value enums so the same behavior should be
extended to other value types that are made to implicitly conform to these
protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Should it be possible to easily omit certain properties from automatically
generated equality tests or hash value computation? This could be valuable,
for example, if a property is merely used as an internal cache and does not
actually contribute to the "value" of the instance. Under the rules above,
if this cached value was equatable, a user would have to override == and
hashValue and provide their own implementations to ignore it. If there is
significant evidence that this pattern is common and useful, we could
consider adding a custom attribute, such as @transient, that would omit
the property from the generated computations.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely explicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change will have no impact on existing code because it is purely
additive. Value types that already provide custom implementations of == or
hashValue but satisfy the rules above would keep the custom
implementation because it would override the compiler-provided default.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate
for automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.

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


(L Mihalkovic) #5

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

A word of warning: an earlier proposal on memberwise initializers ran aground because it tried to annotate properties to tell the compiler which ones should be included in the generated initializer. It was ultimately judged too complex a solution for the specialized problem space it was trying to tackle.

Can't fathom how one would not see the difference in complexity between the initializer proposals (untainable as they were proposed) and how simple it is to discriminate during generation of identity. Not to mention the other reasons why initializer generation could be turned down.

···

On May 26, 2016, at 3:08 AM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

In other words, Keep It Simple, Stupid. <https://en.wikipedia.org/wiki/KISS_principle>

--
Brent Royal-Gordon
Architechies

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


(plx) #6

I really want synthesized equality (etc.), but having seen the previous discussions on this and related topics I am not sure that directly-deriving the `==` function is the right approach.

The main reason I say this is that although this works great for the easy case — all fields equatable, do the obvious thing! — sooner or later people will want to customize it, which would ideally allow someone to say “do the obvious thing for a,b,c but let me handle d and e”, e.g. still get synthesis for the easy parts…but an approach that directly-synthesizes `==` for a type seems like it’ll be difficult to expand to support such customization.

Suppose instead that we had a “magic function” `T#memberwiseEqual(_:_:)` we could invoke like so:

  // the details are *very* bikesheddable here:
  func ==(lhs: Foo, rhs: Foo) -> Bool {
    return Foo#memberwiseEqual(lhs,rhs) // `#` b/c of "compiler magic”
    // ^ compiler error iff any of `Foo`’s members aren’t Equatable
  }

…which’d expand to the expected “lhs.a == rhs.a && lhs.b == rhs.b && …”.

For trivial equatable synthesis this isn’t as nice as a full automatic derivation, but it seems like an *approach* that’d be much-better positioned for future expansion and enhancement, e.g.:

  extension Foo: Equatable {

   // mock syntax; probably too ambiguous for actual use but i think the idea is clear:
   private static func boringComponentsEqual(lhs: Foo, _ rhs: Foo) -> Bool {
      return Foo(boring,boring2,boringIII)#memberwiseEqual(lhs,rhs)
   }

  }

  func ==(lhs: Foo, rhs: Foo) -> Bool {
    return Foo.boringComponentsEqual(lhs,rhs) && // non-trivial equality logic here
  }

…as opposed to trying to retrofit various “customizations" onto a system that directly synthesizes `==` (without exposing any “internals", so to speak).

You can easily imagine a similar `#casewiseEqual` for enums (it seems likely to be trickier, but not impossible), and again a #memberwiseHash for hashing, and so on.

I think you can summarize the above as “all-in-one derivation is appealing, but I think pragmatically and looking-ahead it’s a better move to expose the 'synthesis mechanism’ itself (leaving it the user to do the 'final assembly’)”.

···

On May 25, 2016, at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:

I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.


(Dave Abrahams) #7

I was inspired to put together a draft proposal based on an older discussion in
the Universal Equality, Hashability, and Comparability thread
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently
got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not
possible for the Swift 3 timeline, but it's something that would benefit enough
people that I want to make sure the discussion stays alive. If there are enough
good feelings about it, I'll move it from my gist into an actual
proposal PR.

Hi Tony,

As you might imagine I'm intensely interested in this topic and I have
some strongly held views. That said, since it's out of scope for Swift
3, you shouldn't expect too much participation from me at this point.

···

on Wed May 25 2016, Tony Allevato <swift-evolution@swift.org> wrote:

Automatically deriving Equatable andHashable for value types

* Proposal: SE-0000
* Author(s): Tony Allevato
* Status: Awaiting review
* Review manager: TBD

Introduction

Value types are prevalent throughout the Swift language, and we encourage
developers to think in those terms when writing their own types. Frequently,
developers find themselves writing large amounts of boilerplate code to support
equatability and hashability of value types. This proposal offers a way for the
compiler to automatically derive conformance toEquatable and Hashable to reduce
this boilerplate, in a subset of scenarios where generating the correct
implementation is likely to be possible.

Swift-evolution thread: Universal Equatability, Hashability, and Comparability

Motivation

Building robust value types in Swift can involve writing significant boilerplate
code to support concepts of hashability and equatability. Equality is pervasive
across many value types, and for each one users must implement the == operator
such that it performs a fairly rote memberwise equality test. As an example, an
equality test for a struct looks fairly uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool {
  return lhs.property1 == rhs.property1 &&
         lhs.property2 == rhs.property2 &&
         lhs.property3 == rhs.property3 &&
         ...
}

What's worse is that this operator must be updated if any properties are added,
removed, or changed, and since it must be manually written, it's possible to get
it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type in a
Set or use one as a multi-valuedDictionary key. Writing high-quality,
well-distributed hash functions is not trivial so developers may not put a great
deal of thought into them – especially as the number of properties increases –
not realizing that their performance could potentially suffer as a result. And
as with equality, writing it manually means there is the potential to get it
wrong.

In particular, the code that must be written to implement equality for enums is
quite verbose. One such real-world example (source):

func ==(lhs: HandRank, rhs: HandRank) -> Bool {
  switch (lhs, rhs) {
  case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let rSuit)):
    return lRank == rRank && lSuit == rSuit
  case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let rFour)):
    return lFour == rFour
  case (.fullHouse(three: let lThree), .fullHouse(three: let rThree)):
    return lThree == rThree
  case (.flush(let lRank, let lSuit), .flush(let rRank, let rSuit)):
    return lSuit == rSuit && lRank == rRank
  case (.straight(high: let lRank), .straight(high: let rRank)):
    return lRank == rRank
  case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let rRank)):
    return lRank == rRank
  case (.twoPair(high: let lHigh, low: let lLow, highCard: let lCard),
        .twoPair(high: let rHigh, low: let rLow, highCard: let rCard)):
    return lHigh == rHigh && lLow == rLow && lCard == rCard
  case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let lCard3),
        .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let rCard3)):
    return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 == rCard3
  case (.highCard(let lCard), .highCard(let rCard)):
    return lCard == rCard
  default:
    return false
  }
}

Crafting a high-quality hash function for this enum would be similarly
inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases; notably,
enums with raw values conform toRawRepresentable, Equatable, and Hashable
without the user explicitly declaring them:

enum Foo: Int {
  case one = 1
  case two = 2
}

let x = (Foo.one == Foo.two) // works
let y = Foo.one.hashValue // also works
let z = Foo.one.rawValue // also also works

Since there is precedent for this in Swift, we propose extending this support to
more value types.

Proposed solution

We propose that a value type be Equatable/Hashable if all of its members are
Equatable/Hashable, with the result for the outer type being composed from its
members.

Specifically, we propose the following rules for deriving Equatable:

* A struct implicitly conforms to Equatable if all of its fields are of types
  that conform to Equatable – either explicitly, or implicitly by the
  application of these rules. The compiler will generate an implementation of ==
  (lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields
  x in T.

* An enum implicitly conforms to Equatable if all of its associated values
  across all of its cases are of types that conform to Equatable – either
  explicitly, or implicitly by the application of these rules. The compiler will
  generate an implementation of ==(lhs: T, rhs: T) that returns true if and only
  if lhs and rhs are the same case and have payloads that are memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

* A struct implicitly conforms to Hashable if all of its fields are of types
  that conform to Hashable – either explicitly, or implicitly by the application
  of these rules. The compiler will generate an implementation of hashValue that
  uses a pre-defined hash function† to compute the hash value of the struct from
  the hash values of its members.

  Since order of the terms affects the hash value computation, we recommend
  ordering the terms in member definition order.

* An enum implicitly conforms to Hashable if all of its associated values
  across all of its cases are of types that conform to Hashable – either
  explicitly, or implicitly by the application of these rules. The compiler will
  generate an implementation of hashValue that uses a pre-defined hash function†
  to compute the hash value of an enum value by using the case's ordinal (i.e.,
  definition order) followed by the hash values of its associated values as its
  terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a
multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy
to implement, but we do not rule out other possibilities.

Overriding defaults

Any user-provided implementations of == or hashValue should override the default
implementations that would be provided by the compiler. This is already possible
today with raw-value enums so the same behavior should be extended to other
value types that are made to implicitly conform to these protocols.

Open questions

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically
generated equality tests or hash value computation? This could be valuable, for
example, if a property is merely used as an internal cache and does not actually
contribute to the "value" of the instance. Under the rules above, if this cached
value was equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it. If there is significant evidence that
this pattern is common and useful, we could consider adding a custom attribute,
such as @transient, that would omit the property from the generated
computations.

Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely
explicit, or should users have to explicitly list conformance with Equatable and
Hashable in order for the compiler to generate the derived implementation?

Impact on existing code

This change will have no impact on existing code because it is purely additive.
Value types that already provide custom implementations of == or hashValue but
satisfy the rules above would keep the custom implementation because it would
override the compiler-provided default.

Alternatives considered

The original discussion thread also included Comparable as a candidate for
automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for users,
but worse, it also means that reordering properties in the source code changes
the code's behavior at runtime. (This is true for hashability as well if a
multiplicative hash function is used, but hash values are not intended to be
persistent and reordering the terms does not produce a significant behavioral
change.)

Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo
Jimenez for providing great real-world examples of boilerplate needed to support
equatability for some value types, and to Mark Sands for necromancing the
swift-evolution thread that convinced me to write this up.

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

--
Dave


(Patrick Smith) #8

This would be very handy! It’s one of those rare scenarios where I think “I can’t believe Swift makes me type all this out, there must be an easier way”.

I think explicitly conformance to Equatable and Hashable would be preferable. This means if one of the members is not Equable/Hashable, the user knows by getting an error of ‘Does not conform to Equatable, must implement func ==’ at the type level rather than scratching their head when instances are not automatically Equatable. It also means code is only generated when it is needed.

There’s a small typo (before [sic] below):

···

On 26 May 2016, at 4:28 AM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:

As with raw-value enums today, should the derived conformance be completely explicit [sic], or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?


(Ricardo Parada) #9

I like this.

I don't see why not make this the default.

If someone thinks it is not needed for their application then they simply don't use it. Having it there would not cause any harm. Unless someone had a requirement to have strict control on the size of the application and had to cut down on the amount of code.

If we establish that value types get this by default then there is no need to make it explicit. It would become a known fact for value types in the Swift language.

I don't see a reason to make this opt-in. I think there is more beneficial to make the behavior automatic and allow a way to override/ customize.

···

On May 25, 2016, at 2:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:

I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.

Automatically deriving Equatable andHashable for value types
Proposal: SE-0000
Author(s): Tony Allevato
Status: Awaiting review
Review manager: TBD
Introduction

Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.

Swift-evolution thread: Universal Equatability, Hashability, and Comparability

Motivation

Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool {
  return lhs.property1 == rhs.property1 &&
         lhs.property2 == rhs.property2 &&
         lhs.property3 == rhs.property3 &&
         ...
}
What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.

In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):

func ==(lhs: HandRank, rhs: HandRank) -> Bool {
  switch (lhs, rhs) {
  case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let rSuit)):
    return lRank == rRank && lSuit == rSuit
  case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let rFour)):
    return lFour == rFour
  case (.fullHouse(three: let lThree), .fullHouse(three: let rThree)):
    return lThree == rThree
  case (.flush(let lRank, let lSuit), .flush(let rRank, let rSuit)):
    return lSuit == rSuit && lRank == rRank
  case (.straight(high: let lRank), .straight(high: let rRank)):
    return lRank == rRank
  case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let rRank)):
    return lRank == rRank
  case (.twoPair(high: let lHigh, low: let lLow, highCard: let lCard),
        .twoPair(high: let rHigh, low: let rLow, highCard: let rCard)):
    return lHigh == rHigh && lLow == rLow && lCard == rCard
  case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let lCard3),
        .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let rCard3)):
    return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 == rCard3
  case (.highCard(let lCard), .highCard(let rCard)):
    return lCard == rCard
  default:
    return false
  }
}
Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:

enum Foo: Int {
  case one = 1
  case two = 2
}

let x = (Foo.one == Foo.two) // works
let y = Foo.one.hashValue // also works
let z = Foo.one.rawValue // also also works
Since there is precedent for this in Swift, we propose extending this support to more value types.

Proposed solution

We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.

Specifically, we propose the following rules for deriving Equatable:

A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.

An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.

Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.

An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.

Overriding defaults

Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

Open questions

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

Impact on existing code

This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.

Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

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


(L Mihalkovic) #10

Regards
(From mobile)

Sent from my iPad

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

A word of warning: an earlier proposal on memberwise initializers ran aground because it tried to annotate properties to tell the compiler which ones should be included in the generated initializer. It was ultimately judged too complex a solution for the specialized problem space it was trying to tackle.

That's not entirely true. The solution the core team was leaning towards in their feedback also included property annotations. The proposal was deferred because a lot of new ideas were discussed during the review period and our understanding of the design space was refined. By the end of the review not even I was convinced that the proposal as written was the right long term solution.

If we're going to derive automatic Equatable and Hashable implementations it is necessary to exclude certain members. We can talk about strategies for doing that, and possibly for minimizing cases where the annotations are used, but we need some kind of control.

The common case where annotations will be required is likely to be for a small number of members relative to those contributing to Equatable and Hashable. An annotation or two are much better than writing out manual implementations. They also scale nicely if we are able to derive implementations of other protocols in the future.

There are existing precedents that even show what the code looks like... and it is not bad at all.

···

On May 26, 2016, at 3:46 AM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:
On May 25, 2016, at 8:08 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

In other words, Keep It Simple, Stupid. <https://en.wikipedia.org/wiki/KISS_principle>

--
Brent Royal-Gordon
Architechies

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

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


(Michael Peternell) #11

Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

···

Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org>:

Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)

On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:
I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.

Automatically deriving Equatable andHashable for value types

  • Proposal: SE-0000
  • Author(s): Tony Allevato
  • Status: Awaiting review
  • Review manager: TBD
Introduction

Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.

Swift-evolution thread: Universal Equatability, Hashability, and Comparability

Motivation

Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool
{
  
return lhs.property1 == rhs.property1 &&

         lhs
.property2 == rhs.property2 &&

         lhs
.property3 == rhs.property3 &&

...

}

What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.

In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):

func ==(lhs: HandRank, rhs: HandRank) -> Bool
{
  
switch
(lhs, rhs) {
  
case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
rSuit)):
    
return lRank == rRank && lSuit ==
rSuit
  
case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
rFour)):
    
return lFour ==
rFour
  
case (.fullHouse(three: let lThree), .fullHouse(three: let
rThree)):
    
return lThree ==
rThree
  
case (.flush(let lRank, let lSuit), .flush(let rRank, let
rSuit)):
    
return lSuit == rSuit && lRank ==
rRank
  
case (.straight(high: let lRank), .straight(high: let
rRank)):
    
return lRank ==
rRank
  
case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
rRank)):
    
return lRank ==
rRank
  
case (.twoPair(high: let lHigh, low: let lLow, highCard: let
lCard),
        
.twoPair(high: let rHigh, low: let rLow, highCard: let
rCard)):
    
return lHigh == rHigh && lLow == rLow && lCard ==
rCard
  
case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
lCard3),
        
.onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
rCard3)):
    
return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
rCard3
  
case (.highCard(let lCard), .highCard(let
rCard)):
    
return lCard ==
rCard
  
default
:
    
return false

  }
}

Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:

enum Foo: Int
{
  
case one = 1

case two = 2

}

let x = (Foo.one == Foo.two) // works
let y = Foo.one.hashValue // also works
let z = Foo.one.rawValue // also also works
Since there is precedent for this in Swift, we propose extending this support to more value types.

Proposed solution

We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.

Specifically, we propose the following rules for deriving Equatable:

  • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.

  • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

  • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.

Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.

  • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.

Overriding defaults

Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

Open questions

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

Impact on existing code

This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.

Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

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

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


(Ricardo Parada) #12

As Steve Jobs once said when demoing Interface Builder during the NeXT days: "The line of code you don't have to write is the line of code you don't have to debug."

P.S. I hope I got the quote right, but that was the idea. :slight_smile:

···

Sent from my iPhone

On May 25, 2016, at 10:02 PM, Patrick Smith via swift-evolution <swift-evolution@swift.org> wrote:

This would be very handy! It’s one of those rare scenarios where I think “I can’t believe Swift makes me type all this out, there must be an easier way”.


(TJ Usiyan) #13

+1 to a `deriving` keyword

···

On Thu, May 26, 2016 at 3:58 AM, Michael Peternell via swift-evolution < swift-evolution@swift.org> wrote:

Can we just copy&paste the solution from Haskell instead of creating our
own? It's just better in every aspect. Deriving `Equatable` and `Hashable`
would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be
automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason),
you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any
new incompatibilities. For example, `CustomStringConvertible` could be
derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving
Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if
`X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not
used, in which case every `Shape<T>` would be equatable. Unless something
in the definition of `Shape` makes deriving `Equatable` impossible => this
produces an error.)
- It is proven to work in production.

-Michael

> Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution < > swift-evolution@swift.org>:
>
> Thanks so much for putting this together, Tony! Glad I was able to be
some inspiration. :^)
>
>
> On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution < > swift-evolution@swift.org> wrote:
> I was inspired to put together a draft proposal based on an older
discussion in the Universal Equality, Hashability, and Comparability thread
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that
recently got necromanced (thanks Mark Sands!).
>
> I'm guessing that this would be a significant enough change that it's
not possible for the Swift 3 timeline, but it's something that would
benefit enough people that I want to make sure the discussion stays alive.
If there are enough good feelings about it, I'll move it from my gist into
an actual proposal PR.
>
> Automatically deriving Equatable andHashable for value types
>
> • Proposal: SE-0000
> • Author(s): Tony Allevato
> • Status: Awaiting review
> • Review manager: TBD
> Introduction
>
> Value types are prevalent throughout the Swift language, and we
encourage developers to think in those terms when writing their own types.
Frequently, developers find themselves writing large amounts of boilerplate
code to support equatability and hashability of value types. This proposal
offers a way for the compiler to automatically derive conformance
toEquatable and Hashable to reduce this boilerplate, in a subset of
scenarios where generating the correct implementation is likely to be
possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and
Comparability
>
> Motivation
>
> Building robust value types in Swift can involve writing significant
boilerplate code to support concepts of hashability and equatability.
Equality is pervasive across many value types, and for each one users must
implement the == operator such that it performs a fairly rote memberwise
equality test. As an example, an equality test for a struct looks fairly
uninteresting:
>
> func ==(lhs: Foo, rhs: Foo) -> Bool
> {
>
> return lhs.property1 == rhs.property1 &&
>
> lhs
> .property2 == rhs.property2 &&
>
> lhs
> .property3 == rhs.property3 &&
>
>
> ...
>
> }
>
> What's worse is that this operator must be updated if any properties are
added, removed, or changed, and since it must be manually written, it's
possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type
in a Set or use one as a multi-valuedDictionary key. Writing high-quality,
well-distributed hash functions is not trivial so developers may not put a
great deal of thought into them – especially as the number of properties
increases – not realizing that their performance could potentially suffer
as a result. And as with equality, writing it manually means there is the
potential to get it wrong.
>
> In particular, the code that must be written to implement equality for
enums is quite verbose. One such real-world example (source):
>
> func ==(lhs: HandRank, rhs: HandRank) -> Bool
> {
>
> switch
> (lhs, rhs) {
>
> case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank ,
let
> rSuit)):
>
> return lRank == rRank && lSuit ==
> rSuit
>
> case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
> rFour)):
>
> return lFour ==
> rFour
>
> case (.fullHouse(three: let lThree), .fullHouse(three: let
> rThree)):
>
> return lThree ==
> rThree
>
> case (.flush(let lRank, let lSuit), .flush(let rRank, let
> rSuit)):
>
> return lSuit == rSuit && lRank ==
> rRank
>
> case (.straight(high: let lRank), .straight(high: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.twoPair(high: let lHigh, low: let lLow, highCard: let
> lCard),
>
> .twoPair(high: let rHigh, low: let rLow, highCard: let
> rCard)):
>
> return lHigh == rHigh && lLow == rLow && lCard ==
> rCard
>
> case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2,
card3: let
> lCard3),
>
> .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
> rCard3)):
>
> return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 &&
lCard3 ==
> rCard3
>
> case (.highCard(let lCard), .highCard(let
> rCard)):
>
> return lCard ==
> rCard
>
> default
> :
>
> return false
>
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly
inconvenient to write, involving another large switchstatement.
>
> Swift already provides implicit protocol conformance in some cases;
notably, enums with raw values conform toRawRepresentable, Equatable, and
Hashable without the user explicitly declaring them:
>
> enum Foo: Int
> {
>
> case one = 1
>
>
> case two = 2
>
> }
>
>
> let x = (Foo.one == Foo.two) // works
> let y = Foo.one.hashValue // also works
> let z = Foo.one.rawValue // also also works
> Since there is precedent for this in Swift, we propose extending this
support to more value types.
>
> Proposed solution
>
> We propose that a value type be Equatable/Hashable if all of its members
are Equatable/Hashable, with the result for the outer type being composed
from its members.
>
> Specifically, we propose the following rules for deriving Equatable:
>
> • A struct implicitly conforms to Equatable if all of its fields
are of types that conform to Equatable – either explicitly, or implicitly
by the application of these rules. The compiler will generate an
implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x
== rhs.x for all fields x in T.
>
> • An enum implicitly conforms to Equatable if all of its
associated values across all of its cases are of types that conform to
Equatable – either explicitly, or implicitly by the application of these
rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)
that returns true if and only if lhs and rhs are the same case and have
payloads that are memberwise-equal.
>
> Likewise, we propose the following rules for deriving Hashable:
>
> • A struct implicitly conforms to Hashable if all of its fields
are of types that conform to Hashable – either explicitly, or implicitly by
the application of these rules. The compiler will generate an
implementation of hashValue that uses a pre-defined hash function† to
compute the hash value of the struct from the hash values of its members.
>
> Since order of the terms affects the hash value computation, we
recommend ordering the terms in member definition order.
>
> • An enum implicitly conforms to Hashable if all of its associated
values across all of its cases are of types that conform to Hashable –
either explicitly, or implicitly by the application of these rules. The
compiler will generate an implementation of hashValue that uses a
pre-defined hash function† to compute the hash value of an enum value by
using the case's ordinal (i.e., definition order) followed by the hash
values of its associated values as its terms, also in definition order.
>
> † We leave the exact definition of the hash function unspecified here; a
multiplicative hash function such as Kernighan and Ritchie or Bernstein is
easy to implement, but we do not rule out other possibilities.
>
> Overriding defaults
>
> Any user-provided implementations of == or hashValue should override the
default implementations that would be provided by the compiler. This is
already possible today with raw-value enums so the same behavior should be
extended to other value types that are made to implicitly conform to these
protocols.
>
> Open questions
>
> Omission of fields from generated computations
>
> Should it be possible to easily omit certain properties from
automatically generated equality tests or hash value computation? This
could be valuable, for example, if a property is merely used as an internal
cache and does not actually contribute to the "value" of the instance.
Under the rules above, if this cached value was equatable, a user would
have to override == and hashValue and provide their own implementations to
ignore it. If there is significant evidence that this pattern is common and
useful, we could consider adding a custom attribute, such as @transient,
that would omit the property from the generated computations.
>
> Explicit or implicit derivation
>
> As with raw-value enums today, should the derived conformance be
completely explicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?
>
> Impact on existing code
>
> This change will have no impact on existing code because it is purely
additive. Value types that already provide custom implementations of == or
hashValue but satisfy the rules above would keep the custom implementation
because it would override the compiler-provided default.
>
> Alternatives considered
>
> The original discussion thread also included Comparable as a candidate
for automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant behavioral change.)
>
> Acknowledgments
>
> Thanks to Joe Groff for spinning off the original discussion thread,
Jose Cheyo Jimenez for providing great real-world examples of boilerplate
needed to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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


(Matthew Johnson) #14

+1 to a `deriving` keyword

+ 1. I like it as well. It makes the feature opt-in, declaring conformance and requesting synthesis at the same time. The syntactic difference from a simple conformance declaration means manual conformance can still be checked properly with no ambiguity about whether you were requesting synthesis or not. This approach also generalizes well.

This bullet makes me uncomfortable though:

- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well.

You should not be able to just say `struct Shape<T> deriving Equatable`. You should have to do this:

extension Shape deriving Equatable where T: Equatable {}

Or some equivalent syntax that makes it clear that you only intend to derive equatable when T meets the stated conditions.

···

On May 26, 2016, at 10:18 AM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, May 26, 2016 at 3:58 AM, Michael Peternell via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

> Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:
>
> Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)
>
>
> On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).
>
> I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.
>
> Automatically deriving Equatable andHashable for value types
>
> • Proposal: SE-0000
> • Author(s): Tony Allevato
> • Status: Awaiting review
> • Review manager: TBD
> Introduction
>
> Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and Comparability
>
> Motivation
>
> Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:
>
> func ==(lhs: Foo, rhs: Foo) -> Bool
> {
>
> return lhs.property1 == rhs.property1 &&
>
> lhs
> .property2 == rhs.property2 &&
>
> lhs
> .property3 == rhs.property3 &&
>
>
> ...
>
> }
>
> What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.
>
> In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):
>
> func ==(lhs: HandRank, rhs: HandRank) -> Bool
> {
>
> switch
> (lhs, rhs) {
>
> case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
> rSuit)):
>
> return lRank == rRank && lSuit ==
> rSuit
>
> case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
> rFour)):
>
> return lFour ==
> rFour
>
> case (.fullHouse(three: let lThree), .fullHouse(three: let
> rThree)):
>
> return lThree ==
> rThree
>
> case (.flush(let lRank, let lSuit), .flush(let rRank, let
> rSuit)):
>
> return lSuit == rSuit && lRank ==
> rRank
>
> case (.straight(high: let lRank), .straight(high: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.twoPair(high: let lHigh, low: let lLow, highCard: let
> lCard),
>
> .twoPair(high: let rHigh, low: let rLow, highCard: let
> rCard)):
>
> return lHigh == rHigh && lLow == rLow && lCard ==
> rCard
>
> case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
> lCard3),
>
> .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
> rCard3)):
>
> return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
> rCard3
>
> case (.highCard(let lCard), .highCard(let
> rCard)):
>
> return lCard ==
> rCard
>
> default
> :
>
> return false
>
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.
>
> Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:
>
> enum Foo: Int
> {
>
> case one = 1
>
>
> case two = 2
>
> }
>
>
> let x = (Foo.one == Foo.two) // works
> let y = Foo.one.hashValue // also works
> let z = Foo.one.rawValue // also also works
> Since there is precedent for this in Swift, we propose extending this support to more value types.
>
> Proposed solution
>
> We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.
>
> Specifically, we propose the following rules for deriving Equatable:
>
> • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.
>
> • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.
>
> Likewise, we propose the following rules for deriving Hashable:
>
> • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.
>
> Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.
>
> • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.
>
> † We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.
>
> Overriding defaults
>
> Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.
>
> Open questions
>
> Omission of fields from generated computations
>
> Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.
>
> Explicit or implicit derivation
>
> As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?
>
> Impact on existing code
>
> This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.
>
> Alternatives considered
>
> The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)
>
> Acknowledgments
>
> Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

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


(Michael Peternell) #15

I agree that this might be a problem that needs some consideration. The difference in Haskell is that type declarations are usually very short, e.g.

    data Maybe a = Nothing | Just a deriving (Eq, Ord)

and to any sane reader it is obvious, that if `a` is not in `Eq`, then `Maybe a` is not in `Eq` as well. Having to write something like

    data Maybe a = Nothing | Just a deriving ({Eq where Eq a}, {Ord where Ord a})

would produce no benefit. The situation is a bit different in Swift, because type declarations are usually much larger. On the other hand, Generics are less important in Swift than they are in Haskell, so having a slightly more awkward syntax when using it in a generic way is not that bad. Maybe we could say

    struct Shape<T> deriving Eq? { ... }

and the "?" after Eq means "if possible"? To opt-in for "derive if you can" behavior? However, I would like to see an example where the "derive if you can" behavior would lead to problems / confusing language semantics. I'm not saying that there is no such example, I just cannot think of one currently. The worst that can happen is that the developer is surprised that a particular type is not equatable, even though he has "derived" an Equatable "instance". He will find out at compile time I guess, and Stackoverflow will have the answer ("swift deriving doesn't work"). But still, the question is also how obvious the requirements for a type are for `deriving Equatable` to work well.

-Michael

···

Am 26.05.2016 um 17:35 schrieb Matthew Johnson <matthew@anandabits.com>:

On May 26, 2016, at 10:18 AM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org> wrote:

+1 to a `deriving` keyword

+ 1. I like it as well. It makes the feature opt-in, declaring conformance and requesting synthesis at the same time. The syntactic difference from a simple conformance declaration means manual conformance can still be checked properly with no ambiguity about whether you were requesting synthesis or not. This approach also generalizes well.

This bullet makes me uncomfortable though:

- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well.

You should not be able to just say `struct Shape<T> deriving Equatable`. You should have to do this:

extension Shape deriving Equatable where T: Equatable {}

Or some equivalent syntax that makes it clear that you only intend to derive equatable when T meets the stated conditions.


(L Mihalkovic) #16

what i care about is to have a choice about what DEFINES the identity of my values, not just an all-or-nothing situation.

···

On May 26, 2016, at 5:18 PM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org> wrote:

+1 to a `deriving` keyword

On Thu, May 26, 2016 at 3:58 AM, Michael Peternell via swift-evolution <swift-evolution@swift.org> wrote:
Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

> Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org>:
>
> Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)
>
>
> On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:
> I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).
>
> I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.
>
> Automatically deriving Equatable andHashable for value types
>
> • Proposal: SE-0000
> • Author(s): Tony Allevato
> • Status: Awaiting review
> • Review manager: TBD
> Introduction
>
> Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and Comparability
>
> Motivation
>
> Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:
>
> func ==(lhs: Foo, rhs: Foo) -> Bool
> {
>
> return lhs.property1 == rhs.property1 &&
>
> lhs
> .property2 == rhs.property2 &&
>
> lhs
> .property3 == rhs.property3 &&
>
>
> ...
>
> }
>
> What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.
>
> In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):
>
> func ==(lhs: HandRank, rhs: HandRank) -> Bool
> {
>
> switch
> (lhs, rhs) {
>
> case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
> rSuit)):
>
> return lRank == rRank && lSuit ==
> rSuit
>
> case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
> rFour)):
>
> return lFour ==
> rFour
>
> case (.fullHouse(three: let lThree), .fullHouse(three: let
> rThree)):
>
> return lThree ==
> rThree
>
> case (.flush(let lRank, let lSuit), .flush(let rRank, let
> rSuit)):
>
> return lSuit == rSuit && lRank ==
> rRank
>
> case (.straight(high: let lRank), .straight(high: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.twoPair(high: let lHigh, low: let lLow, highCard: let
> lCard),
>
> .twoPair(high: let rHigh, low: let rLow, highCard: let
> rCard)):
>
> return lHigh == rHigh && lLow == rLow && lCard ==
> rCard
>
> case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
> lCard3),
>
> .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
> rCard3)):
>
> return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
> rCard3
>
> case (.highCard(let lCard), .highCard(let
> rCard)):
>
> return lCard ==
> rCard
>
> default
> :
>
> return false
>
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.
>
> Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:
>
> enum Foo: Int
> {
>
> case one = 1
>
>
> case two = 2
>
> }
>
>
> let x = (Foo.one == Foo.two) // works
> let y = Foo.one.hashValue // also works
> let z = Foo.one.rawValue // also also works
> Since there is precedent for this in Swift, we propose extending this support to more value types.
>
> Proposed solution
>
> We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.
>
> Specifically, we propose the following rules for deriving Equatable:
>
> • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.
>
> • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.
>
> Likewise, we propose the following rules for deriving Hashable:
>
> • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.
>
> Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.
>
> • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.
>
> † We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.
>
> Overriding defaults
>
> Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.
>
> Open questions
>
> Omission of fields from generated computations
>
> Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.
>
> Explicit or implicit derivation
>
> As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?
>
> Impact on existing code
>
> This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.
>
> Alternatives considered
>
> The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)
>
> Acknowledgments
>
> Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

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


(Ricardo Parada) #17

I wonder if synthesizes would be a better choice than deriving.

···

On May 26, 2016, at 5:58 AM, Michael Peternell via swift-evolution <swift-evolution@swift.org> wrote:

Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
   ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org>:

Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)

On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:
I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).

I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.

Automatically deriving Equatable andHashable for value types

   • Proposal: SE-0000
   • Author(s): Tony Allevato
   • Status: Awaiting review
   • Review manager: TBD
Introduction

Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.

Swift-evolution thread: Universal Equatability, Hashability, and Comparability

Motivation

Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:

func ==(lhs: Foo, rhs: Foo) -> Bool
{

return lhs.property1 == rhs.property1 &&

        lhs
.property2 == rhs.property2 &&

        lhs
.property3 == rhs.property3 &&

...

}

What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.

Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.

In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):

func ==(lhs: HandRank, rhs: HandRank) -> Bool
{

switch
(lhs, rhs) {

case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
rSuit)):

return lRank == rRank && lSuit ==
rSuit

case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
rFour)):

return lFour ==
rFour

case (.fullHouse(three: let lThree), .fullHouse(three: let
rThree)):

return lThree ==
rThree

case (.flush(let lRank, let lSuit), .flush(let rRank, let
rSuit)):

return lSuit == rSuit && lRank ==
rRank

case (.straight(high: let lRank), .straight(high: let
rRank)):

return lRank ==
rRank

case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
rRank)):

return lRank ==
rRank

case (.twoPair(high: let lHigh, low: let lLow, highCard: let
lCard),

.twoPair(high: let rHigh, low: let rLow, highCard: let
rCard)):

return lHigh == rHigh && lLow == rLow && lCard ==
rCard

case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
lCard3),

.onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
rCard3)):

return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
rCard3

case (.highCard(let lCard), .highCard(let
rCard)):

return lCard ==
rCard

default
:

return false

}
}

Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.

Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:

enum Foo: Int
{

case one = 1

case two = 2

}

let x = (Foo.one == Foo.two) // works
let y = Foo.one.hashValue // also works
let z = Foo.one.rawValue // also also works
Since there is precedent for this in Swift, we propose extending this support to more value types.

Proposed solution

We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.

Specifically, we propose the following rules for deriving Equatable:

   • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.

   • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.

Likewise, we propose the following rules for deriving Hashable:

   • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.

Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.

   • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.

† We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.

Overriding defaults

Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

Open questions

Omission of fields from generated computations

Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.

Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

Impact on existing code

This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.

Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

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

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

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


(E. Maloney) #18

I agree.

This also isn't the only case where a 'deriving' keyword would come in handy. I'm mulling a proposal for a compiler-derived enum, and I worried the magic-ness of it would face strong opposition. Having a 'deriving' keyword is the perfect solution, since it becomes explicit.

···

On May 26, 2016, at 11:18 AM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org> wrote:

+1 to a `deriving` keyword

On Thu, May 26, 2016 at 3:58 AM, Michael Peternell via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

> Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:
>
> Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)
>
>
> On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).
>
> I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.
>
> Automatically deriving Equatable andHashable for value types
>
> • Proposal: SE-0000
> • Author(s): Tony Allevato
> • Status: Awaiting review
> • Review manager: TBD
> Introduction
>
> Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and Comparability
>
> Motivation
>
> Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:
>
> func ==(lhs: Foo, rhs: Foo) -> Bool
> {
>
> return lhs.property1 == rhs.property1 &&
>
> lhs
> .property2 == rhs.property2 &&
>
> lhs
> .property3 == rhs.property3 &&
>
>
> ...
>
> }
>
> What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.
>
> In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):
>
> func ==(lhs: HandRank, rhs: HandRank) -> Bool
> {
>
> switch
> (lhs, rhs) {
>
> case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
> rSuit)):
>
> return lRank == rRank && lSuit ==
> rSuit
>
> case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
> rFour)):
>
> return lFour ==
> rFour
>
> case (.fullHouse(three: let lThree), .fullHouse(three: let
> rThree)):
>
> return lThree ==
> rThree
>
> case (.flush(let lRank, let lSuit), .flush(let rRank, let
> rSuit)):
>
> return lSuit == rSuit && lRank ==
> rRank
>
> case (.straight(high: let lRank), .straight(high: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.twoPair(high: let lHigh, low: let lLow, highCard: let
> lCard),
>
> .twoPair(high: let rHigh, low: let rLow, highCard: let
> rCard)):
>
> return lHigh == rHigh && lLow == rLow && lCard ==
> rCard
>
> case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
> lCard3),
>
> .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
> rCard3)):
>
> return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
> rCard3
>
> case (.highCard(let lCard), .highCard(let
> rCard)):
>
> return lCard ==
> rCard
>
> default
> :
>
> return false
>
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.
>
> Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:
>
> enum Foo: Int
> {
>
> case one = 1
>
>
> case two = 2
>
> }
>
>
> let x = (Foo.one == Foo.two) // works
> let y = Foo.one.hashValue // also works
> let z = Foo.one.rawValue // also also works
> Since there is precedent for this in Swift, we propose extending this support to more value types.
>
> Proposed solution
>
> We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.
>
> Specifically, we propose the following rules for deriving Equatable:
>
> • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.
>
> • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.
>
> Likewise, we propose the following rules for deriving Hashable:
>
> • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.
>
> Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.
>
> • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.
>
> † We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.
>
> Overriding defaults
>
> Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.
>
> Open questions
>
> Omission of fields from generated computations
>
> Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.
>
> Explicit or implicit derivation
>
> As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?
>
> Impact on existing code
>
> This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.
>
> Alternatives considered
>
> The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)
>
> Acknowledgments
>
> Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

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


(Ricardo Parada) #19

What if we get the error when trying to use it? For example, if a struct uses a value that is not Equatable / Hashable then it would not be Equatable / Hashable and you would not find out until you tried to use it. Would that be bad?

···

On May 26, 2016, at 11:35 AM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

On May 26, 2016, at 10:18 AM, T.J. Usiyan via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

+1 to a `deriving` keyword

+ 1. I like it as well. It makes the feature opt-in, declaring conformance and requesting synthesis at the same time. The syntactic difference from a simple conformance declaration means manual conformance can still be checked properly with no ambiguity about whether you were requesting synthesis or not. This approach also generalizes well.

This bullet makes me uncomfortable though:

- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well.

You should not be able to just say `struct Shape<T> deriving Equatable`. You should have to do this:

extension Shape deriving Equatable where T: Equatable {}

Or some equivalent syntax that makes it clear that you only intend to derive equatable when T meets the stated conditions.

On Thu, May 26, 2016 at 3:58 AM, Michael Peternell via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Can we just copy&paste the solution from Haskell instead of creating our own? It's just better in every aspect. Deriving `Equatable` and `Hashable` would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason), you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any new incompatibilities. For example, `CustomStringConvertible` could be derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if `X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not used, in which case every `Shape<T>` would be equatable. Unless something in the definition of `Shape` makes deriving `Equatable` impossible => this produces an error.)
- It is proven to work in production.

-Michael

> Am 26.05.2016 um 03:48 schrieb Mark Sands via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:
>
> Thanks so much for putting this together, Tony! Glad I was able to be some inspiration. :^)
>
>
> On Wed, May 25, 2016 at 1:28 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> I was inspired to put together a draft proposal based on an older discussion in the Universal Equality, Hashability, and Comparability thread <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919/> that recently got necromanced (thanks Mark Sands!).
>
> I'm guessing that this would be a significant enough change that it's not possible for the Swift 3 timeline, but it's something that would benefit enough people that I want to make sure the discussion stays alive. If there are enough good feelings about it, I'll move it from my gist into an actual proposal PR.
>
> Automatically deriving Equatable andHashable for value types
>
> • Proposal: SE-0000
> • Author(s): Tony Allevato
> • Status: Awaiting review
> • Review manager: TBD
> Introduction
>
> Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers find themselves writing large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance toEquatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is likely to be possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and Comparability
>
> Motivation
>
> Building robust value types in Swift can involve writing significant boilerplate code to support concepts of hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:
>
> func ==(lhs: Foo, rhs: Foo) -> Bool
> {
>
> return lhs.property1 == rhs.property1 &&
>
> lhs
> .property2 == rhs.property2 &&
>
> lhs
> .property3 == rhs.property3 &&
>
>
> ...
>
> }
>
> What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valuedDictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.
>
> In particular, the code that must be written to implement equality for enums is quite verbose. One such real-world example (source):
>
> func ==(lhs: HandRank, rhs: HandRank) -> Bool
> {
>
> switch
> (lhs, rhs) {
>
> case (.straightFlush(let lRank, let lSuit), .straightFlush(let rRank , let
> rSuit)):
>
> return lRank == rRank && lSuit ==
> rSuit
>
> case (.fourOfAKind(four: let lFour), .fourOfAKind(four: let
> rFour)):
>
> return lFour ==
> rFour
>
> case (.fullHouse(three: let lThree), .fullHouse(three: let
> rThree)):
>
> return lThree ==
> rThree
>
> case (.flush(let lRank, let lSuit), .flush(let rRank, let
> rSuit)):
>
> return lSuit == rSuit && lRank ==
> rRank
>
> case (.straight(high: let lRank), .straight(high: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.threeOfAKind(three: let lRank), .threeOfAKind(three: let
> rRank)):
>
> return lRank ==
> rRank
>
> case (.twoPair(high: let lHigh, low: let lLow, highCard: let
> lCard),
>
> .twoPair(high: let rHigh, low: let rLow, highCard: let
> rCard)):
>
> return lHigh == rHigh && lLow == rLow && lCard ==
> rCard
>
> case (.onePair(let lPairRank, card1: let lCard1, card2: let lCard2, card3: let
> lCard3),
>
> .onePair(let rPairRank, card1: let rCard1, card2: let rCard2, card3: let
> rCard3)):
>
> return lPairRank == rPairRank && lCard1 == rCard1 && lCard2 == rCard2 && lCard3 ==
> rCard3
>
> case (.highCard(let lCard), .highCard(let
> rCard)):
>
> return lCard ==
> rCard
>
> default
> :
>
> return false
>
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly inconvenient to write, involving another large switchstatement.
>
> Swift already provides implicit protocol conformance in some cases; notably, enums with raw values conform toRawRepresentable, Equatable, and Hashable without the user explicitly declaring them:
>
> enum Foo: Int
> {
>
> case one = 1
>
>
> case two = 2
>
> }
>
>
> let x = (Foo.one == Foo.two) // works
> let y = Foo.one.hashValue // also works
> let z = Foo.one.rawValue // also also works
> Since there is precedent for this in Swift, we propose extending this support to more value types.
>
> Proposed solution
>
> We propose that a value type be Equatable/Hashable if all of its members are Equatable/Hashable, with the result for the outer type being composed from its members.
>
> Specifically, we propose the following rules for deriving Equatable:
>
> • A struct implicitly conforms to Equatable if all of its fields are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T)that returns true if and only if lhs.x == rhs.x for all fields x in T.
>
> • An enum implicitly conforms to Equatable if all of its associated values across all of its cases are of types that conform to Equatable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of ==(lhs: T, rhs: T) that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.
>
> Likewise, we propose the following rules for deriving Hashable:
>
> • A struct implicitly conforms to Hashable if all of its fields are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of the struct from the hash values of its members.
>
> Since order of the terms affects the hash value computation, we recommend ordering the terms in member definition order.
>
> • An enum implicitly conforms to Hashable if all of its associated values across all of its cases are of types that conform to Hashable – either explicitly, or implicitly by the application of these rules. The compiler will generate an implementation of hashValue that uses a pre-defined hash function† to compute the hash value of an enum value by using the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.
>
> † We leave the exact definition of the hash function unspecified here; a multiplicative hash function such as Kernighan and Ritchie or Bernstein is easy to implement, but we do not rule out other possibilities.
>
> Overriding defaults
>
> Any user-provided implementations of == or hashValue should override the default implementations that would be provided by the compiler. This is already possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.
>
> Open questions
>
> Omission of fields from generated computations
>
> Should it be possible to easily omit certain properties from automatically generated equality tests or hash value computation? This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it. If there is significant evidence that this pattern is common and useful, we could consider adding a custom attribute, such as @transient, that would omit the property from the generated computations.
>
> Explicit or implicit derivation
>
> As with raw-value enums today, should the derived conformance be completely explicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?
>
> Impact on existing code
>
> This change will have no impact on existing code because it is purely additive. Value types that already provide custom implementations of == or hashValue but satisfy the rules above would keep the custom implementation because it would override the compiler-provided default.
>
> Alternatives considered
>
> The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)
>
> Acknowledgments
>
> Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

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


(Pedro Vieira) #20

I really think this would be a great addition to Swift. Although, I don't
see the need to use a new keyword `deriving` for this feature.
The following would be enough:

struct Foo: Equatable, Hashable {
  ...
}

It's explicit and it uses features already in the language. With this, the
compiler would generate all the functions needed for `Foo` to conform to
`Equatable` and `Hashable` and, in case the developer wants custom behavior
on any of those functions, he/she could just write it from scratch and the
compiler would use it over the generated one.

Michael Peternell via swift-evolution <swift-evolution@swift.org> escreveu
no dia quinta, 26/05/2016 às 10:58:

Can we just copy&paste the solution from Haskell instead of creating our
own? It's just better in every aspect. Deriving `Equatable` and `Hashable`
would become

struct Polygon deriving Equatable, Hashable {
    ...
}

This has several advantages:
- you don't have to guess wether `Equatable` or `Hashable` should be
automatically derived or not.
- Deriving becomes an explicit choice.
- If you need a custom `Equatable` implementation (for whatever reason),
you can still do it.
- It doesn't break any code that is unaware of the change
- It can be extended in future versions of Swift, without introducing any
new incompatibilities. For example, `CustomStringConvertible` could be
derived just as easily.
- It is compatible with generics. E.g. `struct Shape<T> deriving
Equatable` will make every `Shape<X>` equatable if `X` is equatable. But if
`X` is not equatable, `Shape<X>` can be used as well. (Unless `X` is not
used, in which case every `Shape<T>` would be equatable. Unless something
in the definition of `Shape` makes deriving `Equatable` impossible => this
produces an error.)
- It is proven to work in production.

-Michael

Pedro Vieira
http://pedrovieira.me

···

--
Pedro Vieira
http://pedrovieira.me