Multiversal Equality

[odersky]

Note

The status of eqAny and other predefined eq comparisons has changed in #2786, together with the resolution algorithm. The up-to-date details are in the reference http://dotty.epfl.ch/docs/reference/multiversal-equality.html

Motivation

Scala prides itself of its strong static type system. Its type discipline is particularly useful when it comes to refactoring. Indeed, it's possible to write programs in such a way that refactoring problems show up with very high probability as type errors. This is essential for being able to refactor with the confidence that nothing will break. And the ability to do such refactorings is in turn very important for keeping code bases from rotting.

Of course, getting such a robust code base requires the cooperation of the developers. They should avoid type Any, casts, stringly typed logic, and more generally any operation over loose types that do not capture the important properties of a value. Unfortunately, there is one area in Scala where such loose types are very hard to avoid: That's equality. Comparisons with == and != are universal. They compare any two values, no matter what their types are. This causes real problems for writing code and more problems for refactoring it.

For instance, one might want to introduce a proxy for some data structure so that instead of accessing the data structure directly one goes through the proxy. The proxy and the underlying data would have different types. Normally this should be an easy refactoring. If one passes by accident a proxy for the underlying type or vice versa the type checker will flag the error. However, if one accidentally compares a proxy with the underlying type using == or a pattern match, the program is still valid, but will just always say false. This is a real worry in practice. I recently abandoned a desirable extensive refactoring because I feared that it would be too hard to track down such errors.

Current Status

The problems of universal equality in Scala are of course well known. Some libraries have tried to fix it by adding another equality operator with more restricted typing. Most often this safer equality is written ===. While === is certainly useful, I am not a fan of adding another equality operator to the language and core libraries. It would be much better if we could fix == instead. This would be both simpler and would catch all potential equality problems including those related to pattern matching.

How can == be fixed? It looks much harder to do this than adding an alternate equality operator. First, we have to keep backwards compatibility. The ability to compare everything to everything is by now baked into lots of code and libraries. For instance, we might have a Map with Any keys that uses
universal equality and hashcode to store and retrieve any value. Second, with just one equality operator we need to make this operator work in all cases where it makes sense. An alternative === operator can choose to refuse some comparisons which would still be sensical because there's always == to fall back to. With a unique == operator we do not have this luxury.

The current status in Scala is that the compiler will give warnings for some comparisons that are always false. But the coverage is very weak. For instance this will give a warning:

