17 ms·

Equality is an often overlooked complexity in denotational semantics. Dijkstra wrote an EWD [1] on the subject, which should give insight into the difficulties

• jstimpfle 10y ago
  Multiple forms of equality: I think there should be just one "equality": the obvious structural one, which can be inferred by a compiler. What examples are there of cases where there is no obvious equality but still the official "equality" tag is needed? EDIT: got downvoted, why? It's a serious question. I've never had any use for any equality besides the structural one. Honestly want to see if anyone can come up with a valid case.
  • mcbits 10y ago
    new Rational(2, 3) == new Rational(4, 6) You could implement Rationals to be structurally equal by simplifying them immediately on construction, but that may be a lot of unnecessary computation in some cases.
    • jstimpfle 10y ago
      With more context we could probably agree that it's not unnecessary computation if you want to do anything useful with the data.
      • hota_mazi 10y ago
        Indeed. And you only have to do it once, you can then store the result (you should probably make that calculation lazily, though).
        • jstimpfle 10y ago
          Lazily or not, that would be a global design decision (use a lazy language or not)
      • mcbits 10y ago
        In a formula with multiple Rationals, it wouldn't always be necessary to simplify them before using them. You could just simplify the result if/when it's compared to another result. Also, the UI may need to display the unsimplified fraction. If you simplified them immediately, you'd have to store a factor somewhere to reconstruct the original (and not in the Rational class because that would ruin structural equality). In other words, "equal" for I/O purposes and "equal" for mathematical purposes could be different.
        • jstimpfle 10y ago
          How'd you compare the unsimplified number then? How would it be obvious at the calling site what happens? Better explicitly compare only the simplified part (again, structurally).
          • mcbits 10y ago
            The most straightforward way would be to simplify during the equivalence check and maybe cache the value. Or maybe there is some trick to compare them without simplifying. Point is that you can have a notion of "equal but not identical". No doubt it's also possible to represent rationals with only structural equality, but I'd have to see two competing implementations to judge which is more intuitive to use.
            • dllthomas 10y ago
    • smnplk 10y ago
      Clojure supports rational type and it does simplify them. (def a (/ 1 2)) (def b (/ 8 16)) (= a b) true
  • Retra 10y ago
    "Has the same hash value" is a very important set of equality relations which can depend on many factors.
    • jstimpfle 10y ago
      IMO comparing hashes instead of just comparing would only make sense if it's semantical, i.e. explicit at the call site. Why not call equals explicitly on the hash values? Can you make a case for keeping it implicit?
      • Retra 10y ago
        I don't know why implicit equality is relevant here. The idea is that you'd explicitly recognize that there are multiple forms of equality, and that the one you want depends almost entirely on the problem domain. So you shouldn't have any 'implicit' or 'preferred' equality. You'd always let the call site dictate which equality relation it needs. You asked for a non-structural equality relation, and I gave you a whole class of them. There are many more. There isn't even one kind of 'structural equality': are two things equal if they have the same memory layout? The same AST representation? What if the layout depends on the allocator? What if they are identical but must be treated differently through aliases?
        • jstimpfle 10y ago
          You agree it should be explicit. But notice that explicit hash equality is just hashing followed by structural equality. Considering different abstraction levels like AST or memory layout: This is moving up and down the levels of abstraction. It's conventional wisdom that you shouldn't do this in a single context (like a function, module, or even a programming language). But it's a good point - powerful languages like C present all these levels at once. In other words, there is often an impedance mismatch. Structural equality might be not quite the same to the compiler and to the programmer.
          • Retra 10y ago
            And structural equality is just a special (also arbitrary) kind of hash equality. You still have to specify what kind of structure you're comparing. The "structural equality" that you are referring to is vague not uniquely determined.
  • louthy 10y ago
    "ABC" == "abc" Depending on the context, case insensitive equality checking may be required. Also precision on floating point value comparisons. An interesting approach to this in C# (and other languages) is to use ad-hoc polymorphism: public interface Eq<A> { bool AreEqual(A x, A y); } public struct EqInt : Eq<int> { public bool AreEqual(int x, int y) => x == y; } public struct EqDbl : Eq<double> { public bool AreEqual(double x, double y) => Math.Abs(x - y) < 0.00001; } public struct EqStringExact : Eq<string> { public bool AreEqual(string x, string y) => x == y; } public struct EqStringIgnoreCase : Eq<String> { public bool AreEqual(string x, string y) => String.Equals(x, y, StringComparison.CurrentCultureIgnoreCase); } public static class GenericCode { public static A UseFirstIfEqual<EQ, A>(A fst, A snd) where EQ : struct, Eq<A> => default(EQ).AreEqual(fst, snd) ? fst : snd; } GenericCode.UseFirstIfEqual<EqInt, int>(10, 10); // 10 GenericCode.UseFirstIfEqual<EqInt, int>(10, 20); // 20 GenericCode.UseFirstIfEqual<EqDbl, int>(10.0, 10.0); // 10.0 GenericCode.UseFirstIfEqual<EqDbl, int>(10.0, 20.0); // 20.0 GenericCode.UseFirstIfEqual<EqStringExact, string>("ABC", "abc"); // "abc" GenericCode.UseFirstIfEqual<EqStringIgnoreCase, string>("ABC", "abc"); // "ABC" It's slightly more novel than the interface approach, and allows for retrospective equality behaviours to be authored for a sealed type, and importantly, for the selection of the most appropriate equality operation for any particular context. I don't have a compiler to hand, so apologies for any errors!
  • jstimpfle 10y ago
    Found a use case: performance optimizations. If there are functional dependencies that the compiler doesn't know, some fields don't need to be compared.
  • tel 10y ago
    Quotients are often used to describe new behavior. You could reasonably say that this ought to define a new type, but it's still an example of a meaningful coarsening of equality. For example, to define rational numbers using only integers you take a rational to be a pair (n, d) but with a new equality such that (1, 2) and (2, 4) are equated.
  • Coincoin 10y ago
    Is the angle -90 equal to 270? Is the quotient 1/2 equal to 3/6 Is the string "Bébé" equal to "Bebe"? Is the float 0.555555559 equal to 0.6? Is the color RGB(1,1,1) equal to Lab(100,0,0)? Is the equation y=3x+2 equal to y-2=3x? Is the function x=>2+x equal to y=>2+y?
    • jstimpfle 10y ago
      > Is the angle -90 equal to 270? > Is the quotient 1/2 equal to 3/6? I think these are good examples that come up in the real world a lot. The representation structures we use are not sufficient for precise specification. So we have to overspecify (making a superfluous choice in representation, -90, 270, 630?). My opinion still is that data must be normalized with explicit procedure calls. Doing stuff implicitly is neither beneficient to efficiency nor to comprehensibility. Explicit normalization allows to leverage what the compiler _can_ infer. The other questions I have to return because it's not even clear to me, "Should they be"?
      • mbrock 10y ago
        Whether they should be depends on your needs, so it's nice to be able to choose the equality semantics for your application's types.
      • dllthomas 10y ago
        > My opinion still is that data must be normalized with explicit procedure calls. Doing stuff implicitly is neither beneficient to efficiency nor to comprehensibility. It can certainly benefit comprehensibility. Needing to explicitly normalize before I can apply standard comparisons leaves more space for things to go wrong. "Having a value of this type means that I have a normalized value" means I have fewer things to keep track of. (I do note that there is significant space between "it can benefit comprehensibility" and "it will always benefit comprehensibility" - that depends on what I need to be readily able to pull out of the implementation from a quick read of surface syntax) Also, some things may have an easy equality check while normalizing may be expensive or impossible - although I sadly can't think of any examples off the top of my head.
    • 10y ago
  • justinpombrio 10y ago
    How would you want the compiler to compare graphs for equality? Graph isomorphism is a hard problem.
    • jstimpfle 10y ago
      I seem to think of equality as something trivial. Granted that structural equality isn't graph isomorphism. But I don't see why something as specific and performance-sensitive as that deserves the tag "equality". Make a function graphsIsomorphic(), where's the problem? Btw. in my practice (writing really dull code, and some algorithms) I've never seen the need for complex equality functions. In practice I test IDs - typically integers or short strings.
  • dllthomas 10y ago
    I feel like all of the responses are missing most of your question. As I read you, you understand that there are other questions we might want to ask, but why not call them "compareRationals" or whatnot rather than giving them all the same name? I think that it comes down to a question of interfaces/abstraction. Quite a few languages provide you interfaces for asking both questions, "are these structurally equivalent" and "are these practically equivalent" for whatever choice of "practical".
    • jstimpfle 10y ago
      Thanks for putting it that way. I realize "equality" and "equivalence" gets confused a lot here. Equality is a special case of equivalence. It seems absurd to me to have more than one equality.
      • dllthomas 10y ago
        > It seems absurd to me to have more than one equality. Mathematics has several. Probably the most useful for CS is the notion from logic of "extensional equality" - two things are equal if I can't tell them apart. But we quickly want to restrict what approaches we can use, or for most languages that would necessarily be reference equality. Structural equality is one such restriction. For an abstract data type, there's a strong line of reasoning that would say two values should be equal if they aren't distinguishable through the abstraction.
