On Equality (in JavaScript)

<!-- START doctoc generated TOC please keep comment here to allow auto update --> <!-- DON'T EDIT THIS SECTION, INSTEAD RE-RUN doctoc TO UPDATE -->

Table of Contents generated with DocToc

• Breaking News
  • Should Key Ordering Matter in Objects?
  • ECMAScript6 Classes and Type Checking
    • Segue on The Miller Device
• Deep Equality acc to deep-equal-ident
• jsEq
• Language Choice and Motivation
• Test Module Setup
• Implementations Module Setup
• Equality, Identity, and Equivalence
• First Axiom: Value Equality Entails Type Equality
• Equality of Sub-Types
• Equality of Numerical Values in Python
• Second Axiom: Equality of Program Behavior
• Infinity, Positive and Negative Zero
• Not-A-Number
• Object Property Ordering
• Properties on 'Non-Objects'
• Primitive Values vs Objects
• Undefined Properties
• Functions (and Regular Expressions)
• How Many Methods for Equality Testing?
• Plus and Minus Points
• Benchmarks
• Libraries Tested
• Caveats and Rants
• Multiple References and Circularity
  • Multiple References
  • Circularity
• To Do

<!-- END doctoc generated TOC please keep comment here to allow auto update -->

Breaking News

Should Key Ordering Matter in Objects?

• key ordering used to be an accidental property of JS objects
• constance of key ordering (key ordering by definition order) always used to be silently implemented by most popular engines because reasons
• now it's in ES XXX so it's official
• question is, should x = { a: 1, b: 1, }, y = { b: 1, a: 1, } be equal or not equal?
• conventionally key ordering is considered irrelevant for equality, so x eq y should hold
• but sometimes key ordering is used, so x eq y should fail
• propose to agree upon setting a symbol (Symbol.x_orderedkeys) to signal objects that should be keeping key ordering (tested as x[Symbol.x_orderedkeys]?)
• deriving from specific class (class OrderedKeysObject extends Object) possible but better not done as it would conflict with other more important uses of custom classes
• what to do if x has that property but y lacks it?
  • always reject equality because 'x has something that y is lacking', or else
  • assume that x_orderedkeys is 'contagious' but not 'dominant', i.e. presence in any one value mandates checking for ordered keys
• should also be possible to configure test whether to check for this, or use special method (eq_with_ordered_keys())

<!-- ``` coffee> Symbol.iterator Symbol(Symbol.iterator) coffee> Symbol.x undefined coffee> Symbol[ 'iterator' ] Symbol(Symbol.iterator) coffee> Symbol[ Symbol.for 'iterator' ] undefined coffee> Symbol.x_orderedkeys ?= Symbol 'x_orderedkeys' Symbol(x_orderedkeys) coffee> Symbol [Function: Symbol] { x_orderedkeys: Symbol(x_orderedkeys) } ``` -->

ECMAScript6 Classes and Type Checking

UPDATE this topic is dealt with in more detail in InterType.

Whenever one thinks one has tamed the utter madness that is JavaScript's type system, one can be reasonably sure another one of the Hydra's ugly heads is waiting right behind the corner. This happens with ECMAScript6 Classes.

Let us go on a Journey in Five Parts where I'd like to define a class that extends JS Array; I then instantiate it and poke at it with all the sonic screwdrivers I have. This looks good until I use either typeof or the old trusty (but, by now, a bit rusty) Miller Device to ascertain the class name of that thing:

# Preface. Packing for the Journey.
# ---------------------------------

types = new ( require 'intertype' ).Intertype() # https://github.com/loveencounterflow/intertype
class Myclass extends Array

# Chapter I. Embarking on the Boat.
# ---------------------------------

d = new Myclass()             # in REPL, correctly echoes `Myclass(0) []`, `0` being array length

# Chapter II. No Problems (So Far.)
# ---------------------------------

Array.isArray d               # `true`, no problem
d instanceof Array            # `true`, no problem
d instanceof Myclass          # `true`, no problem
types.isa.list d              # `true`, no problem

# Chapter III. OMG It's the Titanic
# ---------------------------------

typeof                  d     # 'object'; NB that `( typeof [] ) == 'object'`
types.type_of           d     # 'list' (our name for JS `Array` instances)
Object::toString.call   d     # 'Miller Device', gives '[object Array]'