scala> 1 == "abc"
<console>:12: warning: comparing values of types Int and String using `==' will always yield false

But this will not:

scala> "abc" == 1
res2: Boolean = false

There are also cases where a warning is given for a valid equality test that actually makes sense because the result could be true. In summary, the current checking catches some obvious bugs, which is nice. But it is far too weak and fickle to be an effective refactoring aid.

Proposal

I believe to do better, we need to enlist the cooperation of developers. Ultimately it's the developer who provides implementations of equality methods and who is therefore best placed to characterize which equalities make sense. Sometimes this characterization can be involved. For instance, an Int can be compared to other primitive numeric values or to instances of type Number but any other comparison will always yield false. Or, it makes sense to compare two List values if and only if it makes sense to compare the list's element values.

The best known way to characterize such relationships is with type classes (aka implicit values). A type class Eq[T, U] can capture the property that values of type T can be compared to values of type U. Here's the proposed definition of this type class:

package scala

import annotation.implicitNotFound

/** A marker trait indicating that values of kind `T` can be compared to values of type `U`. */
@implicitNotFound("Values of types ${L} and ${R} cannot be compared with == or !=")
sealed trait Eq[-L, -R]

/** Besides being a companion object, this object
 *  can also be used as a value that's compatible with
 *  any instance of `Eq`.
 */
object Eq extends Eq[Any, Any] {

  /** A fall-back implicit to compare values of any types.
   *  The compiler will restrict implicit instances of `eqAny`. An instance
   *  `eqAny[T, U]` is _invalid_ if `T` or `U` is a non-bottom type that
   *  has an implicit `Eq[T, T]` (respectively `Eq[U, U]`) instance.
   *  An implicit search will fail instead of returning an invalid `eqAny` instance,
   */
  implicit def eqAny[L, R]: Eq[L, R] = Eq
}

Note 1: Eq is contravariant. So an instance of, say, Eq[Number, Number] is also an instance of Eq[BigInt, BigDecimal]. In other words: If all instances of Number can be compared then BigInts can be compared to BigDecimals, because they are both instances of Number.

Note 2: Eq does not have any members; it's a pure marker trait. The idea is that the Scala compiler will check every time it encounters a potentially problematic comparison between values of types T and U that there is an implicit instance of Eq[T, U]. A comparison is potentially problematic if it is between incompatible types. As long as T <: U or U <: T the equality could make sense because both sides can potentially be the same value.

The Scala compiler will also perform this check on every pattern match against a value (i.e. where the pattern is a non-variable identifier or a selection, or a literal). It treats such a pattern match like a comparison between the type of the scrutinee and the type of the pattern value.

Developers can define equality classes by giving implicit Eq instances. Here is a simple one:

   implicit def eqString: Eq[String, String] = Eq

Since Eq does not have any members, the sole purpose of these implicit instances is for type checking. The right hand side of the instance does not matter, as long as it is type-correct. The companion object Eq is always correct since it extends Eq[Any, Any].

Parameterized types generally need polymorphic Eq instances. For example:

  implicit def eqList[T, U](implicit _eq: Eq[T, U]): Eq[List[T], List[U]] = Eq

This expresses that Lists can be compared if their elements can be compared.

What about types for which no Eq instance exists? To maintain backwards compatibility, we allow comparisons of such types as well, by means of the standard eqAny instance in the Eq object that was shown above. The type signature of eqAny suggests that it works for any two types, but this would render equality checking ineffective, because Eq instances would always be found. But in fact the compiler will check any generated eqAny instance in implicit search for validity.

Let lift be a function on types that maps every covariant occurrence of an abstract type to its upper bound and that drops all refinements in covariant positions. An instance

  eqAny[T, U]

is valid if T <: lift(U) or if U <: lift(T) or if both T, U are Eq-free. A type S is Eq-free if there is no implicit instance of type Eq[S, S] other than eqAny itself. Invalid eqAny instances will not returned from implicit search.

Note 3: The purpose of lift above is to make code like this compile:

    def f[T](x: T) = 
      if (x == null) ... 
      else if (x == "abc") ...
      else ...

Without it, we would have to resort to a widening cast, i.e. if (x.asInstanceOf[Any] == null, which is ugly.

Note 4: It is conceivable that the eqAny behavior can be implemented as a macro. We will know more once macros are redesigned.

A Refinement

The scala.equalityClass annotation can be used to avoid the boilerplate of writing implicit Eq instances by hand. If @equalityClass is given for a class C, the companion object of C would get an automatically generated Eq instance defined in the way sketched above. For instance:

  @equalityClass trait Option[+T] { ... }

would generate the following Eq instance:

object Option {
  implicit def eqOption[T, U](implicit $x0: Eq[T, U]): Eq[Option[T], Option[U]] = Eq
}

It should be possible to get this functionality by making @equalityClass a macro annotation.

Properties

Here are some properties of the proposal

1. It is opt-in. To get safe checking, developers have to annotate classes that should
   allow comparisons only between their instances with @equalityClass, or they have to define implicit
   Eq instances by hand.
2. It is backwards compatible. Without @equalityClass annotations equality works as before.
3. It carries no run-time cost compared to universal equality. Indeed the run-time behavior of
   equality is not affected at all.
4. It has no problems with parametricity, variance, or bottom types.
5. Depending on the actual Eq instances given, it can be very precise. That is,
   no comparisons that might yield true need to be rejected, and most comparisons that
   will always yield false are in fact rejected.

The scheme effectively leads to a partition of the former universe of types into sets of types. Values with types in the same partition can be compared among themselves but values with types in different partitions cannot.

An @equalityClass annotation on a type creates a new partition. All types that do not have any Eq instances (except eqAny, that is) form together another partition.

So instead of a single universe of values that can be compared to each other we get a multiverse of partitions. Hence the name of the proposal: Multiversal Equality.

Implementation Status

The core of the proposal is implemented in #1246. The refinement of having @equalityClass annotations generate Eq instances is not yet implemented.

Experience

As a first step, I added Eq instances to some of the core types of dotty: Type, Symbol, Denotation, Name. Two bugs were found where comparisons made no sense because they compared values of different types and therefore would always yield false (one of them was a pattern match). There were no instances where a sensical comparison was flagged as an error.

A Possible Variant

The current proposal needs a change to the handling of contravariant type parameters in implicit search and overloading resolution, which is described and implemented in 340f883. Without that change, eqAny would always take precedence over any other implicit Eq instance, which is not what we want.

If we do not want to rely on that change, one could alternatively make Eq non-variant, but then
Eq instances become more complicated because they have to talk about all possible subtypes
of an equality class using additional type parameters.

[smarter]

1. T is one of the bottom types Nothing or Null.

I think this can be refined further, we don't wont to be able to call == between an AnyVal and a Null, right?

[odersky]

@smarter. Yes, indeed. Maybe we can drop the clause completely because it is already subsumed by the "don't test if it's a global subtype" requirement.

[OlegYch]

so, does this proposal introduce '===' or fix '==' ?

[smarter]

@OlegYch : It fixes ==.

[soc]

I'm a bit concerned regarding the @equalityClass annotation.

• Wouldn't that create a dramatic amount of bit-rot in the sense that after its introduction most declarations without would be considered legacy code?
• Additionally, wouldn't it be just create boilerplate if everyone keeps adding @equalityClass to class declarations?

From my perspective it would be better if there was a boilerplate free way to phase-in the new approach, and offer some (maybe annotation-based?) solution to get back the old behavior?

Has the "more traditional" way been considered of requiring a typeclass for equality operations instead of providing them by default? What was the lesson here and how did it compare to the proposed approach in this PR?

More conceptually, how will this work with the varying levels of "sameness": Identity, equality and floating-point rules?

[odersky]

@soc equalityClass only applies to top-level types. Otherwise put, once you have established a class of types that accept equality it makes no sense to refine that. So I don't think there will be that many @equalityClass annotations necessary.

I have discussed lots of other ways to make == safe with lots of people, but none of them worked out as well as this one. But that should not stop others from trying!

[odersky]

@smarter

T is one of the bottom types Nothing or Null.

I think this can be refined further, we don't wont to be able to call == between an AnyVal and a Null, right?

I now think it is slightly more consistent to change the requirement on eqAny as follows:

An instance

eqAny[T, U]

is valid if T <: U or U <: T or if both of its argument types T, U are Eq-free. An argument type T is Eq-free if there is no implicit instance of type Eq[T, T] other than eqAny itself.

[smarter]

if there is no implicit instance of type Eq[T, T]

To be perfectly precise you should exclude eqAny[T, T] from that definition.

[odersky]

OK, changed.

[Sciss]

While I applaud the attempt to make == safer, I'm on Simon's side with respect to the noise introduced by @equalityClass. Basically we are saying, from now on to have properly safe equality, you should add that annotation to your classes. This is counter-intuitive and makes code look more horrible.

I think the better solution is to have the opposite defaults: If you want to allow universal equality on a type, you must add @universalEquality to it. That way code stays clean and nice.

To avoid the problem of backwards incompatibility, one could easily add a language feature import such as import scala.language.universalEquality for legacy code.

WDYT?

[Blaisorblade]

@soc equalityClass only applies to top-level types.

@martin Do you mean top-level as in "root of some hierarchy"? I keep reading "top-level" as "non-nested" 😦

So I don't think there will be that many @equalityClass annotations necessary.

What about case class hierarchies?

trait Base //possibly sealed
case class A extends Base
case class B extends Base
...

An annotation would be appropriate for Base — it's not clear it can ever be inferred somehow.

[Blaisorblade]

@Sciss Martin's goal, as I understand it, is: Existing code should keep working without changes. Proposals ignoring that will get ignored — I thought that much was clear from the debate on redoing collections. And I'd say, you need a plausible path to incrementally convert code to the new rules, as in gradual typing.

So if you want to make that proposal considered, at least flip things: provide import scala.language.multiversalEquality, and people who like it everywhere can use it as -language:multiversalEquality, written once in their SBT files. For this to have a chance of being a reasonable migration path, I guess that annotation should affect the definition-site, not the client-site: that is, uses of == should work the same way with or without the flag, but the flag should imply @equalityClass annotations everywhere appropriate. But I even doubt Scalac can guess that: how would Scalac know that Base above should be annotated? What about a less trivial example?

[DarkDimius]

I'd like to point out that implementing this proposal requires changes to implicit search: 340f883
Moreover, the current proposed implementation works differently for top-level and non-top-level contravariant type arguments.

The main motivation for this proposal is safe refactorings. Unfortunately, the implementation introduces a difference in behavior of top-level type arguments from all the other. This may make refactorings harder as introducing one more(even invariant!) level of type arguments would be a huge change to behavior of the API.

At the same time, such a difference in behavior introduces one more freedom of flexibility for library author(as implicits can be chained to infer parameters level-by-level). This can be a source of surprise for someone who tries to understand how implicits work.

While I see the rationale, and I like the generated code. I'd feel a lot more confident in making needed change to implicit search if it went through a proper sip process. I'm in favor of this change currently, though I'm not sure how much would it affect existing code and how much surprising would this behavior be to newcomers.

[Sciss]

@Blaisorblade

Existing code should keep working without changes.

That's exactly what I'm proposing with import scala.language.universalEquality. That's exactly the same as saying we need to import now scala.language.implicitConversion if we want to have implicit conversions (one would have to discuss warning vs. error). Existing code with zero changes doesn't make sense. It's simple enough to add, as you propose for the opposite flag, that flag to your sbt file. Secondly, we are talking about Dotty not Scala 2.x.

What you are saying is flip things back to Martin's proposal. So what's the addition here?

---

So if your old code read

def foo(x: Option[String], b: String) = x == b

That constituted a bug, and thus "breaking" compilation in the new version should be the desired behaviour. So we assume everything in std lib will have @equalityClass, or—as I suggest—nothing will have nothing because this is the default. I can't see a case where you would have @universalEquality in std.lib.

Then in client code if you have the rare case of

trait Not
trait Related { def equals(that: Any): Boolean = that.isInstanceOf[Not] }

You can still compile it if you add legacy flag -language:universalEquality.

Win-win IMHO.

[Blaisorblade]

@Sciss

Secondly, we are talking about Dotty not Scala 2.x.

No, only the prototype is for Dotty, otherwise compatibility would indeed make no sense.

What you are saying is flip things back to Martin's proposal.

That's not the intention: scala.language.multiversalEquality would avoid the annotations you dislike.
By flipping the default, one moves the busywork to those that want to get different behavior and accept dealing with the corresponding overhead. Of course, this variant keeps the whole Eq infrastructure in place. Do you mean your idea doesn't? I can't tell for sure.

But developers that want to upgrade a huge codebase to a new compiler (say, enterprise shops) will only need to deal with deprecations, without additional busywork.

It's simple enough to add, as you propose for the opposite flag, that flag to your sbt file

I propose adding that flag for small or new projects. That doesn't work for converting a code base. See the experience with the transition to Python 3 (still ongoing) or with the alternative to gradual typing (that weren't adopted because with them converting to a code base was implausible).

With Martin's proposal, you can add @equalityClass to one class at a time and fix the corresponding errors before moving on to the next.
With the opposite default, to similarly convert classes in a file a file one by one, you'd need to disable file-level universalEquality, add the annotation to each class, and then remove it one-by-one and fix errors.

[Blaisorblade]

Issue: Can one ever introduce Eq instances in an existing library (for types in the public API) while preserving compatibility? Say, in the Scala standard library?
If the goal is strict compatibility, the answer seems no, unless finer control is given on the resulting errors.

An excellent inspiration is given by gradual typing. There you have two type systems, a lax and a strict one (the weak one is usually "no type system", but that seems incidental).

There, you need to opt-in to the strict type system both at the definition-site and at the call-site.

When you turn some laxly-typed API into strictly-typed API (say, by adding a type signature), existing laxly-typed clients keep compiling, until they're switched to strict typing themselves. For strict compatibility, we'd need to do something similar: some language flag saying "in the scope where this is visible, uses of equals are checked with the new discipline".

This might be overkill, but to check if this is actually needed, we'd need to study the overhead on community builds, and confirm it's below some very low threshold. We'll also need numbers about the number of false positives in a bigger study: if all errors are bugs, they might be a bit more acceptable.

[Sciss]

scala.language.multiversalEquality would avoid the annotations you dislike.

Then I fail to understand how this would magically avoid the annotations. The import surely happens on the use-site not declaration-site. Or do you mean that if I import that flag, all traits and classes scalac encounters in a source file will have a @equalityClass added? That would be very weird. So if you say this is a use-site import then how do you determine that a non-annotated class is suddenly annotated? Say I have

case class Foo()

Then if I have a use-site

import scala.language.multiversalEquality

trait Test {
  Foo() == Foo()
}

How would that import change the compiler's behaviour in your opinion? Presumably that import means universal equality is disabled. So how do you get your Eq[Foo, Foo] now if not from thin air?

---

That doesn't work for converting a code base

That works precisely for converting a code base. If you have obsolete

// declaration site
trait Not
trait Related { def equals(that: Any): Boolean = that.isInstanceOf[Not] }

// use site
import scala.language.universalEquality

trait Test {
  new Related {} == new Not {}
}

Then if you remove the import, you get the compile error. Then if you want to stick to your declaration, you add @universalEquality to Related. Where exactly is the problem, I don't see one?

And what does this have to do with Python 3? There will be a Scala version where procedure syntax and XML literals go from warning to error. So what? I thought we were better than Java in allowing the language to improve over time.

---

The problem with @universalEquality is not one of logic, but only one of implementation. Because Martin's approach can rely on the way implicits work, they can only positively witness something but not negatively. But then the question remains if you should solve the issue in a "flipped way" (from how it should be IMO) just because that's what is more straight forward to implement with the existing functions of the language (positive implicit resolution). I will see if I can come up with an implementation of the negative resolution.

[argv-minus-one]

What about scala.math.Equiv? It seems pretty close in meaning to this new Eq type, though it is not contravariant. Will it be deprecated?

[Blaisorblade]

@Sciss

Then I fail to understand how this would magically avoid the annotations. The import surely happens on the use-site not declaration-site.

If you were to read my posts, I did describe the opposite:

For this to have a chance of being a reasonable migration path, I guess that annotation should affect the definition-site, not the client-site: that is, uses of == should work the same way with or without the flag, but the flag should imply @equalityClass annotations everywhere appropriate.

I also described some issues with that.

Presumably that import means universal equality is disabled. So how do you get your Eq[Foo, Foo] now if not from thin air?

If I had a use-site flag (which I proposed later, orthogonally to our discussion), it would enable the discipline being proposed by Martin, under which Eq[Foo, Foo] would not be needed.

Then if you remove the import, you get the compile error. Then if you want to stick to your declaration, you add @universalEquality to Related. Where exactly is the problem, I don't see one?

I'm talking about codebases big enough that getting to a new correct state takes lots of time — hundreds of thousands of lines.

There will be a Scala version where procedure syntax and XML literals go from warning to error.

Deprecation warnings are different: if your code compiles without deprecation warnings, it will work with the next version (modulo small unforeseen issues). And IIRC Martin claimed, at some point, that doing those changes required automated refactoring support.

I thought we were better than Java in allowing the language to improve over time.

"Yes", but developers are very concerned about the existing user base, so changes have to happen carefully — especially for something as pervasive as equality. Some summarize the situation as "no", though I disagree.

If you want some evidence, take a look at the collection redesign that I already mentioned: #818. Most proposed changes were excluded because they broke compatibility. I only answered your post to inform you that this kind of concern.

Overall: I'll take a break from this subthread, because it's dominating the rest; it does not seem very productive; moreover, our perspectives seem too distant. (And I'm not the one to convince anyway).

[nafg]

1. Eq-free could be expressed with a general notation for absence of an implicit
2. It's great to have a way to express in the type system which types can be compared to which. But the equals method still had the same old essentially untyped signature. Any chance there could be a way to define equals that was in lockstep with Eq? Maybe an alternative signature? Maybe def == ?
3. This only solves the problem of knowing what types can be compared against which. Since it uses typeclasses (implicits) the answer depends on the current scope. However the implementation, equals, is still universal. This raises two questions:
   A. Is there any hope of getting scope-dependent equality? Different contexts may call for different senses of equality!
   B. It's nice to have a powerful type-level tool. But In light of 2 and 3, essentially the types are lying! There's no way to ensure that the equals method fulfills the claim of the typeclass, and the flexibility of typeclasses means there are sets of claims that can be made but can't be fulfilled!

Couldn't the type class instance just come with an implementation method, and if you have it then use it?

[esarbe]

I like the proposal, but would prefer the defaults to be switched. I.E. opt-out of the new behavior of == instead of opt-in

1. Stage: Deprecation warning for the old behavior and a compiler flag to opt-out of the new behavior
2. Stage: Deprecation warning for the old behavior, deprecation of the compiler flag to opt-out, introduction of call-site opt-out (via implicit import)
3. Stage: Old code will produce error without Eq

[odersky]

@Blaisorblade @Sciss It's an interesting idea to switch the defaults. As far as dotty is concerned I am not so much concerned about backwards compatibility - we already have a -language:Scala2 import which could take care of that.

But the real problem that I see is what @Blaisorblade noticed: Not all classes are an @equalityClass, so where should the annotation be inserted? One way I can see is:

• Insert it for all classes that are not annotated @universalEquality and that are not subtypes of an equality class.

But that's fragile. Say we have a hierachy

trait Displayable
trait Geometric
trait Shape extends Geometric with Displayable
trait Point extends Geometric with Displayable

and we want to make Points comparable to Points and Shapes comparable to Shapes (as seems reasonable). Under the current proposal you write

trait Geometric
trait Displayable
@equalityClass trait Shape extends Geometric
@equalityClass trait Point extends Geometric

Under the alternative proposal you write:

@universalEquality trait Geometric
@universalEquality trait Displayable
trait Shape extends Geometric with Displayable
trait Point extends Geometric with Displayable

This seems a bit backwards and fragile to me. It's easy to forget @universalEquality on some trait, and if you do forget it you get overlapping equality classes in subclasses that mix in this trait. I would not be surprised if in the end the number of necessary @unversalEquality annotations would greatly exceed the number of necessary @equalityClass annotations under the current proposal.

[odersky]

Regarding the universal signature of the equals method. That cannot be changed. equals is used in contexts where universal equality is required, for instance it can be called in a HashMap[Any, _].

[odersky]

@Sciss @Blaisorblade The currently proposed scheme also supports a simple heuristic:

When redefining equals on a class, consider annotating that class with @equalityClass.

I don't see a similar heuristic for @universalEquality.

[jbgi]

Regarding the universal signature of the equals method. That cannot be changed. equals is used in contexts where universal equality is required

Could the implementation of equals be generated and delegate to the typeclass instance implementation, after some simple isInstanceOf / asInstanceOf glue?
This is what is done in functionaljava, eg.:
https://github.com/functionaljava/functionaljava/blob/master/core/src/main/java/fj/Equal.java#L577
https://github.com/functionaljava/functionaljava/blob/master/core/src/main/java/fj/data/Option.java#L608

[Sciss]

@odersky Thanks for your comments. I can see the difficulties in unambiguously deciding for which types we have the new equality under the "opposite default" scheme. With the heuristics of synthesising the type class when equals is overridden, perhaps this already solves the "noisiness". I also infer from this that every case class will automatically have @equalityClass (because it produces its own equals and hashCode) and you do not need to add this explicitly.

This kind of connects then to the question of ADT syntax - because you can have sealed trait Option[+A]; case class Some[A](x: A) extends Option[A]; case object None extends Option[Nothing] which with the heuristics would only produce Eq[Some] and Eq[None], but we would still have to say @equalityClass sealed trait Option? Or could the heuristics infer from sealed with all sub-classes having @equalityClass to again implicitly define its own @equalityClass?

[Sciss]

I strongly agree with @lrytz. If the long term goal is simplification of the language, we cannot always rely on implementing everything with macros and annotation purely as library views. While I generally like Scala's approach of going library first before baking it into the language - e.g. collections, concurrency - I think these fundamental things like equality, abstract data types etc. should look very clean and not tucked on through some @annotations. Having close integration in the language itself will help fight against all those misperceptions such Scala = C++, etc. One should be able to formulate any standard type of program without annotations (for the same reason we have lazy val and not @lazy val.

[Blaisorblade]

@lrytz I thought the goal this issue requires fragmenting equality into legacy and non-legacy mode and giving choices to users. So why should annotations not be composable? My proposal is simply that
@closedAdt trait MyDataSet could expand to @equalityClass sealed trait MyDataSet, and @case class Something(...) extends MyDataSet could expand to final case class Something(...) extends MyDataSet.
And as long as different annotations stick to the same API, there's no reason the generated code should be incompatible.

I'm not talking about splitting case into composable blocks, unlike in that link. That does have issues for all metaprograms that do something special for case classes — both the compiler and other macros like shapeless, that is, everything that actually makes sense for algebraic data types, rather than their case-class-based encoding.

Then, there's already a split between builtin equality and Haskell-style Eq, as in Scalaz, cats, etc.; the latter is not backwards compatible and would benefit from some form of typeclass specialization, but appears otherwise more elegant and simpler. You only need support for generating instances, either from the compiler or from macros. This suggests that a clean equality implementation need not compiler support.

Finally: if a solution if is flexible enough and clearly right, it doesn't hurt to make it a builtin.
Otherwise, building it in goes at the expense of alternatives.

Regarding Scala's approach in general, I'd recommend https://www.youtube.com/watch?v=_ahvzDzKdB0 (you can also google "Growing a language Guy Steele" to find a transcript).

[odersky]

@Blaisorblade I am not too concerned about migration away from eqAny. Maybe we don't have to drop eqAny at all. There more classes are annotated with @equalityClass (which is in my so far limited experience very easy and safe to do as long as eqAny is around), the smaller the partition of unannotated classes becomes anyway. So that means that most errors will be caught even if we keep eqAny.

[odersky]

I moved eqAny to Predef (in the proposal and in the PR).

[japgolly]

IMO there's still a big issue in this proposal that seems to have gone unnoticed, in that we're still relying on a dev's one-time, trusted declaration of equality. As we all know, over time and after refactorings, past declarations can easily become invalid. Consider:

// In file A we have:
@equalityClass case class A (number: Int, name: String)

// Then in another file, much further down the dependency graph, we have
@equalityClass case class B (allOfMyStuff: List[A], number: Int)

All looks good in the above and then a year later there's a refactoring to A such that it becomes:

// New and improved A!
// Universal equality no longer holds here.
trait A {
  val number: Int
  def name(): String
}

whilst, unbeknownst to the refactorer, the following code has now become incorrect and escaped their notice.

// ↓ No longer true! Oh noes.
@equalityClass case class B (allOfMyStuff: List[A], number: Int)

I recently open-sourced a small library with a similar objective to this proposal, called UnivEq. I solved this by having a macro to derive an instance after inspecting the fields of a case class. If all the case class's fields have proven or trusted universal equality, then all is well, else there is a compiler error that informs the user about the bereft fields.

In code, it looks like this:

case class B (allOfMyStuff: List[A], number: Int)
object B {
  implicit def univEq = UnivEq.derive[B]
}

which compiles in the first case above, and fails compilation after the refactoring to A.

I think it critical to include some kind of similar ability in this proposal, or else the refactoring fear remains.

[odersky]

// ↓ No longer true! Oh noes.
@equalityClass case class B (allOfMyStuff: List[A], number: Int)

In what sense is this no longer true? B's can be compared as before.

[Blaisorblade]

First, I generally agree with the concern that Eq instances can get out of sync with the equals implementation, more than Eq which at least must implement equality. But we know that is incompatible.

Second, going to @japgolly's comment, I guess his UnivEq does not do the same thing as this proposal.
In the example, the issue is that after the change A has default (reference) equality, which is a concern. But it's a different one.

@japgolly's UnivEq[A] does I think something slightly different — it proves that A.equals "correctly defines the equality", according to its docs, while @equalityClass simply declares that A shouldn't be comparable with unrelated types (assuming no further Eq instance). There might be some overlap between the proposals, but I can't be sure without clearer docs for UnivEq.

[japgolly]

@odersky

In what sense is this no longer true? B's can be compared as before.

Say you start with this:

scala> case class A(i: Int)
defined class A

scala> case class B(as: List[A])
defined class B

scala> A(1) == A(1)
res0: Boolean = true

scala> B(A(1) :: Nil) == B(A(1) :: Nil)
res1: Boolean = true

And then after a refactoring, A changes

scala> class A(val i: Int)
defined class A

scala> case class B(as: List[A])
defined class B

scala> new A(1) == new A(1)
<console>:13: warning: comparing a fresh object using `==' will always yield false
       new A(1) == new A(1)
                ^
res0: Boolean = false

scala> B(new A(1) :: Nil) == B(new A(1) :: Nil)
res1: Boolean = false

Here you can can see here that B no longer has meaningful == because A now falls back to reference equality. (Although if that were desired, then one could leave the @equalityClass annotation in place after the refactoring.)

If I refactored a class and, for whatever reason, had to remove it's equality, then it's very important for me to know that any other classes whose equality depends on the equality just removed, should also be flagged to me. Else I could find out in production that "hey something's wrong, oh it turns out that @equalityClass needed to be removed on B but we missed it cos the codebase is huge.".

@Blaisorblade np, I'll try to update my docs to make it clearer. The point of my library was that I need to know (and continue to know) that if I depend on ==, that it works, where "works" means either I've axiomatically declared it so (like this proposal), or that it was possible to automatically derive a typeclass instance according to rules, rules such as ensuring that a case class's dependencies (fields) all support meaningful == , because that is what case class generated equality depends on.

If you're correct in:

@equalityClass simply declares that A shouldn't be comparable with unrelated types

then IMO this proposal does way to little to be useful, because it's just too easy to introduce incorrectness after refactorings, or even when you're first creating classes. Maybe it's a philosophical difference in that I'm not just interested in ensuring that == only works with matching types, it's critically important to me that when I use ==, it does what I expect it to and won't just always return false which can happen quite easily in a large code graph.

