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

[Aaron W. Hsu <arcfide@x>]

John Cowan <cowan@x> wrote:

> John Boyle scripsit:
>
> > ... I am tempted to suggest, as you seem to do, that we take a hybrid
> > approach and have "equal?" degrade to "isomorphic?" when a cycle is
> > detected (the way "write" is probably going to degrade to "write-shared"
> > when a cycle is detected).
>
> That's a non-conformant implementation of R7RS `write`, which is required
> to use labels only in the presence of cycles, not in the presence of
> structure-sharing.

While I disagree with the proposals here for EQUAL?, I don't think 
you are correct when you say that the above is a non-conformant 
implementation of WRITE. Indeed, I explicitly mentioned this to Alex, 
and in my voting rationale, but my understanding and expectation is 
that the easiest way to correctly implement WRITE given WRITE-SHARED 
and WRITE-SIMPLE is to check for cycles ahead of time, and if they 
exist, use the WRITE-SHARED variant, and if they do not, use WRITE-SIMPLE. 
The above says that WRITE degrades to WRITE-SHARED when a cycle is 
detected, which is the same thing. If it degrades to WRITE-SHARED 
when shared structures are detected, this would be non-conformant, 
but not when cycles are detected; this is the correct behavior.

I also think that an implementation may if it chooses use a different 
approach to ensuring that the cylces do not result in an infininite 
stream of output to the port. The output of WRITE in the presence 
of cycles need not match the output of WRITE-SHARED on the same input, 
but it may very well match it. It need only terminate having sent 
some valid output which is EQUAL? to the input when READ back in. 
And this brings up the point about EQUAL? which is not meant to 
compare pointer identities, but instead meant to check for some 
level of structural equality, and where I think the R6RS description 
of termination as stated in these lists seems reasonable enough.

> > Meanwhile, Will Clinger has a reference implementation of "unfolding",
> > Racket and probably others have full implementations, and R6RS
> > specifies it.
>
> Indeed, Chez, Vicare, Ypsilon, Mosh, and IronScheme all implement it
> correctly.  For whatever reason, Larceny returns #f at the REPL.

I believe that Michael Adams also has a paper on implementing EQUAL? 
efficiently. This is the method that Chez uses, I think.

-- 

Aaron W. Hsu | arcfide@x | http://www.sacrideo.us
Programming is just another word for the lost art of thinking.

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