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@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
Afficher les réponses par date
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@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@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
-
Dimitris Vyzovitis