3 ms·
Two-place equality methods are a general solution, but not a very good idea. I have hit upon the a better abstraction for handling custom equality, which I call
by kazinator 6y ago
Two-place equality methods are a general solution, but not a very good idea. I have hit upon the a better abstraction for handling custom equality, which I call "equality substitution". An objects equality method doesn't perform the equality comparison, but rather nominates an alternative value which is used as that object's representative for equality comparisons. That alternative is the "equality substitute".
This is documented in the TXR Lisp reference manual: https://www.nongnu.org/txr/txr-manpage.html#N-02CDB347 https://www.nongnu.org/txr/txr-manpage.html#N-02CDB347
The key idea is that we have a reasonably rich set of built-in objects in the language that support equal equality useful ways.
Instead of trying to bend other objects to also support equal equality from scratch, we require objects to calculate a representative of themselves which is some language built-in data type that natively supports equal.
Equality substitution, though not a perfect concept, removes much of the error proneness of defining equality.
- The application developer is never required to write a hashing function. Not only does that relieve the application programmer of burden, but it also relieves the system of the burden of having to support custom hashing functions everywhere such as in hash tables.
- Inequality comes for free also. For instance, suppose a user-account structure has an equality method that produces the user-id (a character string) as the substitute. This means that we can now compare two user-account objects using less. One user-account is less than another if their respective user-id fields are less, which is a lexicographic comparison.
- The equality substitute can be the result of a complex calculation, which is cached in the object. I.e. the equal method can produce some compound key the first time it is invoked, and then use the cached value subsequently.
Demo:
This is the TXR Lisp interactive listener of TXR 257.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
Join TXR Rewards now, and get 15000 closing parentheses you can use anywhere.
1> (defstruct account ()
user-id
(:method equal (me) me.user-id))
#<struct-type account>
2> (defvarl a (new account user-id "aardvark"))
a
3> (defvarl b (new account user-id "bat"))
b
4> (defvarl z (new account user-id "zebra"))
z
5> (less a b z)
t
6> (less b a)
nil
7> (equal a b)
nil
8> (equal a a)
t
9> (equal a (new account user-id "aardvark"))
t
10> (hash-equal a)
327970753
11> (hash-equal "aardvark")
327970753
12> (defvarl h (hash))
h
13> (set [h a] 100)
100
14> (set [h b] 200)
200
15> 4
4
16> (set [h z] 300)
300
17> h
#H(() (#S(account user-id "bat") 200) (#S(account user-id "aardvark") 100)
(#S(account user-id "zebra") 300))
18> [h a]
100
19> [h b]
200
20> [h "aardvark"]
100
A key observation here is that the object a, of account type, is equal to the character string "aardvark", as well as to any object of any type which produces that string as its equality substitute.
However, this is a very clear aspect of the model, and not a hidden pitfall.
We are saying that a participates in equality as if it literally were the string "aardvark" (though not satisfying the stringp predicate).
This is clear from the beginning and you program your logic accordingly, taking advantage of that while anticipating whatever risks it may cause.
The system is very easy to understand and use; so far in every program where I took advantage of equality substitution, it was a pleasure to work with.
- taeric 6y agoHow is this superior to the standard relational algebra method of using immutable keys associated with mutable attributes? The fun example is ZIP CODE for houses. Since one house can have multiple values, it makes sense that the house had another key representation. And that using equality based on what is ultimately a mutable attribute just doesn't really make sense. Even your "aardvark" example fails if you for some reason also reference it as an "Orycteropus afer". Right? Now, if you expose that at all equal spots, it makes sense. Sorta "a.equals(b, by(get name))". Or as common lisp does it in most spots, ":key #'person-name". :)
- kazinator 6y agoFirstly, whatever problems you anticipate with the aardvark also afflict the Java way of defining a two-place equal method, with the hashing burden and all. Ultimately, what do these operations do? They bottom out on some built-in data types like strings and numbers: stuff made of bits. Equality substitution says: please, just produce the representative bits, and let the regular equality deal with it, instead of keeping those bits encapsulated and trying to implement hashing, equality and inequality yourself. Imagine the account object implemented in a Java-like way. All that the binary equal method is going to do is compare the darned user-id strings. The hash method will hash the string. The less comparison method will compare the strings. At the end of all that, due to the encapsulation, you still don't have the useful property that a and "aardvark" are equal: the equal method is only called for other account objects. Equality substitution doesn't enforce the immutability of keys. That's up to the programmer and almost always a good idea. In a small "throwaway" program, if someone finds some clever use for a mutating equality substitute, I mean, more power to them. (That program probably won't be, or shouldn't be, using hash tables, because the documentation explicitly states that hash table behavior becomes unspecified if objects are inserted into it whose equality substitutes mutate.) The leeway in the system allows an object to come to life without an equality substitute value, which is then lazily calculated by the equal method and cached. Since that happens on the first call, it doesn't look like a mutation from the equality point of view. Objects can have more than one key. Objects of the same kind can be considered equal in more than one way. Well, there is only one equal function: you get to pick one of those equalities to be the one that equal uses. I thought about ways to work-in multiple equality relations, but that's a work in progress.