This paper describes a software-engineering problem, proposes a solution and shows how that solution in uences language design. In many object-oriented programming languages, when implementing equality the programmer has to make sure that it obeys a set of rules, called equality contract. Not only is it di cult to adhere to these seemingly simple rules, but the equality contract itself is a source of potential errors. Even if equality complies with the contract, it can lead to faulty, unintended, indeterministic program behavior. This paper proposes a modi ed contract that avoids these problems. Additionally, the modi ed contract describes equality unambiguously, and it implies that equality for values and identity for objects can be regarded as the very same concept. Based on the modi ed contract the language design can be enhanced in a way that supports value equality and object identity more clearly and more safely.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
Submission to: 8. Arbeitstagung Programmiersprachen, Dresden, Germany, 18-Mar-2015, to appear at http://ceur-ws.org
Adhering to the contract is amazingly di cult. Even in professional code and in textbooks you nd equals methods that violate it; [LK02a] and [VTFD07] cite some examples. Many papers propose guidelines and techniques for implementing equals in a contract-conforming way, mostly for Java, e. g. [BV02], [Coh02], [LK02a], [LK02b], [SP03], [RH08].
This paper, however, addresses a di erent issue. It claims that the contract itself is a source of problems : it is not su ciently restrictive to prevent erroneous code and subtle bugs. Even though equality adheres to the contract, several programming errors can occur: 1. According to the contract, equality may depend on mutable state, yet it leads to indeterministic, contradictory behavior, e. g. when adding an element to a collection and trying to retrieve it after it has been modi ed (see [OSV09]). For this reason, Vaziri et al. propose a \revised contract" that demands equality not to depend on mutable state [VTFD07]. 2. If a and b are equal, then the hashCodes of a and b must be equal, too. This \hashcode rule" is not a part of the equality contract but a programming guideline on its own. Inadvertently or unknowingly violating the hashcode rule also leads to unexpected, unintended behavior in collections (see [Blo08, Item 9, p. 46]). 3. What pertains to hashCode actually holds true for every read-only method q: If a and b are equal, then a.q() and b.q() must be equal as well. As stated by Liskov and Guttag, \it should be impossible to distinguish between two equal objects" [LG86, p. 93]. As for the hashcode rule, it can be shown that violating indistinguishability can result in unexpected, indeterministic behavior. 4. In Java, the equals method is inherently asymmetric for null references. Because equals is an instance method, null.equals(a) throws a NullPointerException, whereas, according to the contract, a.equals(null) must yield false. This asymmetry results in unpredictable behavior (see, e. g. [Hor03]).
Moreover, it leads to intricate, verbose code, because it forces the clients to check for null. 5. Since equality is usually de ned in a class at the top of the hierarchy (like Object in Java), it can compare expressions of incomparable types (like String and Button). However, in such cases the result can never be true, and mostly the comparison is a programming error (see [VTFD07]). 6. In many object-oriented languages, there is more than one comparison, for example == and equals in Java.
Inadvertently using the \wrong" comparison leads to subtle and hard-to- nd errors. For example, comparing two String expressions with == instead of equals is a well-known, yet widespread source of errors in Java.
In general, there may be more than one operation that adheres to the contract. E. g., identity is one of them, see item no. 6. At rst glance, this is not a problem. After all, the contract does not claim to be a unique description, but its ambiguity gives rise to questions, such as: Can a type have more than one equality? Is equality a universal concept, or does it mean something di erent for each type? 3
To prevent problems 1 to 6, we propose a contract with more, and stronger conditions than the ones described in section 2. We call it the modi ed equality contract : A. Equality must always be an equivalence relation (i. e. re exive, symmetric and transitive), this also applies to null references.
B. Equality must be independent of mutable state. In this respect, we follow the revised contract of Vaziri et al. [VTFD07] (see section 2, problem no. 1).
C. Equality must be indistinguishable: if a and b are equal, there must not exist a read-only operation q that yields di erent results for a and b. (Condition C refers solely to read-only operations, because for mutating operations in general it cannot be satis ed. If operation m modi es the instance it is called for, even two calls to a.m() can yield di erent results.)
By de nition, equality that adheres to the modi ed contract su ers none of the problems described in the previous section. Problem 1 is prevented by condition B. Problems 2 and 3 are prevented by condition C (actually, problem 2 is a special case of problem 3), problem 4 by condition A, and problem 5 by condition D. It can be proved that there exists at most one operation that adheres to the modi ed contract.1 This uniqueness solves problem 6: If there is only one equality, then there is no danger of accidental confusion.
Because of its uniqueness, the modi ed contract serves as an implementation-independent speci cation. When we de ne equality as the concept described by the modi ed contract, we receive the following answers to the conceptual questions posed in section 2: There is one equality only. Equality means the same thing for every type. Equality is the most ne-grained distinction possible (\the nest distinction" [Bak93, p. 3]). It determines what we are referring to when we talk about \one" instance of a type.
Uniqueness has yet another implication: For objects, the concept described by the modi ed contract means identity. For values, it means value equality.
We de ne objects as stateful abstractions like persons, cars, or bank accounts. Objects can basically be created, destroyed and changed (even though they don't have to). To put it more abstractly, their operations can be referentially opaque and cause side e ects. Values, by contrast, are stateless; they comprise abstractions such as numbers and characters, strings, points and monetary amounts. Values cannot be changed, created or destroyed, they exist per se. Operations on values are always referentially transparent and never cause side e ects. Distinguishing objects and values separates two fundamentally di erent programming paradigms, with objects representing the imperative side and values representing the functional side. Table 1 lists the de ning characteristics of objects and values.
Distinguishing objects and values is a wide-spread modeling approach (see [Mac82], [BRS+98], [Fow09, p. 486495], [Eva04, p. 97-103]). Fowler even de nes values as \abstractions whose equality is not based on identity" in line with the modi ed contract. Liskov and Guttag hold the view that \in the case of mutable objects, all distinct objects are distinguishable (i. e. equals has the same meaning as ==)" and \if two immutable objects have the same state, they should be considered equal because there will not be any way to distinguish among them by callig their methods."[LG01, p. 94] Liskov and Guttag distinguish \mutable objects" and \immutable objects" { which comes close to our distinction between objects and values, though it is not exactly the same.
The distinction of objects and values is not fully supported by current programming languages. Note that so-called \value types" in C#, e. g. structs, are not necessarily stateless and thus are not the same concept as the values mentioned above. struct does not support values, but \value semantics", an implementation technique also used for primitive types. This also applies to similar language mechanisms like expanded types in Ei el, structs in X10, \value objects" in Fortress etc.
Because the modi ed contract describes both object identity and value equality, calling this comparison \equality" is not quite appropriate. However, neither is the term \identity" appropriate, because \identity" does not include value equality. For want of a better name, we shall call that comparison \equality/identity".
The modi ed contract excludes some comparisons that, in colloquial language, are also termed \equality". For example, two cars are often regarded as \equal" if they are the same model from the same manufacturer, yet they are two distinct physical entities. In this case, the objects are distinguishable, at least by identity, and mostly by other properties as well (owner, serial number etc). Thus this \object equality" violates the modi ed contract. Object equality and value equality are di erent concepts. Value equality does adhere to the modi ed contract, and it results, e. g., in recognizing 3/4 and 6/8 as the very same value.
Figure 1 depicts object identity, value equality, object equality and their relationships. It illustrates that, despite a di erent name, object identity and value equality can be regarded as the very same concept, whereas, despite the same name, value equality and \object equality" denote two fundamentally di erent concepts.
There is no such thing as a \right" or a \wrong" equality contract. Choosing the characteristics you expect from equality is a mere matter of de nition. However, rejecting the modi ed contract and starting out from a less restrictive contract (e. g. the one for Java) means implicitly accepting the inconsistencies and potential errors described in section 2.
In the next sections, we focus on (value) equality/ (object) identity more extensively; we do not consider \object equality" any further. 4
A contract can be regarded as a set of criteria that guide the programmer how (and how not) to implement equality. In general, the criteria are not assured or checked by the language. Programming equality that adheres to the modi ed contract is easier to achieve in some respects and more di cult in others.
Some conditions of the modi ed contract can be met with adequate programming discipline: writing equality as an equivalence relation for non-null references, avoiding dependence on mutable state, and implementing all read-only operations (especially hashCode) so that equal instances are indistinguishable.
With the understanding that for object types equality is identity, these tasks get even easier: For object-like, i. e. stateful types like Person or BankAccount, implement equality as a call to identity (or, if this is the standard behavior anyway, as in Java, simply refrain from overriding equals).
For value-like, i. e. stateless classes like MonetaryAmount, in many cases canonical equality (see [Bak93, p. 18]) { compare all matching data elds and link results by logical And { is appropriate and straightforward. For example, comparing two MonetaryAmounts m1 and m2 can be implemented as
m1.amount == m2.amount && m1.currency == m2.currency Canonical equality is already the most ne-grained value comparison. Thus making equality indistinguishable does not require any further programming e ort.
For some value-like classes, a more elaborate equality may be required. For example, comparing rational numbers r1 and r2 may need an implementation like
r1.numerator * r2.denominator == r2.numerator * r1.denominator Without canonical equality, special care must be taken to make equality indistinguishable. E. g., in the example above an operation like getNumerator is not permitted because it would destroy indistinguishability: Equality recognizes 3/4 and 6/8 as equal, but getNumerator would enable clients to distinguish between them.
At rst glance, it may seem strange for a class RationalNumber not to provide a method like getNumerator. However, it consequently conveys the notion of rational numbers as abstract entities, characterized by their operations (addition, multiplication etc). If we say that the numerator of \3/4" is 3, then we refer to a speci c representation. But the rational number denoted by \3/4" can have more than one representation, therefore it does not make sense to ascribe it a numerator. It is exactly the purpose of a class to present an abstract view (\speci cation view") of the type towards clients and to shield them from the representation and other details that are needed for implementing the class' behavior.
In the case of rational numbers, it is conceivable to provide an operation that computes the numerator of the reduced representation. For reasons of clarity, it should be termed something like \getNumeratorOfReducedRepresentation". Programming it this way, the operation would satisfy indistinguishability, as demanded by the modi ed contract. For \3/4" and for \6/8", this operation would yield the same result, 3. Possibly, this operation may be required under certain conditions. However, the result of arithmetical operations on rational numbers does not depend on their representation.
Many conditions of the modi ed contract are hard to adhere to. If equality is implemented as an instance method (like equals in Java), it is di cult to make it symmetric for null references. One could do so by throwing a NullPointerException if the parameter is null, violating the Java equality contract which states that a.equals(null) must yield false. For this problem, Scala has a ready-made solution: The operator \==" handles null references; it does so in a symmetrical way, and in the case of non-null references, \==" implicitly calls equals. From the client's perspective, in Scala \==" can be regarded as a \null-safe" version of equals. As another consequence of this design, in Scala both object identity and value equality can be called via the operator \==", provided equals is implemented in a way matching the object nature or value nature of the class. With respect to equality/identity, the language model of Scala is closer to the modi ed contract than the language model of Java.
Yet, there are still open issues both in Java and in Scala. For value-like classes, equality is not indistinguishable. \Equal" instances can be distinguished by \==" in Java, and by eq in Scala. These comparisons are not appropriate for value-like classes, and they violate the modi ed contract, but nonetheless they are always available.
In general, equals permits the comparison of incomparable types. The programmer of the equals method could implement additional type checks, which would result in runtime errors. Programming a type-safe comparison, i. e. one that is checked at compile-time, requires a language feature like typeclasses (as in Haskell, where instances of typeclass Eq are compared in a type-safe manner). In Scala, typeclasses can be emulated, using an intricate combination of traits, implicit parameters and implicit conversions; and indeed the library scalaz does provide a type-safe comparison (===). However, it adds yet one more comparison to the Scala ecosystem. This contradicts the modi ed contract which implies that there can be one comparison only.
A programming language that provides two or more comparisons, like Java or Scala, undermines equality/identity as a unique concept and leaves loopholes for problem no. 6 (see section 2). Sather, for example, is di erent in this respect; it provides one language-supported comparison only [SO96, p. 64] (the symbol \=" is syntactic sugar for a call to is eq).
The bottom line is: depending on the programming language and its implicit assumptions, adhering to the modi ed contract can be hard, even virtually impossible. The examples from Java, Scala and Sather described in this section give an idea of many subtle di erences in the ways programming languages handle equality/identity. 5
As section 4 has shown, it is the programming language that prevents implementing equality so that it adheres to all conditions of the modi ed contract. Therefore a dedicated language support for equality can solve the problem. Section 4 has also shown that, to a certain extent, language support for equality already exists. Equality is deeply interwoven with programming language design. It is a basic concept; as Odersky puts it, \equality is at the basis of many things" [OSV09]. This section will show that language support for equality/identity, as speci ed by modi ed contract, is possible and bene cial.
Supporting equality/identity by the language requires separating objects and values on the language level. The language must provide two kinds of classes, object classes and value classes. Otherwise, the language cannot \know" if a class is meant to model object-like or value-like abstractions and therefore, if object identity or value equality is the appropriate comparison. For example, a class with two data elds might as well model an object type (like Person with name and salary) or a value type (like MonetaryAmount with amount and currency). Nevertheless, generating an appropriate comparison is not the primary motivation and by far not the only reason for the separation. Objects and values denote two fundamentally di erent concepts. Distinguishing between them enhances modeling power, clarity and safety of a language in many respects (see [Mac82], [BRS+98], [Fow09, p. 486-487], [Eva04, p. 81]). For example, it can ensure the conceptual properties of objects and values respectively. In the following points, we shall describe a language support for equality/identity:
The language ensures that the comparison matches the type, i. e. object classes are compared by object identity, value classes by value equality.
Whenever possible, the language generates an implementation for the comparison. For object classes, the language provides object identity as a language primitive, e. g. based on comparing storage addresses { just as many current object-oriented languages already do. That way, object identity cannot (and need not) be implemented by the programmer. For value classes, the language provides canonical equality (comparing all matching data elds, see section 4) as the standard implementation. As section 4 has argued, canonical equality is just what many value classes need. As has been shown previously, there may be value classes where canonical equality is not suitable. For these cases, the language provides a mechanism that enables the programmer to implement value equality di erently.
The uni ed comparison is denoted by a single symbol (or a single keyword). Hence clients always call equality/identity with the same symbol, no matter whether it refers to objects or values, and no matter whether it was generated by the language or implemented by the programmer. Since equality/identity is frequently used, a short notation is advisable. (The symbol \=" is an obvious candidate, because it has been used in mathematics for a long time.) The language handles null cases. If the right side or the left side of a comparison yields null, then the result of the comparison will be false.
The language takes care of incomparable types. Comparing expressions with incomparable types results in a compile time error.
Equality/identity as just described di ers largely from the way current object-oriented languages treat equality and identity. Language support for equality/identity, as sketched above, has numerous advantages:
In the cases of object identity and canonical value equality { both generated by the language { all conditions of the modi ed contract are taken care of by the language.
In case of a manually implemented value equality, the programmer has to make sure that equality is an equivalence relation and that it is indistinguishable. Even then, the other conditions of the modi ed contract can be taken care of by the language. This applies especially to conditions that, for a programmer, are hard or even impossible to ensure: The language can handle null references, and it can preclude comparing incomparable types. Because value classes do not possess mutable state, in all cases value equality is necessarily independent of mutable state.
In summary, many problems that are frequently associated with programming and using equality (see section 2) are no longer possible. This enhances language safety.
There is no way of confusing equality/identity with \object equality" (see section 3). However, this does not mean that object equality cannot be implemented with such a language. With the approach described above, object equality is just a user-de ned operation like any other: it gets no special language support. Just like any other similar operation, the programmer has to implement object equality manually and give it a suitable name.
There is also no way of using an identity-like comparison for values, e. g. based on a technical address. For value classes, such a comparison would have no meaning, it would allow implementation details to \leak through" to the programmer (see [Bak93, p. 6]), and it would violate indistinguishability and thus break the modi ed contract.
The largest bene t of language support for the modi ed contract is a gain in conceptual clarity. When the language provides two kinds of classes (value and object) and a single comparison { instead of one type of class (object) and two or more comparisons { and when it uses the same comparison symbol for every class, then it expresses clearly that it regards object identity and value equality as the very same concept, leaving less room for ambiguity and erroneous behavior.
The language model described in this paper might preferably be taken into consideration when designing a new programming language. Current object-oriented programming languages like Java, C# or Scala are implicitly based on language models that di er substantially from the one presented here. The attempt to incorporate equality/identity { and its prerequisite, the separation of object classes and value classes { into an existing language would destroy upwards compatibility and is therefore less promising. [Bak93]
Henry G. Baker. Equal rights for functional objects or, the more things change, the more they are the same. SIGPLAN OOPS Mess., 4(4):2{27, 1993. [BV02]
Joshua Bloch and Bill Venners. Josh Bloch on Design, A Conversation with E ective Java Author. http://www.artima.com/intv/blochP.html, 1 2002.
Tal Cohen. How Do I Correctly Implement the equals() Method? Dr. Dobb's Journal, 5 2002.
http://www.artima.com/weblogs/viewpost.jsp?thread=4744, 5 2003.
Barbara Liskov and John Guttag. Abstraction and Speci cation in Program Development. MIT Press, Cambridge, MA, 1986.
Barbara Liskov and John Guttag. Program Development in Java : Abstraction, Speci cation, and Object-Oriented Design. Addison-Wesley, 2001.
Angelika Langer and Klaus Kreft. Secrets of equals() - Part 1, Not all implementations of equals() are equal. JavaSolutions, 4 2002.
Angelika Langer and Klaus Kreft. Secrets of equals() - Part 2, How to implement a correct slice comparison in Java. Java Solutions, 6 2002.