Re: [Scheme-reports] Cycle detection problems: #442, #338, "equal?"

[Ray Dillinger <bear@x>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 08/30/2012 05:51 AM, David A. Wheeler wrote:
> John Cowan:
>> Note that having a portable implementation of R7RS `equal?` is
>> not an issue, as all implementations are expected to provide it.
>> They may also (as Chibi does) also provide the R5RS `equal?`
>> function in a different library.
> 
> Okay.  I still think it's important that the spec clearly state
> what happens if a cycle is detected by "equal?".  I recommend text
> like "If a cycle is detected, #f is returned."  I'm guessing that's
> what many implementations with cycle-detection do (is that true?).
> 

I agree that the standard ought to clearly state what equal?
does in the presence of cycles.

The behavior I would prefer, however, is that outlined by
Per Bothner.

To state it precisely in terms clear enough for the standard
and also calculated to tell people exactly how to implement it:

"If one operand has a cycle and the other does not, then the
predicate returns #f.  If all have cycles, then iff the printed
representations of the structures are identical up to the
point when all have entered their cycles at least twice, then
the predicate returns #t."

The point is that if the above condition (identical up to
the point where each has entered its cycle at least twice) is
true, then the two structures generate the same infinite
sequence.

An alternative, also possibly useful, would be to check for
structural isomorphism; ie, the structures are equal up to
the beginning of their cycles, enter their cycles at the same
number of elements from the beginning, have cycles of
equivalent length, and the content of the cycles is equal.
But, while conceptually simpler, that predicate is even
more difficult to implement and probably slower.


				Bear


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJQP7ehAAoJEAOzWkqOibfN3ckIALHv7zJx3+fuy+rSbaoascx4
I9Q8E6OHMoMzIl/peyODhBsqduyfl1n2EhFSwdDpbM+ODimLwPXv6Zz1jNEmpPSX
bn/3aGFS5NMr2TWCw7MdhQSEh8zETXInc49ABA65iJscn3iLsZfEj/oZf4KWYM1a
2BLC9IjEbqBB0Yob4eYNCpRfoSgf4q4onamUntADRTVgY03nvvp/2NS+cfO54HKA
1BHkLs0wr9FDxZoU9KdKpYgIPYjPRODqFeVDOOMMgRMcxhDRBK5t7ImSx7XQfmd0
G9mojMDhExZyI8SWy5RA9/C2K93FVgxBfz7nGM4JW9XH5ppE6q2uUYbG62FlUoM=
=JEcC
-----END PGP SIGNATURE-----

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports