equivalence-predicates.texinfo (10648B)
1 @node Equivalence predicates 2 @section Equivalence predicates 3 4 A @define{predicate} is a procedure that always returns a boolean value 5 (@code{#t} or @code{#f}). An @define{equivalence predicate} is the 6 computational analogue of a mathematical equivalence relation; it is 7 symmetric, reflexive, and transitive. Of the equivalence predicates 8 described in this section, @code{eq?} is the finest or most 9 discriminating, @code{equal?} is the coarsest, and @code{eqv?} is 10 slightly less discriminating than @code{eq?}. 11 12 @deffn procedure eqv? @var{obj@sub{1}} @var{obj@sub{2}} 13 14 The @code{eqv?} procedure defines a useful equivalence relation on 15 objects. Briefly, it returns @code{#t} if @var{obj@sub{1}} and 16 @var{obj@sub{2}} are normally regarded as the same object. This 17 relation is left slightly open to interpretation, but the following 18 partial specification of @code{eqv?} holds for all implementations 19 of Scheme. 20 21 The @code{eqv?} procedure returns @code{#t} if: 22 23 @itemize 24 25 @item 26 @var{obj@sub{1}} and @var{obj@sub{2}} are both @code{#t} or 27 both @code{#f}. 28 29 @item 30 @var{obj@sub{1}} and @var{obj@sub{2}} are both symbols and 31 are the same symbol according to the @code{symbol=?} procedure 32 (@ref{Symbols}). 33 34 @item 35 @var{obj@sub{1}} and @var{obj@sub{2}} are both exact 36 numbers and are numerically equal (in the sense of @code{=}). 37 38 @item 39 @var{obj@sub{1}} and @var{obj@sub{2}} are both inexact 40 numbers such that they are numerically equal (in the sense of @code{=}) 41 and they yield the same results (in the sense of @code{eqv?}) when 42 passed as arguments to any other procedure that can be defined as a 43 finite composition of Scheme's standard arithmetic procedures, provided 44 it does not result in a NaN value. 45 46 @item 47 @var{obj@sub{1}} and @var{obj@sub{2}} are both characters and are the 48 same character according to the @code{char=?} procedure 49 (@ref{Characters}). 50 51 @item 52 @var{obj@sub{1}} and @var{obj@sub{2}} are both the empty list. 53 54 @item 55 @var{obj@sub{1}} and @var{obj@sub{2}} are pairs, vectors, bytevectors, 56 records, or strings that denote the same location in the store 57 (@ref{Storage model}). 58 59 @item 60 @var{obj@sub{1}} and @var{obj@sub{2}} are procedures whose location 61 tags are equal (@ref{Procedures}). 62 63 @end itemize 64 65 The @code{eqv?} procedure returns @code{#f} if: 66 67 @itemize 68 69 @item 70 @var{obj@sub{1}} and @var{obj@sub{2}} are of different types 71 (@ref{Disjointness of types}). 72 73 @item 74 one of @var{obj@sub{1}} and @var{obj@sub{2}} is @code{#t} but the other 75 is @code{#f}. 76 77 @item 78 @var{obj@sub{1}} and @var{obj@sub{2}} are symbols but are not the same 79 symbol according to the @code{symbol=?} procedure (@ref{Symbols}). 80 81 @item 82 one of @var{obj@sub{1}} and @var{obj@sub{2}} is an exact number but the 83 other is an inexact number. 84 85 @item 86 @var{obj@sub{1}} and @var{obj@sub{2}} are both exact numbers and are 87 numerically unequal (in the sense of @code{=}). 88 89 @item 90 @var{obj@sub{1}} and @var{obj@sub{2}} are both inexact numbers such 91 that either they are numerically unequal (in the sense of @code{=}), or 92 they do not yield the same results (in the sense of @code{eqv?}) when 93 passed as arguments to any other procedure that can be defined as a 94 finite composition of Scheme's standard arithmetic procedures, provided 95 it does not result in a NaN value. As an exception, the behavior of 96 @code{eqv?} is unspecified when both @var{obj@sub{1}} and 97 @var{obj@sub{2}} are NaN. 98 99 @item 100 @var{obj@sub{1}} and @var{obj@sub{2}} are characters for which the 101 @code{char=?} procedure returns @code{#f}. 102 103 @item 104 one of @var{obj@sub{1}} and @var{obj@sub{2}} is the empty list but the 105 other is not. 106 107 @item 108 @var{obj@sub{1}} and @var{obj@sub{2}} are pairs, vectors, bytevectors, 109 records, or strings that denote distinct locations. 110 111 @item 112 @var{obj@sub{1}} and @var{obj@sub{2}} are procedures that would behave 113 differently (return different values or have different side effects) 114 for some arguments. 115 116 @end itemize 117 118 @lisp 119 (eqv? 'a 'a) @result{} #t 120 (eqv? 'a 'b) @result{} #f 121 (eqv? 2 2) @result{} #t 122 (eqv? 2 2.0) @result{} #f 123 (eqv? '() '()) @result{} #t 124 (eqv? 100000000 100000000) @result{} #t 125 (eqv? 0.0 +nan.0) @result{} #f 126 (eqv? (cons 1 2) (cons 1 2)) @result{} #f 127 (eqv? (lambda () 1) 128 (lambda () 2)) @result{} #f 129 (let ((p (lambda (x) x))) 130 (eqv? p p)) @result{} #t 131 (eqv? #f 'nil) @result{} #f 132 @end lisp 133 134 The following examples illustrate cases in which the above rules do not 135 fully specify the behavior of @code{eqv?}. All that can be said about 136 such cases is that the value returned by @code{eqv?} must be a boolean. 137 138 @lisp 139 (eqv? "" "") @result{} @r{unspecified} 140 (eqv? '#() '#()) @result{} @r{unspecified} 141 (eqv? (lambda (x) x) 142 (lambda (x) x)) @result{} @r{unspecified} 143 (eqv? (lambda (x) x) 144 (lambda (y) y)) @result{} @r{unspecified} 145 (eqv? 1.0e0 1.0f0) @result{} @r{unspecified} 146 (eqv? +nan.0 +nan.0) @result{} @r{unspecified} 147 @end lisp 148 149 Note that @code{(eqv? 0.0 -0.0)} will return @code{#f} if negative zero 150 is distinguished, and @code{#t} if negative zero is not distinguished. 151 152 The next set of examples shows the use of @code{eqv?} with procedures 153 that have local state. The @code{gen-counter} procedure must return a 154 distinct procedure every time, since each procedure has its own 155 internal counter. The @code{gen-loser} procedure, however, returns 156 operationally equivalent procedures each time, since the local state 157 does not affect the value or side effects of the procedures. However, 158 @code{eqv?} may or may not detect this equivalence. 159 160 @lisp 161 (define gen-counter 162 (lambda () 163 (let ((n 0)) 164 (lambda () (set! n (+ n 1)) n)))) 165 166 (let ((g (gen-counter))) 167 (eqv? g g)) @result{} #t 168 169 (eqv? (gen-counter) (gen-counter)) 170 @result{} #f 171 (define gen-loser 172 (lambda () 173 (let ((n 0)) 174 (lambda () (set! n (+ n 1)) 27)))) 175 176 (let ((g (gen-loser))) 177 (eqv? g g)) @result{} #t 178 179 (eqv? (gen-loser) (gen-loser)) 180 @result{} @r{unspecified} 181 182 (letrec ((f (lambda () (if (eqv? f g) 'both 'f))) 183 (g (lambda () (if (eqv? f g) 'both 'g)))) 184 (eqv? f g)) 185 @result{} @r{unspecified} 186 187 (letrec ((f (lambda () (if (eqv? f g) 'f 'both))) 188 (g (lambda () (if (eqv? f g) 'g 'both)))) 189 (eqv? f g)) 190 @result{} #f 191 @end lisp 192 193 Since it is an error to modify constant objects (those returned by 194 literal expressions), implementations may share structure between 195 constants where appropriate. Thus the value of @code{eqv?} on constants 196 is sometimes implementation-dependent. 197 198 @lisp 199 (eqv? '(a) '(a)) @result{} @r{unspecified} 200 (eqv? "a" "a") @result{} @r{unspecified} 201 (eqv? '(b) (cdr '(a b))) @result{} @r{unspecified} 202 (let ((x '(a))) 203 (eqv? x x)) @result{} #t 204 @end lisp 205 206 The above definition of @code{eqv?} allows implementations latitude in 207 their treatment of procedures and literals: implementations may either 208 detect or fail to detect that two procedures or two literals are 209 equivalent to each other, and can decide whether or not to merge 210 representations of equivalent objects by using the same pointer or bit 211 pattern to represent both. 212 213 Note: If inexact numbers are represented as IEEE binary floating-point 214 numbers, then an implementation of @code{eqv?} that simply compares 215 equal-sized inexact numbers for bitwise equality is correct by the 216 above definition. 217 218 @end deffn 219 220 @deffn procedure eq? @var{obj@sub{1}} @var{obj@sub{2}} 221 222 The @code{eq?} procedure is similar to @code{eqv?} except that in some 223 cases it is capable of discerning distinctions finer than those 224 detectable by @code{eqv?}. It must always return @code{#f} when 225 @code{eqv?} also would, but may return @code{#f} in some cases where 226 @code{eqv?} would return @code{#t}. 227 228 On symbols, booleans, the empty list, pairs, and records, and also on 229 non-empty strings, vectors, and bytevectors, @code{eq?} and @code{eqv?} 230 are guaranteed to have the same behavior. On procedures, @code{eq?} 231 must return true if the arguments' location tags are equal. On numbers 232 and characters, @code{eq?}'s behavior is implementation-dependent, but 233 it will always return either true or false. On empty strings, empty 234 vectors, and empty bytevectors, @code{eq?} may also behave differently 235 from @code{eqv?}. 236 237 @lisp 238 (eq? 'a 'a) @result{} #t 239 (eq? '(a) '(a)) @result{} @r{unspecified} 240 (eq? (list 'a) (list 'a)) @result{} #f 241 (eq? "a" "a") @result{} @r{unspecified} 242 (eq? "" "") @result{} @r{unspecified} 243 (eq? '() '()) @result{} #t 244 (eq? 2 2) @result{} @r{unspecified} 245 (eq? #\A #\A) @result{} @r{unspecified} 246 (eq? car car) @result{} #t 247 (let ((n (+ 2 3))) 248 (eq? n n)) @result{} @r{unspecified} 249 (let ((x '(a))) 250 (eq? x x)) @result{} #t 251 (let ((x '#())) 252 (eq? x x)) @result{} #t 253 (let ((p (lambda (x) x))) 254 (eq? p p)) @result{} #t 255 @end lisp 256 257 @rationale{} 258 259 It will usually be possible to implement @code{eq?} much 260 more efficiently than @code{eqv?}, for example, as a simple pointer 261 comparison instead of as some more complicated operation. One reason is 262 that it is not always possible to compute @code{eqv?} of two numbers in 263 constant time, whereas @code{eq?} implemented as pointer comparison 264 will always finish in constant time. 265 266 @end deffn 267 268 @deffn procedure equal? @var{obj@sub{1}} @var{obj@sub{2}} 269 270 The @code{equal?} procedure, when applied to pairs, vectors, strings 271 and bytevectors, recursively compares them, returning @code{#t} when 272 the unfoldings of its arguments into (possibly infinite) trees are 273 equal (in the sense of @code{equal?}) as ordered trees, and @code{#f} 274 otherwise. It returns the same as @code{eqv?} when applied to booleans, 275 symbols, numbers, characters, ports, procedures, and the empty list. If 276 two objects are @code{eqv?}, they must be @code{equal?} as well. In all 277 other cases, @code{equal?} may return either @code{#t} or @code{#f}. 278 Even if its arguments are circular data structures, @code{equal?} must 279 always terminate. 280 281 @lisp 282 (equal? 'a 'a) @result{} #t 283 (equal? '(a) '(a)) @result{} #t 284 (equal? '(a (b) c) 285 '(a (b) c)) @result{} #t 286 (equal? "abc" "abc") @result{} #t 287 (equal? 2 2) @result{} #t 288 (equal? (make-vector 5 'a) 289 (make-vector 5 'a)) @result{} #t 290 (equal? '#1=(a b . #1#) 291 '#2=(a b a b . #2#)) @result{} #t 292 (equal? (lambda (x) x) 293 (lambda (y) y)) @result{} @r{unspecified} 294 @end lisp 295 296 Note: A rule of thumb is that objects are generally @code{equal?} if 297 they print the same. 298 299 @end deffn