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
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>SRFI 228: A further comparator library</title>
<link href="/favicon.png" rel="icon" sizes="192x192" type="image/png">
<link rel="stylesheet" href="https://srfi.schemers.org/srfi.css" type="text/css">
<style>
.issue {
background-color: pink;
padding: 0.5em;
}
</style>
<meta name="viewport" content="width=device-width, initial-scale=1"></head>
<body>
<h1><a href="https://srfi.schemers.org/"><img class="srfi-logo" src="https://srfi.schemers.org/srfi-logo.svg" alt="SRFI surfboard logo" /></a>228: A further comparator library</h1>
<p>by Daphne Preston-Kendal</p>
<h2 id="status">Status</h2>
<p>This SRFI is currently in <em>draft</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+228+at+srfi+dotschemers+dot+org">srfi-228@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://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-228">archive</a>.</p>
<ul>
<li>Received: 2021-08-28</li>
<li>60-day deadline: 2021-10-30</li>
<li>Draft #1 published: 2021-08-31</li>
</ul>
<h2 id="abstract">Abstract</h2>
<p>Further procedures and syntax forms for defining <a href="https://srfi.schemers.org/srfi-128/srfi-128.html">SRFI 128</a> comparators, and for extracting comparison procedures similar to those defined for Scheme’s built-in types using them.
<p>Best enjoyed in combination with <a href="https://srfi.schemers.org/srfi-162/srfi-162.html">SRFI 162</a>.
<h2 id="issues">Issues</h2>
<p class=issue>Outstanding issues are noted inline, denoted by a highlighted background.
<h2 id="rationale">Rationale</h2>
<p>A typical pattern for defining comparison behaviour for record types and other user-defined Scheme types is some form of lexicographical order over their member slots. The comparator abstraction of SRFI 128 has useful potential for reducing the code bulk of defining such comparison behaviours. This library is intended to take advantage of that potential.
<h2 id="specification">Specification</h2>
<p>All identifiers defined in this SRFI are exported in the <code>(srfi 228)</code> library. However, as in the case of SRFI 162, it is hoped and intended that they will simply be added to the existing comparator libraries of RnRSes and Scheme implementations, rather than being in a separate library.
<dl>
<dt><code>(make-wrapper-comparator</code> <var>type-test</var> <var>unwrap</var> <var>contents-comparator</var><code>)</code> (Procedure)
<dd>
<p>Returns a comparator which compares values satisfying the predicate <var>type-test</var> by first calling the given <var>unwrap</var> procedure on them, then comparing the output of that procedure with the given <var>contents-comparator</var>. The hash function of the wrapper comparator returns the same value as the <var>contents-comparator</var> run on the unwrapped value.</p>
<dt><code>(make-product-comparator</code> <var>comparator</var> ... <code>)</code> (Procedure)
<dd>
<p>Returns a comparator which compares values satisfying the type tests of all of the given <var>comparator</var>s by comparing them with each of the given comparators in turn, left to right, and returning the result of the first non-equal comparison. If all the given comparators consider two values equal, the product comparator also considers them equal. The hash function of the product comparator hashes together the results of all the given comparators in an implementation-defined way. If the equality or ordering predicates or the hash function of any of the given comparators is <code>#f</code>, the corresponding procedure in the product comparator will also be <code>#f</code>.</p>
<dt><code>(make-sum-comparator</code> <var>comparator</var> ... <code>)</code> (Procedure)
<dd>
<p>Returns a comparator which compares values satisfying the <var>type-test</var>s of any of the given <var>comparator</var>s such that values which satisfy the type test of a given comparator are ordered before any values satisfying the type tests of any comparators that appear to the right of it, and values satisfying the same comparator’s type test are tested for ordering and equality according that comparator. The hash function of the sum comparator returns the value of the hash function of the leftmost comparator whose type test is satisfied by the given value. If the equality or ordering predicates or the hash function of any of the given comparators is <code>#f</code>, the corresponding procedure in the product comparator will also be <code>#f</code>.</p>
<dt><code>(comparison-procedures</code> <var>comparator</var><code>)</code> (Procedure)
<dd>
<p>Returns five values, variadic procedures corresponding to <code><</code>, <code><=</code>, <code>=</code>, <code>>=</code>, and <code>></code> respectively for the given comparator. Each one is equivalent to a partial application of the SRFI 128 procedures <code><?</code>, <code><=?</code>, <code>=?</code>, <code>>=?</code>, and <code>>?</code> with the given comparator.</p>
<p class=issue>This is admittedly a rather large number of return values. I hope that that R7RS will adopt some kind of keyword argument system, capable of being extended to keyword return values, and that it will then be possible to redefine <code>comparison-procedures</code> to return procedures associated with keyword names to make the order irrelevant and code using this procedure less opaque. In the meanwhile …?</p>
<p class=issue>As long as we’re stuck with positional return values, I should note that this isn’t the order usually used for the specification of comparison procedures (e.g. the <code>char*?</code> family in R7RS small uses the order <code>char=?</code>, <code>char<?</code>, <code>char>?</code>. <code>char<=?</code>, <code>char>=?</code>). I find the order here easier to remember, but perhaps it would be better to switch to that order for consistency.</p>
</dl>
<h2 id=examples>Examples</h2>
<p>Personal names are usually sorted lexicographically and case-insensitively by the last name, then the first name if the last names are the same. The following example shows how <code>make-wrapper-comparator</code> and <code>make-product-comparator</code> can be used to create a comparator which orders a record type of personal names in this way, and how <code>comparison-procedures</code> can then be used for this ordering.
<pre><code>(define-record-type Person
(make-person first-name last-name)
person?
(first-name person-first-name)
(last-name person-last-name))
(define person-name-comparator
(make-product-comparator
(make-wrapper-comparator person? person-last-name string-ci-comparator)
(make-wrapper-comparator person? person-first-name string-ci-comparator)))
(define-values (person-name<?
person-name<=?
person-name=?
person-name>?
person-name>=?)
(comparison-procedures person-name-comparator))
(person-name<? (make-person "John" "Cowan")
(make-person "Daphne" "Preston-Kendal")) ;=> #t
(person-name>? (make-person "Tom" "Smith")
(make-person "John" "Smith")) ;=> #t</code></pre>
<p>This example can be extended with nested comparators to sort a catalogue in which CDs appear at the end of the list after books:
<pre><code>(define-record-type Book
(make-book author title)
book?
(author book-author)
(title book-title))
(define book-comparator
(make-product-comparator
(make-wrapper-comparator book? book-author person-name-comparator)
(make-wrapper-comparator book? book-title string-ci-comparator)))
(define-record-type CD
(make-cd artist title)
cd?
(artist cd-artist)
(title cd-title))
(define cd-comparator
(make-product-comparator
(make-wrapper-comparator cd? cd-artist person-name-comparator)
(make-wrapper-comparator cd? cd-title string-ci-comparator)))
(define item-comparator
(make-sum-comparator book-comparator cd-comparator))
(define-values (item<?
item<=?
item=?
item>?
item>=?)
(comparison-procedures item-comparator))
(list-sort item<?
(list (make-cd (make-person "The" "Beatles") "Abbey Road")
(make-book (make-person "Jacob" "Grimm") "Deutsche Grammatik")
(make-book (make-person "William" "Shakespeare") "Sonnets")
(make-book (make-person "William" "Shakespeare") "A Midsummer Night’s Dream")
(make-cd (make-person "Bob" "Dylan") "Blonde on Blonde")
(make-cd (make-person "The" "Beatles") "Revolver")))
;; => ({Book {Person "Jacob" "Grimm"} "Deutsche Grammatik"}
;; {Book {Person "William" "Shakespeare"} "Sonnets"}
;; {Book {Person "William" "Shakespeare"} "A Midsummer Night’s Dream"}
;; {CD {Person "The" "Beatles"} "Abbey Road"}
;; {CD {Person "The" "Beatles"} "Revolver"}
;; {CD {Person "Bob" "Dylan"} "Blonde on Blonde"})</code></pre>
<h2 id="implementation">Implementation</h2>
<p>A portable sample implementation and test suite for R7RS may be found <a href="https://github.com/scheme-requests-for-implementation/srfi-228">in the repository</a> for this SRFI.
<h2 id="acknowledgements">Acknowledgements</h2>
<p><code>make-sum-comparator</code>, and by extension the inspiration for the name of <code>make-product-comparator</code>, is originally from Adam Nelson’s Schemepunk.
<p>Marc Nieper-Wißkirchen and John Cowan suggested means of improving the <code>comparison-procedures</code> procedure; as of the current draft, this remains an open issue.
<h2 id=future-work>Future work</h2>
<p>The author hopes that a future SRFI will add a procedure for creating comparators yielding lexicographical order over any sequence type by delegating to a common iteration protocol. An idea to do this using <code>fold</code> procedures foundered on two grounds: the first and more intrinsic one is that <code>fold</code> called on two sequences, one of which is a prefix of the other, cannot determine which of the two is longer, and a sort using <code>fold</code>-based iteration would incorrectly consider them equal; the second is that there is currently an inconsistency among Scheme libraries in what order the <var>kons</var> procedure argument to <code>fold</code> receives the accumulator and the next values in the sequence (compare <a href="https://srfi.schemers.org/srfi-1/srfi-1.html#fold">SRFI 1 <code>fold</code></a> with <a href="https://srfi.schemers.org/srfi-133/srfi-133.html#vector-fold">SRFI 133 <code>vector-fold</code></a>). <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generators were rejected on the ground that their sequences cannot contain any arbitrary Scheme datum.
<h2 id="copyright">Copyright</h2>
<p>© 2021 Daphne Preston-Kendal.</p>
<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 (including the
next paragraph) 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">Arthur A. Gleckler</a></address></body></html>
|