[Blaisorblade]

Now that we know better there are two different things in discussion, we can compare them — and I like @japgolly's idea. It also resembles the behavior of Haskell's deriving Eq: a type can be compared only if all members can be compared — where however "compared" excludes reference equality by default.

But I haven't worked out & checked all the details — I haven't even re-read the proposal in full to check if this change would fit in and preserve all properties, though I guess it should.

[mdedetrich]

Well it should also be noted that Scala does have a concept of reference equality as well as structural equality, unlike Haskell which only really deals with structural equality.

[odersky]

Here you can can see here that B no longer has meaningful == because A now falls back to reference equality. (Although if that were desired, then one could leave the @equalityClass annotation in place after the refactoring.)

This is in fact desired, and assumed. The proposal here and UnivEq are different in his key aspect. So the discussion does not make much sense in the context of this proposal.

[odersky]

The described implementation has been merged.

[Atry]

Is it possible to make @equalityClass annotation work for =:= as well?

If it is possible, we can proof equality at compile time, like:

val x1: Some[42] = Some(42)
val x2: Some[42] = Some(42)

implicitly[x1.type =:= x2.type] // It should compile with the help of `@equalityClass`

[Blaisorblade]

@Atry You seem to imply that x1.type and x2.type are equal types, though =:= can't detect this. In fact, they are nowadays different types: the only member of x1.type is the object x1 (in particular, x1.type is not a way to get Some[42]). And changing type equality without breaking type soundness is far from trivial.

