[gambit-list] Implementation of equal? for recursive structures

Dimitris Vyzovitis vyzo at hackzen.org
Thu Sep 14 09:46:23 EDT 2017


Thanks, that explains a lot!

I think it makes sense to port the Chez version, i'll prepare a patch.

-- vyzo

On Thu, Sep 14, 2017 at 4:30 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:

> At Thu, 14 Sep 2017 16:21:29 +0300, Dimitris Vyzovitis wrote:
> > > Have you looked at how other implementations of Scheme do this?
> >
> > I looked at chibi which has a native C impl, and racket which is insanely
> > complex.
> > No definitive answer yet on how to resolve the edge case properly.
>
> Here's a paper about Chez Scheme's implementation:
>
>  Efficient nondestructive equality checking for trees and graphs.
>  Adams & Dybvig, ICFP'08
>  http://www.cs.indiana.edu/~dyb/pubs/equal.pdf
>
> I think the union-find aspect is probably what you're looking for.
>
> Here's the current implementation:
>
>  https://github.com/cisco/ChezScheme/blob/master/s/5_1.ss#L31
>
> Probably less interesting/useful, but Racket-on-Chez currently has its
> own `equal?` to support chaperones and impersonators, and it has the
> same union-find part:
>
>   https://github.com/racket/racket7/blob/master/racket/
> src/cs/core/equal.ss
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20170914/a3686ab6/attachment.htm>


More information about the Gambit-list mailing list