# Chapter IV. One Single Raft Left.
# ---------------------------------

d.constructor.name            # 'Myclass'! Yay!

Turns out only d.constructor.name does the trick—let's call it the Dominic Denicola Device since he wrote the top-rated SO answer to this pressing question back in 2015.

So let's try and see what the DDDevice can do for us.

In essence, we just need to set up a function ddd = ( x ) -> x.constructor.name; the only problem with that is of course that checking attributes on null and undefined will fail loudly (as if JS ever cared but whatever), so we have to safeguard against that; these two definitions are equivalent:

ddd = ( x ) -> if x? then x.constructor.name else ( if x is null then 'null' else 'undefined' )
ddd = ( x ) -> x?.constructor.name ? ( if x is null then 'null' else 'undefined' )

Our ddd() method does give reasonable answers (for a JS type detecting method):

ddd {}                  # 'Object'
ddd []                  # 'Array'
ddd null                # 'null'
ddd true                # 'Boolean'
ddd 42                  # 'Number'
ddd NaN                 # 'Number'
ddd Infinity            # 'Number'
ddd ( new Myclass() )   # 'Myclass'

Segue on The Miller Device

A code comment from 2010 (CND Types module):

It is outright incredible, some would think frightening, how much manpower has gone into reliable JavaScript type checking. Here is the latest and greatest for a language that can claim to be second to none when it comes to things that should be easy but aren’t: the ‘Miller Device’ by Mark Miller of Google (http://www.caplet.com), popularized by James Crockford of Yahoo!.*

As per https://groups.google.com/d/msg/nodejs/P_RzSyPkjkI/NvP28SXvf24J, now also called the 'Flanagan Device'

• http://ajaxian.com/archives/isarray-why-is-it-so-bloody-hard-to-get-right
• http://blog.360.yahoo.com/blog-TBPekxc1dLNy5DOloPfzVvFIVOWMB0li?p=916 # page gone
• http://zaa.ch/past/2009/1/31/the_miller_device_on_null_and_other_lowly_unvalues/ # moved to:
• http://zaa.ch/post/918977126/the-miller-device-on-null-and-other-lowly-unvalues

Deep Equality acc to deep-equal-ident

GitHub user fkling has recently published deep-equal-ident, where he wants to "track[...] the identity of nested objects". That may sound a bit cryptic at first, but should become clear when considering two example test cases:

#                             #1
a   = [ 1, 2, 3, ]
b   = [ 1, 2, 3, ]
foo = [ a, a, ]
bar = [ b, b, ]

deepEqualIdent foo, bar       # true

#                             #2
a   = [ 1, 2, 3, ]
b   = [ 1, 2, 3, ]
foo = [ a, a, ]
bar = [ a, b, ]

deepEqualIdent foo, bar       # false

The gist of the comparison policy of deep-equal-ident is this: for two objects foo, bar to be deeply equal, we should expect that they contain deeply equal values at the same indices. now, if we inspect foo and bar, we find that both objects in both cases do have x[ 0 ][ 0 ] == 1, x[ 0 ][ 1 ] == 2, x[ 1 ][ 0 ] == 1, and so on, so at a glance, foo and bar should be considered deeply equal.

However, we've all learned in school that when you have an equation like x == y * 4, that equation must still hold when transformed in a way that does the same to the left and the right hand term; for example, you might want to divide both sides by four, which gives you

                  x       y * 4
x = y * 4   =>   ———  == ———————   =>   x / 4 == y
                  4         4

So far so good. Now consider what happens in test case #2 when we manipulate a or b. We start out with assuming foo == bar. Then we perform the same operation on the left and the right hand side, say

                  | foo[ 1 ][ 0 ] += 1
foo == bar   =>   |                      =>   ?
                  | bar[ 1 ][ 0 ] += 1

Does equality still hold or has it been violated? Indeed, the latter is the case: when we say foo[ 1 ][ 0 ] += 1, we're really doing a[ 0 ] += 1, since foo[ 1 ] is a (foo[ 1 ] is identical to a). But a is also referenced as the first element of foo, so foo[ 0 ] changes along with foo[ 1 ], which means foo is now [ [ 2, 2, 3, ], [ 2, 2, 3, ], ].

OK great, what with bar? Doing bar[ 1 ][ 0 ] += 1 gives [ 2, 2, 3, ] alright, but in *this