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

Dimitris Vyzovitis vyzo at hackzen.org
Thu Sep 14 13:04:09 EDT 2017


Implementation attached for review.

This is a direct port of the Chez version.
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).

Marc, I want to open a PR -- but where should I put it?
It has a dependency on random-integer as it needs to randomize to avoid
pathological inputs.
so it can't quite go in _system.scm

-- vyzo

On Thu, Sep 14, 2017 at 4:46 PM, Dimitris Vyzovitis <vyzo at hackzen.org>
wrote:

> 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/f8950ffe/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: equal.scm
Type: text/x-scheme
Size: 15645 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20170914/f8950ffe/attachment.bin>


More information about the Gambit-list mailing list