[Atry]

The current .type behavior breaks referential transparency

[nafg]

How?

…

On Mon, Jul 10, 2017 at 11:39 AM 杨博 (Yang Bo) ***@***.***> wrote: The current .type behavior breaks referential transparency — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1247 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAGAUByS9sER-swgOTU_bU2i3NurMp2Nks5sMkWlgaJpZM4IZY7K> .

[Atry]

Given `val x: Some[42] = Some[42](42)`, `x`, as a case class, it should be able to replace to its definition without changing behavior. It's true for expressions. However, not true for types: `implicitly[Some[42] =:= Some[42]] // compiles` `implicitly[x.type =:= Some[42]] // does not compile` 2017-07-11 8:23 GMT+08:00 nafg <notifications@github.com>:

…

How? On Mon, Jul 10, 2017 at 11:39 AM 杨博 (Yang Bo) ***@***.***> wrote: > The current .type behavior breaks referential transparency > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#1247 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AAGAUByS9sER-swgOTU_ bU2i3NurMp2Nks5sMkWlgaJpZM4IZY7K> > . > — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1247 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAktus8ljgyxweIEmPAMHtYXmbGcO1fKks5sMsCHgaJpZM4IZY7K> .

-- 杨博 (Yang Bo)

[Atry]

The case class behavior is different from binding of literal types: val y: 4 = 4 implicitly[y.type =:= 4] // compiles 2017-07-11 8:54 GMT+08:00 杨博 <pop.atry@gmail.com>:

…

Given `val x: Some[42] = Some[42](42)`, `x`, as a case class, it should be able to replace to its definition without changing behavior. It's true for expressions. However, not true for types: `implicitly[Some[42] =:= Some[42]] // compiles` `implicitly[x.type =:= Some[42]] // does not compile` 2017-07-11 8:23 GMT+08:00 nafg ***@***.***>: > How? > > On Mon, Jul 10, 2017 at 11:39 AM 杨博 (Yang Bo) ***@***.***> > wrote: > > > The current .type behavior breaks referential transparency > > > > — > > You are receiving this because you were mentioned. > > Reply to this email directly, view it on GitHub > > <#1247 (comment)>, > > or mute the thread > > <https://github.com/notifications/unsubscribe-auth/ > AAGAUByS9sER-swgOTU_bU2i3NurMp2Nks5sMkWlgaJpZM4IZY7K> > > > . > > > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#1247 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AAktus8ljgyxweIEmPAMHtYXmbGcO1fKks5sMsCHgaJpZM4IZY7K> > . > -- 杨博 (Yang Bo)

-- 杨博 (Yang Bo)

[nafg]

That's because XXX.type is defined to be a singleton type (a type that is inhabited by exactly one value) and the literal type 4 is a singleton type. So they are the identical type: the singleton type defined to be inhabited only by 4. However Some[42] is not a singleton type at all. There can be multiple values of type Some[42]. Given val x, x.type is inhabited only by the value x. So they are not the same type. They are different types and their inhabitants differ. Honestly I've never heard of type-level referential transparency anyway (although as I explained it's a moot point here). Anyway I'm no compiler hacker or type theorist so I could be wrong, but that's how I see it and why your objection doesn't bother me. On Mon, Jul 10, 2017 at 8:58 PM 杨博 (Yang Bo) <notifications@github.com> wrote:

…

The case class behavior is different from binding of literal types: val y: 4 = 4 implicitly[y.type =:= 4] // compiles 2017-07-11 8:54 GMT+08:00 杨博 ***@***.***>: > Given `val x: Some[42] = Some[42](42)`, > `x`, as a case class, it should be able to replace to its definition > without changing behavior. It's true for expressions. However, not true for > types: > > `implicitly[Some[42] =:= Some[42]] // compiles` > > > `implicitly[x.type =:= Some[42]] // does not compile` > > > > > 2017-07-11 8:23 GMT+08:00 nafg ***@***.***>: > >> How? >> >> On Mon, Jul 10, 2017 at 11:39 AM 杨博 (Yang Bo) ***@***.*** > >> wrote: >> >> > The current .type behavior breaks referential transparency >> > >> > — >> > You are receiving this because you were mentioned. >> > Reply to this email directly, view it on GitHub >> > <#1247 (comment) >, >> > or mute the thread >> > <https://github.com/notifications/unsubscribe-auth/ >> AAGAUByS9sER-swgOTU_bU2i3NurMp2Nks5sMkWlgaJpZM4IZY7K> >> >> > . >> > >> >> — >> You are receiving this because you were mentioned. >> Reply to this email directly, view it on GitHub >> <#1247 (comment)>, >> or mute the thread >> < https://github.com/notifications/unsubscribe-auth/AAktus8ljgyxweIEmPAMHtYXmbGcO1fKks5sMsCHgaJpZM4IZY7K > >> . >> > > > > -- > 杨博 (Yang Bo) > -- 杨博 (Yang Bo) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1247 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAGAUHgjVBAefra8zq3q7WFBKh37rhYOks5sMsi0gaJpZM4IZY7K> .

[odersky]

Note: I edited the definition of "lifting" by adding the clause:

"and that drops all refinements in covariant positions"

Here's a scenario where this is important:

 class Designator { type ThisName: Name }
 class Name extends Designator

 implicit def eqName: Eq[Name, Name]

In the dotc compiler itelf, we want to compare a

`Designator { type ThisName = TypeName }` with a `Name`

Without the change, this fails as Designator { type ThisName = TypeName } is not a supertype of Name and Designator and Name are not in the same equality class (which is a good thing!). But of course there are valid comparisons because Name could be a TypeName. By ignoring refinements in lifting we make this code compile.

We might need further tweaks in the future to what exactly lifting should be.

[Atry]

However Some[42] is not a singleton type at all. There can be multiple
values of type Some[42].

It's the case without @equalityClass. If @equalityClass works at type-level, then it should be able to make singleton type "widen" to a base type, like it always make the comparison on the base type .