<p>I'm wondering how could pitfall #4 in this link be avoided without runtime type (or class ID etc.) checks: <a href="https://www.artima.com/articles/how-to-write-an-equality-method-in-java" rel="noreferrer">https://www.artima.com/articles/how-to-write-an-equality-method-in-java</a>.</p>
<p>From a language designer's point of view, the problem is the following:</p>
<p>We want to add an <code>equals</code> (or <code>operator ==</code>) method in a system with subtyping. It should be possible for users to implement it for their types.</p>
<p>The method should have the usual properties:</p>
<ul>
<li>Reflexivity: <code>a == a</code> should be <code>true</code>, for any <code>a</code></li>
<li>Symmetry: if <code>a == b</code> is <code>true</code>, then <code>b == a</code> should be <code>true</code>.</li>
<li>Transitivity: if <code>a == b</code> is <code>true</code> and <code>b == c</code> is <code>true</code>, <code>a == c</code> should be <code>true</code>.</li>
</ul>
<p>We have a few options on where and how to add the method:</p>
<ol>
<li>We can do as some of the mainstream OOP languages do and add a <code>bool equals(Object other)</code> to the <code>Object</code> type. (where <code>Object</code> is the top type)</li>
<li>We can have a separate class/abstract class/interface: <code>abstract class Equals { bool equals(Self other); }</code>.</li>
<li>We can have something like a trait or typeclass: <code>trait Equals { bool equals(Self other) }</code>.</li>
</ol>
<p>Regardless of how and where we add this, user-written implementations will inevitably break symmetry, and probably transitivity as well.</p>
<p>As an example, let's consider the same example as in the link:</p>
<pre><code>class Point {
    int x;
    int y;
}

class ColoredPoint extends Point {
    Color color;
}
</code></pre>
<p>Regardless of how we implement equality on these types, it will be possible to call <code>point == coloredPoint</code> (where <code>point : Point</code> and <code>coloredPoint : ColoredPoint</code>), which will compare <code>x</code> and <code>y</code> and return <code>true</code> in some cases, but <code>coloredPoint == point</code> will always return <code>false</code>.</p>
<p>The ways shown in the post to fix this require class ID or runtime type checks (like <code>instanceof</code>), and even then they break substitutability (e.g. a value of <code>ColoredPoint</code> cannot be passed where <code>Point</code> is expected as it behaves differently).</p>
<p>So it seems like something fundamental needs to change, either how we model equality, or maybe some aspects of the language.</p>
<p>Is avoiding subtyping the only option? Can I have an alternative equality relation (maybe relaxing some of the properties without creating potential for surprising behavior) that works in data structures like hash maps?</p>

