source: project/wiki/eggref/5/srfi-128 @ 36359

Last change on this file since 36359 was 36359, checked in by DeeEff, 11 months ago

Add man-5 and bump version history

File size: 18.7 KB
Line 
1== SRFI-128: Comparators
2
3This SRFI provides comparators, which bundle a type test predicate, an equality
4predicate, an ordering predicate, and a hash function (the last two are
5optional) into a single Scheme object. By packaging these procedures together,
6they can be treated as a single item for use in the implementation of data
7structures.
8
9[[toc:]]
10
11== Installation
12
13 $ chicken-install srfi-128
14
15or
16
17 $ chicken-install srfi-128 -test
18
19if you want to run the tests for the egg in addition.
20
21== SRFI Description
22
23For a full description of this SRFI, see the full SRFI
24[[http://srfi.schemers.org/srfi-128/srfi-128.html|document]]. This
25documentation covers the API only.
26
27== Comparators
28
29=== Predicates
30
31<procedure>(comparator? obj)</procedure>
32
33Returns {{#t}} if {{obj}} is a comparator, and {{#f}} otherwise.
34
35<procedure>(comparator-ordered? comparator)</procedure>
36
37Returns {{#t}} if {{comparator}} has a supplied ordering predicate, and {{#f}} otherwise.
38
39<procedure>(comparator-hashable? comparator)</procedure>
40
41Returns {{#t}} if {{comparator}} has a supplied hash function, and {{#f}} otherwise.
42
43=== Constructors
44
45The following comparator constructors all supply appropriate type test
46predicates, equality predicates, ordering predicates, and hash functions based
47on the supplied arguments. They are allowed to cache their results: they need
48not return a newly allocated object, since comparators are pure and functional.
49In addition, the procedures in a comparator are likewise pure and functional.
50
51<procedure>(make-comparator type-test equality ordering hash)</procedure>
52
53Returns a comparator which bundles the {{type-test}}, {{equality}},
54{{ordering}}, and {{hash}} procedures provided. However, if {{ordering}} or
55{{hash}} is {{#f}}, a procedure is provided that signals an error on
56application. The predicates {{comparator-ordered?}} and/or
57{{comparator-hashable?}}, respectively, will return {{#f}} in these cases.
58
59Here are calls on make-comparator that will return useful comparators for
60standard Scheme types:
61
62<enscript highlight="scheme">
63(make-comparator boolean? boolean=? (lambda (x y) (and (not x) y)) boolean-hash)
64</enscript>
65
66will return a comparator for booleans, expressing the ordering {{#f}} < {{#t}} and the
67standard hash function for booleans.
68
69<enscript highlight="scheme">
70(make-comparator real? = < (lambda (x) (exact (abs x))))
71</enscript>
72
73will return a comparator expressing the natural ordering of real numbers and a
74plausible (but not optimal) hash function.
75
76<enscript highlight="scheme">
77(make-comparator string? string=? string<? string-hash)
78</enscript>
79
80will return a comparator expressing the implementation's ordering of strings
81and the standard hash function.
82
83<enscript highlight="scheme">
84(make-comparator string? string-ci=? string-ci<? string-ci-hash)
85</enscript>
86
87will return a comparator expressing the implementation's case-insensitive
88ordering of strings and the standard case-insensitive hash function.
89
90<procedure>(make-pair-comparator car-comparator cdr-comparator)</procedure>
91
92This procedure returns comparators whose functions behave as follows:
93
94* The type test returns {{#t}} if its argument is a pair, if the car satisfies the type test predicate of {{car-comparator}}, and the cdr satisfies the type test predicate of {{cdr-comparator}}.
95* The equality function returns {{#t}} if the cars are equal according to {{car-comparator}} and the cdrs are equal according to {{cdr-comparator}}, and {{#f}} otherwise.
96* The ordering function first compares the cars of its pairs using the equality predicate of {{car-comparator}}. If they are equal, then the ordering predicate of {{car-comparator}} is applied to the cars and its value is returned. Otherwise, the predicate compares the cdrs using the equality predicate of {{cdr-comparator}}. If they are not equal, then the ordering predicate of {{cdr-comparator}} is applied to the cdrs and its value is returned.
97* The hash function computes the hash values of the car and the cdr using the hash functions of {{car-comparator}} and {{cdr-comparator}} respectively and then hashes them together in an implementation-defined way.
98
99<procedure>(make-list-comparator element-comparator type-test empty? head tail)</procedure>
100
101This procedure returns comparators whose functions behave as follows:
102
103* The type test returns {{#t}} if its argument satisfies {{type-test}} and the elements satisfy the type test predicate of element-comparator.
104* The total order defined by the equality and ordering functions is as follows (known as lexicographic order):
105** The empty sequence, as determined by calling {{empty?}}, compares equal to itself.
106** The empty sequence compares less than any non-empty sequence.
107** Two non-empty sequences are compared by calling the {{head}} procedure on each. If the heads are not equal when compared using {{element-comparator}}, the result is the result of that comparison. Otherwise, the results of calling the {{tail}} procedure are compared recursively.
108* The {{hash}} function computes the hash values of the elements using the hash function of {{element-comparator}} and then hashes them together in an implementation-defined way.
109
110<procedure>(make-vector-comparator element-comparator type-test length ref)</procedure>
111
112This procedure returns comparators whose functions behave as follows:
113
114* The type test returns {{#t}} if its argument satisfies {{type-test}} and the elements satisfy the type test predicate of {{element-comparator}}.
115* The equality predicate returns {{#t}} if both of the following tests are satisfied in order: the lengths of the vectors are the same in the sense of {{=}}, and the elements of the vectors are the same in the sense of the equality predicate of {{element-comparator}}.
116* The ordering predicate returns {{#t}} if the results of applying length to the first vector is less than the result of applying length to the second vector. If the lengths are equal, then the elements are examined pairwise using the ordering predicate of {{element-comparator}}. If any pair of elements returns {{#t}}, then that is the result of the list comparator's ordering predicate; otherwise the result is {{#f}}
117* The {{hash}} function computes the hash values of the elements using the hash function of {{element-comparator}} and then hashes them together in an implementation-defined way.
118
119Here is an example, which returns a comparator for byte vectors:
120
121<enscript highlight="scheme">
122(make-vector-comparator
123  (make-comparator exact-integer? = < number-hash)
124  bytevector?
125  bytevector-length
126  bytevector-u8-ref)
127</enscript>
128
129<procedure>(make-eq-comparator)</procedure>
130<procedure>(make-eqv-comparator)</procedure>
131<procedure>(make-equal-comparator)</procedure>
132
133These procedures return comparators whose functions behave as follows:
134
135* The type test returns {{#t}} in all cases.
136* The equality functions are {{eq?}}, {{eqv?}}, and {{equal?}} respectively.
137* The ordering function is implementation-defined, except that it must conform to the rules for ordering functions. It may signal an error instead.
138* The hash function is {{default-hash}}.
139
140These comparators accept circular structure (in the case of equal-comparator,
141provided the implementation's {{equal?}} predicate does so) and NaNs.
142
143=== Standard hash functions
144
145These are hash functions for some standard Scheme types, suitable for passing
146to {{make-comparator}}. Users may write their own hash functions with the same
147signature. However, if programmers wish their hash functions to be backward
148compatible with the reference implementation of SRFI 69, they are advised to
149write their hash functions to accept a second argument and ignore it.
150
151<procedure>(boolean-hash obj)</procedure>
152<procedure>(char-hash obj)</procedure>
153<procedure>(char-ci-hash obj)</procedure>
154<procedure>(string-hash obj)</procedure>
155<procedure>(string-ci-hash obj)</procedure>
156<procedure>(symbol-hash obj)</procedure>
157<procedure>(number-hash obj)</procedure>
158
159These are suitable hash functions for the specified types. The hash functions
160{{char-ci-hash}} and {{string-ci-hash}} treat their argument
161case-insensitively. Note that while {{symbol-hash}} may return the hashed value
162of applying {{symbol->string}} and then {{string-hash}} to the symbol, this is
163not a requirement.
164
165=== Bounds and salt
166
167The following macros allow the callers of hash functions to affect their
168behavior without interfering with the calling signature of a hash function,
169which accepts a single argument (the object to be hashed) and returns its hash
170value. They are provided as macros so that they may be implemented in different
171ways: as a global variable, a SRFI 39 or R7RS parameter, or an ordinary
172procedure, whatever is most efficient in a particular implementation.
173
174<syntax>(hash-bound)</syntax>
175
176Hash functions should be written so as to return a number between 0 and the
177largest reasonable number of elements (such as hash buckets) a data structure
178in the implementation might have. What that value is depends on the
179implementation. This value provides the current bound as a positive exact
180integer, typically for use by user-written hash functions. However, they are
181not required to bound their results in this way.
182
183<syntax>(hash-salt)</syntax>
184
185A salt is random data in the form of a non-negative exact integer used as an
186additional input to a hash function in order to defend against dictionary
187attacks, or (when used in hash tables) against denial-of-service attacks that
188overcrowd certain hash buckets, increasing the amortized O(1) lookup time to
189O(n). Salt can also be used to specify which of a family of hash functions
190should be used for purposes such as cuckoo hashing. This macro provides the
191current value of the salt, typically for use by user-written hash functions.
192However, they are not required to make use of the current salt.
193
194The initial value is implementation-dependent, but must be less than the value
195of (hash-bound), and should be distinct for distinct runs of a program unless
196otherwise specified by the implementation. Implementations may provide a means
197to specify the salt value to be used by a particular invocation of a hash
198function.
199
200=== Default comparators
201
202<procedure>(make-default-comparator)</procedure>
203
204Returns a comparator known as a default comparator that accepts Scheme values
205and orders them in some implementation-defined way, subject to the following
206conditions:
207
208* Given disjoint types {{a}} and {{b}}, one of three conditions must hold:
209** All objects of type {{a}} compare less than all objects of type {{b}}.
210** All objects of type {{a}} compare greater than all objects of type {{b}}.
211** All objects of both type {{a}} and type {{b}} compare equal to each other. This is not permitted for any of the Scheme types mentioned below.
212* The empty list must be ordered before all pairs.
213* When comparing booleans, it must use the total order {{#f}} < {{#t}}.
214* When comparing characters, it must use {{char=?}} and {{char<?}}. '''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.
215* When comparing pairs, it must behave the same as a comparator returned by {{make-pair-comparator}} with default comparators as arguments.
216* When comparing symbols, it must use an implementation-dependent total order. One possibility is to use the order obtained by applying {{symbol->string}} to the symbols and comparing them using the total order implied by {{string<?}}.
217* When comparing bytevectors, it must behave the same as a comparator created by the expression {{(make-vector-comparator (make-comparator < = number-hash) bytevector? bytevector-length bytevector-u8-ref)}}.
218* When comparing numbers where either number is complex, since non-real numbers cannot be compared with {{<}}, 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.
219* When comparing real numbers, it must use {{=}} and {{<}}.
220* When comparing strings, it must use {{string=?}} and {{string<?}}. '''Note:''' In R5RS, this is lexicographic order on the implementation-dependent order defined by char<?; in R6RS it is lexicographic order on Unicode codepoint order; in R7RS it is an implementation-defined order.
221* When comparing vectors, it must behave the same as a comparator returned by {{(make-vector-comparator (make-default-comparator) vector? vector-length vector-ref)}}.
222* When comparing members of types registered with {{comparator-register-default!}}, it must behave in the same way as the comparator registered using that function.
223
224Default comparators use {{default-hash}} as their hash function.
225
226<procedure>(default-hash obj)</procedure>
227
228This is the hash function used by default comparators, which accepts a Scheme
229value and hashes it in some implementation-defined way, subject to the
230following conditions:
231
232* When applied to a pair, it must return the result of hashing together the values returned by {{default-hash}} when applied to the car and the cdr.
233* When applied to a boolean, character, string, symbol, or number, it must return the same result as {{boolean-hash}}, {{char-hash}}, {{string-hash}}, {{symbol-hash}}, or {{number-hash}} respectively.
234* When applied to a list or vector, it must return the result of hashing together the values returned by {{default-hash}} when applied to each of the elements.
235
236<procedure>(comparator-register-default! comparator)</procedure>
237
238Registers {{comparator}} for use by default comparators, such that if the
239objects being compared both satisfy the type test predicate of {{comparator}},
240it will be employed by default comparators to compare them. Returns an
241unspecified value. It is an error if any value satisfies both the type test
242predicate of comparator and any of the following type test predicates:
243{{boolean?}}, {{char?}}, {{null?}}, {{pair?}}, {{symbol?}}, {{bytevector?}},
244{{number?}}, {{string?}}, {{vector?}}, or the type test predicate of a
245comparator that has already been registered.
246
247This procedure is intended only to extend default comparators into territory
248that would otherwise be undefined, not to override their existing behavior. In
249general, the ordering of calls to {{comparator-register-default!}} should be
250irrelevant. However, implementations that support inheritance of record types
251may wish to ensure that default comparators always check subtypes before
252supertypes.
253
254=== Accessors and invokers
255
256<procedure>(comparator-type-test-predicate comparator)</procedure>
257<procedure>(comparator-equality-predicate comparator)</procedure>
258<procedure>(comparator-ordering-predicate comparator)</procedure>
259<procedure>(comparator-hash-function comparator)</procedure>
260
261Return the four procedures of {{comparator}}.
262
263<procedure>(comparator-test-type comparator obj)</procedure>
264
265Invokes the type test predicate of {{comparator}} on {{obj}} and returns what
266it returns. More convenient than comparator-type-test-predicate, but less
267efficient when the predicate is called repeatedly.
268
269<procedure>(comparator-check-type comparator obj)</procedure>
270
271Invokes the type test predicate of {{comparator}} on {{obj}} and returns true
272if it returns true, but signals an error otherwise. More convenient than
273{{comparator-type-test-predicate}}, but less efficient when the predicate is
274called repeatedly.
275
276<procedure>(comparator-hash comparator obj)</procedure>
277
278Invokes the hash function of {{comparator}} on {{obj}} and returns what it
279returns.  More convenient than {{comparator-hash-function}}, but less efficient
280when the function is called repeatedly.
281
282'''Note:''' No invokers are required for the equality and ordering predicates,
283because {{=?}} and {{<?}} serve this function.
284
285=== Comparison predicates
286
287<procedure>(=? comparator object1 object2 object3 ...)</procedure>
288<procedure>(<? comparator object1 object2 object3 ...)</procedure>
289<procedure>(>? comparator object1 object2 object3 ...)</procedure>
290<procedure>(<=? comparator object1 object2 object3 ...)</procedure>
291<procedure>(>=? comparator object1 object2 object3 ...)</procedure>
292
293These procedures are analogous to the number, character, and string comparison
294predicates of Scheme. They allow the convenient use of comparators to handle
295variable data types.
296
297These procedures apply the equality and ordering predicates of comparator to
298the objects as follows. If the specified relation returns {{#t}} for all
299objecti and objectj where n is the number of objects and 1 <= i < j <= n, then
300the procedures return {{#t}}, but otherwise #f. Because the relations are
301transitive, it suffices to compare each object with its successor. The order in
302which the values are compared is unspecified.
303
304=== Syntax
305
306<syntax>(comparator-if<=> [ <comparator> ] <object1> <object2> <less-than> <equal-to> <greater-than>)</syntax>
307
308It is an error unless {{<comparator>}} evaluates to a comparator and
309{{<object1>}} and {{<object2>}} evaluate to objects that the comparator can
310handle. If the ordering predicate returns true when applied to the values of
311{{<object1>}} and {{<object2>}} in that order, then <less-than> is evaluated
312and its value returned. If the equality predicate returns true when applied in
313the same way, then {{<equal-to>}} is evaluated and its value returned. If
314neither returns true, {{<greater-than>}} is evaluated and its value returned.
315
316If {{<comparator>}} is omitted, a default comparator is used.
317
318== Repository
319
320[[https://github.com/ThatGeoGuy/srfi-128|Github]]
321
322== Version History
323
324; 0.9 : Full CHICKEN-5 support
325; 0.8 : CHICKEN-5 support (no tests)
326; 0.7 : Includes bug fix for {{make-list-comparator}} from Marc Nieper-Wisskirchen
327; 0.6 : Removed hardcoded .so in setup file
328; 0.5 : Standard README.org added to all SRFIs
329; 0.4 : Update to fix SRFI-128 mustard
330; 0.3 : Packages egg without extraneous files
331; 0.2 : Fixes bugs in setup
332; 0.1 : Initial release
333
334== License
335
336Copyright (C) John Cowan (2016). All Rights Reserved.
337
338Permission is hereby granted, free of charge, to any person obtaining a copy of
339this software and associated documentation files (the "Software"), to deal in
340the Software without restriction, including without limitation the rights to
341use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
342of the Software, and to permit persons to whom the Software is furnished to do
343so, subject to the following conditions:
344
345The above copyright notice and this permission notice shall be included in all
346copies or substantial portions of the Software.
347
348THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
349IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
350FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
351AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
352LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
353OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
354SOFTWARE.
Note: See TracBrowser for help on using the repository browser.