The Left Hand of Equals | Hacker News Reader

The Left Hand of Equals

lambda-the-ultimate.org

I've found that the concept of identity and its relationship to equals in OO is a confusion. And by confusion, I mean an accidental combination that creates accidental complexity. Because in the OO I've seen, you have a permanent fusion of of state and identity. Which is to say what happens to the object is the same thing as the object. Which is not true about things in the real world at all. Does this paper address this problem?

The real problem is that equality is an operator that creates a relation between two objects. Equality is not and should never be decided by one object -- both objects must "agree". An object A in itself cannot say for sure that another object B is equal unless A asks B (and then B asks A leading to infinite recursion). The classic case of this, as pointed out in the paper, is inheritance which is the prime culprit for broken symmetry eg:

Point a = ...;

ColoredPoint b = ...;

a.equals(b) // false, a says b is not a 'Point'

b.equals(a) // true, b says my 'color-ness' is irrelevant, I'm a Point -- represent!

The only way to ensure that a. equals(b) and b.equals(a) is always true is to reify the equality relation into its own first-class type or method.

class Point { public static boolean operator_equals(Point a, Point b); }

It's too bad that Java and other languages do not offer first class support for operators. a == b can be shorthand for Point.operator_equals(a, b). If there is any ambiguity at all (because b is a subclass and there exists a method ColoredPoint.operator_equals()) then raise an error and force the developer to be explicit about exactly which equality operator is intended. If such a method doesn't exist then raise an error and force the developer to say exactly what is intended by equality. (Don't fall back to reference equality!).

This would eliminate a whole lot of bugs and all the confusion around equality.

I think that if Liskov's principle is respected, a shouldn't care about b not being of the same class. Rather, b could rightfully complain about the colorless thing it is compared to - although it wouldn't be wise to do so.

Inheritance is just a scapegoat here. Changing the definition of the equality in the subclass is probably a design mistake (because it's confusing and error prone).

The core of the problem is that, contrary to trivial things like integers, with complex objects one may be interested in defining different equivalence relationships in different parts of the same application. If everyone insists to use the = sign to note "their" equality, inevitably there will be conflicts.

So in a way, not allowing to highjack the = operator (or == depending on how the language expresses assignment) and keep it for identity (i.e. address equality) could actually be the sane approach. In your example, renaming "equals" to "hasSameCoordinates" wouldn't be bad practice, I believe.

This.

What is relevantly the same in one application may not be relevant in another. Equivalently, differences between objects may or may not matter, depending on the application.

One can go further to say that in many settings the correct output to an equality-query may appropriately depend on the identity of the caller.

I re-read your comment a couple times, and understood your main point to succinctly be this:

If `Point` is a subclass of `ColoredPoint`, and `p` and `cp` exist as instances respectively, there is ambiguity between `p == cp` and `cp == p`.

In Python there is first class support for operators: the `eq` dunder method:

    def __eq__(self, other):
        if not isinstance(other, type(self)):
            return False
        return self.point == other.point

This ambiguity is hard to solve around.

This doesn't really solve the ambiguity. You can do the same in Java (and people often do):

   if (getClass() != other.getClass())
      return false;

This does guarantee that equality is symmetric but it's also troublesome. First, you have to trust everybody to do this comparison. If one type forgets then symmetry breaks. But also, sometimes, in the case of value objects like Points you do want equality between different types. Point2D and Point3D and RasterPoint all have x,y coordinates and should be equatable.

The proposal is to capture equality (and all other operators) as static methods.

   class Point2D {
      public static boolean operator_equals(Point2D p1, Point2D p2) { ... }
   }

   class ColoredPoint {
      public static boolean operator_equals(ColoredPoint cp, Point2D p2) { ... }
   }

In certain cases the compiler can unambiguously determine that there is a single static method that defines equality then this can be invoked by 'a == b' and we can also be sure that 'b == a' because both refer to the same method.

The point here is that equality is not something that can be decided by one object, it is an operator that establishes relations between types of objects. There's a very fundamental difference between sending a message to a single object and establishing a relation and this is the source of all the confusion around equality.

A solution was suggested by the grandparent: make `a==b` call both equality methods.

Dunno if you raise or just return false if they disagree.

I was working on a hobby language a few years ago and trying to figure out a way to handle equality to avoid these problems. One solution I considered was:

1. Ask the LHS for its equality function.

2. Ask the RHS for its equality function.

3. If the two return different functions (non-identical), the objects are not equal.

4. Otherwise, return the result of invoking the function.

The first two steps are polymorphic, so objects can define interesting equality semantics with whatever policy makes sense for them. But step 3 ensures that the two objects must agree on that policy before you can compare them.

> One solution I considered

It sounds pretty reasonable, but I have no idea how "sounds reasonable" correlates with "is helpful in practice". (I think one of the commenters in the linked page might have raised that point too.)

Fulfilling axioms of equality definitely does sound useful for being able to write code, though -- having symmetry, not having to think about whether you need to write `a==b` or `b==a`, seems like it'd lighten the cognitive load.

I suppose also when the objects disagree about equality you also have some license to say "this may not do quite what you expect" and do your best to make the most of it.

> I was working on a hobby language a few years ago

Hah, you're famous enough that we've all probably heard of the language if it has seen the light of day ;-).

My own hobby language has no methods or dynamic dispatch of any kind, haha. It's a little stressful to have to come up with some equality rule that works for essentially every use-case, though -- I don't think it's sufficient to enumerate the data types in the language, I really have to go over all the ways I think they could be used :-/.

Oh well, it's fun at least.

Xtend allows defining extension methods for operator comparison: http://www.eclipse.org/xtend/documentation/203_xtend_express...

Could one resolve the problem by insisting that the properties that form part of the equality be part of all items in the class hierarchy.

eg. Even though Point may not have a color instance variable, there is no reason why it can't have a default color for all "plain" Points.

Of course, extending this to a smalltalk / ruby "Objects all the way down" hierarchy if Point inherits from Object then Object needs to have a default (x,y) position and colour.

It would seem mad to give place default values for every property of any object ever on the Object base class...

However one could provide default values for Point and ColoredPoint which the equality operator uses.

Most OO languages discriminate between identity and equality (e.g. == vs .equals() in Java, or id() vs == in Python). The relational model nails it even more explicitly.

You probably mean “‘is’ vs ‘==’ in Python” – nobody should use id() for identity comparisons in Python. For instance, two Python objects may, if they have non-overlapping lifetimes, have the same id() value.

If they don't have overlapping lifetimes, there would seem to be very little risk of accidentally considering them to be equal, because you could never reference them in the same expression.

True in practice, but you can reference them in the same expression if one lifetime ends at the expression and the other is created there. Eg:

  p = (id([]) == id([]))
  : mklist 0 # alloc -> 0x1234
  : call id # free(0x1234)
  : mklist 0 # alloc -> 0x1234 (free list is a stack)
  : call id # free(0x1234)
  : cmp == # true

Not having heard of the `id` function in Python before, it still sounds like you can make mistakes with this; what if you saved the result of the `id` call of the first value into a variable and then compared it to the result of calling `id` on other values?

I'm sure this could happen somehow, but it's difficult to think of a concrete example of where it would matter.

Make wrong lifetime assumptions and you get data corruption.

I can imagine someone using it eg as an identifier in a web form, and passing it back to the app to lookup in some keyed data structure where they have used id as the keyfn - and getting back the incorrect object because the id has been recycled. Then it's saved to the db and you get data corruption.

Sure. But the problem stems not from identity and equality in OO. It stems from the coupling of state and identity, which has the side effect of muddying the waters between identity and equality too. To whit this discussion.

Direct link http://web.cecs.pdx.edu/~black/publications/egal.pdf

A lot of the complexity comes from having a top-level type (Object) and inheritance. Functional languages often don't have this, so comparing two objects of different types doesn't come up. (Collections don't contain objects of different types either.)

Sure, but most functional languages don't permit useful comparisons between functions of same type either, so while the complexity is limited, the power is limited as well.

Well, an equality function could be defined that compares closure values and instructions, as mentioned in the article.

As I understand it, the reason it isn't typically done is conceptual: two functions are mathematically equal if the same inputs produce the same outputs. (The same way you'd define equality for a hashmap by comparing keys and values.) But this is impossible to calculate for arbitrary functions.

The power to reason is limited in complex languages.

I'm assuming the title supposed to be a reference to The Left Hand of Darkness [0], a book that also deals with equality and comparisons.

[0] https://en.wikipedia.org/wiki/The_Left_Hand_of_Darkness

Edit: Ah, the reference is explicit inside the linked PDF, but I'll leave this up for anybody else is ctrl-f-ing to satisfy the same curiosity.

The identity stuff is fine.

But the talk about OO philosophy is the same old fool's gold. OO is a very useful filing system for organizing large amounts of code. Sure, code organization can tend to mirror code function, and even sometimes in some ways mirror parts of the application space. Philosophers could talk about that, but it's philosophy not coding.

The philosophy is a distraction, especially for new people learning OO.

So OO as a 'model of reality'? OO is a model of reality to about the same extent that the Dewey Decimal System is a model of reality. Every branch of "OO philosophy" that doesn't make this simple point clear is a barrier to entry.

Reply on news.ycombinator.com