Equality

gistfile1.txt

This is an annotated test suite for an equality proposal based on our
discussion yesterday.  There are two equality predicates, equal and identical,
which I've written with operators =? and == respectively (we should argue
about that separately).  I'm also trying out the is%(pred) syntax, and I've
added a provisional "isnot" testing form that I think seems pretty darn useful
for testing the negation of equality.

I've sketched out a proposal for how we should deal with function errors in
nested comparisons.  I think it can be implemented efficiently and has
deterministic semantics.  Here's the spec (without refs, but the
accumulator-graph extension is orthogonal to the three-valued thing going on
here):

    IsEqual= { true, false, err }

    equal : Val x Val -> IsEqual

    equal(num1, num2) --> num1 math= num2
    equal(str1, str2) --> str1 string= str2
    equal({ _equals: v11, f2: v12 ... } as o, v) --> o._equals(v)
    # (note, same exact field names match up below)
    equal({ f1: v11, f2: v12 ... }, { f1: v21, f2: v22 ... }) -->
      equal-and(equal(v11, v21), equal(v12, v22), ...)
      ...
    equal(lam(): e end, lam(): e end) --> err
    equal(method(): e end, method(): e end) --> err

    # non-matching tags is false
    equal(_, _) -> false

    equal-and : IsEqual x IsEqual -> IsEqual
    equal-and(true, true) -> true
    # False *always wins*.  Even if functions are compared at some point, if you
    # see some values that don't match and you can use to prove falsity, do it
    equal-and(_, false) -> false
    equal-and(false, _) -> false
    # However, if everything else is true, throw the error if functions or methods
    # were compared at some point
    equal-and(err, true) -> err
    equal-and(true, err) -> err

