Next: , Up: Standard procedures   [Contents][Index]

6.1 Equivalence predicates

A predicate is a procedure that always returns a boolean value (#t or #f). An equivalence predicate is the computational analogue of a mathematical equivalence relation; it is symmetric, reflexive, and transitive. Of the equivalence predicates described in this section, eq? is the finest or most discriminating, equal? is the coarsest, and eqv? is slightly less discriminating than eq?.

procedure: (eqv? obj1 obj2)

The eqv? procedure defines a useful equivalence relation on objects. Briefly, it returns #t if obj1 and obj2 are normally regarded as the same object. This relation is left slightly open to interpretation, but the following partial specification of eqv? holds for all implementations of Scheme.

The eqv? procedure returns #t if:

  • obj1 and obj2 are both #t or both #f.
  • obj1 and obj2 are both symbols and are the same symbol according to the symbol=? procedure (see Symbols).
  • obj1 and obj2 are both exact numbers and are numerically equal (in the sense of =).
  • obj1 and obj2 are both inexact numbers such that they are numerically equal (in the sense of =) and they yield the same results (in the sense of eqv?) when passed as arguments to any other procedure that can be defined as a finite composition of Scheme’s standard arithmetic procedures, provided it does not result in a NaN (Not a Number) value.
  • obj1 and obj2 are both characters and are the same character according to the char=? procedure (see Characters).
  • obj1 and obj2 are both the empty list.
  • obj1 and obj2 are pairs, vectors, bytevectors, records, or strings that denote the same location in the store (see Storage model).
  • obj1 and obj2 are procedures whose location tags are equal (see Procedures).

The eqv? procedure returns #f if:

  • obj1 and obj21 are of different types (see Disjointness of types).
  • one of obj1 and obj2 is #t but the other is #f.
  • obj1 and obj2 are symbols but are not the same symbol according to the symbol=? procedure (see Symbols).
  • one of obj1 and obj2 is an exact number but the other is an inexact number.
  • obj1 and obj2 are both exact numbers and are numerically unequal (in the sense of =).
  • obj1 and obj2 are both inexact numbers such that either they are numerically unequal (in the sense of =), or they do not yield the same results (in the sense of eqv?) when passed as arguments to any other procedure that can be defined as a finite composition of Scheme’s standard arithmetic procedures, provided it does not result in a NaN value. As an exception, the behavior of eqv? is unspecified when both obj1 and obj2 are NaN.
  • obj1 and obj2 are characters for which the char=? procedure returns #f.
  • one of obj1 and obj2 is the empty list but the other is not.
  • obj1 and obj2 are pairs, vectors, bytevectors, records, or strings that denote distinct locations.
  • obj1 and obj2 are procedures that would behave differently (return different values or have different side effects) for some arguments. 
(eqv? 'a 'a)                 ⇒ #t
(eqv? 'a 'b)                 ⇒ #f
(eqv? 2 2)                   ⇒ #t
(eqv? 2 2.0)                 ⇒ #f
(eqv? '() '())               ⇒ #t
(eqv? 100000000 100000000)   ⇒ #t
(eqv? 0.0 +nan.0)            ⇒ #f
(eqv? (cons 1 2) (cons 1 2)) ⇒ #f
(eqv? (lambda () 1)
      (lambda () 2))         ⇒ #f
(let ((p (lambda (x) x)))
  (eqv? p p))                ⇒ #t
(eqv? #f 'nil)               ⇒ #f

The following examples illustrate cases in which the above rules do not fully specify the behavior of eqv?. All that can be said about such cases is that the value returned by eqv? must be a boolean. 

(eqv? "" "")          ⇒ unspecified
(eqv? '#() '#())      ⇒ unspecified
(eqv? (lambda (x) x)  ⇒ unspecified
      (lambda (x) x)) ⇒ unspecified
(eqv? (lambda (x) x)  ⇒ unspecified
      (lambda (y) y)) ⇒ unspecified
(eqv? 1.0e0 1.0f0)    ⇒ unspecified
(eqv? +nan.0 +nan.0)  ⇒ unspecified

Note that (eqv? 0.0 -0.0) will return #f if negative zero is distinguished, and #t if negative zero is not distinguished.

The next set of examples shows the use of eqv? with procedures that have local state. The gen-counter procedure must return a distinct procedure every time, since each procedure has its own internal counter. The gen-loser procedure, however, returns operationally equivalent procedures each time, since the local state does not affect the value or side effects of the procedures. However, eqv? may or may not detect this equivalence. 

(define gen-counter
  (lambda ()
    (let ((n 0))
      (lambda () (set! n (+ n 1)) n))))

(let ((g (gen-counter)))
  (eqv? g g))           ⇒ #t

(eqv? (gen-counter) (gen-counter))
                        ⇒ #f
(define gen-loser
  (lambda ()
    (let ((n 0))
      (lambda () (set! n (+ n 1)) 27))))

(let ((g (gen-loser)))
  (eqv? g g))           ⇒ #t

(eqv? (gen-loser) (gen-loser))
                        ⇒ unspecified

(letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
         (g (lambda () (if (eqv? f g) 'both 'g))))
  (eqv? f g))
                        ⇒ unspecified

(letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
         (g (lambda () (if (eqv? f g) 'g 'both))))
  (eqv? f g))
                        ⇒ #f

Since it is an error to modify constant objects (those returned by literal expressions), implementations may share structure between constants where appropriate. Thus the value of eqv? on constants is sometimes implemen­ta­tion-dependent. 

(eqv? '(a) '(a))         ⇒ unspecified
(eqv? "a" "a")           ⇒ unspecified
(eqv? '(b) (cdr '(a b))) ⇒ unspecified
(let ((x '(a)))
  (eqv? x x))            ⇒ #t

The above definition of eqv? allows implementations latitude in their treatment of procedures and literals: implementations may either detect or fail to detect that two procedures or two literals are equivalent to each other, and can decide whether or not to merge representations of equivalent objects by using the same pointer or bit pattern to represent both.

Note: If inexact numbers are represented as IEEE binary floating-point numbers, then an implementation of eqv? that simply compares equal-sized inexact numbers for bitwise equality is correct by the above definition.

procedure: (eq? obj1 obj2)

The eq? procedure is similar to eqv? except that in some cases it is capable of discerning distinctions finer than those detectable by eqv?. It must always return #f when eqv? also would, but may return #f in some cases where eqv? would return #t.

On symbols, booleans, the empty list, pairs, and records, and also on non-empty strings, vectors, and bytevectors, eq? and eqv? are guaranteed to have the same behavior. On procedures, eq? must return true if the arguments’ location tags are equal. On numbers and characters, eq?’s behavior is implementation-dependent, but it will always return either true or false. On empty strings, empty vectors, and empty bytevectors, eq? may also behave differently from eqv?. 

(eq? 'a 'a)               ⇒ #t
(eq? '(a) '(a))           ⇒ unspecified
(eq? (list 'a) (list 'a)) ⇒ #f
(eq? "a" "a")             ⇒ unspecified
(eq? "" "")               ⇒ unspecified
(eq? '() '())             ⇒ #t
(eq? 2 2)                 ⇒ unspecified
(eq? #\A #\A)             ⇒ unspecified
(eq? car car)             ⇒ #t
(let ((n (+ 2 3)))
  (eq? n n))              ⇒ unspecified
(let ((x '(a)))
  (eq? x x))              ⇒ #t
(let ((x '#()))
  (eq? x x))              ⇒ #t
(let ((p (lambda (x) x)))
  (eq? p p))              ⇒ #t

It will usually be possible to implement eq? much more efficiently than eqv?, for example, as a simple pointer comparison instead of as some more complicated operation. One reason is that it is not always possible to compute eqv? of two numbers in constant time, whereas eq? implemented as pointer comparison will always finish in constant time.

procedure: (equal? obj1 obj2)

The equal? procedure, when applied to pairs, vectors, strings and bytevectors, recursively compares them, returning #t when the unfoldings of its arguments into (possibly infinite) trees are equal (in the sense of equal?) as ordered trees, and #f otherwise. It returns the same as eqv? when applied to booleans, symbols, numbers, characters, ports, procedures, and the empty list. If two objects are eqv?, they must be equal? as well. In all other cases, equal? may return either #t or #f. Even if its arguments are circular data structures, equal? must always terminate. 

(equal? 'a 'a)               ⇒ #t
(equal? '(a) '(a))           ⇒ #t
(equal? '(a (b) c)
        '(a (b) c))          ⇒ #t
(equal? "abc" "abc")         ⇒ #t
(equal? 2 2)                 ⇒ #t
(equal? (make-vector 5 'a)
        (make-vector 5 'a))  ⇒ #t
(equal? '#1=(a b . #1#)
        '#2=(a b a b . #2#)) ⇒ #t
(equal? (lambda (x) x)
        (lambda (y) y))      ⇒ unspecified

Note: A rule of thumb is that objects are generally equal? if they print the same.

Next: Numbers, Up: Standard procedures   [Contents][Index]