<language-design><types><type-systems><subtypes>
What are some options for adding a sound equality operator (or avoiding it) in a type system with subtyping?
CC BY-SA 4.0
2024-10-22T16:29:05.050Z
Something which could be interesting: keep subtyping, but remove the [Liskov Substitution Principle](https://en.wikipedia.org/wiki/Liskov_substitution_principle). A type may either be "open" (allows subtypes to be instances) or "closed" (instances are guaranteed to be the exact type, i.e. never a subtype). Then equality methods only take a "closed" type as a parameter. I wonder if any languages have done something like this.
tarzh
CC BY-SA 4.0
2024-10-22T18:26:40.563Z
This whole thing is a peeve of mine and a huge mess. I wish there were an obviously correct way to do it but I don't think there's a perfect solution.
Eric Lippert
CC BY-SA 4.0
2024-10-22T21:29:25.613Z
To me, a major downside of adding the `equals` method to object is that it forces reference equality to be the default implementation. You then have an `equals` method that sometimes is value equality and sometimes is reference equality. I think those ought to be distinct operations.
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-23T13:07:39.933Z
You can enforce symmetry by defining `==` as `a.equals(b) && b.equals(a)` - ie. have the class define only the "is equal to me from my point of view" part of equality and require the two implementations to agree on that. Whether it's actually useful...
Maciej Stachowski
CC BY-SA 4.0
2024-10-25T01:20:11.927Z
This is one of the things you can solve by preferring composition over inheritence.  If you can force a `ColoredPoint` to be a class that Holds a `Point` and a `Color` instead of inheriting, then you can also make sure that a user is always explicitly comparing either only the `Point` or the `Point + Color`.  Such a language could get some of the benefits of inheritance by allowing a "downcast" via specifying a field or property to take it's place.  Then a `(Point)coloredPoint` would return the `Point` field.
Turksarama
CC BY-SA 4.0
2024-10-25T19:13:32.427Z
@tarzh: Technically Rust does something like that by [prohibiting the use of `Self` or generics in dynamically dispatched methods](https://doc.rust-lang.org/reference/items/traits.html#object-safety), effectively meaning that F-bounded polymorphism cannot be combined with runtime polymorphism. You *can* write e.g. `impl PartialEq for &dyn Foo{...}`, but then you don't have dynamic dispatch, you just have one implementation that statically applies to all instances of `&dyn Foo` regardless of their runtime type.
Kevin
CC BY-SA 4.0
2024-12-19T20:43:37.310Z
@JeffWalkerCodeRanger: I'd favor having two different kinds of equality, but I'd phrase them as "The object identified by reference X is and always will be semantically equivalent to the one identified by reference Y" and "The state of the object identified by reference X is the same as that of the object referred to by Y, and will remain so if no reference to either is exposed to anything that might modify it".  For mutable types, the first comparison would only be true for objects that were reference equal, but immutable types could define perpetual equivalence more broadly.
supercat
<p>I suggest make equal relation completely separate concept. Original method have unavoidable problem: unclear semantics. What does it mean to compare object to another? It is impossible to answer this question in general. Because of that you can always be surprised by results.</p>
<p>And since semantic is unclear chances to be surprised increases if you work with third party code. One popular library wasn't unable to provide symmetric implementation (I'm looking at you <code>appache.commons.lang</code>).</p>
<p>Instead of <code>equals(Object)</code> method use <code>static</code> method <code>boolean equals(TypeFoo, TypeFoo)</code> for each type you want to compare.</p>
<p>If you have <code>TypeBar</code> inherited from <code>TypeBar</code> you just get another method.</p>
<p>If you have some algorithm that requires checking equality relation just parametrize it with <code>interface EqualityRelation&lt;T&gt;{ boolean equal(T, T);}</code> and pass relation you want to use.</p>
<p>No surprises here. You always explicitly tell which relation you want. You can have as many relation between same type as you want. Want to use color and x coordinate of your <code>ColoredPoint</code>? No problem: just define new relation, it is just a method.</p>

CC BY-SA 4.0
2024-10-22T17:23:50.773Z
2024-10-22T17:30:27.830Z
2024-10-22T17:30:27.830Z
talex
<p>A fundamental problem is that the concepts of the world do not neatly organise into fixed categorical hierarchies, where at the top sits a general concept and everything beneath is a specialisation.</p>
<p>Ironically a similar piece of learning about hierarchies was incorporated into Codd's Relational Algebra model as long ago as 1970, where the perceived hierarchies between tables are only encoded transiently into specific queries (not encoded into the fixed schema and enforced upon all queries), yet the insight that hierarchies tend to be contextual and dependent on purpose doesn't seem to have percolated more widely.</p>
<p>Sometimes there are schemes of concepts that are explicitly <em>designed</em> to be a hierarchy.</p>
<p>But information about a Point and information about a Color do not seem to be an example - as bedfellows they're completely disjoint conceptually.</p>
<p>There is equally no master algorithm that is capable of comparing two pieces of arbitrary data and declaring their equivalence or not for all purposes in the universe and for all time. Equality, too, is contextual like hierarchies are.</p>
<p>A Point and a ColoredPoint might be equal in some contexts where the X,Y information is all that matters, and in other contexts not.</p>
<p>This is traditionally (outside OOP) why data is kept separate from algorithms that operate upon it, because the choice of algorithm to apply doesn't always depend just on the data, but on the specific usage of the data and the context and purpose of processing it.</p>
<p>My advice would be to simply accept that subtyping is not well-suited to your use here.</p>

CC BY-SA 4.0
2024-10-23T13:32:53.857Z
2024-10-23T13:32:53.857Z
Steve
CC BY-SA 4.0
2024-10-24T14:28:23.607Z
You advice makes sense, but then the problem becomes: how to design collection types like hash maps and sets that require comparing keys for equality. One option is, as mentioned by two other responses here, to pass the equality function as you construct such collections. Are there other options? Perhaps this should be discussed in a separate thread..
osa1
CC BY-SA 4.0
2024-10-24T15:02:37.060Z
@osa1, as well as passing a comparison function at construction time, ultimately you could just design the entire collection bespoke to incorporate the relevant comparison function in a fixed way, or you could fall back on using plain arrays and separate insertion/retrieval methods that work on the array and enforce/employ the desired constraints as part of their workings. It isn't always necessary, or desirable, to attach the algorithms directly to the data.
Steve
<p>One way of dealing with this I thought of inspired by a paper I read a few years ago [1] is to have the equality method depend on the type the values are being compared at, not just the values by themselves.</p>
<p>So you have something like (using equalities that compare the the coordinates for <code>Points</code> and the coordinates and the colours for <code>ColoredPoints</code>)</p>
<pre><code>Point p = Point(3, 7)
ColoredPoint c1 = ColoredPoint(3, 7, Red)
ColoredPoint c2 = ColoredPoint(3, 7, Blue)


p.equals[Point](p)          // true
p.equals[Point](c1)         // true
p.equals[ColoredPoint](c1)  // Type Error: p not ColoredPoint
c1.equals[ColoredPoint](c2) // false
c1.equals[Point](c2)        // true
</code></pre>
<p>The rules for the equality methods should require each one to be reflexive, transitive and symmetric. While I'm unsure of the necessity of it, it seems like a good idea to also require that if two values are equal at a subtype they should also be equal at a supertype.</p>
<hr />
<p>[1] Florian Rabe, A Language with Type-Dependent Equality. <a href="https://kwarc.info/people/frabe/Research/rabe_tde_21.pdf" rel="nofollow noreferrer">https://kwarc.info/people/frabe/Research/rabe_tde_21.pdf</a></p>

CC BY-SA 4.0
2024-10-24T06:48:27.987Z
2024-10-24T06:55:10.423Z
2024-10-24T06:55:10.423Z
Potato44
CC BY-SA 4.0
2024-10-24T14:45:53.727Z
Interesting idea. This seems similar to passing around a comparison object/function like some of the other responses suggest. `equals[Point]` looks similar to static function `bool pointEquals(Point p1, Point p2)`.
osa1
<p>In chapter 3, item #10 of <em>Effective Java</em>, 3rd ed., Josh Bloch states (correctly):</p>
<blockquote>
<p><strong>There is no way to extend an instantiable class and add a value component while preserving the <em>equals</em> contract</strong>, unless you're willing to forgo the benefits of object-oriented abstraction.</p>
</blockquote>
<p>(p. 42 in the 3rd edition, other editions may vary; highlight from the original text)</p>
<p>I always found this to be one of the most fundamental statements about Java (and, by extension, other languages that support a similar <em>equals</em> contract), but it is a frequently ignored fact and unfortunately the source of many, many bugs.</p>
<p>So, the short answer is &quot;You can't have it all&quot;, but the sentence indirectly also lists your options for finding a compromise:</p>
<ol>
<li>Not &quot;<em>extend an instantiable class</em>&quot; -- by not allowing extension you can keep your equality relationship sound. This is what Java does by declaring many classes like <code>Integer</code>, <code>String</code>, etc. as <code>final</code>.</li>
<li>Not &quot;<em>add a value component</em>&quot; -- as long as there is no additional field that needs to factor into the equality you can still extend and implement a base type. This is why <code>List</code> objects still follow the <code>equals</code> contract in Java, and an <code>ArrayList</code> can be compared to a <code>LinkedList</code> (and will be considered equal if both lists represent the same sequence of objects). I am not aware of any programming language that allows to enforce a &quot;do not add a value component&quot; rule. Java definitely does not have such a feature, which is why declaring a class <code>final</code> is your best bet.</li>
<li>Not &quot;<em>preserving the equals contract</em>&quot; -- if you need to be able to extend a type and add value components you can always loosen or redefine what &quot;equal&quot; means. This is tricky for languages like Java which assume that every object follows the contract. Even if you are not constrained by this, coming up with alternative semantics that actually work will often be difficult.</li>
<li>Or &quot;<em>forgo the benefits of object-oriented abstraction</em>&quot; -- if you are OK with violating the LSP, you can still have 1, 2, and 3, but the LSP is there for a very good reason, and things will derail very quickly without it.</li>
</ol>
<p>Personally, I always found option #2 the most interesting one to explore. Having a language feature that says &quot;you can extend this class but you can't add any value component&quot; and actually enforces this property would go a long way in this equality dilemma.</p>

CC BY-SA 4.0
2024-11-06T23:16:17.900Z
2024-11-06T23:16:17.900Z
raner
CC BY-SA 4.0
2024-12-20T19:56:19.743Z
One thing I've thought could be useful in a GC-managed language would be a family of classes with a private `telecopingEquality` field which, if set to a non-null value, would invite the GC to at its leisure replace any references to a the object where the field was non-null with references to the target.  Classes couldn't set the field directly, but would have a method identifying an object with which they should be considered interchangeable, and a method of asking for the an object equivalent to any given object.  Something like a string comparison that finds that two strings are equal...
supercat
CC BY-SA 4.0
2024-12-20T19:57:58.207Z
...could then let the GC know that the two objects should be equivalent, allowing them to be merged.  Such a feature would require that types uphold a concept of immutable equality regardless of whether the language "enforced" it directly, since types that behaved in contrary fashion would behave rather oddly as a consequence.
supercat
<p>One possible way to deal with this as a language designer is to add <a href="https://en.wikipedia.org/wiki/Multiple_dispatch" rel="nofollow noreferrer">multimethods aka multiple dispatch</a>. This allows a &quot;method&quot; to be dynamically dispatched on the type of parameters, not just on <code>this</code>/<code>self</code>.</p>
<p>In a statically typed language, if the <code>==</code> operation is a multimethod then the compiler can statically enforce that the equality of every pair of subtypes of the type that declares the method must be covered. In pseudocode, this might be something like:</p>
<pre class="lang-csharp prettyprint-override"><code>class Point {
    int x;
    int y;
}

// Declare a multimethod operator that works on points and its subclasses
// The `multi` keyword makes this dynamically dispatch on the type of p1 and p2
// Note: because of multiple dispatch, this will be called only when the two parameters are `Point` and not for any subtypes.
multi bool operator ==(Point p1, Point p2) =&gt; p1.x == p2.x &amp;&amp; p1.y == p2.y;

class ColoredPoint: Point {
    Color color;
}

// Since ColoredPoint is declared, you must now cover three more cases
multi bool operator ==(ColoredPoint p1, Point p2) =&gt; false;
multi bool operator ==(Point p1, ColoredPoint p2) =&gt; false;
multi bool operator ==(ColoredPointp1, ColoredPointp2) =&gt; ...;
</code></pre>
<p>Here the compiler will emit an error if any of the three cases are not covered. There are various ways to reduce the burden of this on developers. For example, a <code>symmetric</code> keyword as in JAI could allow one method to cover both <code>(ColoredPoint, Point)</code> and <code>(Point, ColoredPoint)</code>. You can also provide ways of syntax allowing a method implementation to handle any type in a specific parameter (e.g. <code>* p2</code>) or any subtype of a specific type in a parameter (e.g. <code>* &lt;: Point p2</code>).</p>
<p><strong>EDIT:</strong> Alternative Syntax</p>
<p>Some people found the above syntax confusing. Here is another syntax that might be clearer. In this syntax <code>#T</code> means exactly the type <code>T</code> and not a subtype.</p>
<pre class="lang-csharp prettyprint-override"><code>class Point {
    int x;
    int y;
}

// Declare a multimethod operator that works on points and its subclasses
// The `multi` keyword makes this dynamically dispatch on the type of p1 and p2
abstract multi operator ==(Point p1, Point p2);

// Note: because of multiple dispatch and exact types, this will be called only when the two parameters are both `Point` and not for any subtypes.
multi bool operator ==(#Point p1, #Point p2) =&gt; p1.x == p2.x &amp;&amp; p1.y == p2.y;

class ColoredPoint: Point {
    Color color;
}

// Since ColoredPoint is declared, you must now cover three more cases
multi bool operator ==(#ColoredPoint p1, #Point p2) =&gt; false;
multi bool operator ==(#Point p1, #ColoredPoint p2) =&gt; false;
multi bool operator ==(#ColoredPointp1, #ColoredPointp2) =&gt; ...;
<span class="math-container">```</span>
</code></pre>

CC BY-SA 4.0
2024-10-22T21:47:40.237Z
2024-10-22T22:45:03.447Z
2024-10-22T22:45:03.447Z
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-22T21:55:11.240Z
Doesn't the first declaration, `==(Point p1, Point p2)`, already cover every pair of types, and the others are just overrides?
kaya3
CC BY-SA 4.0
2024-10-22T22:03:58.637Z
"the compiler will statically enforce that the equality of every pair of types must be covered" This sounds excessive. Most pairs of types aren’t meaningful to compare (or trivially unequal if one insists) yet there are a lot of them.
MisterMiyagi
CC BY-SA 4.0
2024-10-22T22:24:50.950Z
No @kaya3, `==(Point p1, Point p2)` is not considered to cover every pair of types in my pseudocode because it should be called only when both parameters are `Point` and not subtypes to satisfy the multiple dispatch. Don't think of these as static overloads or simple overrides. (I've added a comment to try to clarify).
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-22T22:26:44.793Z
@MisterMiyagi I've clarified that it is every pair of types that are a subtype of the base type. So in this example, every pair of subtypes of type `Point` must somehow be covered.
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-22T22:30:24.853Z
@JeffWalkerCodeRanger Well, those can still be a lot. But more critically, in languages that have a common base type (think `Object` in Java or Python) or expect equality to be universal these are still all types.
MisterMiyagi
CC BY-SA 4.0
2024-10-22T22:31:20.180Z
Yes, this approach does not work well for a language with universal equality.
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-22T22:33:18.007Z
So if I understand correctly, a multimethod defined for a parameter of type `T` does not work on an argument of type `S` where `S < T`. Is that not a clear violation of the Liskov substitution principle?
kaya3
CC BY-SA 4.0
2024-10-22T22:42:19.060Z
Different languages handle multimethods differently. I chose a particular handling that would force safe equality. Some languages do allow a multimethod to match all subtypes of its parameters. Some languages have a way to do what I have said. No, it doesn't violate Liskov substitution because of multiple dispatches. Think of it as being like a visitor pattern where you are required to implement every case. It is just saying the multimethod must be overriden for each type.
Jeff Walker Code Ranger
<p>The paper <a href="https://dl.acm.org/doi/10.1145/2888392" rel="noreferrer"><em><code>ThisType</code> for Object-Oriented Languages: From Theory to Practice</em> by Sukyoung Ryu</a> provides another option. Unfortunately, it comes with fairly complex additional language features. The paper gives a formal type theory for it but does a decent job explaining the language features in the context of a Java-like language in a way that makes sense even if you don't follow the type theory. I will try to summarize here.</p>
<p>Add a special type variable, <code>This</code>, to the language, which roughly means the runtime type of the current instance. The special variable <code>this</code> has type <code>This</code>. You can then define equality as <code>bool equals(This other)</code>. The compiler will only allow <code>equals</code> to be called when the types prove that the two instances have the same runtime type. To support that, they add the following features to the language:</p>
<ol>
<li>Exact Types: For a class <code>C</code>, the exact type <code>#C</code> is the type of instances of <code>C</code> and no subclasses. The exact type <code>#C</code> is a subtype of <code>C</code> but not vice versa.</li>
<li>Exact Type Parameterization: The type <code>C&lt;/X/&gt;</code> is &quot;the type of an
object that has a declared class type <code>C</code> and a runtime exact type <code>X</code>.&quot; The type <code>C&lt;/∼/&gt;</code> is a wildcard type similar to <code>?</code> in Java, except that the <code>~</code> must be an exact type. <em>In code, using <code>C</code> is equivalent to <code>C&lt;/~/&gt;</code></em>.</li>
<li>Exact Type Capture and Exact Type Inference: basically just that the compiler figures out the exact types whenever possible.</li>
<li>Named Wildcards: You can give the wildcards a name to indicate that two wildcards must be equal. For example, the method <code>int compare(Ordered&lt;/X/&gt; a, Ordered&lt;/X/&gt; b)</code> compares two instances of <code>Ordered</code> that have the same runtime type.</li>
<li>Virtual Constructors: A constructor that must be overridden and is virtual. This allows for a constructor that can return an instance of type <code>This</code>. This is useful for things like cloning and factories. (Swift has virtual constructors that return <code>Self</code>.)</li>
<li>Runtime Type Match: A control flow that determines if two instances have the same runtime type and uses flow typing. The strawman syntax they give is <code>classesmatch (x,y) { /* then-block */ ... } else { /* else-block */ ... }</code>. Within the then-block, the compiler knows that the runtime types of <code>x</code> and <code>y</code> are equal and would allow the call to <code>x.equals(y)</code> (assuming proper supertypes, etc.).</li>
</ol>
<p>In most cases, the developer does not need to use the new types and syntax. It is generally only necessary in parts of the code that declare or call methods taking a parameter of type <code>This</code>.</p>
<p>I'm not sure how often the runtime type check is needed. I think in many cases, it could be avoided, but they do give an example where it is needed. The example they give is inside of <code>int countEqualPairs(ArrayList&lt;Point&gt; list)</code> where the compiler doesn't know that all the <code>Point</code>s have the same runtime type (e.g., some might be <code>Point</code> and others <code>ColoredPoint</code>).</p>

CC BY-SA 4.0
2024-10-22T22:18:43.790Z
2024-10-22T23:06:56.933Z
2024-10-22T23:06:56.933Z
Jeff Walker Code Ranger
<blockquote>
<p>The ways shown in the post to fix this require class ID or runtime type checks (like <code>instanceof</code>), and even then they break substitutability (e.g. a value of <code>ColoredPoint</code> cannot be passed where <code>Point</code> is expected as it behaves differently).</p>
</blockquote>
<p>I think this is a misinterpretation. The linked article does provide sound implementations of <code>equals</code> for the two classes <code>Point</code> and <code>ColoredPoint</code>:</p>
<pre class="lang-java prettyprint-override"><code>class Point {
    // ...
    
    @Override public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof Point) {
            Point that = (Point) other;
            result = (this.getX() == that.getX() &amp;&amp; this.getY() == that.getY()
                    &amp;&amp; this.getClass().equals(that.getClass()));
        }
        return result;
    }
}

class ColoredPoint extends Point {
    // ...
    
    @Override public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof ColoredPoint) {
            ColoredPoint that = (ColoredPoint) other;
            result = (this.color.equals(that.color) &amp;&amp; super.equals(that));
        }
        return result;
    }
}
</code></pre>
<p>The linked article calls this &quot;technically valid, but unsatisfying&quot;. But it indeed defines an equivalence relation, so the implementation is sound. And I would argue that it is not really &quot;unsatisfying&quot;.</p>
<p>To be clear, this implementation <em>does not</em> break substitutability ─ yes, <code>new ColoredPoint(1, 2, &quot;red&quot;)</code> behaves differently to <code>new Point(1, 2)</code> when using the <code>.equals()</code> method ─ but only because it is <em>supposed</em> to behave differently; they are equal to different things, so of course their <code>.equals()</code> methods give different answers. This doesn't violate substitutability any more than <em>any</em> subclass overriding <em>any</em> method, changing its behaviour, does. (That is, you're free to think this is a problem, and <a href="https://en.wikipedia.org/wiki/Circle%E2%80%93ellipse_problem" rel="noreferrer">it kind of is</a>, but then you must accept that inheritance itself is a problem.)</p>
<p>The only trouble with the above implementation is that it's not completely extensible: you cannot define a new subclass of <code>Point</code> such that <code>new MyPoint(1, 2).equals(new Point(1, 2))</code> is true without breaking symmetry. This is only a problem in a quite specific set of circumstances:</p>
<ul>
<li>Your language allows inheritance, particularly <em>open</em> inheritance such that first-party classes may be extended by third-party subclasses,</li>
<li>You want an equivalence relation which is extensible to third-party subclasses,</li>
<li>You want those third-party classes to be able to choose how they are related to first-party classes or other third-party classes.</li>
</ul>
<p>Even if the first two hold, the third is quite an unusual requirement, and (in my opinion) indicates a design problem in the user's code. The problem is that if Alice and Bob both extend this class, which of them gets to decide whether <code>new AlicePoint(1, 2)</code> is equal to <code>new BobPoint(1, 2)</code>?</p>
<p>Suppose Alice says that an <code>AlicePoint</code> equals any point with the same x, y coordinates, and Bob says a <code>BobPoint</code> only equals another <code>BobPoint</code>. Whose definition should win? Fundamentally, by promising this kind of extensibility to your users, the promise you make to Alice (that she can decide which objects hers are equal to) is incompatible with the promise you make to Bob (that he can decide the same for his objects). That is, the promise you want to make is inconsistent with itself.</p>
<p>The only way you can make an equivalence relation extensible, therefore, is by saying that two objects can only be equal if <em>both</em> classes are defined in such a way as to allow them to equal objects of the other class; i.e. both classes explicitly cooperate in order to have equal objects. Then it is up to the implementor of those two classes to ensure that they properly implement an equivalence relation. Then across module boundaries, <code>equals</code> necessarily returns <code>false</code>; and that's fine.</p>
<p>Note that this is a non-issue if your language only has closed inheritance (i.e. users can only extend their own classes). Closed inheritance still allows for extensibility, just through other means (e.g. composition, generics, callback functions, etc.).</p>

CC BY-SA 4.0
2024-10-22T16:24:22.147Z
2024-10-22T23:53:59.650Z
2024-10-22T23:53:59.650Z
kaya3
CC BY-SA 4.0
2024-10-22T22:36:12.050Z
An example of wanting a third-party class to choose how it relates to the other classes is for a proxy. The proxy may want to be treated as equal to one of the existing classes when its value is equal.
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-23T14:30:29.767Z
@JeffWalkerCodeRanger That still has the same fundamental problem that your proxy wants to decide what it's equal to, and other third-party classes may want to not be equal to your proxy. Such use cases can be handled soundly by composition rather than inheritance; use the newtype pattern to wrap objects, and then define equality for the wrapper type. If not all objects want to be proxied, make the newtype an enum between `Proxied(obj)` and `Transparent(obj)` where the `Transparent` case simply copies the wrapped object's behaviour without modifications.
kaya3
CC BY-SA 4.0
2024-10-23T14:32:26.630Z
If you like, you can go further and make the `Proxied` case only present in debug builds (e.g. if it's only used for tests), and the compiler should be smart enough to recognise that the wrapper has no effect at runtime in release builds.
kaya3
CC BY-SA 4.0
2024-12-19T20:47:15.673Z
@kaya3: It generally doesn't make sense to consider mutable objects of different types equivalent, but it might make sense for e.g. an `Immutable2dMatrix` whcih is square and has zeroes everyplace except the main diagonal to compare equal to an `ImmutableDiagonalMatrix` which only stores elements on the diagonal and has a `GetValueAt` method that returns 0 for all coordinates off the diagonal, if all of the numbers on the diagonal match.
supercat
CC BY-SA 4.0
2024-12-19T23:02:15.340Z
@supercat Sure, and you can do that soundly, if both classes cooperate. But cooperation requires a lot ─ particularly, for the relation to be transitive, then "class A cooperates with class B" must itself be a transitive relation. In other words, all of the cooperating classes need to agree on which classes they all cooperate with, and none may cooperate with any classes outside that set. I don't think you can achieve that in practice if cooperation is allowed between different modules with different authors.
kaya3
CC BY-SA 4.0
2024-12-19T23:06:14.123Z
The problem is like this: suppose classes A and B declare their cooperation with the semantics like you describe, but they also declare cooperation with classes C and D. And the authors of classes C and D have cooperated to ensure that *all* instances of C are equal to all instances of D. Now by the transitive property, all instances of A must equal all instances of B, contrary to their own declarations; or some instances of C must be unequal to some instances of D, contrary to their own declarations.
kaya3
CC BY-SA 4.0
2024-12-20T16:45:39.400Z
@kaya3: The base class contract would require that all subclasses have a defined criterion for equality which is globally applicable.  For something like an immutable matrix base class, two matrices would be equal if they have the same dimensions, and if every value GetElementAt() query would return the same values.  If a ZeroMatrix class knows that it will equal a DiagonalMatrixClass if everthing on the diagonal is zero, its equality check can avoid having to perform queries for all of the entries off the diagonal, but if there were some other variant of DiagonalMatrix it didn't know about...
supercat
CC BY-SA 4.0
2024-12-20T16:46:21.243Z
...equality testing would still work--it would just be slower because of the extra testing required.
supercat
CC BY-SA 4.0
2024-12-20T18:07:13.897Z
@supercat In that case, the base class fully defines what it means for subclass instances to be equal, and subclasses cannot override `equals` to choose what equality means for their own instances. That is not extensible in the way this question asks about.
kaya3
CC BY-SA 4.0
2024-12-20T19:46:59.753Z
@kaya3: Even thought the base class would define the *meaning* of `equals`, and no non-broken subclass could override `equals` in a manner that would return a different result from the base equality-check method, allowing subclasses to override the method with other implementations that yield the same semantics may greatly improve performance.  If code needs to compare a 16x16 ZeroMatrix and a 16x16 DiagonalMatrix, having a base-class `equals` method calling `GetValueAt(i,j)` for all combinations of `i` and `j` would result in 16 useful comparisons and 240 useless ones.  If the code for...
supercat
CC BY-SA 4.0
2024-12-20T19:48:32.097Z
...ZeroMatrix understands the internal representation of `DiagonalMatrix`, it could reduce the number of comparisons from 256 to 16, achieving the same behavior as the base class method but perhaps 90% faster.
supercat
CC BY-SA 4.0
2024-12-20T20:34:27.483Z
@supercat As I said, that is not extensible in the way this question asks about. It's also not clear how the language would be able to enforce that the subclasses don't change the meaning of the code. Either you get users to write proofs that their overridden methods are behaviour-equivalent to the original method, or you allow them to change the behaviour but trust that they won't. And this question is about soundness, and a language which lets users do unsound things but asks them to pinky-swear not to, is unsound.
kaya3
<h3>What's equality?</h3>
<p>I think the first fundamental problem is that equality is ill-defined, in the first place.</p>
<p>Yes, mathematics describe what properties an equivalence relationship should have. That's objective, great. The subjective part comes into play when one starts asking whether:</p>
<ul>
<li>Values should only be equivalent if all their properties are equivalent, or if the user is allowed to define a subset: &quot;cache&quot; fields are a legitimate case here.</li>
<li>Values should only be equivalent if their dynamic types are equivalent, or if they can be equivalent <em>across</em> types: lightweight wrappers, proxies, mimicry etc... have a legitimate case here.</li>
<li>Values should only be equivalent if they are structurally equivalent, or if they can be equivalent beyond structure: hash sets, etc... have a legitimate case here.</li>
</ul>
<p>The more freedom you allow your users -- and there are very good to allow them! -- the more difficult it becomes to double-check they're not making a mess.</p>
<h3>Fields</h3>
<p>The user should be able to pick which fields participate in the identity of the value, and which don't.</p>
<p>This means that, realistically speaking, the identity of the object is defined -- recursively -- by an order list of values.</p>
<p>Rather than ask the user to write the <em>code</em> for these values, it may be easier, instead, to ask the user to <em>enumerate</em> these values.</p>
<p>That is, the user writes:</p>
<pre><code>def key(self) -&gt; Generator[Object]:
    yield self.x
    yield self.y
    yield self.z
</code></pre>
<p>This is <strong>great</strong>, as immediately you get to:</p>
<ul>
<li>Be assured that the equality operation derived from this is <em>actually</em> an equivalence relationship.</li>
<li>Be assured that the equality operation uses the same set of fields as the hashing operation.</li>
</ul>
<p>Two birds with one stone. Aren't we living the dream?</p>
<p><em>Note: a generator, or lazily generated list, is crucial for performance here, at least for the performance of the not-equal case.</em></p>
<p><em>Note: a visitor method isn't as good, because it's hard to visit two objects in lock-steps.</em></p>
<p><em>Note: in Rust, <code>#[derive(Identity)]</code> is a completely different solution achieving the same goal. It doesn't work as well, however, for mixing types.</em></p>
<h3>Types</h3>
<p>The user should ideally be able to pick which types can be compared to each other.</p>
<p>It should be as simple as allowing the user to <em>declare</em> that. That is, for any two types, in <em>one</em> of the type &quot;modules&quot;, one should be able to declare something like:</p>
<pre><code>impl Eq[X] for Y
</code></pre>
<p>The runtime will then generate the necessary code for checking whether the types do compare equal, and from there it's just a matter of checking their key fields.</p>
<h3>Non-Structurals</h3>
<p>And then we have collections. Ideally, a set should be equal to another set iff both sets contain the same list of elements. No matter what their types are.</p>
<p>There's no way to make that work using our <code>Generator[Object]</code> type: the objects may simply NOT be listed in the same order depending on the underlying implementation.</p>
<p>For now, I cannot think of a better solution than allowing an <em>escape hatch</em>.</p>
<p>Since the <em>escape hatch</em> may be useful anyway for performance reasons, I would argue it's a fair thing to do. But it <em>is</em>, obviously, a bit of a cope out.</p>

CC BY-SA 4.0
2024-10-24T12:12:32.770Z
2024-10-24T12:12:32.770Z
Matthieu M.
CC BY-SA 4.0
2024-10-24T14:24:53.833Z
I don't understand what is the escape hatch you allow for collections. Do you have an example?
osa1
CC BY-SA 4.0
2024-10-24T14:39:18.187Z
@osa1: I was thinking of a _complete_ escape hatch, where the user manually implements the `equals` method instead of it being auto-generated by the compiler from the pieces provided (`Eq` impl & `key` method). In short, just giving up on attempting to enforce any guarantee about the soundness of the equality for this type.
Matthieu M.
<p><a href="https://en.wikipedia.org/wiki/Equivalence_relation" rel="nofollow noreferrer">EquivalenceRelations</a> should be their own class hierarchy and, if the type system is ∀- or λ-polymorph (i.e. offers generics or templates), it should take the base type as an argument.</p>
<blockquote>
<p>Is avoiding subtyping the only option?</p>
</blockquote>
<p>No. The best way is to offer an equals function yielding an EquivalenceRelation similar to Iterable/Iterator.</p>
<p>Also, EquivalenceRelations can exist in a Cohierarchy for the purpose of optimizing, however, the contract for overridden equals functions is in essence that a static upcast of this, i.e. using the super implementation instead, results in the same result for all values.</p>
<p>This restrictions does not really work in Java, because it would render <code>equals</code> an expensive duplicate of <code>==</code>.</p>
<p>Note: HashCode is related to equivalence relations, as hashes are essentially names for equivalence classes. As such, <a href="https://en.wikipedia.org/wiki/Hash_table#Hash_function" rel="nofollow noreferrer">HashedEquivalenceRelation</a> should be a subclass of EquivalenceRelation.</p>
<p>Note: The nature of the equals function yielding the natural EquivalenceRelation for a type would make it a good candidate for a class function for languages having them.</p>

CC BY-SA 4.0
2024-10-22T16:50:23.780Z
2024-10-23T18:57:17.587Z
2024-10-23T18:57:17.587Z
feldentm
CC BY-SA 4.0
2024-10-22T17:16:00.733Z
I don't know what `EquivalenceRelation` is. I've searched for it in two different search engines and asked a chat but, but no luck. Where can I learn more about it?

I also don't know what `∀-polymorph` and `λ-polymorph` are.. Any sources on these would be appreciated.
osa1
CC BY-SA 4.0
2024-10-23T19:37:49.660Z
Sorry for the confusion -- as Alexis says I know about the relation, I thought (because of the spelling) you are referring to a type in a programming language, and I was curious to see how it's used.
osa1
<p>In an interface specifies that implementations will behave like data holders whose content can only legitimately be changed by someone with holding a reference to the data holder, and that interface supports an equality-check operation which is supposed to report objects as equal if they could not be distinguished <em>only using members of the interface that don't try to write to them</em>, then it may be useful to have a quasi-private interface member (that could only be used by implementations of that equality method) which would first test whether it has any special knowledge that would help it quickly recognize itself as equal or unequal, and if not perform an item-wise equality check.  The primary equality method would then check whether the type implementing it has special knowledge about the other object, and chain to the quasi-private one of not, so the item-wise check would only be performed if neither type had any special knowledge.</p>
<p>If, for example, one had a &quot;square matrix of float&quot; interface, with implementations of &quot;arbitrary matrix&quot;, &quot;constant matrix&quot;, a &quot;diagonal matrix&quot; type, and &quot;identity matrix&quot;, equality-check logic for a diagonal matrix could compare itself quickly against another diagonal matrix by just examining the cells along the primary diagonal, against the identify matrix by checking whether all cells on its diagonal were equal to 1, and could check itself against the constant matrix by first checking whether either the size was less than 2 or constant was zero, and then checking whether any of its own members were non-zero.</p>
<p>BTW, I'd suggest that data-holder interfaces have subtypes for mutable and immutable data holders, as well as <code>asImmutable</code>, <code>asCopy</code>, <code>asMutable</code>, and <code>asNewMutable</code> methods (an immutable object would return itself for the first two, and a new mutable object for the others; a mutable object would return a new immutable object for the first, a new mutable copy for the second or fourth, and itself for the third).</p>

CC BY-SA 4.0
2024-10-24T20:03:46.323Z
2024-10-24T20:03:46.323Z
supercat
<blockquote>
<p>It should be possible for users to implement it for their types.</p>
</blockquote>
<p>No.</p>
<p>It should not be possible for users to implement it.</p>
<p>It would be possible to <em>annotate</em> that a user type should have the equality operator to be <em>derived</em> by the compiler, where it is possible to <em>guarantee</em> that the generated code is sound. This may not sound so easy (pun intended), but consider the alternative: to provide or <em>prove</em> soundness, it would be necessary to prove that the user provided code is sound, and this is a much harder problem.</p>
<blockquote>
<p>Regardless of how and where we add this, user-written implementations will inevitably break symmetry, and probably transitivity as well.</p>
</blockquote>
<p>So it's not up to the user to write any of this implementation.</p>
<p>The user can, instead, provide annotations that describe in that terms a type can be considered equals to other. For example, by annotating fields that should <em>not</em> be considered. And after that, the compiler than can test if all other fields have intrinsic or derived proofs/metadata indicating that equality operations are sound or not.</p>
<blockquote>
<p>Is avoiding subtyping the only option? Can I have an alternative equality relation (maybe relaxing some of the properties without creating potential for surprising behavior) that works in data structures like hash maps?</p>
</blockquote>
<p>This is a &quot;solved&quot; problem where data types cannot have cycles, or by separating types into reference types (compare only storage address) and simple value types, that compare by their leaf constituents. But this question is about two distinct types that may compare equals based on some relation between them.</p>
<p>Numeric relations are a prime example of this, where <code>1</code>, <code>1.0</code> and <code>1/1</code> may be (or should be) compared equals.</p>
<p>In the case of substitutability, again, I would argue this is a compiler job, not a programmers job. Object oriented substitutability is about substitution, after all. It's about changing some functionality and, at same time, by maintaining some signature compatibility. Where the change of functionality <em>also</em> breaks equality should be determined by the compilation process, that has a privileged view of all object internals, and could in principle calculate if all equivalence relation properties can be expected or not, between a type and a subtype.</p>
<p>Going for your example, if <code>Point</code> and <code>ColoredPoint</code> are two distinct types, without <em>any</em> relation, besides some name overlap, they should not compare equals, in any way whatsoever.</p>
<p>But if <code>ColoredPoint</code> is a specialization of <code>Point</code>, this is a relation that hints, but not grantees, equability. For example, if <code>ColoredPoint</code> adds a property or method, that cannot interfere in any way with <code>Point</code>s behavior, it is then possible to have a compiler generated equality operator for these two types.</p>
<p>But if <code>ColoredPoint</code> is implemented as:</p>
<pre><code>def ColoredPoint type, implements Point
    var X int { get =&gt; this.X + 1; set =&gt; this.X = value -2; }
    var Y int { get =&gt; this.Y * 2; set =&gt; this.Y = value / 60; }
    var Color string = &quot;red&quot;;
</code></pre>
<p>Then <code>ColoredPoint</code> can be used where any <code>Point</code> is expected <strong>except</strong> on any equality operation, because the compiler cannot prove these two types have the same behavior for the equality protocol.</p>
<hr />
<blockquote>
<p>without creating potential for surprising behavior) that works in data structures like hash maps?</p>
</blockquote>
<p>Should equals method/operator allocates, or should let it cause stack overflows in the normal case? This may sound an surprising <em>question</em>, but consider this example:</p>
<pre><code>var h1 = new HashSet&lt;object&gt;();
var h2 = new HashSet&lt;object&gt;();

h1.add(h2);
h2.add(h1);

console.log( h1 == h2 );
</code></pre>
<p>The convention of comparing reference types by their storage address, and leaf bitfield types by their bit contents obviously avoids <em>both</em> the surprising behaviors above, as is guaranteed that will at most allocate a few stack frames.</p>
<hr />
<p>The discussion above hints the solution may lurk on having the <strong>sound</strong> equality protocol being controlled entirely by the compiler and some special metadata.</p>
<p>Any two objects then may compare equals or not based on soundness proof generated by the compiler, in order to guarantee there is not any difference in behaviour, beyond any difference in public signatures.</p>
<p><strong>TL;DR:</strong> Only the compiler may generate <em>and use</em> a sound equal operator.</p>

CC BY-SA 4.0
2024-10-22T22:07:11.197Z
2024-10-22T23:28:28.367Z
2024-10-22T23:28:28.367Z
André L F S Bacci
CC BY-SA 4.0
2024-10-22T22:19:22.023Z
Is the compiler actually able to implement *meaningful* equality operators? It would seem that many types have degenerate information from more primitive types on which they are built without it impacting equality. For example, an array would normally compare equal taking into account ordering and duplicates. Yet, building a set type that uses an array as storage should not care about ordering.
MisterMiyagi
CC BY-SA 4.0
2024-10-22T22:27:10.937Z
@MisterMiyagi In principle it's possible to achieve this in a similar way that sorting functions avoid the problem of "what if the user provides an unsound comparator?" by accepting a key function instead of a comparator. For equality, a "key" function would be some kind of canonicalisation, such that the image of an equivalence class is a single point. Taking the "array-backed set" as an example, such a canonicalisation could be "make a sorted copy of the array". Then equality can be derived for the array-backed set type by comparing the canonicalised (i.e. sorted) arrays.
kaya3
CC BY-SA 4.0
2024-10-22T22:29:09.117Z
The downside is that now your set can only contain a type for which an ordering is defined, and comparing equality of two hashsets requires sorting in O(n log n) time with O(n) auxiliary space, whereas a user-defined "equals" method could use the hashes to test for equality in O(n) time and O(1) auxiliary space. The other downside is that some equivalence relations might not support an easy "canonicalisation" mapping.
kaya3
CC BY-SA 4.0
2024-10-22T22:35:08.547Z
@kaya3 I can think of a myriad of ways how a key function can break the desired features unless serious and expensive scaffolding is used. Simply being able to return a random key means the key would need to be immutable and cached for as long as the object lives, for example. (Which wouldn’t be useful for mutable types at least.)
MisterMiyagi
CC BY-SA 4.0
2024-10-22T22:37:00.093Z
@MisterMiyagi Well, at least it is easier for a language to verify that a type is immutable and a function is pure, than it is to verify that a comparator function defines a total order or an equivalence relation.
kaya3
CC BY-SA 4.0
2024-10-22T23:02:19.930Z
I don't think this is a viable answer. The update to address `HashSet` really misses the point. Consider the .NET `ImmutableHashSet<T>` class. As an immutable set, it should be compared based on the values, NOT by reference. It has a complex implementation based on an AVL tree. You can't just generate equality for it. You will want to hand-write equality to get good performance. It is a framework class, and very good performance in all cases matters a lot.
Jeff Walker Code Ranger
CC BY-SA 4.0
2024-10-22T23:20:41.653Z
An framework class is not "user code", in the usual sense of this question.
André L F S Bacci
CC BY-SA 4.0
2024-10-22T23:30:53.983Z
How should we distinguish between "user code" where defining the behaviour of `equals` should be forbidden, and "framework" code written by users, where it should be allowed?
kaya3
CC BY-SA 4.0
2024-10-23T02:33:49.540Z
By compiler analysis, as noted above. The framework quib is about how framework code is usually special in relation to normal use code. There a lot of `unsafe` in standard Rust lib.
André L F S Bacci
CC BY-SA 4.0
2024-10-23T05:08:15.040Z
@kaya3 Just being verifiable is pointless. Making all instances equal/unequal but to themselves achieves that. Comparisons must be meaningful, otherwise people just ignore them and roll their own comparison function/method/operator which then cannot be verified either.
MisterMiyagi
# What are some options for adding a sound equality operator (or avoiding it) in a type system with subtyping?
Posted by: username_0 on 2024-10-22
I'm wondering how could pitfall #4 in this link be avoided without runtime type (or class ID etc.) checks: https://www.artima.com/articles/how-to-write-an-equality-method-in-java.
From a language designer's point of view, the problem is the following:
We want to add an equals (or operator ==) method in a system with subtyping. It should be possible for users to implement it for their types.
The method should have the usual properties:

Reflexivity: a == a should be true, for any a
Symmetry: if a == b is true, then b == a should be true.
Transitivity: if a == b is true and b == c is true, a == c should be true.

We have a few options on where and how to add the method:

We can do as some of the mainstream OOP languages do and add a bool equals(Object other) to the Object type. (where Object is the top type)
We can have a separate class/abstract class/interface: abstract class Equals { bool equals(Self other); }.
We can have something like a trait or typeclass: trait Equals { bool equals(Self other) }.

Regardless of how and where we add this, user-written implementations will inevitably break symmetry, and probably transitivity as well.
As an example, let's consider the same example as in the link:
class Point {
    int x;
    int y;
}

class ColoredPoint extends Point {
    Color color;
}

Regardless of how we implement equality on these types, it will be possible to call point == coloredPoint (where point : Point and coloredPoint : ColoredPoint), which will compare x and y and return true in some cases, but coloredPoint == point will always return false.
The ways shown in the post to fix this require class ID or runtime type checks (like instanceof), and even then they break substitutability (e.g. a value of ColoredPoint cannot be passed where Point is expected as it behaves differently).
So it seems like something fundamental needs to change, either how we model equality, or maybe some aspects of the language.
Is avoiding subtyping the only option? Can I have an alternative equality relation (maybe relaxing some of the properties without creating potential for surprising behavior) that works in data structures like hash maps?
**Tags:** language-design types type-systems subtypes
> **Comments:**
> **username_1**: Something which could be interesting: keep subtyping, but remove the [Liskov Substitution Principle](https://en.wikipedia.org/wiki/Liskov_substitution_principle). A type may either be "open" (allows subtypes to be instances) or "closed" (instances are guaranteed to be the exact type, i.e. never a subtype). Then equality methods only take a "closed" type as a parameter. I wonder if any languages have done something like this.  
> **username_2**: This whole thing is a peeve of mine and a huge mess. I wish there were an obviously correct way to do it but I don't think there's a perfect solution.  
> **username_3**: To me, a major downside of adding the `equals` method to object is that it forces reference equality to be the default implementation. You then have an `equals` method that sometimes is value equality and sometimes is reference equality. I think those ought to be distinct operations.  
> **username_4**: You can enforce symmetry by defining `==` as `a.equals(b) && b.equals(a)` - ie. have the class define only the "is equal to me from my point of view" part of equality and require the two implementations to agree on that. Whether it's actually useful...  
> **username_5**: This is one of the things you can solve by preferring composition over inheritence.  If you can force a `ColoredPoint` to be a class that Holds a `Point` and a `Color` instead of inheriting, then you can also make sure that a user is always explicitly comparing either only the `Point` or the `Point + Color`.  Such a language could get some of the benefits of inheritance by allowing a "downcast" via specifying a field or property to take it's place.  Then a `(Point)coloredPoint` would return the `Point` field.  
> **username_6**: @tarzh: Technically Rust does something like that by [prohibiting the use of `Self` or generics in dynamically dispatched methods](https://doc.rust-lang.org/reference/items/traits.html#object-safety), effectively meaning that F-bounded polymorphism cannot be combined with runtime polymorphism. You *can* write e.g. `impl PartialEq for &dyn Foo{...}`, but then you don't have dynamic dispatch, you just have one implementation that statically applies to all instances of `&dyn Foo` regardless of their runtime type.  
> **username_7**: @JeffWalkerCodeRanger: I'd favor having two different kinds of equality, but I'd phrase them as "The object identified by reference X is and always will be semantically equivalent to the one identified by reference Y" and "The state of the object identified by reference X is the same as that of the object referred to by Y, and will remain so if no reference to either is exposed to anything that might modify it".  For mutable types, the first comparison would only be true for objects that were reference equal, but immutable types could define perpetual equivalence more broadly.  
---
## 11 answers
### Answer by username_3 on 2024-10-22. Score: 8
The paper [*`ThisType` for Object-Oriented Languages: From Theory to Practice* by Sukyoung Ryu](https://dl.acm.org/doi/10.1145/2888392) provides another option. Unfortunately, it comes with fairly complex additional language features. The paper gives a formal type theory for it but does a decent job explaining the language features in the context of a Java-like language in a way that makes sense even if you don't follow the type theory. I will try to summarize here.

Add a special type variable, `This`, to the language, which roughly means the runtime type of the current instance. The special variable `this` has type `This`. You can then define equality as `bool equals(This other)`. The compiler will only allow `equals` to be called when the types prove that the two instances have the same runtime type. To support that, they add the following features to the language:

1. Exact Types: For a class `C`, the exact type `#C` is the type of instances of `C` and no subclasses. The exact type `#C` is a subtype of `C` but not vice versa.
2. Exact Type Parameterization: The type `C` is "the type of an
   object that has a declared class type `C` and a runtime exact type `X`." The type `C` is a wildcard type similar to `?` in Java, except that the `~` must be an exact type. *In code, using `C` is equivalent to `C`*.
3. Exact Type Capture and Exact Type Inference: basically just that the compiler figures out the exact types whenever possible.
4. Named Wildcards: You can give the wildcards a name to indicate that two wildcards must be equal. For example, the method `int compare(Ordered a, Ordered b)` compares two instances of `Ordered` that have the same runtime type.
5. Virtual Constructors: A constructor that must be overridden and is virtual. This allows for a constructor that can return an instance of type `This`. This is useful for things like cloning and factories. (Swift has virtual constructors that return `Self`.)
6. Runtime Type Match: A control flow that determines if two instances have the same runtime type and uses flow typing. The strawman syntax they give is `classesmatch (x,y) { /* then-block */ ... } else { /* else-block */ ... }`. Within the then-block, the compiler knows that the runtime types of `x` and `y` are equal and would allow the call to `x.equals(y)` (assuming proper supertypes, etc.).

In most cases, the developer does not need to use the new types and syntax. It is generally only necessary in parts of the code that declare or call methods taking a parameter of type `This`.

I'm not sure how often the runtime type check is needed. I think in many cases, it could be avoided, but they do give an example where it is needed. The example they give is inside of `int countEqualPairs(ArrayList list)` where the compiler doesn't know that all the `Point`s have the same runtime type (e.g., some might be `Point` and others `ColoredPoint`).
---
### Answer by username_12 on 2024-10-22. Score: 7
The ways shown in the post to fix this require class ID or runtime type checks (like instanceof), and even then they break substitutability (e.g. a value of ColoredPoint cannot be passed where Point is expected as it behaves differently).

I think this is a misinterpretation. The linked article does provide sound implementations of equals for the two classes Point and ColoredPoint:
class Point {
    // ...
    
    @Override public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof Point) {
            Point that = (Point) other;
            result = (this.getX() == that.getX() && this.getY() == that.getY()
                    && this.getClass().equals(that.getClass()));
        }
        return result;
    }
}

class ColoredPoint extends Point {
    // ...
    
    @Override public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof ColoredPoint) {
            ColoredPoint that = (ColoredPoint) other;
            result = (this.color.equals(that.color) && super.equals(that));
        }
        return result;
    }
}

The linked article calls this "technically valid, but unsatisfying". But it indeed defines an equivalence relation, so the implementation is sound. And I would argue that it is not really "unsatisfying".
To be clear, this implementation does not break substitutability ─ yes, new ColoredPoint(1, 2, "red") behaves differently to new Point(1, 2) when using the .equals() method ─ but only because it is supposed to behave differently; they are equal to different things, so of course their .equals() methods give different answers. This doesn't violate substitutability any more than any subclass overriding any method, changing its behaviour, does. (That is, you're free to think this is a problem, and it kind of is, but then you must accept that inheritance itself is a problem.)
The only trouble with the above implementation is that it's not completely extensible: you cannot define a new subclass of Point such that new MyPoint(1, 2).equals(new Point(1, 2)) is true without breaking symmetry. This is only a problem in a quite specific set of circumstances:

Your language allows inheritance, particularly open inheritance such that first-party classes may be extended by third-party subclasses,
You want an equivalence relation which is extensible to third-party subclasses,
You want those third-party classes to be able to choose how they are related to first-party classes or other third-party classes.

Even if the first two hold, the third is quite an unusual requirement, and (in my opinion) indicates a design problem in the user's code. The problem is that if Alice and Bob both extend this class, which of them gets to decide whether new AlicePoint(1, 2) is equal to new BobPoint(1, 2)?
Suppose Alice says that an AlicePoint equals any point with the same x, y coordinates, and Bob says a BobPoint only equals another BobPoint. Whose definition should win? Fundamentally, by promising this kind of extensibility to your users, the promise you make to Alice (that she can decide which objects hers are equal to) is incompatible with the promise you make to Bob (that he can decide the same for his objects). That is, the promise you want to make is inconsistent with itself.
The only way you can make an equivalence relation extensible, therefore, is by saying that two objects can only be equal if both classes are defined in such a way as to allow them to equal objects of the other class; i.e. both classes explicitly cooperate in order to have equal objects. Then it is up to the implementor of those two classes to ensure that they properly implement an equivalence relation. Then across module boundaries, equals necessarily returns false; and that's fine.
Note that this is a non-issue if your language only has closed inheritance (i.e. users can only extend their own classes). Closed inheritance still allows for extensibility, just through other means (e.g. composition, generics, callback functions, etc.).
> **Comments:**
> **username_3** (2024-10-22): An example of wanting a third-party class to choose how it relates to the other classes is for a proxy. The proxy may want to be treated as equal to one of the existing classes when its value is equal.  
> **username_12** (2024-10-23): @JeffWalkerCodeRanger That still has the same fundamental problem that your proxy wants to decide what it's equal to, and other third-party classes may want to not be equal to your proxy. Such use cases can be handled soundly by composition rather than inheritance; use the newtype pattern to wrap objects, and then define equality for the wrapper type. If not all objects want to be proxied, make the newtype an enum between `Proxied(obj)` and `Transparent(obj)` where the `Transparent` case simply copies the wrapped object's behaviour without modifications.  
> **username_12** (2024-10-23): If you like, you can go further and make the `Proxied` case only present in debug builds (e.g. if it's only used for tests), and the compiler should be smart enough to recognise that the wrapper has no effect at runtime in release builds.  
> **username_7** (2024-12-19): @kaya3: It generally doesn't make sense to consider mutable objects of different types equivalent, but it might make sense for e.g. an `Immutable2dMatrix` whcih is square and has zeroes everyplace except the main diagonal to compare equal to an `ImmutableDiagonalMatrix` which only stores elements on the diagonal and has a `GetValueAt` method that returns 0 for all coordinates off the diagonal, if all of the numbers on the diagonal match.  
> **username_12** (2024-12-19): @supercat Sure, and you can do that soundly, if both classes cooperate. But cooperation requires a lot ─ particularly, for the relation to be transitive, then "class A cooperates with class B" must itself be a transitive relation. In other words, all of the cooperating classes need to agree on which classes they all cooperate with, and none may cooperate with any classes outside that set. I don't think you can achieve that in practice if cooperation is allowed between different modules with different authors.  
> **username_12** (2024-12-19): The problem is like this: suppose classes A and B declare their cooperation with the semantics like you describe, but they also declare cooperation with classes C and D. And the authors of classes C and D have cooperated to ensure that *all* instances of C are equal to all instances of D. Now by the transitive property, all instances of A must equal all instances of B, contrary to their own declarations; or some instances of C must be unequal to some instances of D, contrary to their own declarations.  
> **username_7** (2024-12-20): @kaya3: The base class contract would require that all subclasses have a defined criterion for equality which is globally applicable.  For something like an immutable matrix base class, two matrices would be equal if they have the same dimensions, and if every value GetElementAt() query would return the same values.  If a ZeroMatrix class knows that it will equal a DiagonalMatrixClass if everthing on the diagonal is zero, its equality check can avoid having to perform queries for all of the entries off the diagonal, but if there were some other variant of DiagonalMatrix it didn't know about...  
> **username_7** (2024-12-20): ...equality testing would still work--it would just be slower because of the extra testing required.  
> **username_12** (2024-12-20): @supercat In that case, the base class fully defines what it means for subclass instances to be equal, and subclasses cannot override `equals` to choose what equality means for their own instances. That is not extensible in the way this question asks about.  
> **username_7** (2024-12-20): @kaya3: Even thought the base class would define the *meaning* of `equals`, and no non-broken subclass could override `equals` in a manner that would return a different result from the base equality-check method, allowing subclasses to override the method with other implementations that yield the same semantics may greatly improve performance.  If code needs to compare a 16x16 ZeroMatrix and a 16x16 DiagonalMatrix, having a base-class `equals` method calling `GetValueAt(i,j)` for all combinations of `i` and `j` would result in 16 useful comparisons and 240 useless ones.  If the code for...  
> **username_7** (2024-12-20): ...ZeroMatrix understands the internal representation of `DiagonalMatrix`, it could reduce the number of comparisons from 256 to 16, achieving the same behavior as the base class method but perhaps 90% faster.  
> **username_12** (2024-12-20): @supercat As I said, that is not extensible in the way this question asks about. It's also not clear how the language would be able to enforce that the subclasses don't change the meaning of the code. Either you get users to write proofs that their overridden methods are behaviour-equivalent to the original method, or you allow them to change the behaviour but trust that they won't. And this question is about soundness, and a language which lets users do unsound things but asks them to pinky-swear not to, is unsound.  
---
### Answer by username_8 on 2024-10-22. Score: 5
I suggest make equal relation completely separate concept. Original method have unavoidable problem: unclear semantics. What does it mean to compare object to another? It is impossible to answer this question in general. Because of that you can always be surprised by results.

And since semantic is unclear chances to be surprised increases if you work with third party code. One popular library wasn't unable to provide symmetric implementation (I'm looking at you `appache.commons.lang`).

