impls/lib/equality.mal

   1 ;; equality.mal
   2
   3 ;; This file checks whether the `=` function correctly implements equality of
   4 ;; hash-maps and sequences (lists and vectors).  If not, it redefines the `=`
   5 ;; function with a pure mal (recursive) implementation that only relies on the
   6 ;; native original `=` function for comparing scalars (integers, booleans,
   7 ;; symbols, strings, keywords, atoms, nil).
   8
   9 ;; Save the original (native) `=` as scalar-equal?
  10 (def! scalar-equal? =)
  11
  12 ;; A faster `and` macro which doesn't use `=` internally.
  13 (defmacro! bool-and                    ; boolean
  14   (fn* [& xs]                          ; interpreted as logical values
  15     (if (empty? xs)
  16       true
  17       `(if ~(first xs) (bool-and ~@(rest xs)) false))))
  18 (defmacro! bool-or                     ; boolean
  19   (fn* [& xs]                          ; interpreted as logical values
  20     (if (empty? xs)
  21       false
  22       `(if ~(first xs) true (bool-or ~@(rest xs))))))
  23
  24 (def! starts-with?
  25   (fn* [a b]
  26     (bool-or (empty? a)
  27              (bool-and (mal-equal? (first a) (first b))
  28                        (starts-with? (rest a) (rest b))))))
  29
  30 (def! hash-map-vals-equal?
  31   (fn* [a b map-keys]
  32     (bool-or (empty? map-keys)
  33              (let* [key (first map-keys)]
  34                (bool-and (contains? b key)
  35                          (mal-equal? (get a key) (get b key))
  36                          (hash-map-vals-equal? a b (rest map-keys)))))))
  37
  38 ;; This implements = in pure mal (using only scalar-equal? as native impl)
  39 (def! mal-equal?
  40   (fn* [a b]
  41     (cond
  42
  43       (sequential? a)
  44       (bool-and (sequential? b)
  45                 (scalar-equal? (count a) (count b))
  46                 (starts-with? a b))
  47
  48       (map? a)
  49       (let* [keys-a (keys a)]
  50         (bool-and (map? b)
  51                   (scalar-equal? (count keys-a) (count (keys b)))
  52                   (hash-map-vals-equal? a b keys-a)))
  53
  54       true
  55       (scalar-equal? a b))))
  56
  57 (def! hash-map-equality-correct?
  58   (fn* []
  59     (try*
  60       (bool-and (= {:a 1} {:a 1})
  61                 (not (= {:a 1} {:a 1 :b 2})))
  62       (catch* _ false))))
  63
  64 (def! sequence-equality-correct?
  65   (fn* []
  66     (try*
  67       (bool-and (= [:a :b] (list :a :b))
  68                 (not (= [:a :b] [:a :b :c])))
  69       (catch* _ false))))
  70
  71 ;; If the native `=` implementation doesn't support sequences or hash-maps
  72 ;; correctly, replace it with the pure mal implementation
  73 (if (not (bool-and (hash-map-equality-correct?)
  74                    (sequence-equality-correct?)))
  75   (do
  76     (def! = mal-equal?)
  77     (println "equality.mal: Replaced = with pure mal implementation")))