Lambda the Ultimate

Fixed, sorry about that.

Part of what makes equality hard is that there are just so many different meanings of the word, and they're not all equal ;-)

Immutable values are easier to reason about, but even with them, there are questions. Take for example two immutable sets of data: Are they equal if they contain the same values? Yes, I would argue, until you point out that one of them is an ordered data structure and the other is not.

In the OO world (e.g. Smalltalk "=", Java "equals()"), we often ask one object if it is equal to the other. Now we are really in a conundrum, because if we ask the unordered set if it is equal to the other, it is only too happy to answer "Yes!!!", while asking the ordered set the same question would result in a resounding "No." Of course, you could always ask each of them in turn, to make sure that they agree, but that seems almost criminally inefficient.

Should equality be reflexive? It isn't in Java (see NaN for example).

Should equality be symmetric? It isn't if you have to ask one of the two objects to evaluate equality.

Should equality be transitive? Ironically, if the above two properties cannot be guaranteed, transitivity seems almost pointless.

A couple points:

* Having two (or even eight) explicit forms of equality (reference versus value) is (IMHO) horrid.

* The David Ungar quote is beautiful, but it is also not reflective of real world use. ("Basically, given two references, A and B, A == B implies that for any message M, you could send M to A or send M to B and there would be no observable change in the future response to messages of the system.") It's a very dogmatic interpretation of equality, and would preclude our sorted set (from the example above) to be used in place of an unsorted one.

* The Andrew Black quote (“An application ...may have its own notion of identity that differs from the underlying system”) is spot on. I think this points to the kernel of the equality problem.

I got excited when they acknowledged that a single equality operator for a language was a good thing, but unfortunately the paper quickly devolved from the abstract perfection of that suggestion to a plethora of equality approaches, and we were right back where we began.

I do think that there is a solution to this problem for strongly typed languages, and I would propose that the solution is shockingly simple: base equality on the compile time type of the objects being compared, not on the runtime type. This is the model that we adopted, and thus far, it has not shown any holes. However, until used in anger, its weaknesses will not be exposed.

It is not surprising that equality has so many variants, because it essentially encodes the notion of equivalence. And because equivalence is formally always "up to" some system of observation, the question becomes how to encode such a system. If this is true, then there should be even many more variants of equality.

I agree with that. I once made a list. Didn't end. Leibnitz equality, structural equality, confluence equality, intentional and extensional equality, ..

I would be interested in someone doing an analysis of it.

But the lens that you're looking through when you ask the question "are these two things equal" ... that lens seems to be the type of the things themselves, i.e. the aperture through which you see the things.

I am not sure I get you. But let's continue! If math fails, maybe mysticism will help!

You say "the lens is the type of things themselves", I say "the type doesn't describe the thing!"

(EDIT: I suck at this. Forget it.)

By "lens", I mean the _means_ of interacting with a value, an object, a reference, whatever. In C++, perhaps it's the pure virtual class type that a pointer is defined with. In Smalltalk, it's the messages that the caller is certain that an object can respond to. In Java, it's the interface type that (e.g.) a parameter is declared with.

So while an object may be capable of much more (e.g. a sorted order) than you know of it, the "lens" that you see it through says "this is a set". So when you compare it to another thing through the same lens, you really don't care about their order or the lack thereof, because you are viewing them both simply as "sets".

You seem to argue that an ordered set _should_ answer "No" if it is asked whether it is equal to an unordered set with the same elements. If I am interpreting that correctly, why do you think so? It seems like a reasonable design choice for it to answer "Yes".

I guess it depends on what you mean by "public fields". I assume they're talking about the kind of public fields that exist in languages like Scala or Kotlin, where using what looks like a public field is really syntactic sugar for a private field with a public getter (and a public setter if the field is mutable), or like ES6, where the distinction between fields and accessor methods exists, but can be safely ignored in most situations.

IMHO C++ and Java are really behind the times in this area. It bugs me because using explicit accessor methods introduces a lot of boilerplate definitions, and it severely limits the usefulness of field-access syntax, forcing developers to use method-call syntax instead. Method-call syntax is more verbose and less visually distinctive than field-access syntax, resulting in a small but significant loss of readability in almost every nontrivial piece of code in those languages.

Good points. I have no qualms with C++ fields, since the only "hiding" done from a C++ developer is the encapsulation and hiding done by the C++ developer (i.e. in C++, one hides underlying fields and structures simply to maintain one's own sanity, with varying degrees of success, and nothing hidden can stay hidden in C++ if one chooses to dig for it.)

In a higher level OO language, I'd prefer a model that separates the virtual domain entirely from the non-virtual domain, such that a concrete concept like a field simply disappears. Ideally, the need for storage (struct) for the state (fields) of an object should be infer-able from the design of the object. By doing so, the storage aspects disappear from the interface of the object entirely, leaving a pure behavioral interface, which itself is virtual in composition. (I hope to know soon enough how this approach works out ;-)