Equality Considered Harmful

Implementing optimized versions of certain operations is typically both useful and fun. However, once the implementations have to replicate a particular equality predicate, verifying - or at least testing - becomes a nightmarish experience. Let us dive knee-deep in the behavioral predicates of different equality definitions.

The simplest equality eq? is when we are comparing a primitive value to itself. For example two integers or two pointers to immutable objects like to the same list:

(define x 1)
(eq? x x)
; => #t
(define y 1)
(eq? x y)
; => #t
(define z '(1))
(eq? z z)
; => #t
(define w '(1))
(eq? z w)
; => #f

With this type of equality it should be easy to write a predicate which returns #t if and only if the given procedure satisfies it. Remember this is not a formal verification, just a set of positive and negative tests of the behaviour meant to catch obvious mistakes.

(define (eq?-behaviour? p)
  (define x '(1))
  (define y '(1))
  (define z (+ 1.0 1.0))
  (define w (+ 1.0 1.0))
  (and (p x x)
       (not (p x y))
       (not (p z w))))
(eq?-behaviour? eq?)
; => #t
(eq?-behaviour? eqv?)
; => #f
(eq?-behaviour? equal?)
; => #f
(eq?-behaviour? equal-always?)
; => #f

Now we want similar behavioral predicates for all the remaining three common equalities. Looking at the eqv? documentation tells us that it should behave almost the same as eq? with basically the exception of handling boxed floating-point values like equal? would. Testing that should be easy by constructing two distinct floating-point values with the same value:

(define (eqv?-behaviour? p)
  (define x '(1))
  (define y '(1))
  (define z (+ 1.0 1.0))
  (define w (+ 1.0 1.0))
  (and (p x x)
       (not (p x y))
       (p z w)))
(eqv?-behaviour? eq?)
; => #f
(eqv?-behaviour? eqv?)
; => #t
(eqv?-behaviour? equal?)
; => #f
(eqv?-behaviour? equal-always?)
; => #f

The next one should be easy as equal? captures the usual equality as humans tend to understand it. With one caveat though - it must distinguish between equal? and equal-always? behaviour somehow. With equal-always? returning #t if and only if both values are eq? or if and only if they point to the same immutable value. Therefore equal? should return #t for two boxes with the same wrapped value while equal-always? should return #f. This allows extending our behavioral tests to produce the following:

(define (equal?-behaviour? p)
  (define x '(1))
  (define y '(1))
  (define z (+ 1.0 1.0))
  (define w (+ 1.0 1.0))
  (define a (box 1))
  (define b (box 1))
  (and (p x x)
       (p x y)
       (p z w)
       (p a b)))
(equal?-behaviour? eq?)
; => #f
(equal?-behaviour? eqv?)
; => #f
(equal?-behaviour? equal?)
; => #t
(equal?-behaviour? equal-always?)
; => #f

And because our main concern with this predicate was how to distinguish it from equal-always?, writing the last behavioral predicate is as easy as negating a single expression:

(define (equal-always?-behaviour? p)
  (define x '(1))
  (define y '(1))
  (define z (+ 1.0 1.0))
  (define w (+ 1.0 1.0))
  (define a (box 1))
  (define b (box 1))
  (and (p x x)
       (p x y)
       (p z w)
       (not (p a b))))
(equal-always?-behaviour? eq?)
; => #f
(equal-always?-behaviour? eqv?)
; => #f
(equal-always?-behaviour? equal?)
; => #f
(equal-always?-behaviour? equal-always?)
; => #t

In the end it looks pretty straightforward. However pin-pointing all the cases correctly can make your brain hurt - which some of us truly consider harmful. Perhaps this should have been just a small case against equality, right?

Hope you liked this little venture into behavioral predicates (and all those obivous puns) and make sure to tune in next time!