What are some options for adding a sound equality operator (or avoiding it) in a type system with subtyping?

Question

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:

1. 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)
2. We can have a separate class/abstract class/interface: abstract class Equals { bool equals(Self other); }.
3. 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?

Answer 1

The paper ThisType for Object-Oriented Languages: From Theory to Practice by Sukyoung Ryu 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</X/> 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</X/> a, Ordered</X/> 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<Point> list) where the compiler doesn't know that all the Points have the same runtime type (e.g., some might be Point and others ColoredPoint).

Answer 2

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.).

Answer 3

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<T>{ 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 4

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.

Answer 5

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) => ...;
```

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

EquivalenceRelations 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 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.

Answer 10

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<object>();
var h2 = new HashSet<object>();

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.

Answer 11

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).