[R6RS] a totalization of equal?

[dyb at cs.indiana.edu]

> 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'm happy to consider it for R6RS, but I would like a motivation.
Has anyone actually had a need for such a predicate?  I don't even make
use of equal? all that often, except in my intro course, and don't recall
ever wanting to apply it to cyclic structures.

I'd also like to point out that there is another at least equally
reasonable semantics for equiv?.  With the proposed semantics,
equiv? actually equates different graphs.  For example (sorry for the
crude ascii art):

   +--------------------+
   |                    |
   v                    |
 +---+---+   +---+---+  |
 | o | o-+-->| o | o-+--+
 +-|-+---+   +-|-+---+
   |           |
   v           v
   a           b

is equiv? to

   +--------------------------------------------+
   |                                            |
   v                                            |
 +---+---+   +---+---+   +---+---+   +---+---+  |
 | o | o-+-->| o | o-+-->| o | o-+-->| o | o-+--+
 +-|-+---+   +-|-+---+   +-|-+---+   +-|-+---+
   |           |           |           |
   v           v           v           v
   a           b           a           b

and even to

               +---------------------+
               |                     |
               v                     |
 +---+---+   +---+---+   +---+---+   |
 | o | o-+-->| o | o-+-->| o | o-+-->+
 +-|-+---+   +-|-+---+   +-|-+---+
   |           |           |
   v           v           v
   a           b           a

In graph-printing notation, this is

  (equiv? '#1=(a b . #1#) '#2=(a b a b . #2#))

and

  (equiv? '#1=(a b . #1#) '(a . #2=(b a . #2#)))

This doesn't just arise in the presence of cycles.  We also have

        +---+---+
        | o | o +
        +/--+--\+
        /       \
       /         \
      v           v
    +---+---+   +---+---+
    | o | o +   | o | o +
    +-|-+-|-+   +-|-+-|-+
      |   |       |   |
      v   v       v   v
      a   b       a   b

is equiv? to

        +---+---+
        | o | o +
        +-|-+-|-+
           \ /
            |
            v
          +---+---+
          | o | o +
          +-+-+-+-+
            |   |
            v   v
            a   b

That is,

  (equiv? '((a . b) . (a . b)) '(#1=(a . b) . #1#))

This is fine when testing the equivalence of finite automata, where such
differences are unimportant.  In our world of mutable data structures,
however, it strikes me as being at best only one of two reasonable
semantics for an equivalence predicate that works on cyclic as opposed
to acyclic graphs.  The other reasonable semantics is one that returns true
only if the two inputs have precisely the same structure.

The proposed semantics does have the property of behaving like equal? on
DAGS.  For example,

  (<pred> '((a . b) . (a . b)) '(#1=(a . b) . #1#))

is true whether <pred> is equiv? or equal?.  This would certainly be
a good thing for backward compatibility if we were talking about a
terminating version of equal?, which we may still want to consider.
But as long as equal? remains in the language as a separate entity, this
correspondence in (not the only "right") behavior is not necessarily
a virtue.

Understand that I'm not arguing for one semantics over the other,
just pointing out that there are two that are reasonable.  I'm also
questioning whether we need another equality predicate at all.  If others
think the predicate would be used sufficiently often and also agree on
the semantics, I have no objection to including it.  I'm also willing
to redefine equal? to have the semantics Will suggests for equiv? (for
pairs and vectors at least, if not for records) if there is general
agreement on that.

Kent