Hacker News Reader

Comment by edejong | Hacker News Reader

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

In most languages, I prefer to think of equality as a property outside of structure or class. Languages such as Java bind equals() strongly with the object, but this is a mistake. First of all, it promotes ordering where there is none. Equality is reflexive and symmetric. Second of all, it does not allow for multiple forms of equality. Lastly, since it is defined in Object, it forces the equality relation to all underlying types, even when there is no equality defined.

[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/E...

View on HN

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.

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.

The only thing .net could have done differently was to make Equals and GetHashcode into interfaces and perhaps included some best practices.

== is there for legacy reasons, and meaning reference equality with the ability to overload it, seems like a reasonable compromise for object types. What we're missing is the ability to create custom value types, that consist of other value types. We already know that it's working with F#, so the CLR does support it. Question is if C# the language can be extented with it.

.net could have made equality entirely optional; and it could have exposed machinery to implement equality (including all aspects of it!) by composition, not manual fiddling - at least not by default!

That would have made .net less memory-hungry, faster, less bugprone, and simpler.

There's absolutely no good reason for this horribly complicated and inefficient state of affairs; not all platforms/languages suffer from these limitations. As you point out, even F# manages to do better despite the considerable extra limitation of needing to maintain some sort of compatibility even at runtime with the current crazy state, and despite what is certainly a much more limited development budget.

In hindsight there is a lot they should have done differently. Immuteable by default and not nullable by default are two of the obvious. But they where targeting Java developers, so they couldn't just bring a completely different language to the market. They had to be a better Java.

Yes Equals and GetHashCode should have been in an interface.

After 13years of full time .NET it's the only thing I repeat over and over to newer devs: don't override equals and hash code . Use explicit comparers in your dictionaries because equality is rarely property of your THING, it's a property of the use case. I'd prefer the noise of having to always pass an explicit comparer to a Dict constructor, just for clarity.

A similar but related thing they got wrong was the possibility to format strings without an explicit formatter. The result of this? Run all unit test suites for all C# projects on a French/Swedish machine (decimal comma) and I can guarantee that most that involve any kind of formatting will fail because of it. I'd be delighted if they changed this behavior, breaking compatibility with every single C# program ever written, that's how bad it is.

You don't have much say in Equals and GetHashCode when using objects for for instance ItemSource for a ComboBox. But it's not that bad, you just need to have a senior dev sign off the implementations.

A Control that does comparisons isn't much different from any other class that does internal comparisons- just like for a Set or Dictionary. If objects didn't have a default Equals/GetHashCode then all constructors for Dictionaries (And combo boxes) would take an IEqualityComparer argument.

It does complicate things quite a bit because WPF declares things in XAML, and giving constructor arguments is a major pain. You could make it a DependencyProperty, but it's still convoluted.

I'm sure it's already possible and you could make the call default implicit so if you don't pass an equality comparer it just uses DefaultParer.Instance which does what the current default (object) comparer does.

Agree with everything here. I posted an example [1] of how this can be solved now with C# (although in reality it just adds another 'equality solution' to the mix). It uses ad-hoc polymorphism to implement a type-class (interface) and instance (struct) approach, similar to Haskell. There's no IEqualityComparer instance allocation cost either.

[1] https://news.ycombinator.com/item?id=12954790

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.

What is an example of a type that should not have an equality?

The most obvious are lambdas (anything in this package, basically):

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

While anonymous functions should really only have reference equality, I still think the Java designers fucked up in extending this to method references. this::foo != this::foo, which is a bit painful for registering event listeners when you want to remove them later again. For those things you have to store the reference in a field.

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.

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.

    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.

With more context we could probably agree that it's not unnecessary computation if you want to do anything useful with the data.

Indeed. And you only have to do it once, you can then store the result (you should probably make that calculation lazily, though).

Lazily or not, that would be a global design decision (use a lazy language or not)

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.

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

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.

> Or maybe there is some trick to compare them without simplifying.

a / b == c / d is equivalent to a * d = c * b, although whether that's a good approach depends on a lot of things.

Clojure supports rational type and it does simplify them.

(def a (/ 1 2)) (def b (/ 8 16)) (= a b) true

"Has the same hash value" is a very important set of equality relations which can depend on many factors.

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?

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?

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.

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.

You made great points, and I've realized that the compiler/interpreter doesn't always know what's the part of the context that we are actually interested in. There's often too much context available and it's not always easy to throw away the information that we're not interested in. However when one does manage to make a function to a structural representation that contains exactly the interesting things, then equality is this function followed by structural equality.

    "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!

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.

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.

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?

> 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"?

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.

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

>Is the equation y=3x+2 equal to y-2=3x?

Sorry, had to be pedantic. These equations are not equal under usual mathematical and logical definitions of equality applied to equations. They do possibly express the similar relationships between the variables.

But I agree with your general point. "Equals" has different definitions in different contexts.

> These equations are not equal under usual mathematical and logical definitions of equality applied to equations. They do possibly express the similar relationships between the variables.

Could you elaborate? The second sentence in particular surprises me - don't these necessarily express exactly the same relationship between the variables?

I'm not sure he's right at all. I'd define any equation "a" which can be re-arranged to equation "b" to be equal ie. a==b

They are the same thing. Thusly

    y=3x+2

is equal to

    10y-20=30x

is equal to

    5y-15x=10

etc

It's been a while since uni, but I don't remember any other mathematical definition of equations being considered equal. I guess the thought is something about what is being defined in terms of what (y= vs x=) but I don't think that's a meaningful distinction between two equations.

Turns out, there are many more interesting equivalence relations on values than simply structural equality!

... that all need to be called .equals()? No - that's actually the best argument for structural equality, since that is the "minimal" equality.

I agree. Lots of language make it too hard to use custom equivalence or ordering relations.

> Is the angle -90 equal to 270?

This is trickier than it might seem. Is this a description of static geometry, or is this a delta that I'm going to want to interpolate/integrate/etc?

In the latter case, -90 is very different than 270, which is different than 630...

How would you want the compiler to compare graphs for equality? Graph isomorphism is a hard problem.

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.

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

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.

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

Reply on news.ycombinator.com