[R6RS] a totalization of equal?

[William D Clinger]

As mentioned in the "non-opaque record equality" thread...

I propose we define an always-terminating predicate, say
equiv?, that always returns the same value as equal? when
equal? actually terminates and returns a value.

If we had finite mappings with amortized constant-time
lookups based on object identity, we could implement a
version of equiv? that runs in O(n) time and space,
where n is the size of the larger of the objects being
compared.

Even if we restrict ourselves to portable R5RS Scheme,
and use linear-time lookups based on lists, we can still
implement a version of equiv? that runs in O(n) space
and O(n^2) time for the worst case, and runs in O(n)
time for most common cases.  Note that the R5RS equal?
procedure does not run in polynomial time, even when
restricted to acyclic structures.

For a prototype implementation of equiv?, see
http://www.ccs.neu.edu/home/will/R6RS/equiv.sch
http://www.ccs.neu.edu/home/will/Research/ILC2005/Source/run-benchmark.chez

The second of these files defines the run-benchmark
procedure for Chez Scheme, and can be modified for
most other systems.  That procedure is needed only
to run the benchmarks.

I ran the benchmarks on my old SunBlade 100 in Chez
Scheme v6.1 (optimize-level 2) and Larceny v0.90, with
(representation-inference #f) to turn off a compiler bug.
The table below shows the ratios obtained by dividing the
run time for equiv? by the run time for the system's
predefined equal? procedure.  The main reason Larceny's
ratios are smaller than Chez's is that Chez Scheme's
pre-defined equal? procedure is faster than Larceny's.

                                               ratios
                                           Chez      Larceny
equality0:10     circular flat list         .0          .0
equality1:10     DAG (much sharing)        9.5         3.5
equality2:7      tree (no sharing)         8.5         3.0
equality3:1000   flat list                 3.2          .7
equality4:300    shallow list             13.5         4.2
equality5:500    worst case             1450         715
equality5:1000   worst case             2650        1225

The last two lines confirm the algorithm's O(n^2) behavior.

Will