Equality and hashing for new datatypes

Equality and hashing for new datatypes

[Philip McGrath]

[-- Attachment #1: Type: text/plain, Size: 1029 bytes --]

Hi,

What is the recommended way for a library to customize `equal?` and `equal?`
-based hashing for new datatypes it defines?

I know from [1] that `equal?` can be customized using GOOPS; however, some
projects do not use GOOPS (e.g. [2]), so it would seem more friendly for a
generic library to avoid it. Also, it is not clear if the same mechanism is
even an option for customizing `equal-hash` to match `equal?`.

I'm looking for something like Racket's `gen:equal+hash` [3] or Chez Scheme's
`record-equal-procedure` and `record-hash-procedure` [4].

This came up while I was working on a portable version of the immutable
hash-table implementations from Racket-on-Chez.

-Philip

[1]: https://www.gnu.org/software/guile/manual/html_node/GOOPS-Object-Miscellany.html
[2]: https://lists.gnu.org/archive/html/info-gnu/2023-05/msg00005.html
[3]: https://docs.racket-lang.org/reference/Equality.html#%28part._.Implementing_.Equality_for_.Custom_.Types%29
[4]: https://cisco.github.io/ChezScheme/csug9.5/objects.html#./objects:h14

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: Equality and hashing for new datatypes

[Taylan Kammer]

On 22.06.2023 00:25, Philip McGrath wrote:
> Hi,
> 
> What is the recommended way for a library to customize `equal?` and `equal?`
> -based hashing for new datatypes it defines?
> 
> I know from [1] that `equal?` can be customized using GOOPS; however, some
> projects do not use GOOPS (e.g. [2]), so it would seem more friendly for a
> generic library to avoid it. Also, it is not clear if the same mechanism is
> even an option for customizing `equal-hash` to match `equal?`.
> 
> I'm looking for something like Racket's `gen:equal+hash` [3] or Chez Scheme's
> `record-equal-procedure` and `record-hash-procedure` [4].
> 
> This came up while I was working on a portable version of the immutable
> hash-table implementations from Racket-on-Chez.
> 
> -Philip
> 
> [1]: https://www.gnu.org/software/guile/manual/html_node/GOOPS-Object-Miscellany.html
> [2]: https://lists.gnu.org/archive/html/info-gnu/2023-05/msg00005.html
> [3]: https://docs.racket-lang.org/reference/Equality.html#%28part._.Implementing_.Equality_for_.Custom_.Types%29
> [4]: https://cisco.github.io/ChezScheme/csug9.5/objects.html#./objects:h14

Hi Philip,

You can use SRFI 69 hash tables in Guile.  This library offers a way to specify
the equality and hash procedures that should be used by a hash table, e.g.:

  (import (srfi srfi-69))

  (define (my-equal? x y)
    (equal? (foo x) (foo y)))

  (define (my-hash x)
    (hash (foo x)))  ; standard 'hash' procedure also imported from SRFI 69

  (define my-table
    (make-hash-table my-equal? my-hash))

Now any operation with my-table will use my-equal? and my-hash, which implement
an equality logic based on the result of calling 'foo' on objects.

Note that this doesn't affect the behavior of the standard 'equal?' procedure,
it only affects the SRFI 69 hash table operations on the created hash table.

I currently don't remember whether Guile's own non-portable hash table library
supports the same feature.  It probably does in some way.

The R6RS, SRFI 125, and SRFI 126 libraries also support it.  Guile supports R6RS,
so you could use the (rnrs hashtables) library instead of SRFI 69 if you desire.
SRFI 125 is an extension of 69, and SRFI 126 is an extension to R6RS hashtables,
but neither is supported in Guile I believe.
-- 
Taylan

Re: Equality and hashing for new datatypes

[Philip McGrath]

[-- Attachment #1: Type: text/plain, Size: 2304 bytes --]

On Thursday, June 22, 2023 7:33:06 AM EDT Taylan Kammer wrote:
> On 22.06.2023 00:25, Philip McGrath wrote:
> > Hi,
> > 
> > What is the recommended way for a library to customize `equal?` and
> > `equal?` -based hashing for new datatypes it defines?
> > 
> > I know from [1] that `equal?` can be customized using GOOPS; however, some
> > projects do not use GOOPS (e.g. [2]), so it would seem more friendly for a
> > generic library to avoid it. Also, it is not clear if the same mechanism
> > is
> > even an option for customizing `equal-hash` to match `equal?`.
> > 
> > I'm looking for something like Racket's `gen:equal+hash` [3] or Chez
> > Scheme's `record-equal-procedure` and `record-hash-procedure` [4].
> > 
> > This came up while I was working on a portable version of the immutable
> > hash-table implementations from Racket-on-Chez.
> > 
> > -Philip
> > 
> > [1]:
> > https://www.gnu.org/software/guile/manual/html_node/GOOPS-Object-Miscella
> > ny.html [2]:
> > https://lists.gnu.org/archive/html/info-gnu/2023-05/msg00005.html [3]:
> > https://docs.racket-lang.org/reference/Equality.html#%28part._.Implementi
> > ng_.Equality_for_.Custom_.Types%29 [4]:
> > https://cisco.github.io/ChezScheme/csug9.5/objects.html#./objects:h14
> Hi Philip,
> 
> You can use SRFI 69 hash tables in Guile.  This library offers a way to
> specify the equality and hash procedures that should be used by a hash
> table, e.g.:
> 
> [...]
> 
> Note that this doesn't affect the behavior of the standard 'equal?'
> procedure, it only affects the SRFI 69 hash table operations on the created
> hash table.
> 
> I currently don't remember whether Guile's own non-portable hash table
> library supports the same feature.  It probably does in some way.
> 

Thanks, but this is the opposite of what I want to do. The library I'm porting 
already supports creating tables with custom equality and hashing functions. 
What I'm trying to do is make the standard `equal?` procedure recognize when 
two of my table values are semantically the same even if internal 
implementation details differ.

(Note also that SRFI 69 and other libraries provide *mutable* hash tables. The 
Racket-on-Chez library I'm porting provides immutable hash tables, more 
properly Hash Array Mapped Tries, as made famous by Clojure.)

-Philip

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: Equality and hashing for new datatypes

[Taylan Kammer]

On 23.06.2023 00:45, Philip McGrath wrote:
> On Thursday, June 22, 2023 7:33:06 AM EDT Taylan Kammer wrote:
>> On 22.06.2023 00:25, Philip McGrath wrote:
>>> Hi,
>>>
>>> What is the recommended way for a library to customize `equal?` and
>>> `equal?` -based hashing for new datatypes it defines?
>>>
>>> I know from [1] that `equal?` can be customized using GOOPS; however, some
>>> projects do not use GOOPS (e.g. [2]), so it would seem more friendly for a
>>> generic library to avoid it. Also, it is not clear if the same mechanism
>>> is
>>> even an option for customizing `equal-hash` to match `equal?`.
>>>
>>> I'm looking for something like Racket's `gen:equal+hash` [3] or Chez
>>> Scheme's `record-equal-procedure` and `record-hash-procedure` [4].
>>>
>>> This came up while I was working on a portable version of the immutable
>>> hash-table implementations from Racket-on-Chez.
>>>
>>> -Philip
>>>
>>> [1]:
>>> https://www.gnu.org/software/guile/manual/html_node/GOOPS-Object-Miscella
>>> ny.html [2]:
>>> https://lists.gnu.org/archive/html/info-gnu/2023-05/msg00005.html [3]:
>>> https://docs.racket-lang.org/reference/Equality.html#%28part._.Implementi
>>> ng_.Equality_for_.Custom_.Types%29 [4]:
>>> https://cisco.github.io/ChezScheme/csug9.5/objects.html#./objects:h14
>> Hi Philip,
>>
>> You can use SRFI 69 hash tables in Guile.  This library offers a way to
>> specify the equality and hash procedures that should be used by a hash
>> table, e.g.:
>>
>> [...]
>>
>> Note that this doesn't affect the behavior of the standard 'equal?'
>> procedure, it only affects the SRFI 69 hash table operations on the created
>> hash table.
>>
>> I currently don't remember whether Guile's own non-portable hash table
>> library supports the same feature.  It probably does in some way.
>>
> 
> Thanks, but this is the opposite of what I want to do. The library I'm porting 
> already supports creating tables with custom equality and hashing functions. 
> What I'm trying to do is make the standard `equal?` procedure recognize when 
> two of my table values are semantically the same even if internal 
> implementation details differ.
> 
> (Note also that SRFI 69 and other libraries provide *mutable* hash tables. The 
> Racket-on-Chez library I'm porting provides immutable hash tables, more 
> properly Hash Array Mapped Tries, as made famous by Clojure.)
> 
> -Philip

Ah, apologies then.  As far as I know, there's no other way to do that in Guile
than with GOOPS, which you've already mentioned.

In standard Scheme there's no way to do it at all.  I don't think there's even
an SRFI for it (I just searched a bit, out of curiosity, couldn't find anything).

-- 
Taylan

Re: Equality and hashing for new datatypes

[Robby Zambito]

Taylan Kammer <taylan.kammer@gmail.com> writes:

> On 23.06.2023 00:45, Philip McGrath wrote:
>> 
>> Thanks, but this is the opposite of what I want to do. The library I'm porting 
>> already supports creating tables with custom equality and hashing functions. 
>> What I'm trying to do is make the standard `equal?` procedure recognize when 
>> two of my table values are semantically the same even if internal 
>> implementation details differ.
>> 
>> (Note also that SRFI 69 and other libraries provide *mutable* hash tables. The 
>> Racket-on-Chez library I'm porting provides immutable hash tables, more 
>> properly Hash Array Mapped Tries, as made famous by Clojure.)
>> 
>> -Philip
>
> Ah, apologies then.  As far as I know, there's no other way to do that in Guile
> than with GOOPS, which you've already mentioned.
>
> In standard Scheme there's no way to do it at all.  I don't think there's even
> an SRFI for it (I just searched a bit, out of curiosity, couldn't find anything).

YASOS can be implemented in standard Scheme[1], but it has the same
limitations as GOOPS in this context. It cannot really be "injected"
into existing modules AFAIK.  

Footnotes:
[1]  https://notabug.org/PangolinTurtle/yasos-r7rs

Re: Equality and hashing for new datatypes

[Jean Abou Samra]

[-- Attachment #1: Type: text/plain, Size: 601 bytes --]

Le mercredi 21 juin 2023 à 18:25 -0400, Philip McGrath a écrit :
> Hi,
> 
> What is the recommended way for a library to customize `equal?` and `equal?`
> -based hashing for new datatypes it defines?
> 
> I know from [1] that `equal?` can be customized using GOOPS; however, some
> projects do not use GOOPS (e.g. [2]), so it would seem more friendly for a
> generic library to avoid it. Also, it is not clear if the same mechanism is
> even an option for customizing `equal-hash` to match `equal?`.


As far as I can see from the code in libguile/eq.c, GOOPS is the only way,
sorry.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]