Instead of `equals(Object)` method use `static` method `boolean equals(TypeFoo, TypeFoo)` for each type you want to compare.

If you have `TypeBar` inherited from `TypeBar` you just get another method.

If you have some algorithm that requires checking equality relation just parametrize it with `interface EqualityRelation{ boolean equal(T, T);}` and pass relation you want to use.

No surprises here. You always explicitly tell which relation you want. You can have as many relation between same type as you want. Want to use color and x coordinate of your `ColoredPoint`? No problem: just define new relation, it is just a method.
---
### Answer by username_9 on 2024-10-23. Score: 5
A fundamental problem is that the concepts of the world do not neatly organise into fixed categorical hierarchies, where at the top sits a general concept and everything beneath is a specialisation.

Ironically a similar piece of learning about hierarchies was incorporated into Codd's Relational Algebra model as long ago as 1970, where the perceived hierarchies between tables are only encoded transiently into specific queries (not encoded into the fixed schema and enforced upon all queries), yet the insight that hierarchies tend to be contextual and dependent on purpose doesn't seem to have percolated more widely.

Sometimes there are schemes of concepts that are explicitly *designed* to be a hierarchy.

But information about a Point and information about a Color do not seem to be an example - as bedfellows they're completely disjoint conceptually.

There is equally no master algorithm that is capable of comparing two pieces of arbitrary data and declaring their equivalence or not for all purposes in the universe and for all time. Equality, too, is contextual like hierarchies are.

