r7rs-small-texinfo

R7RS-small Scheme converted to Texinfo.
git clone https://kaka.farm/~git/r7rs-small-texinfo
Log | Files | Refs | README | LICENSE

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