Equality

An equality operation is a predicate on two values of the same type, typically written as a = b. Ideally, it partitions the values into disjoint equivalence classes. For this, the predicate has to be reflexive,

a = a

symmetric,

a = b ⟺ b = a

and transitive.

a = b ∧ b = c → a = c

These must hold for all a, b and c.

In object-oriented languages, the relation of equality and inheritance is not obvious.

Kinds of equality

There are basically three kinds of equality

• Reference equality: Do two references refer to the same memory location?
• Value equality: Do two instances contain the same values?
• Deep value equality: Do two instances contain the same values? In case instances contain references, does this hold, recursively, for the referenced instances?
• Abstract equality: Do two objects represent the same abstract value?

A total order ≤ defines an equality relation as follows

a = b :⟺ a ≤ b ∧ b ≤ a

while a partial order does not. It is therefore important to define an equality operation in a way that it could easily be extended to or derived from a total order.

Other languages

Java

Reference equality

The Java infix operator == performs a check for reference equality. This goes awfully wrong for code such as

(Integer) i == (Integer) i

that results in true for some values of i and false for others.

Object.equals()

This is a real mess. Typical implementations of equals consist of an instanceof check of the argument and a comparison of fields in case it is the same instance. The result is that equals is generally not symmetric in case of several redefinitions of equals along the inheritance tree

Comparator

Comparator is a generic interface in Java that compares two instances of the type given as a generic argument. This allows the definition of several equality relations for different types at different levels in an inheritance tree. It is generally more flexible and allows different equivalence relations to be defined for the same type, but it is more cumbersome to use than Object.equals().

Equality in Fuzion

Guiding principles:

• There should be no support to test reference equality. References should be hidden from the developer as much as possible and the compiler should be allowed to turn references into inline values as an optimization.
• Abstract equality is the preferred equality operation. Equality might not be defined for some types, while different types along the inheritance chain could define different equivalence relations.
• No equality operation defined by default means that values cannot be searched for, i.e. any operations that find elements in lists or that collect elements in sets are not possible unless an equality operation for the element type is defined explicitly!
• It should be possible to use simple syntax a = b to test for the 'natural' equality corresponding to the static type of the two instances.
• It should, nevertheless, be possible to define and use other equivalence relations for the same static type.
• It does not seem to make sense to use dynamic binding for the equals operator (as in Java's Object.equals())

Approach: TBD!

Literature

• Noble, Black, Bruce, Homer, Miller: The Left Hand of Equals., presented at Onward! 2016.