• bunderbunder 10y ago
  This is another thing that I think .NET got (mostly) right, though the overall shape of things is complicated enough that it's still easy to get tripped up if you don't know all the details. .NET has: - Several basic ways doing comparisons: the == operator, the object.Equals() method, and the object.ReferenceEquals() method. == is intended to be for referential equality, and object.Equals() can optionally be overridden to implement value equality. == can be overridden (though it's not generally recommended), which is why there's the separate ReferenceEquals() method for when you absolutely must compare references. - An IEqualityComparer interface for implementing custom equality. Collection classes that rely on determining if objects are equal (e.g., hash sets and dictionaries) let you supply one of these so that you can do purpose-specific equality. - IComparable interface for when you want to implement a default ordering on a type. - IComparer interface for when you want to use custom ordering rules.
  • emn13 10y ago
    This is one of the things .net did pretty terribly wrongly for it includes equals and GetHashCode on every object. Not only is that autocompletion (and api) pollution of the absolutely worst kind (infects every "thing" in the language!) it also lends itself to bugs; so most people simply don't implement Equals or GetHashCode at all, or only with tools. If you do, it's easy to get wrong; and the built-in api has no guiderails to help avoid trivial mistakes (why is plain equality by composition so hard to express?). Furthermore, the default choice of reference equality means that in particular reference types need to have some GC-surviving notion of identity. And that means that every reference type has a larger object header: and memory density matters hugely to performance. It's quite conceivable to imagine a system with no object header at all, or more conservatively, only with a (potentially optional) type id. The built-in api further makes it natural to implement non-symmetric or non-reflexive "equality", and it binds the definition of equality tightly to the type, when in fact (as you point out with IEqualityComparer) equality can easily be perspective dependent. Edit: Probably by virtue of professional brain damage through years of getting used to the status quo I almost overlooked another bit of insanity: The fact that Equals is not equivalent to "operator ==" ! That simply makes no sense whatsoever, you just have to get used to it. To be clear: it's fine (in rare but necessary niche cases) to have multiple equality relationships; it's a nasty gotcha to spring that on the reader without warning. And to add insult to injury the operators == and != are barely related - there's little help in ensuring they're mutually consistent. Fortunately, .net has value types, and those by default implement sane equality rules, right? Well... structs work in some sense, but it's not always desirable to couple something with such specific GC and performance characteristics to a semantic, so it's not a trivial switch. And then - the implementation by default of struct only "works" in some academic sense of the word. Sure, it correctly determines equality by composition, but it doesn't implement all the api's (operators and generic interfaces) so it's not always practical, and the performance is consistently very bad (reflection!), and somethings surprisingly terrible: in particular, the hashcode computation ignores some fields and can even ignore all fields due to what can only be described as the worst hashcode algorithm in common use. Even when the GetHashCode does use all fields it's very slow, and it mixes bits so poorly that common data causes unnecessarily many hash collisions. Frankly: struct's equality is a trap, and it's not broadly applicable anyhow. All in all, to implement something that should be trivial (say: A is equal to B if and only if all components of A are equal to the respective components of B) correctly in a broadly applicable way you'd need to implement not just one method, but five: object.Equals, object.GetHashCode, IEqualityComparer<T>.Equals, operator ==, and operator !=. Just don't make any typos when copy-pasting all that boilerplate, because testing these for correctness isn't easy, and it is easy to end up in a situation that is appears superficially correct but has bugs in corner cases. So, I'd call equality and related features in .net pretty terribly designed. It looks to me like they didn't think this through and simply copied java 1.0 a little too closely. In fact, I challenge you to name a language that's worse in this regard.
• tikhonj 10y ago
  Equality in general is a surprisingly subtle subject. "When is one thing equal to some other thing?"[1] is a fun article about it. Java's equals method has two core problems in my eyes: it forces every type to define equality (when some types really shouldn't) and it lets you compare any two values, even if they don't have compatible types. My Java is rusty, but I think an Eq<T> interface comparable to Comparable<T> would be a reasonable design: public interface Eq<T> { public boolean equals(T o); } In particular, I don't mind the fact that there can be at most one equals per type: it's a sensible default 99% of the time. Most things that admit some sort of equality have an "obvious" default equality that makes sense; it's fine to make other comparison functions more explicit. Weird types with no obvious default equals method just shouldn't implement that interface. Worst case, you could just construct a wrapper that exposes a particular equals for that type.
  • jayd16 10y ago
    What is an example of a type that should not have an equality?
    • berdario 10y ago
      The most obvious are lambdas (anything in this package, basically): https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html https://docs.oracle.com/javase/8/docs/api/java/util/function... Iterable/Iterator in general might also be problematic, since they might yield an infinite sequence of values (trying to equate them would loop indefinitely... obviously you can write a concrete class that is guaranteed to iterate a finite number of times, but this means that you should then implement an Equality interface only for them) Also, anything that is thus closely related to Streams, references to stuff in the outside world or things that aren't easily Serializable (and thus are probably not Value Objects), like File Handles/Sockets (you might compare them by reference, obviously) Also, Float and Doubles should arguably not implement an Equality interface. Rust for example does not have them implement Eq, but rather PartialEq due to NaN. Any Product (composite) or Sum type containing any such value might also not make sense to implement value equality PS: I think that Tikhon forgot to link the document he mentioned, this should be it: http://abel.math.harvard.edu/~mazur/preprints/when_is_one.pdf http://abel.math.harvard.edu/~mazur/preprints/when_is_one.pd...
• wyager 10y ago
  I like the way Haskell does it; equality is provided via the "Eq" typeclass. The language supports auto-deriving "Eq" instances that do a straightforward structural and sub-structural equality check (e.g. if I have data Foo a b = Foo a b Int, then (Foo a1 b1 i1) == (Foo a2 b2 i2) = (a1 == a2) && (b1 == b2) && (i1 == i2)), but you can define it yourself it for types that have more representations than semantic values, like sets or maps or finger trees.