• Home
• All tickets
• All wiki pages

Source for wiki ComparatorsCowan version 16

author

cowan

comment

ipnr

127.11.51.1

name

ComparatorsCowan

readonly

0

text

Please see [http://srfi.schemers.org/srfi-114/ SRFI 114] for the successor to this proposal.

SRFI 114 has been deprecated by its author.  Here is the first draft of a simpler and better replacement,  which will eventually become a new SRFI.

{{{
#!html
<h2 id="Abstract">Abstract</h2>
<p>
This SRFI provides <i>comparators</i>, procedure bundles that represent one or more of a total order, an equality predicate, and a hash function.  By packaging these procedures together, along with a type test predicate, they can be treated as a single item for use in the implementation of data structures.
</p>
<h2 id="Issues">Issues</h2>
<ol>
<li>Should <code>make-inexact-real-comparator</code> be flushed? It is the only way to handle NaNs, but it is a very specialized case.</li>
<li>Should <code>make-reverse-constructor</code> be flushed?  It's quite useful when you need it, but probably will not be needed all that often.</li>
<li>Should <code>make-debug-comparator</code> be flushed?  It came originally from SRFI 67.  It's not clear that such a specialized contract checker is specially necessary.</li>
<li>Should <code>make-boolean-comparator, make-char-comparator, make-char-ci-comparator, make-string-comparator, make-string-ci-comparator, make-symbol-comparator</code> be flushed?  They take no arguments and basically rovide subsets of a default comparator's behavior.</li>
</ol>

<h2 id="Rationale">Rationale</h2>
<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 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, a comparison procedure is 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="http://srfi.schemers.org/srfi-114/srfi-114">SRFI 114</a>, and shares some of its design rationale and all of its acknowledgements.  Special thanks to Taylan Ulrich Bayırlı/Kammer, whose insistence that SRFI 114 was over-complicated but also inadequate inspired this redesign.</p>

<h2 id="Specification">Specification</h2>

<p>The procedures in this SRFI are in the <code>(srfi ???)</code> library (or <code>(srfi :???)</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 id="Definitions">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 either for equality or for ordering.  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>comparison procedure</em> returns -1, 0, or 1 if the first object precedes the second, is equal to the second, or follows the second, respectively, in a total order defined by the comparator.  It is the programmer's responsibility to ensure that it is reflexive, weakly antisymmetric, transitive, can handle any arguments that satisfy the type test predicate, and returns 0 iff the equality predicate returns <code>#t</code>.  Comparison procedures are compatible with the <em>compare procedures</em> of <a class="ext-link" href="http://srfi.schemers.org/srfi-67/srfi-67.html#node_sec_5">SRFI 67</a>; see SRFI 67 for the rationale for adopting this return convention.</p>
</li>
<li><p>The <em>hash function</em> takes one or more arguments and returns an exact non-negative integer; the first argument is the object to be hashed.  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>

<p>If a second argument is provided, it is a non-negative exact integer, hint from the caller of the hash function that the returned value should be bounded above by the second argument.  There is no requirement that a hash
function support this hint, and the caller cannot count on its being applied.  Supplying <code>#f</code>
as the second argument is equivalent to providing no argument.</p>

<p>If a third argument is provided, it is also a non-negative exact integer that serves as a <i>salt</i> value to be mixed in along with the first argument when performing the hash calculation.  If the caller is careful to provide a sufficiently random salt, attacks on the hash function become more difficult.  In addition, callers that need more than one hash function can easily obtain it by varying the salt.  Like the upper bound, the salt is a hint: no hash function is required to make use of it.</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 objects containing them.  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-comparison-procedure?, comparator-hash-function?</code></p></li>
<li><p><a href="#Standardcomparatorconstructorss">Standard comparator constructors</a>: <code>make-comparator, make-boolean-comparator, make-char-comparator, make-char-ci-comparator, make-string-comparator, make-string-ci-comparator, make-symbol-comparator, make-real-number-comparator, make-complex-number-comparator, make-list-comparator, make-vector-comparator, make-inexact-real-comparator, make-reverse-comparator, make-debug-comparator</code></p></li>
<li><p><a href="#Defaultcomparators">Default comparators</a>: <code>default-comparator, comparator-register-default!</code></p></li>
<li><p><a href="#Wrappedequalitypredicates">Wrapped equality predicates</a>: <code>make-eq-comparator, make-eqv-comparator, make-equal-comparator</code></p></li>
<li><p><a href="#Accessors">Accessors</a>: <code>comparator-type-test-procedure, comparator-equality-predicate, comparator-comparison-procedure, comparator-hash-function, comparator-check-type</code></p></li>
<li><p><a href="#Comparisonpredicates">Comparison predicates</a>: <code>=?, &lt;?, >?, &lt;=?, >=?</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-comparison-procedure? </code><em>comparator</em><code>)</code>
</p>
<p>
Returns <code>#t</code> if <em>comparator</em> has a supplied comparison procedure, and <code>#f</code> otherwise.
</p>
<p><code>(comparator-hash-function? </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="Standardcomparators">Standard comparator constructors</h3>
<p>
The following comparator constructors all supply appropriate type test functions, equality predicates and comparison procedures, 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.
</p></p>
<p>
<code>(make-comparator </code><em>type-test equality compare hash</em><code>)</code>
</p>
<p>
Returns a comparator which bundles the <em>type-test, equality, compare</em>, and <em>hash</em> procedures provided.  As a convenience, the following additional values are accepted:
</p>
<ul><li>If <em>type-test</em> is <code>#t</code>, a type-test procedure that accepts any arguments is provided.
</li>
<li>If <em>equality</em> is <code>#t</code>, an equality predicate is provided that returns <code>#t</code> iff <em>compare</em> returns 0.
</li>
<li>If <em>compare</em> or <em>hash</em> is <code>#f</code>, a procedure is provided that signals an error on application.  The predicates <code>comparator-comparison-procedure?</code> and/or <code>comparator-hash-function?</code>, respectively, will return <code>#f</code> in these cases.
</li>
</ul>
<p>
<code>(make-boolean-comparator)</code>
</p>
<p>
Returns a comparator that compares booleans using the total order <code>#f</code> &lt; <code>#t</code>.
</p>
<p>
<code>(make-char-comparator)</code>
</p>
<p>
Returns a comparator that compares characters using the total order implied by <code>char&lt;?</code>.  On R6RS and R7RS systems, this is Unicode codepoint order.
</p>
<p>
<code>(make-char-ci-comparator)</code>
</p>
<p>
Returns a comparator that compares characters using the total order implied by <code>char-ci&lt;?</code>  On R6RS and R7RS systems, this is Unicode codepoint order after the characters have been folded to lower case.
</p>
<p>
<code>(make-string-comparator)</code>
</p>
<p>
Returns a comparator that compares strings using the total order implied by <code>string&lt;?</code>.  Note that this order is implementation-dependent.
</p>
<p>
<code>(make-string-ci-comparator)</code>
</p>
<p>
Returns a comparator that compares strings using the total order implied by <code>string-ci&lt;?</code>.  Note that this order is implementation-dependent.
</p>
<p>
<code>(make-symbol-comparator)</code>
</p>
<p>
Returns a comparator that compares symbols using an implementation-dependent total order.  One possibility is the order obtained applying <code>symbol-&gt;string</code> to the symbols and comparing them using the total order implied by <code>string&lt;?</code>.  It is not a requirement that the hash function of <code>symbol-comparator</code> be consistent with the hash function of <code>string-comparator</code>, however.
</p>
<p>
<code>(make-real-number-comparator</code> [ <var>type-test</var> ]<code>)</code>

<p>Returns a comparator that compares real numbers using <code>&lt;</code> and <code>=</code>.  The
<var>type-test</var> serves as the type test predicate for the comparator returned.  Its default value is <code>real?</code>.  Different comparators returned by this procedure must be compatible with the R5RS numerical tower in the following sense: If S is a subtype of the numerical type T and the two objects are members of S, then the equality predicate and comparison procedures (but not necessarily the hash function) of S-comparator and T-comparator compute the same results on those objects.
</p>
<p>
<code>(make-complex-number-comparator)</code>
</p>
<p>
Returns a comparator that compares complex numbers.  Since non-real numbers cannot be compared with <code>&lt;</code>, the following least-surprising ordering is defined: If the real parts are &lt; or &gt;, 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>
<p><code>(make-list-comparator </code><em>element-comparator type-test empty? head tail</em><code>)</code>
</p>
<p>
Returns a comparator which compares two sequences that satisfy <em>type-test</em> lexicographically, as follows:</p>
<ul>
<li>The empty sequence, as determined by calling <var>empty?</var> (<code>null?</code> by default) 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 comparing the result of calling the <var>head</var> procedure (<code>car</code> by default).  If the heads are not equal when compared using <var>element-comparator</var> (a default comparator by default), then the result is the result of that comparison.  Otherwise, the results of calling the <var>tail</var> procedure (<code>cdr</code> by default) are compared recursively.
</p>
<p>In particular, <code>(make-list-comparator)</code> returns a comparator that compares lists using a default comparator for the elements, and <code>(make-list-comparator </code><var>element-comparator</var><code>)</code> returns a comparator that compares lists using <var>element-comparator for the elements.</p>
<p>
<code>(make-vector-comparator </code><em>element-comparator type-test length ref</em><code>)</code>
</p>
<p>
Returns a comparator which compares two sequences that satisfy <em>type-test</em> as vectors, using the <em>length</em> procedure (<code>vector-length</code> by default) to determine the lengths of the sequences, and the <em>ref</em> procedure (<code>vector-ref</code> by default) to access a particular elements.  If one sequence is shorter than the other, it compares less than the other.  If the sequences are the same length, they are compared element-wise using <var>element-comparator</var> (a default comparator by default) until they are exhausted.</p>
<p>
In particular, <code>(make-vector-comparator</code> returns a comparator that compares vectors using a default comparator for the elements, and <code>(make-vector-comparator </code><var>element-comparator</var><code>)</code> returns a comparator that compares vectors using <var>element-comparator</var>.  Similarly, <code>(make-vector-comparator (make-default-comparator) bytevector? bytevector-length bytevector-u8-ref)</code> returns a comparator that compares bytevectors.
</p>
<p>
<code>(make-inexact-real-comparator </code><em>epsilon rounding nan-handling</em><code>)</code>
</p>
<p>
Returns a comparator that compares inexact real numbers including NaNs as follows:  if after rounding to the nearest <em>epsilon</em> they are the same, they compare equal; otherwise they compare as specified by <code>&lt;</code>.  The direction of rounding is specified by the <em>rounding</em> argument, which is either a procedure accepting two arguments (the number and <em>epsilon</em>, or else one of the symbols <code>floor</code>, <code>ceiling</code>, <code>truncate</code>, or <code>round</code>.
</p>
<p>
The argument <em>nan-handling</em> specifies how to compare NaN arguments to non-NaN arguments.  If it is a procedure, the procedure is invoked on the other argument if either argument is a NaN.  If it is the symbol <code>min</code>, NaN values precede all other values; if it is the symbol <code>max</code>, they follow all other values, and if it is the symbol <code>error</code>, an error is signaled if a NaN value is compared.  If both arguments are NaNs, however, they always compare as equal.
</p>
<p>
<code>(make-reverse-comparator </code><em>comparator</em><code>)</code>
</p>
<p>Returns a comparator that behaves like <em>comparator</em>, except that the compare procedure returns 1, 0, and -1 instead of -1, 0, and 1 respectively.  This allows ordering in reverse.</p>
<p>
<code>(make-debug-comparator </code><em>comparator</em><code>)</code>
</p>
<p>
Returns a comparator that behaves exactly like <em>comparator</em>, except that whenever any of its procedures are invoked, it verifies all the programmer responsibilities (except stability), and an error is signaled if any of them are violated.  Because it requires three arguments, transitivity is not tested on the first call to a debug comparator; it is tested on all future calls using an arbitrarily chosen argument from the previous invocation.  Note that this may cause unexpected storage leaks. 

<h3 id="Thedefaultcomparator">Default comparators</h3>
<p>
<code>(make-default-comparator)</code>
</p>
<p>
Returns a comparator known as a <var>default comparator</var> that accepts any two Scheme values (with the exceptions listed in the Limitations section) and orders them in some implementation-defined way, subject to the following conditions:
</p>
<ul><li><p>The following ordering between types must hold: the empty list precedes other lists, which precede booleans, which precede characters, which precede strings, which precede symbols, which precede numbers, which precede vectors, which precede bytevectors, which precede all other objects.  This ordering is compatible with <a href="http://srfi.schemers.org/srfi-67/srfi-67.html#node_sec_4.4">SRFI 67</a>.</p></li>
<li>When applied to lists, booleans, characters, strings, symbols, or vectors, or bytevectors, its behavior must be the same as <code>make-list-comparator</code>, <code>make-boolean-comparator</code>, <code>make-char-comparator</code>, <code>make-string-comparator</code>, <code>make-symbol-comparator</code>, and code>make-vector-comparator</code> respectively when invoked with no arguments.</li>
<li><p>When applied to numbers, its behavior is the same as the result of calling <code>make-complex-number-comparator</code> with no arguments if either number is complex, and the same as the result of calling <code>make-real-number-comparator</code> otherwise.</p></li>
<li><p>When applied to bytevectors, its behavior is the same as a comparator created by <code>(make-vector-comparator (make-default-comparator) bytevector? bytevector-length bytevector-u8-ref)</code>.</p></li>
<li><p>When applied to types registered with <code>comparator-register-default!</code>, its behavior is the same as the comparator registered using that function.</p></li>
<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 either type <em>a</em> or type <em>b</em> compare equal to each other.  This is not permitted for any of the standard types mentioned above.</li>
</ul>
</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 all default comparators
to compare them.
</p>
</p>
<h3 id="Wrappedequalitypredicates">Wrapped equality predicates</h3>
<p>
<code>(make-eq-comparator)</code>
</p>
<p>
<code>(make-eqv-comparator)</code>
</p>
<p>
<code>(make-equal-comparator)</code>
</p>
<p>
The equality predicates of these comparators are <code>eq?</code>, <code>eqv?</code>, and <code>equal?</code> respectively.  When their comparison procedures are applied to non-equal objects, their behavior is implementation-defined.  The type test predicates always return <code>#t</code>.
</p>
<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="Accessors">Accessors</h3>
<p>
<code>(comparator-type-test-procedure </code><em>comparator</em><code>)</code>
</p>
<p>
Returns the type test predicate of <em>comparator</em>.
</p>
<p>
<code>(comparator-equality-predicate </code><em>comparator</em><code>)</code>
</p>
<p>
Returns the equality predicate of <em>comparator</em>.
</p>
<p>
<code>(comparator-comparison-procedure </code><em>comparator</em><code>)</code>
</p>
<p>
Returns the comparison procedure of <em>comparator</em>.
</p>
<p>
<code>(comparator-hash-function </code><em>comparator</em><code>)</code>
</p>
<p>
Returns the hash function of <em>comparator</em>.
</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 and signals an error otherwise.
</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>(&lt;? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(&gt;? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(&lt;=? </code><em>comparator</em> <em>object<sub>1</sub> object<sub>2</sub> object<sub>3</sub></em> ...<code>)</code>
</p>
<p>
<code>(&gt;=? </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 in situations where the expression types are not usable.  They are also analogous to the similarly named procedures <a href="http://srfi.schemers.org/srfi-67/srfi-67.html#node_sec_4.6">SRFI 67</a>, but handle arbitrary numbers of arguments, which in SRFI 67 requires the use of the variants whose names begin with <code>chain</code>.</p>
<p>These procedures apply the comparison procedure 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 &lt;= <em>i &lt; j &lt;= n</em>, then the procedures return <code>#t</code>, but otherwise <code>#f</code>.</p>

<p>
The order in which the values are compared is unspecified.  Because the relations are transitive, it suffices to compare each object with its successor.
</p>
<h2>Implementation</h2>
<p>The <a href="comparators.tar.gz">sample implementation</a> contains the following files: FIXME</p>
<ul><li><code>basics.scm</code> - the syntax, record type definition, and simple constructors and 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>constructors.scm</code> - most of the constructors</li>
<li><code>advanced.scm</code> - the more complex constructors</li>
<li><code>r7rs-shim.scm</code> - procedures for R7RS compatibility, including a trivial implementation of bytevectors on top of <a href="http://srfi.schemers.org/srfi-4/srfi-4.html">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.sld</code> - an R7RS library</li>
<li><code>comparators.scm</code> - a Chicken library</li></ul>
<p>A future release will include a test program using the Chicken <code>test</code> egg, which is available on Chibi as the <code>(chibi test)</code> library.</p>
}}}

time

2015-10-23 10:20:10

version

16