Annotated tests below:

    check:

      # Some values that we'll use
      f = fun(): 5 end
      g = fun(): 4 end
      m = method(self): 5 end
      n = method(self): 4 end
      x-5 = { x: 5 }
      xy = { x: 5, y: 6 }
      yx = { y: 6, x: 6 }

      eq-all = { _equals(_, _): true end }
      eq-none = { _equals(_, _): false end }

      # These will be bound in the default namespace
      equal = (_ =? _)
      identical = (_ == _)

      # We can argue about the syntax of these operators separately

      # "is" uses equal by default -- it's sugar for is%(equal)

      # =? works structurally, so both of these are true
      x-5 is { x: 5 }
      x-5 is x-5

      x-5 isnot%(identical) { x: 5 }
      x-5 is%(identical) x-5

      # Order of fields doesn't matter structurally
      xy is yx

      # But obviously not identical objects
      xy isnot%(identical) yx

      # Values of incompatible types can be proven observably different, so we say
      # so (and the behavior is for both operators):
      f isnot 5
      5 isnot f
      x-5 isnot f
      f isnot x-5

      f isnot%(identical) 5
      5 isnot%(identical) f
      x-5 isnot%(identical) f
      f isnot%(identical) x-5

      # This even holds for methods and functions
      f isnot m
      m isnot f

      f isnot%(identical) m
      m isnot%(identical) f

      # And nested (since 5 is clearly not a function, comparison sucessfully
      # fails)
      { x: f } isnot { x: 5 }

      # But when two functions or two methods are compared, we cannot know, so we
      # raise:
      (m =? n) raises "un-equalable"
      (n =? m) raises "un-equalable"
      (m =? m) raises "un-equalable"
      (n =? n) raises "un-equalable"
      (f =? g) raises "un-equalable"
      (g =? f) raises "un-equalable"
      (f =? f) raises "un-equalable"
      (g =? g) raises "un-equalable"

      (m == n) raises "un-equalable"
      (n == m) raises "un-equalable"
      (m == m) raises "un-equalable"
      (n == n) raises "un-equalable"
      (f == g) raises "un-equalable"
      (g == f) raises "un-equalable"
      (f == f) raises "un-equalable"
      (g == g) raises "un-equalable"


      # equal is not symmetric, because _equals is only called on the left element
      # Note that this is consistent with <=, etc.
      eq-all is 5
      5 isnot eq-all

      # identical is symmetric
      eq-all isnot%(identical) 5
      5 isnot%(identical) eq-all

      # Objects defining equals can return a value when compared to functions as
      # well
      eq-all is f
      eq-none isnot f

      # This doesn't affect identical
      eq-all isnot%(identical) f
      eq-none isnot%(identical) f

      # Note that underlying implementation eq is *not* an optimization for this
      # equality, because it isn't reflexive
      eq-none isnot eq-none

      # But identical is always reflexive
      eq-none is%(identical) eq-none

      x-f = { x: f, y: 5 }
      x-g = { x: g, y: 6 }

      # Since we can check that the y field differs, we can safely return false
      # here
      x-f isnot x-g

      # identical is not affected
      x-f isnot%(identical) x-g

      # Here, comparing structural equality requires visiting and comparing the x
      # field (since everything else is =?), so an error results
      # Note that using eq as an optimization here would have different semantics
      # again.
      (x-f =? x-f) raises "un-equalable"

      # Again, reflexivity is not affected for ==
      (x-f == x-f) is true

      x-f-nested-check = { x: f, o: { y: 6 } }
      x-g-nested-check = { x: g, o: { y: 6 } }
      x-f-nested-check2 = { x: f, o: { y: 7 } }
      x-g-nested-check2 = { x: g, o: { y: 7 } }

      # Even when the differing element is *nested*, we return false if possible
      x-f-nested-check isnot x-f-nested-check2
      x-f-nested-check isnot x-g-nested-check2
      # But if nothing differs nested, we "go back" and complain because we'd
      # have to compare f to f or g to g in order to prove equality, and we refuse
      # to do so
      (x-f-nested-check =? x-f-nested-check) raises "un-equalable"
      (x-f-nested-check =? x-g-nested-check) raises "un-equalable"

      # For completeness, the identical cases:
      x-f-nested-check isnot%(identical) x-f-nested-check2
      x-f-nested-check isnot%(identical) x-g-nested-check2
      (x-f-nested-check == x-f-nested-check) is true
      (x-f-nested-check == x-g-nested-check) is false

      data MList:
        | mlink(ref first, ref rest)
        | mempty
      end
      mlist = {
        make: fun(arr):
          # fold mlink over arr 
        end
      }

      graph:
        BOS = [mlist: WOR, PROV]
        PROV = [mlist: BOS]
        WOR = [mlist: BOS]
      end

      graph:
        SF = [mlist: OAK, MV]
        MV = [mlist: SF]
        OAK = [mlist: SF]
      end

      # Succeed because isomorphic structurally
      SF is BOS
      PROV is WOR
      PROV is OAK
      OAK is PROV

      # Fail because not identical
      SF isnot%(identical) BOS
      PROV isnot%(identical) WOR
      PROV isnot%(identical) OAK
      OAK isnot%(identical) PROV

      graph:
        ONES = mlink(1, ONES)
      end

      # These all are equal structurally because it chases the ref structure
      ONES is ONES
      ONES!rest is ONES
      ONES!rest!rest!rest!rest is ONES

      # These also are identical because ONES really is ONES:
      ONES is%(identical) ONES
      ONES!rest is%(identical) ONES
      ONES!rest!rest!rest!rest is%(identical) ONES
      
      data Stream<a>:
        | stream(first :: a, rest :: ( -> Stream<a>))
      end
      fun take(s :: Stream<a>, n :: Number) -> List<a>:
        if n <= 0:
          empty-list
        else:
          cons(s.first, take(s.rest(), n - 1))
        end
      end

      fun ones-f():
        stream(1, ones-f)
      end
      ones = ones-f()

      # Because the rest field gets compared, which is a function
      (ones =? ones) raises "un-equalable"

      # Because identical doesn't visit fields
      (ones == ones) is true

      # This gives false because functions aren't streams (but you might make this
      # typo; this would say values not equal "<function>", stream(1, <function>))
      ones isnot ones.rest
      ones isnot%(identical) ones.rest

      # Errors because more function comparison
      (ones =? ones.rest()) raises "un-equalable"
      (ones.rest() =? ones.rest()) raises "un-equalable"

      # Not errors, just false
      (ones == ones.rest()) is false
      (ones.rest() == ones.rest()) is false

      # This is how you should test the behavior of these (TEACHING MOMENT)
      take(ones, 5) is [list: 1, 1, 1, 1, 1]
      take(ones, 5) is take(ones, 5)

      fun mk-nats(n):
        stream(n, fun(): mk-nats(n + 1) end)
      end
      nats = mk-nats(1)

      (nats =? nats) raises "un-equalable"
      (nats =? nats.rest) raises "un-equalable"

      (nats == nats) is true
      (nats == nats.rest) is false

      # This one gives false because 1 and 2 differ
      mk-nats(1) isnot mk-nats(2)
      (mk-nats(1) =? mk-nats(1)) raises "un-equalable"

      # Identical has predictable results here:
      mk-nats(1) isnot%(identical) mk-nats(2)
      (mk-nats(1) == mk-nats(1)) is false

      # Again, here's how we should teach them to test:
      take(mk-nats(1), 5) is [list: 1, 2, 3, 4, 5]


      fun mk-set(elts):
        {
          to-list(self): elts end,
          pick(self):
            {
              element: elts.first,
              remaining: mk-set(elts.rest)
            }
          end,
          add(self, elt):
            if self.has-member(elt):
              self
            else:
              mk-set(link(elt, self.to-list()))
            end
          end,
          remove(self, elt):
            mk-set(self.to-list()^filter(equal, _))
          end,
          has-member(self, elt):
            found = self.to-list()^filter(equal, _)
            found.length > 0
          end,
          _equals(self, other):
            for fold(equal-acc from true, elt from self.to-list()):
              equal-acc and (other.has-member(elt))
            end
          end
        }
      end
      set = {
        make: lam(arr): mk-set(raw-array-to-list(arr)) end
      }

      s1 = [set: 1, 2, 3]
      s2 = [set: 1, 2, 3]

      # via _equals, avoids comparing the other methods and gets a useful answer
      s1 is s1
      s1 is s2
      s1.add(1) is s1
      s1.add(1) is s2

      s1 is%(identical) s1
      s1 isnot%(identical) s2
      s1.add(1) isnot%(identical) s1
      s1.add(1) isnot%(identical) s2

      # lists of sets work just fine, because the underlying algorithm will
      # call _equals on s1 and s2
      [list: s1, s2] is [list: s1, s2]

      # But obviously not identical
      [list: s1, s2] isnot%(identical) [list: s1, s2]

    end