A Point and a ColoredPoint might be equal in some contexts where the X,Y information is all that matters, and in other contexts not.

This is traditionally (outside OOP) why data is kept separate from algorithms that operate upon it, because the choice of algorithm to apply doesn't always depend just on the data, but on the specific usage of the data and the context and purpose of processing it.

My advice would be to simply accept that subtyping is not well-suited to your use here.
> **Comments:**
> **username_0** (2024-10-24): You advice makes sense, but then the problem becomes: how to design collection types like hash maps and sets that require comparing keys for equality. One option is, as mentioned by two other responses here, to pass the equality function as you construct such collections. Are there other options? Perhaps this should be discussed in a separate thread..  
> **username_9** (2024-10-24): @osa1, as well as passing a comparison function at construction time, ultimately you could just design the entire collection bespoke to incorporate the relevant comparison function in a fixed way, or you could fall back on using plain arrays and separate insertion/retrieval methods that work on the array and enforce/employ the desired constraints as part of their workings. It isn't always necessary, or desirable, to attach the algorithms directly to the data.  
---
### Answer by username_10 on 2024-10-24. Score: 4
One way of dealing with this I thought of inspired by a paper I read a few years ago [1] is to have the equality method depend on the type the values are being compared at, not just the values by themselves.
So you have something like (using equalities that compare the the coordinates for Points and the coordinates and the colours for ColoredPoints)
Point p = Point(3, 7)
ColoredPoint c1 = ColoredPoint(3, 7, Red)
ColoredPoint c2 = ColoredPoint(3, 7, Blue)


