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

[Pierpaolo Bernardi <olopierpa@x>]

On Thu, Aug 30, 2012 at 9:30 PM, Ray Dillinger <bear@x> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 08/30/2012 11:57 AM, Ray Dillinger wrote:
>
>> 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."
>
> Actually, as I consider the above, there is one case where I'm
> not comfortable with this definition. Vectors can have elements
> whose printed representation is not part of the "infinite
> printed representation" if there is a cycle that starts before
> those elements.  Consider two arrays, each of which has itself
> as its own second element:
>
> V1 ==>   #1=#(1 #1 6)
> V2 ==>   #2=#(1 #2 9)
>
> (equal? V1 v2) ==> ?
>
> The infinite printed representation is identical, well past the
> point where both have entered their cycle at least twice. Both
> would show "#(1 #(1 #(1 #(1 #(1 #(1 ......"  But they can't be
> considered equal? because
>
> (equal? (vector-ref V1 2) (vector-ref V2 2)) => #f
>
> It requires cycle-aware print to distinguish the written
> representation.
>
> So, given the above, I think it's necessary that equal? should
> detect structural isomorphism (written representation under
> cycle-aware printing is equal) rather than generation of
> identical infinite sequences ("infinite" written representation
> up to second entry of cycle is equal).

No need to resort to vectors, the same counterexample also invalidates
the list case:

V1 ==>   #1=(1 #1# 6)
V2 ==>   #2=(1 #2# 9)

(equal? V1 V2) ==> ?

[I think, in this context, "circular" does not mean only circular in the spine]

P.

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