<div dir="ltr"><div>Implementation attached for review.<br></div><div><br>This is a direct port of the Chez version. <br>One thing that needs to be improved is the handling of structs, as it currently only checks to see if the struct is opaque and if not it directly compares fields (instead of also checking individual fields for opaqueness). <br></div><div><br></div><div>Marc, I want to open a PR -- but where should I put it?<br></div><div>It has a dependency on random-integer as it needs to randomize to avoid pathological inputs.<br></div><div>so it can't quite go in _system.scm<br></div><div><br></div><div>-- vyzo<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 14, 2017 at 4:46 PM, Dimitris Vyzovitis <span dir="ltr"><<a href="mailto:vyzo@hackzen.org" target="_blank">vyzo@hackzen.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Thanks, that explains a lot!<br><br></div>I think it makes sense to port the Chez version, i'll prepare a patch.<br><br></div>-- vyzo<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 14, 2017 at 4:30 PM, Matthew Flatt <span dir="ltr"><<a href="mailto:mflatt@cs.utah.edu" target="_blank">mflatt@cs.utah.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>At Thu, 14 Sep 2017 16:21:29 +0300, Dimitris Vyzovitis wrote:<br>
> > Have you looked at how other implementations of Scheme do this?<br>
><br>
> I looked at chibi which has a native C impl, and racket which is insanely<br>
> complex.<br>
> No definitive answer yet on how to resolve the edge case properly.<br>
<br>
</span>Here's a paper about Chez Scheme's implementation:<br>
<br>
 Efficient nondestructive equality checking for trees and graphs.<br>
 Adams & Dybvig, ICFP'08<br>
 <a href="http://www.cs.indiana.edu/~dyb/pubs/equal.pdf" rel="noreferrer" target="_blank">http://www.cs.indiana.edu/~dy<wbr>b/pubs/equal.pdf</a><br>
<br>
I think the union-find aspect is probably what you're looking for.<br>
<br>
Here's the current implementation:<br>
<br>
 <a href="https://github.com/cisco/ChezScheme/blob/master/s/5_1.ss#L31" rel="noreferrer" target="_blank">https://github.com/cisco/Chez<wbr>Scheme/blob/master/s/5_1.ss#<wbr>L31</a><br>
<br>
Probably less interesting/useful, but Racket-on-Chez currently has its<br>
own `equal?` to support chaperones and impersonators, and it has the<br>
same union-find part:<br>
<br>
  <a href="https://github.com/racket/racket7/blob/master/racket/src/cs/core/equal.ss" rel="noreferrer" target="_blank">https://github.com/racket/rack<wbr>et7/blob/master/racket/src/cs/<wbr>core/equal.ss</a><br>
<br>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>