p.equals[Point](p)          // true
p.equals[Point](c1)         // true
p.equals[ColoredPoint](c1)  // Type Error: p not ColoredPoint
c1.equals[ColoredPoint](c2) // false
c1.equals[Point](c2)        // true

The rules for the equality methods should require each one to be reflexive, transitive and symmetric. While I'm unsure of the necessity of it, it seems like a good idea to also require that if two values are equal at a subtype they should also be equal at a supertype.

[1] Florian Rabe, A Language with Type-Dependent Equality. https://kwarc.info/people/frabe/Research/rabe_tde_21.pdf
> **Comments:**
> **username_0** (2024-10-24): Interesting idea. This seems similar to passing around a comparison object/function like some of the other responses suggest. `equals[Point]` looks similar to static function `bool pointEquals(Point p1, Point p2)`.  
---
### Answer by username_11 on 2024-11-06. Score: 4
In chapter 3, item #10 of *Effective Java*, 3rd ed., Josh Bloch states (correctly):

> **There is no way to extend an instantiable class and add a value component while preserving the *equals* contract**, unless you're willing to forgo the benefits of object-oriented abstraction.

(p. 42 in the 3rd edition, other editions may vary; highlight from the original text)

I always found this to be one of the most fundamental statements about Java (and, by extension, other languages that support a similar *equals* contract), but it is a frequently ignored fact and unfortunately the source of many, many bugs.

