equal? and primitive arrays

[Per Bothner]

On 10/07/2011 04:06 PM, Jamison Hope wrote:
> I was a little surprised today to discover that
> (equal? (byte[] 1 2) (byte[] 1 2))
> returns #f. Obviously Java arrays are outside the scope of the
> Scheme report, but it would seem to be in the spirit of equal?
> for that to return true. Would it be worthwhile to write a patch
> for IsEqual.java to defer to java.util.Arrays#equals() and
> java.util.Arrays#deepEquals() in the case of arrays?

Well, it's reasonable but not correct.  Using Arrays#equals is fine
for primitive array types, but not object arrays.  The main problem
with Arrays#deepEqual is the "base case" is Object#equals, but for
us the base case should be IsEqual#apply.  However, doing deepEqual
by hand is easy enough - just use the same logic as FVector.

A bigger (but unrelated) problem is that R6RS (and draft R7RS) require
that equals "must always terminate, even if its arguments contain cycles."

The basic cycle-safe equal? implementation is as follows:
Maintain a mapping (Object,Object)->boolean for previously-seen calls.
(This mapping uses the System.identityHashCode on both operands.)

recursiveEquals(Object arg1, Object arg2, Map2 seen) {
     if (arg1 == arg2)
       return true;
     if (arg1 == null || arg2 == null)
       return false;
     Boolean wasSeen = seen.lookup(arg1, arg2);
     if (wasSeen != null)
          return wasSeen.booleanValue();
     seen.set(arg1, arg2, Boolean.TRUE); // protect against cycles
     boolean r = coreEquals(arg1, arg2, seen);
     seen.set(arg1, arg2, Boolean.valueOf(r));
     return r;
}

One might try to be clever so the seen table is only allocated
if we recursing, in some way or other.

The Map2 data structure is somewhat unusual.  One possibility is
to just use an IdentityHashMap<Object,IdnetityHashMap<Object,Boolean>>.
A custom hash table has hash is calculated as
   (System.identityHashCode(arg1) ^ System.identityHashCode(arg2))
could be more efficient.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/