6 ms·

The Left Hand of Equals

mtreis86 8y ago
Direct link http://web.cecs.pdx.edu/~black/publications/egal.pdf http://web.cecs.pdx.edu/~black/publications/egal.pdf
nickbauman 8y ago
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?
- nine_k 8y ago
  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.
  - teddyh 8y ago
    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.
    - recursive 8y ago
      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.
      - saghm 8y ago
        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?
        recursive 8y ago
        I'm sure this could happen somehow, but it's difficult to think of a concrete example of where it would matter.
        fulafel 8y ago
        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.
      - a1369209993 8y ago
        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
  - nickbauman 8y ago
    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.
- dnomad 8y ago
  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.
  - dfee 8y ago
    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.
    - dnomad 8y ago
      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.
skybrian 8y ago
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.)
- myWindoonn 8y ago
  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.
  - skybrian 8y ago
    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.
  - willtim 8y ago
    The power to reason is limited in complex languages.
anythingbotB 8y ago
> ignores ZFC > ignores Naive Set Theory by Paul Halmos > ignores algebra > ignores group theory whatever, dude
- sctb 8y ago
  Is there a PLT Tumblr somewhere where people post like this? If so, please do it there and not here. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
Terr_ 8y ago
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 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.
mcnamaratw 8y ago
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.

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

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?

nine_k 8y ago
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.
- teddyh 8y ago
  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.
  - recursive 8y ago
    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.
    - saghm 8y ago
      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?
      - recursive 8y ago
        I'm sure this could happen somehow, but it's difficult to think of a concrete example of where it would matter.
        fulafel 8y ago
        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.
    - a1369209993 8y ago
      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
- nickbauman 8y ago
  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.
dnomad 8y ago
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.
- dfee 8y ago
  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.
  - dnomad 8y ago
    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.

skybrian 8y ago

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

myWindoonn 8y ago
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.
- skybrian 8y ago
  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.
- willtim 8y ago
  The power to reason is limited in complex languages.

anythingbotB 8y ago

> ignores ZFC > ignores Naive Set Theory by Paul Halmos > ignores algebra > ignores group theory whatever, dude

sctb 8y ago
Is there a PLT Tumblr somewhere where people post like this? If so, please do it there and not here. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

Terr_ 8y ago

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

mcnamaratw 8y ago

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.