So, the short answer is "You can't have it all", but the sentence indirectly also lists your options for finding a compromise:

1. Not "*extend an instantiable class*" -- by not allowing extension you can keep your equality relationship sound. This is what Java does by declaring many classes like `Integer`, `String`, etc. as `final`.
2. Not "*add a value component*" -- as long as there is no additional field that needs to factor into the equality you can still extend and implement a base type. This is why `List` objects still follow the `equals` contract in Java, and an `ArrayList` can be compared to a `LinkedList` (and will be considered equal if both lists represent the same sequence of objects). I am not aware of any programming language that allows to enforce a "do not add a value component" rule. Java definitely does not have such a feature, which is why declaring a class `final` is your best bet.
3. Not "*preserving the equals contract*" -- if you need to be able to extend a type and add value components you can always loosen or redefine what "equal" means. This is tricky for languages like Java which assume that every object follows the contract. Even if you are not constrained by this, coming up with alternative semantics that actually work will often be difficult.
4. Or "*forgo the benefits of object-oriented abstraction*" -- if you are OK with violating the LSP, you can still have 1, 2, and 3, but the LSP is there for a very good reason, and things will derail very quickly without it.

Personally, I always found option #2 the most interesting one to explore. Having a language feature that says "you can extend this class but you can't add any value component" and actually enforces this property would go a long way in this equality dilemma.
> **Comments:**
> **username_7** (2024-12-20): One thing I've thought could be useful in a GC-managed language would be a family of classes with a private `telecopingEquality` field which, if set to a non-null value, would invite the GC to at its leisure replace any references to a the object where the field was non-null with references to the target.  Classes couldn't set the field directly, but would have a method identifying an object with which they should be considered interchangeable, and a method of asking for the an object equivalent to any given object.  Something like a string comparison that finds that two strings are equal...  
> **username_7** (2024-12-20): ...could then let the GC know that the two objects should be equivalent, allowing them to be merged.  Such a feature would require that types uphold a concept of immutable equality regardless of whether the language "enforced" it directly, since types that behaved in contrary fashion would behave rather oddly as a consequence.  
---
### Answer by username_3 on 2024-10-22. Score: 4
One possible way to deal with this as a language designer is to add multimethods aka multiple dispatch. This allows a "method" to be dynamically dispatched on the type of parameters, not just on this/self.
In a statically typed language, if the == operation is a multimethod then the compiler can statically enforce that the equality of every pair of subtypes of the type that declares the method must be covered. In pseudocode, this might be something like:
class Point {
    int x;
    int y;
}

// Declare a multimethod operator that works on points and its subclasses
// The `multi` keyword makes this dynamically dispatch on the type of p1 and p2
// Note: because of multiple dispatch, this will be called only when the two parameters are `Point` and not for any subtypes.
multi bool operator ==(Point p1, Point p2) => p1.x == p2.x && p1.y == p2.y;

class ColoredPoint: Point {
    Color color;
}

// Since ColoredPoint is declared, you must now cover three more cases
multi bool operator ==(ColoredPoint p1, Point p2) => false;
multi bool operator ==(Point p1, ColoredPoint p2) => false;
multi bool operator ==(ColoredPointp1, ColoredPointp2) => ...;

Here the compiler will emit an error if any of the three cases are not covered. There are various ways to reduce the burden of this on developers. For example, a symmetric keyword as in JAI could allow one method to cover both (ColoredPoint, Point) and (Point, ColoredPoint). You can also provide ways of syntax allowing a method implementation to handle any type in a specific parameter (e.g. * p2) or any subtype of a specific type in a parameter (e.g. * <: Point p2).
EDIT: Alternative Syntax
Some people found the above syntax confusing. Here is another syntax that might be clearer. In this syntax #T means exactly the type T and not a subtype.
class Point {
    int x;
    int y;
}

// Declare a multimethod operator that works on points and its subclasses
// The `multi` keyword makes this dynamically dispatch on the type of p1 and p2
abstract multi operator ==(Point p1, Point p2);

