-
Notifications
You must be signed in to change notification settings - Fork 8
/
srfi-128.html
540 lines (498 loc) · 31 KB
/
srfi-128.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
<!DOCTYPE html>
<html>
<!--
SPDX-FileCopyrightText: 2015 John Cowan <[email protected]>
SPDX-License-Identifier: MIT
-->
<head>
<title>SRFI 128: Comparators (reduced)</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet" href="/srfi.css" type="text/css" />
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"></head><body>
<h1>Title</h1>
Comparators (reduced)
<h1>Author</h1>
John Cowan
<h1>Status</h1>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+128+at+srfi+dotschemers+dot+org">srfi-128@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="http://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-128">archive</a>.</p>
<ul>
<li>Received: 2015-10-26</li>
<li>60-day deadline: 2015-12-25</li>
<li>Draft #1 published: 2015-10-26</li>
<li>Draft #2 published: 2015-10-26</li>
<li>Draft #3 published: 2015-10-29</li>
<li>Draft #4 published: 2015-11-02</li>
<li>Draft #5 published: 2015-11-08</li>
<li>Draft #6 published: 2015-11-10</li>
<li>Draft #7 published: 2015-11-23</li>
<li>Draft #8 published: 2015-12-17</li>
<li>Draft #9 published: 2015-12-25</li>
<li>Draft #10 published: 2016-01-18</li>
<li>Draft #11 published: 2016-02-06</li>
<li>Draft #12 published: 2016-02-14</li>
<li>Finalized: 2016-02-14</li>
<li>Revised to fix errata:
<ul>
<li>2016-05-14 (Add post-finalization note.)</li>
<li>2018-10-09 (Add missing "not.")</li>
<li>2021-03-29 (Fix arguments to <code>make-comparator</code> in
the <a href="#Defaultcomparators">Default comparators</a>
section.)</li>
<li>2024-03-01 (Fix <a href="#erratum-floor">example</a>.)</li></ul></li>
</ul>
<p id="pfn1"><b>Post-finalization note #1</b>: Because of the extremely high cost of
conforming to the first and third conditions of <code>default-hash</code>,
implementers may disregard those conditions and examine only a
bounded portion of the argument.</p>
<p id="pfn2"><b>Post-finalization note #2</b>: After finalization, on
2021-06-03, the author requested the addition of a non-normative
recommendation in the description of
<code>comparator-register-default!</code>. See the
<a href="#comparator-register-default-recommendation">third
paragraph</a>.</p>
<p id="pfn3"><b>Post-finalization note #3</b> (added on 2022-07-19):
The hash functions in the <code>eq-comparator</code> and the
<code>eqv-comparator</code> objects are implementation-defined.</p>
<h1>Abstract</h1>
<p>
This SRFI provides <i>comparators</i>, which bundle a type test predicate,
an equality predicate, an ordering predicate, and a hash function (the
last two are optional) into a single Scheme object. By packaging these
procedures together, they can be treated as a single item for use in
the implementation of data structures.
</p>
<h1>Rationale</h1>
<p>
The four procedures above have complex dependencies on one another, and it is inconvenient to have to pass them individually to other procedures that might or might not make use of all of them. For example, a set implementation by its nature requires only an equality predicate, but if it is implemented using a hash table, an appropriate hash function is also required if the implementation does not provide one; alternatively, if it is implemented using a tree, procedures specifying a total order are required. By passing a comparator rather than a bare equality predicate, the set implementation can make use of whatever procedures are available and useful to it.
</p>
<p>This SRFI is a simplified and enhanced rewrite of <a href="https://srfi.schemers.org/srfi-114/srfi-114.html" target="_blank">SRFI 114</a>, and shares some of its design rationale and all of its acknowledgements. The largest change is the replacement of the comparison procedure with the ordering procedure. This allowed most of the special-purpose comparators to be removed. In addition, many of the more specialized
procedures, as well as all but one of the syntax forms, have been removed as unnecessary.</p>
<p>Special thanks to Taylan Ulrich Bayırlı/Kammer, whose insistence
that SRFI 114 was unacceptable inspired this redesign.
Jörg Wittenberger added Chicken-specific type declarations,
which I have moved to <code>comparators.scm</code>, as it is
a Chicken-specific library.
He also provided Chicken-specific metadata and setup commands.
Comments from Shiro Kawai, Alex Shinn, and Kevin Wortman
guided me to the current design for bounds and salt.
</p>
<h1>Specification</h1>
<p>The procedures in this SRFI are in the <code>(srfi 128)</code> library (or <code>(srfi :128)</code> on R6RS), but the sample implementation currently places them in the <code>(comparators)</code> library. This means it can't be used alongside SRFI 114, but there's no reason for anyone to do that.</p>
<h3>Definitions</h3>
<p>
A <em>comparator</em> is an object of a disjoint type. It is a bundle of procedures that are useful for comparing two objects in a total order. It is an error if any of the procedures have side effects. There are four procedures in the bundle:
</p>
<ul><li><p>The <em>type test predicate</em> returns <code>#t</code> if its argument has the correct type to be passed as an argument to the other three procedures, and <code>#f</code> otherwise.</p>
</li>
<li><p>The <em>equality predicate</em> returns <code>#t</code> if the two objects are the same in the sense of the comparator, and <code>#f</code> otherwise. It is the programmer's responsibility to ensure that it is reflexive, symmetric, transitive, and can handle any arguments that satisfy the type test predicate.</p>
</li>
<li><p>The <em>ordering predicate</em> returns <code>#t</code> if the first object precedes the second in a total order, and <code>#f</code> otherwise. Note that if it is true, the equality predicate must be false. It is the programmer's responsibility to ensure that it is irreflexive, antisymmetric, transitive, and can handle any arguments that satisfy the type test predicate.</p>
</li>
<li><p>The <em>hash function</em> takes an object and returns an exact non-negative integer. It is the programmer's responsibility to ensure that it can handle any argument that satisfies the type test predicate, and that it returns the same value on two objects if the equality predicate says they are the same (but not necessarily the converse).</p>
</li></ul>
<p>
It is also the programmer's responsibility to ensure that all four procedures provide the same result whenever they are applied to the same object(s) (in the sense of <code>eqv?</code>), unless the object(s) have been mutated since the last invocation. In particular, they must not depend in any way on memory addresses in implementations where the garbage collector can move objects in memory.
</p>
<h3>Limitations</h3>
<p>The comparator objects defined in this SRFI are not applicable to circular structure or to NaNs, or to objects containing any of these. Attempts to pass any such objects to any procedure defined here, or to any procedure that is part of a comparator defined here, is an error except as otherwise noted.</p>
<h3>Index</h3>
<ul>
<li><p><a href="#Predicates">Predicates</a>: <code>comparator? comparator-ordered? comparator-hashable?</code></p></li>
<li><p><a href="#Constructors">Constructors</a>: <code>make-comparator make-pair-comparator make-list-comparator make-vector-comparator make-eq-comparator make-eqv-comparator make-equal-comparator</code></p></li>
<li><p><a href="#Hashfunctions">Standard hash functions</a>: <code>boolean-hash char-hash char-ci-hash string-hash string-ci-hash symbol-hash number-hash</code></p></li>
<li><p><a href="#Boundsandsalt">Bounds and salt</a>: <code>hash-bound hash-salt</code></p></li>
<li><p><a href="#Defaultcomparators">Default comparators</a>: <code>make-default-comparator default-hash comparator-register-default!</code></p></li>
<li><p><a href="#Accessorsandinvokers">Accessors and invokers</a>: <code>comparator-type-test-predicate comparator-equality-predicate comparator-ordering-predicate comparator-hash-function comparator-test-type comparator-check-type comparator-hash</code></p></li>
<li><p><a href="#Comparisonpredicates">Comparison predicates</a>: <code>=? <? >? <=? >=?</code></p></li>
<li><p><a href="#Syntax">Syntax</a>: <code>comparator-if<=></code></p></li>
</ul>
<h3 id="Predicates">Predicates</h3>
<p>
<code>(comparator? </code><em>obj</em><code>)</code>
</p>
<p>
Returns <code>#t</code> if <em>obj</em> is a comparator, and <code>#f</code> otherwise.</p>
<p><code>(comparator-ordered? </code><em>comparator</em><code>)</code>
</p>
<p>
Returns <code>#t</code> if <em>comparator</em> has a supplied ordering predicate, and <code>#f</code> otherwise.
</p>
<p><code>(comparator-hashable? </code><em>comparator</em><code>)</code>
</p>
<p>
Returns <code>#t</code> if <em>comparator</em> has a supplied hash function, and <code>#f</code> otherwise.
</p>
<h3 id="Constructors">Constructors</h3>
<p>
The following comparator constructors all supply appropriate type test predicates, equality predicates, ordering predicates, and hash functions based on the supplied arguments. They are allowed to cache their results: they need not return a newly allocated object, since comparators are pure and functional. In addition, the procedures
in a comparator are likewise pure and functional.
</p>
<p>
<code>(make-comparator </code><em>type-test equality ordering hash</em><code>)</code>
</p>
<p>
Returns a comparator which bundles the <em>type-test, equality, ordering</em>, and <em>hash</em> procedures provided. However, if <em>ordering</em> or <em>hash</em> is <code>#f</code>, a procedure is provided that signals an error on application. The predicates <code>comparator-ordered?</code> and/or <code>comparator-hashable?</code>, respectively, will return <code>#f</code> in these cases.
</p>
<p>Here are calls on <code>make-comparator</code> that will return useful comparators for standard Scheme types:
</p><p>
</p><ul>
<li><p><code>(make-comparator boolean? boolean=? (lambda (x y) (and (not x) y)) boolean-hash)</code> will return a comparator for booleans, expressing the ordering <code>#f</code> < <code>#t</code> and the standard hash function for booleans.</p></li>
<li id="erratum-floor"><p><code>(make-comparator real? = < (lambda (x) (exact (floor (abs x)))))</code> will return a comparator expressing the natural ordering of real numbers and a plausible (but not optimal) hash function.</p></li>
<li><p><code>(make-comparator string? string=? string<? string-hash)</code> will return a comparator expressing the implementation's ordering of strings and the standard hash function.</p></li>
<li><p><code>(make-comparator string? string-ci=? string-ci<? string-ci-hash</code> will return a comparator expressing the implementation's case-insensitive ordering of strings and the standard case-insensitive hash function.</p></li>
</ul>
<p>
<code>(make-pair-comparator </code> <var>car-comparator cdr-comparator</var><code>)</code>
<p>This procedure returns comparators whose functions behave as follows.
</p>
<ul>
<li><p>The type test returns <code>#t</code> if its argument is a pair,
if the car satisfies the type test predicate of <var>car-comparator</var>, and the
cdr satisfies the type test predicate of <var>cdr-comparator</var>.
</p></li>
<li>The equality function returns <code>#t</code> if the cars are equal
according to <var>car-comparator</var> and the cdrs are equal according
to <var>cdr-comparator</var>, and <code>#f</code> otherwise.</li>
<li><p>The ordering function first compares the cars of its pairs using
the equality predicate of <var>car-comparator</var>. If they are
not equal, then the ordering predicate of <var>car-comparator</var> is
applied to the cars and its value is returned.
Otherwise, the predicate compares the cdrs using
the equality predicate of <var>cdr-comparator</var>. If they are not
equal, then the ordering predicate of <var>cdr-comparator</var>
is applied to the cdrs and its value is returned.</p></li>
<li>The hash function computes the hash values of the
car and the cdr using the hash functions of <var>car-comparator</var>
and <var>cdr-comparator</var> respectively and then hashes them together
in an implementation-defined way.
</ul>
<code>(make-list-comparator </code> <em>element-comparator</em> <em>type-test empty? head tail</em><code>)</code>
<p>
This procedure returns comparators whose functions behave as follows:
</p>
<ul>
<li><p>The type test returns <code>#t</code> if its argument satisfies
<var>type-test</var> and the elements satisfy the type test predicate
of <var>element-comparator</var>.</p></li>
<li><p>The total order defined by the equality and ordering functions
is as follows (known as lexicographic order): </p>
<ul>
<li>The empty sequence, as determined by calling <var>empty?</var>,
compares equal to itself.</li>
<li>The empty sequence compares less than any non-empty sequence.</li>
<li>Two non-empty sequences are compared by calling the <var>head</var>
procedure on each. If the heads are not equal when compared using
<var>element-comparator</var>, the result is the result of that comparison.
Otherwise, the results of calling the <var>tail</var> procedure are
compared recursively.</li>
</ul>
<li><p>The hash function computes the hash values of the
elements using the hash function of <var>element-comparator</var>
and then hashes them together in an implementation-defined way.</p></li>
</ul>
<p><code>(make-vector-comparator </code> <em>element-comparator</em> <em>type-test</em> <em>length ref</em><code>)</code>
</p>
<p>
This procedure returns comparators whose functions behave as follows:
</p>
<ul>
<li><p>The type test returns <code>#t</code> if its argument satisfies
<var>type-test</var> and the elements satisfy the type test predicate
of <var>element-comparator</var>.</p></li>
<li><p>The equality predicate returns <code>#t</code> if both of the following
tests are satisfied in order: the lengths of the vectors are the
same in the sense of <var>=</var>, and the elements of the vectors
are the same in the sense of the equality predicate of
<var>element-comparator</var>.</p></li>
<li><p>The ordering predicate returns <code>#t</code> if
the results of applying <var>length</var> to the first vector is less than
the result of applying <var>length</var> to the second vector.
If the lengths are equal, then the elements are examined pairwise using
the ordering predicate of <var>element-comparator</var>. If any pair of elements
returns <code>#t</code>, then that is the result of the list comparator's
ordering predicate;
otherwise the result is <code>#f</code>
<li>The hash function computes the hash values of the
elements using the hash function of <var>element-comparator</var>
and then hashes them together in an implementation-defined way.</li>
</ul>
<p>Here is an example, which returns a comparator for byte vectors:</p>
<pre>(make-vector-comparator
(make-comparator exact-integer? = < number-hash)
bytevector?
bytevector-length
bytevector-u8-ref)
</pre>
<p>
<code>(make-eq-comparator)</code>
</p>
<p>
<code>(make-eqv-comparator)</code>
</p>
<p>
<code>(make-equal-comparator)</code>
</p>
<p>
<p>
These procedures return comparators whose functions behave as follows:
</p>
<ul>
<li><p>The type test returns <code>#t</code> in all cases.
</p></li>
<li>The equality functions are <code>eq?</code>, <code>eqv?</code>,
and <code>equal?</code> respectively.</li>
<li><p>The ordering function is implementation-defined,
except that it must conform to the rules for ordering functions.
It may signal an error instead.</p></li>
<li><p>The hash function is <code>default-hash</code>.</p></li>
</ul>
<p>These comparators accept circular structure (in the case of
<code>equal-comparator</code>, provided the implementation's <code>equal?</code> predicate
does so) and NaNs.</p>
<h3 id="Hashfunctions">Standard hash functions</h3>
<p>These are hash functions for some standard Scheme types, suitable for
passing to <code>make-comparator</code>. Users may write their own
hash functions with the same signature. However, if programmers wish their hash
functions to be backward compatible with the reference implementation
of <a href="https://srfi.schemers.org/srfi-69/srfi-69.html">SRFI 69</a>,
they are advised to write their hash functions to accept a second argument
and ignore it.
</p>
<p>
<code>(boolean-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(char-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(char-ci-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(string-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(string-ci-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(symbol-hash</code> <var>obj</var><code>)</code>
</p>
<p>
<code>(number-hash</code> <var>obj</var><code>)</code>
</p>
<p>These are suitable hash functions for the specified types. The hash functions <code>char-ci-hash</code> and <code>string-ci-hash</code> treat their argument case-insensitively.
Note that while <code>symbol-hash</code> may return the hashed value of
applying <code>symbol->string</code> and then <code>string-hash</code>
to the symbol, this is not a requirement.
</p>
<h3 id="Boundsandsalt">Bounds and salt</h3>
<p>The following macros allow the callers of hash functions to affect
their behavior without interfering with the calling signature of a hash
function, which accepts a single argument (the object to be hashed)
and returns its hash value. They are provided as macros so that they
may be implemented in different ways: as a global variable, a SRFI 39
or R7RS parameter, or an ordinary procedure, whatever is most efficient
in a particular implementation.</p>
<p><code>(hash-bound)</code> [syntax]</p>
<p>Hash functions should be written so as to return a number between
0 and the largest reasonable number of elements (such as hash buckets)
a data structure in the implementation might have. What that value is
depends on the implementation. This value provides the current bound
as a positive exact integer,
typically for use by user-written hash functions. However, they are
not required to bound their results in this way.</p>
<p><code>(hash-salt)</code> [syntax]</p>
<p>A <var>salt</var> is random data in the form of a non-negative
exact integer used as an additional input to a hash function in order
to defend against dictionary attacks, or (when used in hash tables)
against denial-of-service attacks that overcrowd certain hash buckets,
increasing the amortized O(1) lookup time to O(n). Salt can also be
used to specify which of a family of hash functions should be used for
purposes such as cuckoo hashing. This macro provides the current value
of the salt, typically for use by user-written hash functions. However,
they are not required to make use of the current salt.</p>
<p>The initial value is implementation-dependent, but must be less
than the value of <code>(hash-bound)</code>, and should be distinct
for distinct runs of a program unless otherwise specified by the
implementation. Implementations may provide a means to specify the salt
value to be used by a particular invocation of a hash function.</p>
<h3 id="Defaultcomparators">Default comparators</h3>
<p>
<code>(make-default-comparator)</code>
</p>
<p>
Returns a comparator known as a <var>default comparator</var> that accepts Scheme values and orders them in some implementation-defined way, subject to the following conditions:
</p>
<ul>
<li><p>Given disjoint types <em>a</em> and <em>b</em>, one of three conditions must hold:</p>
<ul>
<li>All objects of type <em>a</em> compare less than all objects of type <em>b</em>.</li>
<li>All objects of type <em>a</em> compare greater than all objects of type <em>b</em>.</li>
<li>All objects of both type <em>a</em> and type <em>b</em> compare equal to each other. This is not permitted for any of the Scheme types mentioned below.</li>
</ul>
<li><p>The empty list must be ordered before all pairs.</p></li>
<li><p>When comparing booleans, it must use the total order <code>#f</code> < <code>#t</code>.</p></li>
<li><p>When comparing characters, it must use <code>char=?</code> and <code>char<?</code>.</p><p>Note: In R5RS, this is an implementation-dependent order that is typically the same as Unicode codepoint order; in R6RS and R7RS, it is Unicode codepoint order.</p></li>
<li><p>When comparing pairs, it must behave the same as a comparator returned by <code>make-pair-comparator</code> with default comparators as arguments.</p></li>
<li><p>When comparing symbols, it must use an implementation-dependent total order. One possibility is to use the order obtained by applying <code>symbol->string</code> to the symbols and comparing them using the total order implied by <code>string<?</code>.</p></li>
<li><p>When comparing bytevectors, it must behave the same as a comparator created by the expression <code>(make-vector-comparator (make-comparator bytevector? = < number-hash) bytevector? bytevector-length bytevector-u8-ref)</code>.</p></li>
<li><p>When comparing numbers where either number is complex, since non-real numbers cannot be compared with <code><</code>, the following least-surprising ordering is defined: If the real parts are < or >, so are the numbers; otherwise, the numbers are ordered by their imaginary parts. This can still produce somewhat surprising results if one real part is exact and the other is inexact.</p></li>
<li><p>When comparing real numbers, it must use <code>=</code> and <code><</code>.</p></li>
<li><p>When comparing strings, it must use <code>string=?</code> and <code>string<?</code>.</p><p>Note: In R5RS, this is lexicographic order on the implementation-dependent order defined by <code>char<?</code>; in R6RS it is lexicographic order on Unicode codepoint order; in R7RS it is an implementation-defined order.</p></li>
<li><p>When comparing vectors, it must behave the same as a comparator returned by <code>(make-vector-comparator (make-default-comparator) vector? vector-length vector-ref)</code>.</p></li>
<li><p>When comparing members of types registered with <code>comparator-register-default!</code>, it must behave in the same way as the comparator registered using that function.</p></li>
</ul>
<p>Default comparators use <code>default-hash</code> as their hash function.</p>
<p>
<code>(default-hash</code> <var>obj</var><code>)</code>
</p>
<p>This is the hash function used by default comparators, which
accepts a Scheme value and hashes it in some implementation-defined way,
subject to the following conditions:</p>
<ul>
<li>When applied to a pair, it must return the result of hashing together the
values returned by <code>default-hash</code> when applied to the car and the cdr.</li>
<li>When applied to a boolean, character, string, symbol, or number,
it must return the same result as <code>boolean-hash</code>,
<code>char-hash</code>, <code>string-hash</code>,
<code>symbol-hash</code>, or <code>number-hash</code> respectively.</li>
<li>When applied to a list or vector, it must return the result of hashing
together the values returned by <code>default-hash</code> when applied
to each of the elements.</li>
</ul>
<p><code>(comparator-register-default! </code><var>comparator</var><code>)</code>
</p>
<p>
Registers <var>comparator</var> for use by default comparators, such that if the objects being compared
both satisfy the type test predicate of <var>comparator</var>, it will be employed by default comparators
to compare them. Returns an unspecified value.
It is an error if any value satisfies both the type test predicate
of <var>comparator</var> and any of the following type test predicates:
<code>boolean?</code>, <code>char?</code>, <code>null?</code>, <code>pair?</code>,
<code>symbol?</code>, <code>bytevector?</code>, <code>number?</code>,
<code>string?</code>, <code>vector?</code>, or
the type test predicate of a comparator that has already been registered.
</p>
<p>
This procedure is intended only to extend default comparators into
territory that would otherwise be undefined, not to override their
existing behavior.
In general, the ordering of calls to <code>comparator-register-default!</code>
should be irrelevant. However, implementations that support inheritance
of record types may wish to ensure that default comparators always check
subtypes before supertypes.
</p>
<p id="comparator-register-default-recommendation">This SRFI
recommends (but does not require) that libraries which
expose comparators do <i>not</i> register them with this procedure,
because the default comparator (which is meant mostly for ad hoc
programming) is meant to be under the control of the program author
rather than the library author. It is the program author's
responsibility to ensure that the registered comparators do not
conflict with each other.</p>
<h3 id="Accessorsandinvokers">Accessors and Invokers</h3>
<p>
<code>(comparator-type-test-predicate </code><em>comparator</em><code>)</code>
</p>
<p>
<code>(comparator-equality-predicate </code><em>comparator</em><code>)</code>
</p>
<p>
<code>(comparator-ordering-predicate </code><em>comparator</em><code>)</code>
</p>
<p>
<code>(comparator-hash-function </code><em>comparator</em><code>)</code>
</p>
<p>Return the four procedures of <i>comparator</i>.</p>
<p>
<code>(comparator-test-type </code><em>comparator obj</em><code>)</code>
</p>
<p>
Invokes the type test predicate of <em>comparator</em> on <em>obj</em> and returns what it returns.
More convenient than <code>comparator-type-test-predicate</code>, but less efficient when the predicate is called repeatedly.</p>
<p>
<code>(comparator-check-type </code><em>comparator obj</em><code>)</code>
</p>
<p>
Invokes the type test predicate of <em>comparator</em> on <em>obj</em> and returns true if it returns true, but signals an error otherwise.
More convenient than <code>comparator-type-test-predicate</code>, but less efficient when the predicate is called repeatedly.</p>
<p>
<code>(comparator-hash </code><em>comparator obj</em><code>)</code>
</p>
<p>
Invokes the hash function of <em>comparator</em> on <var>obj</var> and returns what it returns.
More convenient than <code>comparator-hash-function</code>, but less efficient when the function is called repeatedly.</p>
<p>Note: No invokers are required for the equality and ordering predicates,
because <code>=?</code> and <code><?</code> serve this function.
</p>
<h3 id="Comparisonpredicates">Comparison predicates</h3>
<p>
<code>(=? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(<? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(>? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(<=? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(>=? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
These procedures are analogous to the number, character, and string comparison predicates of Scheme. They allow the convenient use of comparators to handle variable data types.</p>
<p>These procedures apply the equality and ordering predicates of <em>comparator</em> to the <em>objects</em> as follows. If the specified relation returns <code>#t</code> for all <em>object<sub>i</sub></em> and <em>object<sub>j</sub></em> where <em>n</em> is the number of objects and 1 <= <em>i < j <= n</em>, then the procedures return <code>#t</code>, but otherwise <code>#f</code>.
Because the relations are transitive, it suffices to compare each object with its successor.
The order in which the values are compared is unspecified.
</p>
<h3 id="Syntax">Syntax</h3>
<p>
<code>(comparator-if<=> </code>[ <comparator> ] <object<sub>1</sub>> <object<sub>2</sub>> <less-than> <equal-to> <greater-than><code>)</code>
<p>
It is an error unless <comparator> evaluates to a comparator
and <object<sub>1</sub>> and <object<sub>2</sub>> evaluate
to objects that the comparator can handle. If the ordering predicate
returns true when applied to the values of
<object<sub>1</sub>> and <object<sub>2</sub>> in
that order, then <less-than> is evaluated and its value returned.
If the equality predicate returns true when applied in the same way,
then <equal-to> is evaluated and its value returned. If neither
returns true, <greater-than> is evaluated and its value returned.
</p>
<p>If <comparator> is omitted, a default comparator is used.</p>
<h1>Implementation</h1>
<p>The <a href="https://srfi.schemers.org/srfi-128/srfi-128.tgz" target="_blank">sample implementation</a>
is found in the repository of this SRFI. It contains the following files.</p>
<ul><li><code>comparators-impl.scm</code> - the record type definition and most of the procedures</li>
<li><code>default.scm</code> - a simple implementation of the default constructor, which should be improved by implementers to handle records and implementation-specific types</li>
<li><code>r7rs-shim.scm</code> - procedures for R7RS compatibility, including a trivial implementation of bytevectors on top of <a href="https://srfi.schemers.org/srfi-4/srfi-4.html" target="_blank">SRFI 4</a> u8vectors</li>
<li><code>complex-shim.scm</code> - a trivial implementation of <code>real-part</code> and <code>imag-part</code> for Schemes that don't have complex numbers</li>
<li><code>comparators.meta</code> - Chicken-specific metadata</li>
<li><code>comparators.setup</code> - Chicken-specific executable setup</li>
<li><code>comparators.sld</code> - an R7RS library</li>
<li><code>comparators.scm</code> - a Chicken library</li>
<li><code>comparators-test.scm</code> - a test file using the Chicken <code>test</code> egg</li>
</ul>
<h1>Copyright</h1>
Copyright (C) John Cowan (2015). All Rights Reserved.
<p>
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:
</p><p>
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
</p><p>
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
</p><hr>
<address>Editor: <a href="mailto:srfi-editors+at+srfi+dot+schemers+dot+org" target="_blank">Arthur A. Gleckler</a></address>