6.2.1 Equality

Scheme has three different general equality test predicates. Other than these, some types have their own comparison predicates.

Function: eq? obj1 obj2 ¶

[R7RS base] This is the fastest and finest predicate. Returns #t if obj1 and obj2 are identical objects—that is, if they represents the same object on memory or in a register. Notably, you can compare two symbols or two keywords with eq? to check if they are the same or not. You can think eq? as a pointer comparison for any heap-allocated objects.

Booleans can be compared with eq?, but you can’t compare characters and numbers reliably—objects with the same numerical value may or may not eq? to each other. If you identity comparison needs to include those objects, use eqv? below.

(eq? #t #t)               ⇒ #t
(eq? #t #f)               ⇒ #f
(eq? 'a 'a)               ⇒ #t
(eq? 'a 'b)               ⇒ #f
(eq? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eq? x x))              ⇒ #t

Function: eqv? obj1 obj2 ¶

[R7RS base] When obj1 and obj2 are both exact or both inexact numbers (except NaN or -0.0), eqv? returns #t iff (= obj1 obj2) is true. -0.0 is only eqv? to -0.0.

When obj1 and obj2 are both characters, eqv? returns #t iff (char=? obj1 obj2) is true. Otherwise, eqv? is the same as eq? on Gauche.

(eqv? #\a #\a)             ⇒ #t
(eqv? #\a #\b)             ⇒ #f
(eqv? 1.0 1.0)             ⇒ #t
(eqv? 1 1)                 ⇒ #t
(eqv? 1 1.0)               ⇒ #f
(eqv? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eqv? x x))              ⇒ #t

Note that comparison of NaNs has some peculiarity. Any numeric comparison fails if there’s at least one NaN in its argument. Therefore, (= +nan.0 +nan.0) is always #f. However, Gauche may return #t for (eq? +nan.0 +nan.0) or (eqv? +nan.0 +nan.0).

Function: equal? obj1 obj2 ¶

[R7RS+ base] If obj1 and obj2 are both aggregate types, equal? compares its elements recursively. Otherwise, equal? behaves the same as eqv?.

If obj1 and obj2 are not eqv? to each other, not of builtin types, and the class of both objects are the same, equal? calls the generic function object-equal?. By defining the method, users can extend the behavior of equal? for user-defined classes.

(equal? (list 1 2) (list 1 2)) ⇒ #t
(equal? "abc" "abc")           ⇒ #t
(equal? 100 100)               ⇒ #t
(equal? 100 100.0)             ⇒ #f

;; 0.0 and -0.0 is numerically equal (=), but eqv? distingushes them, so as equal?.
(equal? 0.0 -0.0)              ⇒ #f

Note: This procedure correctly handles the case when both obj1 and obj2 have cycles through pairs and vectors, as required by R6RS and R7RS. However, if the cycle involves user-defined classes, equal? may fail to terminate.

Generic Function: object-equal? obj1 obj2 ¶

This generic function is called when equal? is called on the objects it doesn’t know about. You can define this method on your class so that equal? can check equivalence. This method is supposed to return #t if obj1 is equal to obj2, #f otherwise. If you want to check equivalence of elements recursively, do not call object-equal? directly; call equal? on each element.

(define-class <foo> ()
  ((x :init-keyword :x)
   (y :init-keyword :y)))

(define-method object-equal? ((a <foo>) (b <foo>))
  (and (equal? (slot-ref a 'x) (slot-ref b 'x))
       (equal? (slot-ref a 'y) (slot-ref b 'y))))

(equal? (make <foo> :x 1 :y (list 'a 'b))
        (make <foo> :x 1 :y (list 'a 'b)))
  ⇒ #t

(equal? (make <foo> :x 1 :y (make <foo> :x 3 :y 4))
        (make <foo> :x 1 :y (make <foo> :x 3 :y 4)))
  ⇒ #t

Method: object-equal? (obj1 <top>) (obj2 <top>) ¶

This method catches equal? between two objects of a user-defined class, in case the user doesn’t define a specialized method for the class.

When called, it scans the registered default comparators that can handle both obj1 and obj2, and if it finds one, use the comparator’s equality predicate to see if two arguments are equal to each other. When no matching comparators are found, it just returns #f. See Predefined comparators, about the default comparators: Look for the entries of default-comparator and comparator-register-default!.

Note: If you define object-equal? with exactly the same specializers of this method, you’ll replace it and that breaks default-comparator operation. Future versions of Gauche will prohibit such redefinition. For now, be careful not to redefine it accidentally.

Sometimes you want to test if two aggregate structures are topologically equal, i.e., if one has a shared substructure, the other has a shared substructure in the same way. Equal? can’t handle it; module util.isomorph provides a procedure isomorphic? which does the job (see util.isomorph - Determine isomorphism).

---

6.2.2 Comparison

Equality only concern about whether two objects are equivalent or not. However, sometimes we want to see the order among objects. Again, there’s no single “universal order”. It doesn’t make mathematical sense to ask if one complex number is greater than another, but having some artificial order is useful when you want a consistent result of sorting a list of objects including numbers.

Function: compare obj1 obj2 ¶

A general comparison procedure. Returns -1 if obj1 is less than obj2, 0 if obj1 is equal to obj2, and 1 if obj1 is greater than obj2.

If obj1 and obj2 are incomparable, an error is signalled. However, compare defines total order between most Scheme objects, so that you can use it on wide variety of objects. The definition is upper-compatible to the order defined in SRFI-114.

Some built-in types are handled by this procedure reflecting “natural” order of comparison if any (e.g. real numbers are compared by numeric values, characters are compared by char< etc.) For convenience, it also defines superficial order between objects that doesn’t have natural order; complex numbers are ordered first by their real part, then their imaginary part, for example. That is, 1+i comes before 2-i, which comes before 2, which comes before 2+i.

Boolean false comes before boolean true.

Lists are ordered by dictionary order: Take the common prefix. If either one is () and the other is not, () comes first. If both tails are not empty, compare the heads of the tails. (This makes empty list the “smallest” of all lists).

Vectors (including uniform vectors) are compared first by their lengths, and if they are the same, elements are compared from left to right. Note that it’s different from lists and strings.

(compare '(1 2 3) '(1 3))
  ⇒ -1  ; (1 2 3) is smaller
(compare '#(1 2 3) '#(1 3))
  ⇒ 1   ; #(1 3) is smaller
(compare "123" "13")
  ⇒ -1  ; "123" is smaller

If two objects are of subclasses of <object>, a generic function object-compare is called.

If two objects are of different types and at least one of them isn’t <object>, then they are ordered by their types. SRFI-114 defines the order of builtin types as follows:

1. Empty list.
2. Pairs.
3. Booleans.
4. Characters.
5. Strings.
6. Symbols.
7. Numbers.
8. Vectors.
9. Uniform vectors (u8 < s8 < u16 < s16 < u32 < s32 < u64 < s64 < f16 < f32 < f64)
10. All other objects.

Generic Function: object-compare obj1 obj2 ¶

Specializing this generic function extends compare procedure for user-defined classes.

This method must return either -1 (obj1 precedes obj2), 0 (obj1 equals to obj2), 1 (obj1 succeeds obj2), or #f (obj1 and obj2 cannot be ordered).

Method: object-compare (obj1 <top>) (obj2 <top>) ¶

This method catches compare between two objects of a user-defined class, in case the user doesn’t define a specialized method for the class.

When called, it scans the registered default comparators that can handle both obj1 and obj2, and if it finds one, use the comparator’s compare procedure to determine the order of obj1 and obj2. When no matching comparators are found, it returns #f, meaning two objects can’t be ordered. See Predefined comparators, about the default comparators: Look for the entries of default-comparator and comparator-register-default!.

Note: If you define object-compare with exactly the same specializers of this method, you’ll replace it and that breaks default-comparator operation. Future versions of Gauche will prohibit such redefinition. For now, be careful not to redefine it accidentally.

Function: eq-compare obj1 obj2 ¶

Returns -1 (less than), 0 (equal to) or 1 (greater than) according to a certain total ordering of obj1 and obj2. Both arguments can be any Scheme objects, and can be different type of objects. The following properties are guaranteed.

• (eq-compare x y) is 0 iff (eq? x y) is #t.
• The result is consistent within a single run of the process (but may differ between runs).

Other than these, no actual semantics are given to the ordering.

This procedure is useful when you need to order arbitrary Scheme objects, but you don’t care the actual order as far as it’s consistent.

---

6.2.3 Hashing

Hash functions have close relationship with equality predicate, so we list them here.

Function: eq-hash obj ¶

Function: eqv-hash obj ¶

These are hash functions suitable to be used with eq? and eqv?, respectively. The returned hash value is system- and process-dependent, and can’t be carried over the boundary of the running process.

Note: don’t hash numbers by eq-hash. Two numbers are not guaranteed to be eq? even if they are numerically equal.

Function: default-hash obj ¶

[R7RS+ comparator] This is a hash function suitable to be used with equal?. In R7RS, this is defined in scheme.comparator (originally in srfi.128).

If obj is either a number, a boolean, a character, a symbol, a keyword, a string, a list, a vector or a uniform vector, internal hash function is used to calculate the hash value. If obj is other than that, a generic function object-hash is called to calculate the hash value (see below).

The hash value also depends on hash-salt, which differs for every run of the process.

Function: portable-hash obj salt ¶

Sometimes you need to calculate a hash value that’s “portable”, in a sense that the value won’t change across multiple runs of the process, nor between different platforms. Such hash value can be used with storing objects externally to share among processes.

This procedure calculates a hash value of obj with such characteristics; the hash value is the same for the same object and the same salt value. Here “same object” roughly means having the same external representation. Objects equal? to each other are same. If you write out an object with write, and read it back, they are also the same objects in this sense.

This means objects without read/write invariance, such as ports, can’t be handled with portable-hash. It is caller’s responsibility that obj won’t contain such objects.

The salt argument is a nonnegative fixnum and gives variations in the hash function. You have to use the same salt to get consistent results.

If obj is other than a number, a boolean, a character, a symbol, a keyword, a string, a list, a vector, or a uniform vector, this procedure calls a generic function object-hash is called to calculate the hash value (see below).

Function: legacy-hash obj ¶

Up to 0.9.4, Gauche had a hash function called hash that was used in both equal?-hashtable and for the portable hash function. It had a problem, though.

1. There was no way to salt the hash function, which makes the hashtables storing externally provided data vulnerable to collision attack.
2. The hash function behaves poorly, especially on flonums.
3. There are bugs in bignum and flonum hashing code that have produced different results on different architectures.

Since there are existing hash values calculated with the old hash function, we preserve the behavior of the original hash function as legacy-hash. Use this when you need to access old data. (The hash function also behaves as legacy-hash by default, but it has tweaks; see below.)

The new code that needs portable hash value should use portable-hash instead.

Generic Function: object-hash obj rec-hash ¶

By defining a method for this generic function, objects of user-defined types can have a hash value and can be used in a equal? hash table.

The method has to return an exact non-negative integer, and must return the same value for two object which are equal?. Furthermore, the returned value must not rely on the platform or state of the process, if obj is a portable object (see portable-hash above for what is portable.)

If the method needs to get hash value of obj’s elements, it has to call rec-hash on them. It guarantees that the proper hash function is called recursively. So you can count on rec-hash to calculate a portable hash value when object-hash itself is called from portable-hash.

If obj has several elements, you can call combine-hash-value on the elements’ hash values.

(define-class <myclass> () (x y))

;; user-defined equality function
(define-method object-equal? ((a <myclass>) (b <myclass>))
  (and (equal? (ref a 'x) (ref b 'x))
       (= (abs (ref a 'y)) (abs (ref b 'y)))))

;; user-defined hash function
(define-method object-hash ((a <myclass>) rec-hash)
  (combine-hash-value (rec-hash (ref a 'x))
                      (rec-hash (abs (ref a 'y)))))

Note: The base method of object-hash hashes any object to a single hash value (the actual value depends on hash-salt if object-hash is called from default-hash, and a fixed constant value otherwise. It’s because object’s equality semantics can be customized separately, and we can’t compute a non-constant hash value without knowing the equality semantics.

This behavior is the last “safety net”; in general, you should define object-hash method on your class if the instances of your class can ever be hashed.

Method: object-hash (obj <top>) rec-hash ¶

Method: object-hash (obj <top>) ¶

These two methods are defined by the system and ensures the backward compatibility and the behavior of default-comparator. Be careful not to replace these methods by defining the exactly same specializers. In future versions of Gauche, attempts to replace these methods will raise an error.

Function: combine-hash-value ha hb ¶

Returns a hash value which is a combination of two hash values, ha and hb. The guaranteed invariance is that if (= ha1 ha2) and (= hb1 hb2) then (= (combine-hash-value ha1 hb1) (combine-hash-value ha2 hb2)). This is useful to write user-defined object-hash method.

Function: hash obj ¶

This function is deprecated.

Calculate a hash value of obj suitable for equal? hash. By default, it returns the same value as legacy-hash. However, if this is called from default-hash or portable-hash (via object-hash method), it recurses to the calling hash function.

The behavior is to keep the legacy code work. Until 0.9.5, hash is the only hash function to be used for both portable hash and equal?-hash, and object-hash method takes single argument (an object to hash) and calls hash recursively whenever it needs to get a hash value of other objects pointed from the argument.

As of 0.9.5 we have more than one hash functions that calls object-hash, so the method takes the hash function as the second argument to recurse. However, we can’t just break the legacy code; so there’s a default method defined in object-hash which is invoked when no two-arg method is defined for the given object, and dispatches to one-arg method. As far as the legacy object-hash code calls hash, it calls proper function. The new code shouldn’t rely on this behavior, and must use the second argument of object-hash instead.

Function: boolean-hash bool ¶

Function: char-hash char ¶

Function: char-ci-hash char ¶

Function: string-hash str ¶

Function: string-ci-hash str ¶

Function: symbol-hash sym ¶

Function: number-hash num ¶

[R7RS comparator] These are hash functions for specific type of objects, defined in R7RS scheme.comparator. In Gauche, these procedures are just a wrapper of default-hash with type checks (and case folding when relevant). These are mainly provided to conform scheme.comparator; in your code you might just want to use default-hash (or eq-hash/eqv-hash, depending on the equality predicate).

The case-folding versions, char-ci-hash and string-ci-hash, calls char-foldcase and string-foldcase respectively, on the argument before passing it to hash. (See Characters, for char-foldcase. See Full string case conversion, for string-foldcase).

Function: hash-bound ¶

Function: hash-salt ¶

[R7RS comparator] Both evaluates to an exact nonnegative integers. In R7RS, these are defined in scheme.comparator.

(Note: scheme.comparator defines these as macros, in order to allow implementations optimize runtime overhead. In Gauche we use procedures but the overhead is negligible.)

User-defined hash functions can limit the range of the result between 0 and (hash-bound), respectively, without worrying to lose quality of hash function. (User-defined hash functions don’t need to honor (hash-bound) at all; hashtables takes modulo when necessary.)

User-defined hash function can also take into account of the value (hash-salt) into hash calculation; the salt value may differ between runs of the Scheme processes, or even between hash table instances. It is to avoid collision attack. Built-in hash functions already takes the salt value into account, so if your hash function is combining the hash values of primitive types, you don’t need to worry about salt values.

---

6.2.4 Basic comparators

Equality and comparison procedures are parameters in various data structures. A treemap needs to order its keys; a hashtable needs to see if the keys are the same or not, and it also need a hash function consistent with the equality predicate.

If we want to work on generic data structures, we need to abstract those variations of comparison schemes. So here comes the comparator, a record that bundles closely-related comparison procedures together.

There are two SRFIs that define comparators. The one that was originally called SRFI-128 has now become a part of R7RS large as scheme.comparator, and we recommend new code to use it. Gauche has all of scheme.comparator procedures built-in. The older, and rather complex one is SRFI-114; Gauche also supports it mainly for the backward compatibility. Importantly, Gauche’s native <comparator> object is compatible to both scheme.comparator and srfi-114 comparators.

• Comparator class and constructors:
• Comparator predicates and accessors:
• Predefined comparators:
• Combining comparators:

---