equal? and primitive arrays

[Jamison Hope]

On Oct 7, 2011, at 8:02 PM, Per Bothner wrote:

> 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.

Ah, of course.

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

Indeed. That's a problem for any containers (arrays, lists, vectors,  
etc)
that can directly or indirectly contain themselves.

> 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.

I'll tackle the primitive arrays for now and think about how to handle
cycles as a separate patch.

--
Jamison Hope
The PTR Group
www.theptrgroup.com