[R6RS] a totalization of equal?

[William D Clinger]

I would appreciate some advice from the editors concerning
the always-terminating equiv? predicate I proposed.  If we
aren't likely to consider that for R6RS, should I write it
up and submit it to the SRFI process?

I have simplified and improved its portable implementation
quite a bit.  It now runs faster than Larceny's equal? on
all of the benchmarks I've been using, and is over 10 times
as fast on the DAG benchmark.  In Chez Scheme, it is within
a factor of 3 of Chez Scheme's equal? on all of the
benchmarks, and is 5 times as fast on the DAG benchmark.
In MzScheme, the interpreted equiv? is up to 40 times as
slow as the compiled equal?, which is written in C.  Of
course, the equiv? procedure is infinitely faster than
equal? on equal but circular inputs (unless they share
structure with each other, and often even then).

I have also implemented prototype hash-on-object-identity
hash tables in Larceny, which does not provide them as
part of its standard library.  With these hash tables,
the equiv? procedure runs in worst-case linear time for
inputs with several tens of thousands of objects. For
inputs that are built out of 100,000 distinct objects,
my prototype hash tables no longer provide lookups in
amortized constant time, so the algorithm is beginning
to degrade toward quadratic time.  With better coding,
I can postpone this problem for a while, probably to a
million or so objects, but I doubt whether I can get rid
of the problem altogether without some changes to the
object layout.

Will