// Note: because of multiple dispatch and exact types, this will be called only when the two parameters are both `Point` and not for any subtypes.
multi bool operator ==(#Point p1, #Point p2) => p1.x == p2.x && p1.y == p2.y;

class ColoredPoint: Point {
    Color color;
}

// Since ColoredPoint is declared, you must now cover three more cases
multi bool operator ==(#ColoredPoint p1, #Point p2) => false;
multi bool operator ==(#Point p1, #ColoredPoint p2) => false;
multi bool operator ==(#ColoredPointp1, #ColoredPointp2) => ...;
```
> **Comments:**
> **username_12** (2024-10-22): Doesn't the first declaration, `==(Point p1, Point p2)`, already cover every pair of types, and the others are just overrides?  
> **username_13** (2024-10-22): "the compiler will statically enforce that the equality of every pair of types must be covered" This sounds excessive. Most pairs of types aren’t meaningful to compare (or trivially unequal if one insists) yet there are a lot of them.  
> **username_3** (2024-10-22): No @kaya3, `==(Point p1, Point p2)` is not considered to cover every pair of types in my pseudocode because it should be called only when both parameters are `Point` and not subtypes to satisfy the multiple dispatch. Don't think of these as static overloads or simple overrides. (I've added a comment to try to clarify).  
> **username_3** (2024-10-22): @MisterMiyagi I've clarified that it is every pair of types that are a subtype of the base type. So in this example, every pair of subtypes of type `Point` must somehow be covered.  
> **username_13** (2024-10-22): @JeffWalkerCodeRanger Well, those can still be a lot. But more critically, in languages that have a common base type (think `Object` in Java or Python) or expect equality to be universal these are still all types.  
> **username_3** (2024-10-22): Yes, this approach does not work well for a language with universal equality.  
> **username_12** (2024-10-22): So if I understand correctly, a multimethod defined for a parameter of type `T` does not work on an argument of type `S` where `S < T`. Is that not a clear violation of the Liskov substitution principle?  
> **username_3** (2024-10-22): Different languages handle multimethods differently. I chose a particular handling that would force safe equality. Some languages do allow a multimethod to match all subtypes of its parameters. Some languages have a way to do what I have said. No, it doesn't violate Liskov substitution because of multiple dispatches. Think of it as being like a visitor pattern where you are required to implement every case. It is just saying the multimethod must be overriden for each type.  
---
### Answer by username_14 on 2024-10-24. Score: 3
What's equality?
I think the first fundamental problem is that equality is ill-defined, in the first place.
Yes, mathematics describe what properties an equivalence relationship should have. That's objective, great. The subjective part comes into play when one starts asking whether:

Values should only be equivalent if all their properties are equivalent, or if the user is allowed to define a subset: "cache" fields are a legitimate case here.
Values should only be equivalent if their dynamic types are equivalent, or if they can be equivalent across types: lightweight wrappers, proxies, mimicry etc... have a legitimate case here.
Values should only be equivalent if they are structurally equivalent, or if they can be equivalent beyond structure: hash sets, etc... have a legitimate case here.

The more freedom you allow your users -- and there are very good to allow them! -- the more difficult it becomes to double-check they're not making a mess.
Fields
The user should be able to pick which fields participate in the identity of the value, and which don't.
This means that, realistically speaking, the identity of the object is defined -- recursively -- by an order list of values.
Rather than ask the user to write the code for these values, it may be easier, instead, to ask the user to enumerate these values.
That is, the user writes:
def key(self) -> Generator[Object]:
    yield self.x
    yield self.y
    yield self.z

This is great, as immediately you get to:

Be assured that the equality operation derived from this is actually an equivalence relationship.
Be assured that the equality operation uses the same set of fields as the hashing operation.

Two birds with one stone. Aren't we living the dream?
Note: a generator, or lazily generated list, is crucial for performance here, at least for the performance of the not-equal case.
Note: a visitor method isn't as good, because it's hard to visit two objects in lock-steps.
Note: in Rust, #[derive(Identity)] is a completely different solution achieving the same goal. It doesn't work as well, however, for mixing types.
Types
The user should ideally be able to pick which types can be compared to each other.
It should be as simple as allowing the user to declare that. That is, for any two types, in one of the type "modules", one should be able to declare something like:
impl Eq[X] for Y

The runtime will then generate the necessary code for checking whether the types do compare equal, and from there it's just a matter of checking their key fields.
Non-Structurals
And then we have collections. Ideally, a set should be equal to another set iff both sets contain the same list of elements. No matter what their types are.
There's no way to make that work using our Generator[Object] type: the objects may simply NOT be listed in the same order depending on the underlying implementation.
For now, I cannot think of a better solution than allowing an escape hatch.
Since the escape hatch may be useful anyway for performance reasons, I would argue it's a fair thing to do. But it is, obviously, a bit of a cope out.
> **Comments:**
> **username_0** (2024-10-24): I don't understand what is the escape hatch you allow for collections. Do you have an example?  
> **username_14** (2024-10-24): @osa1: I was thinking of a _complete_ escape hatch, where the user manually implements the `equals` method instead of it being auto-generated by the compiler from the pieces provided (`Eq` impl & `key` method). In short, just giving up on attempting to enforce any guarantee about the soundness of the equality for this type.  
---
### Answer by username_15 on 2024-10-22. Score: 1
[EquivalenceRelations](https://en.wikipedia.org/wiki/Equivalence_relation) should be their own class hierarchy and, if the type system is ∀- or λ-polymorph (i.e. offers generics or templates), it should take the base type as an argument.

> Is avoiding subtyping the only option?

No. The best way is to offer an equals function yielding an EquivalenceRelation similar to Iterable/Iterator.

Also, EquivalenceRelations can exist in a Cohierarchy for the purpose of optimizing, however, the contract for overridden equals functions is in essence that a static upcast of this, i.e. using the super implementation instead, results in the same result for all values.

This restrictions does not really work in Java, because it would render `equals` an expensive duplicate of `==`.

Note: HashCode is related to equivalence relations, as hashes are essentially names for equivalence classes. As such, [HashedEquivalenceRelation](https://en.wikipedia.org/wiki/Hash_table#Hash_function) should be a subclass of EquivalenceRelation.

Note: The nature of the equals function yielding the natural EquivalenceRelation for a type would make it a good candidate for a class function for languages having them.
> **Comments:**
> **username_0** (2024-10-22): I don't know what `EquivalenceRelation` is. I've searched for it in two different search engines and asked a chat but, but no luck. Where can I learn more about it?

I also don't know what `∀-polymorph` and `λ-polymorph` are.. Any sources on these would be appreciated.  
> **username_0** (2024-10-23): Sorry for the confusion -- as Alexis says I know about the relation, I thought (because of the spelling) you are referring to a type in a programming language, and I was curious to see how it's used.  
---
### Answer by username_7 on 2024-10-24. Score: 0
In an interface specifies that implementations will behave like data holders whose content can only legitimately be changed by someone with holding a reference to the data holder, and that interface supports an equality-check operation which is supposed to report objects as equal if they could not be distinguished *only using members of the interface that don't try to write to them*, then it may be useful to have a quasi-private interface member (that could only be used by implementations of that equality method) which would first test whether it has any special knowledge that would help it quickly recognize itself as equal or unequal, and if not perform an item-wise equality check. The primary equality method would then check whether the type implementing it has special knowledge about the other object, and chain to the quasi-private one of not, so the item-wise check would only be performed if neither type had any special knowledge.

If, for example, one had a "square matrix of float" interface, with implementations of "arbitrary matrix", "constant matrix", a "diagonal matrix" type, and "identity matrix", equality-check logic for a diagonal matrix could compare itself quickly against another diagonal matrix by just examining the cells along the primary diagonal, against the identify matrix by checking whether all cells on its diagonal were equal to 1, and could check itself against the constant matrix by first checking whether either the size was less than 2 or constant was zero, and then checking whether any of its own members were non-zero.

BTW, I'd suggest that data-holder interfaces have subtypes for mutable and immutable data holders, as well as `asImmutable`, `asCopy`, `asMutable`, and `asNewMutable` methods (an immutable object would return itself for the first two, and a new mutable object for the others; a mutable object would return a new immutable object for the first, a new mutable copy for the second or fourth, and itself for the third).
---
### Answer by username_16 on 2024-10-22. Score: 0
It should be possible for users to implement it for their types.

No.
It should not be possible for users to implement it.
It would be possible to annotate that a user type should have the equality operator to be derived by the compiler, where it is possible to guarantee that the generated code is sound. This may not sound so easy (pun intended), but consider the alternative: to provide or prove soundness, it would be necessary to prove that the user provided code is sound, and this is a much harder problem.

Regardless of how and where we add this, user-written implementations will inevitably break symmetry, and probably transitivity as well.

So it's not up to the user to write any of this implementation.
The user can, instead, provide annotations that describe in that terms a type can be considered equals to other. For example, by annotating fields that should not be considered. And after that, the compiler than can test if all other fields have intrinsic or derived proofs/metadata indicating that equality operations are sound or not.

Is avoiding subtyping the only option? Can I have an alternative equality relation (maybe relaxing some of the properties without creating potential for surprising behavior) that works in data structures like hash maps?

This is a "solved" problem where data types cannot have cycles, or by separating types into reference types (compare only storage address) and simple value types, that compare by their leaf constituents. But this question is about two distinct types that may compare equals based on some relation between them.
Numeric relations are a prime example of this, where 1, 1.0 and 1/1 may be (or should be) compared equals.
In the case of substitutability, again, I would argue this is a compiler job, not a programmers job. Object oriented substitutability is about substitution, after all. It's about changing some functionality and, at same time, by maintaining some signature compatibility. Where the change of functionality also breaks equality should be determined by the compilation process, that has a privileged view of all object internals, and could in principle calculate if all equivalence relation properties can be expected or not, between a type and a subtype.
Going for your example, if Point and ColoredPoint are two distinct types, without any relation, besides some name overlap, they should not compare equals, in any way whatsoever.
But if ColoredPoint is a specialization of Point, this is a relation that hints, but not grantees, equability. For example, if ColoredPoint adds a property or method, that cannot interfere in any way with Points behavior, it is then possible to have a compiler generated equality operator for these two types.
But if ColoredPoint is implemented as:
def ColoredPoint type, implements Point
    var X int { get => this.X + 1; set => this.X = value -2; }
    var Y int { get => this.Y * 2; set => this.Y = value / 60; }
    var Color string = "red";

Then ColoredPoint can be used where any Point is expected except on any equality operation, because the compiler cannot prove these two types have the same behavior for the equality protocol.


without creating potential for surprising behavior) that works in data structures like hash maps?

Should equals method/operator allocates, or should let it cause stack overflows in the normal case? This may sound an surprising question, but consider this example:
var h1 = new HashSet();
var h2 = new HashSet();

h1.add(h2);
h2.add(h1);

console.log( h1 == h2 );

The convention of comparing reference types by their storage address, and leaf bitfield types by their bit contents obviously avoids both the surprising behaviors above, as is guaranteed that will at most allocate a few stack frames.

The discussion above hints the solution may lurk on having the sound equality protocol being controlled entirely by the compiler and some special metadata.
Any two objects then may compare equals or not based on soundness proof generated by the compiler, in order to guarantee there is not any difference in behaviour, beyond any difference in public signatures.
TL;DR: Only the compiler may generate and use a sound equal operator.
> **Comments:**
> **username_13** (2024-10-22): Is the compiler actually able to implement *meaningful* equality operators? It would seem that many types have degenerate information from more primitive types on which they are built without it impacting equality. For example, an array would normally compare equal taking into account ordering and duplicates. Yet, building a set type that uses an array as storage should not care about ordering.  
> **username_12** (2024-10-22): @MisterMiyagi In principle it's possible to achieve this in a similar way that sorting functions avoid the problem of "what if the user provides an unsound comparator?" by accepting a key function instead of a comparator. For equality, a "key" function would be some kind of canonicalisation, such that the image of an equivalence class is a single point. Taking the "array-backed set" as an example, such a canonicalisation could be "make a sorted copy of the array". Then equality can be derived for the array-backed set type by comparing the canonicalised (i.e. sorted) arrays.  
> **username_12** (2024-10-22): The downside is that now your set can only contain a type for which an ordering is defined, and comparing equality of two hashsets requires sorting in O(n log n) time with O(n) auxiliary space, whereas a user-defined "equals" method could use the hashes to test for equality in O(n) time and O(1) auxiliary space. The other downside is that some equivalence relations might not support an easy "canonicalisation" mapping.  
> **username_13** (2024-10-22): @kaya3 I can think of a myriad of ways how a key function can break the desired features unless serious and expensive scaffolding is used. Simply being able to return a random key means the key would need to be immutable and cached for as long as the object lives, for example. (Which wouldn’t be useful for mutable types at least.)  
> **username_12** (2024-10-22): @MisterMiyagi Well, at least it is easier for a language to verify that a type is immutable and a function is pure, than it is to verify that a comparator function defines a total order or an equivalence relation.  
> **username_3** (2024-10-22): I don't think this is a viable answer. The update to address `HashSet` really misses the point. Consider the .NET `ImmutableHashSet<T>` class. As an immutable set, it should be compared based on the values, NOT by reference. It has a complex implementation based on an AVL tree. You can't just generate equality for it. You will want to hand-write equality to get good performance. It is a framework class, and very good performance in all cases matters a lot.  
> **username_16** (2024-10-22): An framework class is not "user code", in the usual sense of this question.  
> **username_12** (2024-10-22): How should we distinguish between "user code" where defining the behaviour of `equals` should be forbidden, and "framework" code written by users, where it should be allowed?  
> **username_16** (2024-10-23): By compiler analysis, as noted above. The framework quib is about how framework code is usually special in relation to normal use code. There a lot of `unsafe` in standard Rust lib.  
> **username_13** (2024-10-23): @kaya3 Just being verifiable is pointless. Making all instances equal/unequal but to themselves achieves that. Comparisons must be meaningful, otherwise people just ignore them and roll their own comparison function/method/operator which then cannot be verified either.  
---
