The Tyranny of Triple-Equals

JavaScript is a language that I love which nonetheless has more than its fair share of weird warts. I can live with the strange syntax choices and the various foot-guns that cannot be removed without breaking backwards compatibility. But while I’ve come to terms with the bad features of JavaScript, I still struggle with the missing features. Consider how equality works in JavaScript:

let x = [1,2,3];
let y = [1,2,3];
let z = x;
x === y // => false
x === z // => true

Here x !== y because objects are compared with reference equality: x and y have the same contents but refer to different objects. In some cases, this behavior is exactly what you want: x and y may be identical now, but they are not interchangeable in the way that x and z are. If we think of the objects at x and y as locations where state lives, it is crucially important that we can distinguish between these locations.

But in a lot of cases, we just want to know if two objects have the same contents — we want to know if they are structurally equivalent — and JavaScript has no built-in way to answer that. Instead, we have to depend on third-party workarounds, which can have significant file size costs and lack the interoperability of standardized solutions.

Let’s look at some of the possible workarounds for structural equality: how do the third party libraries work? What are the pain points this approach? And how would the language incorporate these features in a way that preserves backwards compatibility?

Shallow and deep equality functions

The most common approaches to testing structural equality in JavaScript are “shallow” and “deep” equality functions. Shallow equality (as used by “pure components” in React) compares each property in a pair of objects or arrays; if the values of each object’s property are equal (by reference equality), then the objects are structurally equal. “Deep” equality, as in Node’s assert module or Lodash’s isEqual function, applies this recursively — two objects are deeply equal if the values of each object’s property are deeply equal.

However, there’s a number of implementation difficulties and edge cases that complicate this:

• How do you compare objects with circular references?
• If objects have identical properties, but different prototypes, are they equal?
• How should get/set properties be handled?
• Should objects compare their non-enumerable properties?
• Keys in an object are ordered — i.e. Object.keys({ x: 1, y: 2 }) gives different results than Object.keys({ y: 2, x: 1 }) -- should that matter for structural equality?
• How should you handle private properties, or methods that use closures to simulate this?

No deep equality function will provide a satisfactory answer for all of these edge cases, which has made TC39 reluctant to standardize. But for the sake of argument, what if the behavior of Lodash’s isEqual entered the language as Object.equals (or even x ==== y!) Would that be sufficient?

Equality protocols

Not quite. ES6 introduced Map and Set; while objects could only support strings as keys, maps and sets could use any object as a key. But maps and sets use reference equality for their keys, which dramatically limits how useful objects as keys can be:

let map = new Map()
map.set({ x: 1, y: 2 }, 3)
map.get({ x: 1, y: 2 }) // => undefined

It is not enough to have one function that supports structural equality; it has to permeate the language. Libraries like Immutable.js or Mori that support structural equality do so by implementing their own maps, sets, objects and arrays that speak a common protocol: Immutable’s data structures have an equals method that tests structural equality, and a hashCode method that's used to speed up map & set lookups.

This is how equality is implemented in many languages: Java uses equals and hashCode methods, Rust uses Eq and Hash traits, Python uses __eq__ and __hash__methods. JavaScript would probably use a "well-known symbol" like the Iterator protocol:

class Record {
  [Symbol.equals] (other) { ... }
  [Symbol.hashCode] () { ... }
}

The major problem here is that, to preserve backward compatibility, this would either require new object types or new map & set types; this protocol could not be safely added to both. Returning to our previous example:

let map = new Map()
map.set({ x: 1, y: 2 }, 3)
map.get({ x: 1, y: 2 })

This would now return 3, instead of undefined, in environments where the protocol was supported on both plain objects and maps. Likewise, this would still require a new function or operator for testing structural equality.

There’s also the “moral hazard” of incorrect or inappropriate implementations of equality and hashing. Java, for example, has a notoriously slow and unreliable implementation of URL equality. (If you think non-transitive == is bad, just imagine what people could do with their own custom equality functions!)

Immutable records

Let’s return to the original premises — what does reference equality imply? While its often described in terms of “pointer equality”, that’s not actually how its implemented. Consider strings:

class Foo { }
let x = "Foo"
x === Foo.name // => true

x and Foo.name aren't stored at the same location in memory, but are considered equivalent. Why? because they are functionally identical; strings that are === equivalent have no distinguishing properties, and there is no scenario where one would ever need to distinguish between one instance of "Foo" from another. If two strings are === equal, they have no distinguishing characteristics; no differing metadata, no hidden properties, nothing. Furthermore, two equal strings can never become unequal because they are immutable. You can reassign the value of x, but you can't mutate the string itself; you can't change its text or add properties to it.

These properties — indistinguishability and immutablity — could hold for more complex structures as well. These structures would need to be a lot simpler than “regular” JS objects — no prototype chain, no special properties. This includes stuff like the order of properties: ie. if #{ x: 1, y: 2 } and #{ y: 2, x: 1 } are equivalent, they should also return the same key order for Object.keys.

The immutable data structures proposal for JavaScript follows this approach — instead of adding a protocol for comparing arbitrary objects, add data structures that can be functionally identical, and therefore can safely be compared using ===.

There are a few cases for why this proposal is a better fit for JavaScript than the others:

• It introduces new objects, but does not change any existing ones, and thus avoids any backwards compatibility issues.
• It does not require any new operators, functions, or protocols, because immutable records compare with === and can work as keys in existing maps & sets.
• It avoids the edge cases with deep equality because immutable records have no prototype chain and only enumerable "normal" fields.
• It doesn't prevent future proposals for custom equality and hashing, and removes such a proposal’s need to include its own structurally comparable objects.

The primary disadvantage of this proposal is that, while (contrary to popular belief) its not literally impossible to polyfill, it requires one to store every immutable value that has ever been created. As far as I know, there are no popular libraries that implement this flavor of immutable records, though one can implement it terms of Immutable.js maps.

Conclusions

Its worth noting that none of these proposals are remotely novel. JavaScript users have probably been writing deep equality functions since day 1, equality and hashing protocols are present in nearly every other language created in the last 30 years, and structural equality-by-default for immutable data structures is fundamental to functional programming. Each of these has been proposed in some form or another for official inclusion in the language, but ultimately dismissed — deep equality for its limitations and unavoidable edge cases, equality and hashing protocols for their complexity and possibility for abuse, and immutability for implementation difficulties and … lack of interest.

Frankly, JavaScript is a big tent language, and the most JavaScript-y solution would be to adopt all of these approaches. You can even define them in terms of each other — objects using the equality protocol can delegate to Object.equals, and immutable records can use the hashing protocol to make map lookups in their backing data store more efficient. But JavaScript must adopt some form of structural equality. The status quo is unacceptable; structural equality is as fundamental a feature to modern programming as closures, dictionaries or lexical scope.

Thanks to Jonathan Dahan, Dan Abramov, and David Nolen for background & feedback.