Debian Codegraph @

%3a67/examples.scm

raw
1 ; Copyright (c) 2005 Sebastian Egner and Jens Axel S{\o}gaard.
2 ;
3 ; Permission is hereby granted, free of charge, to any person obtaining
4 ; a copy of this software and associated documentation files (the
5 ; ``Software''), to deal in the Software without restriction, including
6 ; without limitation the rights to use, copy, modify, merge, publish,
7 ; distribute, sublicense, and/or sell copies of the Software, and to
8 ; permit persons to whom the Software is furnished to do so, subject to
9 ; the following conditions:
10 ;
11 ; The above copyright notice and this permission notice shall be
12 ; included in all copies or substantial portions of the Software.
13 ;
14 ; THE SOFTWARE IS PROVIDED ``AS IS'', WITHOUT WARRANTY OF ANY KIND,
15 ; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 ; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 ; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
18 ; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
19 ; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 ; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 ;
22 ; -----------------------------------------------------------------------
23 ;
24 ; Compare procedures SRFI (confidence tests)
25 ; [email protected], [email protected], 2005
26 ;
27 ; history of this file:
28 ; SE, 14-Oct-2004: first version
29 ; ..
30 ; SE, 28-Feb-2005: adapted to make it one-source PLT,S48,Chicken
31 ; JS, 01-Mar-2005: first version
32 ; SE, 18-Apr-2005: added (<? [c] [x y]) and (</<? [c] [x y z])
33 ; SE, 13-May-2005: included examples for <? etc.
34 ; SE, 16-May-2005: naming convention changed; compare-by< optional x y
35 ;
36 ; This program runs some examples on 'compare.scm'.
37 ; It has been tested under
38 ; * PLT 208p1
39 ; * Scheme 48 1.1
40 ; * Chicken 1.70.
41
42 ; Portability workarounds
43 ; =======================
44 ;
45 ; The purpose of these procedures is to push the examples
46 ; through a Scheme system with severe limitations. It is
47 ; not the intention to supply the functionality.
48
49 ; poor man's complex
50 (define (pm-complex? z) (or (real? z) (and (pair? z) (eq? (car z) 'complex))))
51 (define (pm-number? z) (or (real? z) (pm-complex? z)))
52 (define (pm-make-rectangular re im) (list 'complex re im))
53 (define (pm-real-part z) (if (pm-complex? z) (cadr z) z))
54 (define (pm-imag-part z) (if (pm-complex? z) (caddr z) z))
55
56 ; apply on truncated argument list
57 (define (make-apply limit)
58 (let ((original-apply apply))
59 (lambda (f . xs)
60 (let ((args (let loop ((xs xs) (rev-args '()))
61 (cond
62 ((null? xs)
63 (reverse rev-args))
64 ((null? (cdr xs))
65 (append (reverse rev-args) (car xs)))
66 (else
67 (loop (cdr xs) (cons (car xs) rev-args)))))))
68 (if (<= (length args) limit)
69 (original-apply f args)
70 (original-apply
71 f
72 (begin (display "*** warning: truncated apply")
73 (newline)
74 (let truncate ((n 0) (rev-args '()) (xs args))
75 (if (= n limit)
76 (reverse rev-args)
77 (truncate (+ n 1) (cons (car xs) rev-args) (cdr xs)))))))))))
78
79 ; =============================================================================
80
81 ; Running the examples in PLT (DrScheme)
82 ; ======================================
83 ;
84 ; 1. Uncomment the following lines:
85 ;
86 ;plt (require
87 ;plt (lib "16.ss" "srfi") ; case-lambda
88 ;plt (lib "23.ss" "srfi") ; error
89 ;plt (lib "27.ss" "srfi") ; random-integer
90 ;plt (lib "42.ss" "srfi") ; eager comprehensions list-ec etc.
91 ;plt (lib "pretty.ss")) ; pretty-print
92 ;plt (define pretty-write pretty-print)
93 ;plt (load "compare.scm")
94 ;
95 ; 2. Run this file.
96
97 ; Running the examples in Scheme-48
98 ; =================================
99 ;
100 ; 1. Invoke scheme48 with sufficient heap size (-h <words>).
101 ; 2. Paste this into the REPL:
102 ; ,open srfi-16 srfi-23 srfi-27 srfi-42 pp
103 ; (define pretty-write p)
104 ; ,load compare.scm examples.scm
105
106 ; Running the examples in the Chicken Scheme Interpreter
107 ; ======================================================
108 ;
109 ; 1. Fetch and install the srfi-42 egg from the Chicken homepage
110 ; 2. Uncomment the following lines:
111 ; (require-extension srfi-23)
112 ; (define random-integer random)
113 ; (require-extension srfi-42)
114 ; (define pretty-write display)
115 ; (define complex? pm-complex?)
116 ; (define number? pm-number?)
117 ; (define make-rectangular pm-make-rectangular)
118 ; (define real-part pm-real-part)
119 ; (define imag-part pm-imag-part)
120 ; (define apply (make-apply 126)) ; Grrr...
121 ; (load "compare.scm")
122 ; 3. Invoke csi with:
123 ; csi -syntax examples.scm
124 ;
125 ; Note: Chicken doesn't have complex numbers and has a
126 ; severe limit on the number of arguments for apply.
127
128 ; =============================================================================
129
130 ; Test engine
131 ; ===========
132 ;
133 ; We use an extended version of the the checker of SRFI-42 (with
134 ; Felix' reduction on codesize) for running a batch of tests for
135 ; the various procedures of 'compare.scm'. Moreover, we use the
136 ; comprehensions of SRFI-42 to generate examples systematically.
137
138 (define my-equal? equal?)
139 (define my-pretty-write pretty-write)
140
141 (define my-check-correct 0)
142 (define my-check-wrong 0)
143
144 (define (my-check-reset)
145 (set! my-check-correct 0)
146 (set! my-check-wrong 0))
147
148 ; (my-check expr => desired-result)
149 ; evaluates expr and compares the value with desired-result.
150
151 (define-syntax my-check
152 (syntax-rules (=>)
153 ((my-check expr => desired-result)
154 (my-check-proc 'expr (lambda () expr) desired-result))))
155
156 (define (my-check-proc expr thunk desired-result)
157 (newline)
158 (my-pretty-write expr)
159 (display " => ")
160 (let ((actual-result (thunk)))
161 (write actual-result)
162 (if (my-equal? actual-result desired-result)
163 (begin
164 (display " ; correct")
165 (set! my-check-correct (+ my-check-correct 1)) )
166 (begin
167 (display " ; *** wrong ***, desired result:")
168 (newline)
169 (display " => ")
170 (write desired-result)
171 (set! my-check-wrong (+ my-check-wrong 1))))
172 (newline)))
173
174 ; (my-check-ec <qualifier>* <ok?> <expr>)
175 ; runs (every?-ec <qualifier>* <ok?>), counting the times <ok?>
176 ; is evaluated as a correct example, and stopping at the first
177 ; counter example for which <expr> provides the argument.
178
179 (define-syntax my-check-ec
180 (syntax-rules (nested)
181 ((my-check-ec (nested q1 ...) q etc1 etc2 etc ...)
182 (my-check-ec (nested q1 ... q) etc1 etc2 etc ...))
183 ((my-check-ec q1 q2 etc1 etc2 etc ...)
184 (my-check-ec (nested q1 q2) etc1 etc2 etc ...))
185 ((my-check-ec ok? expr)
186 (my-check-ec (nested) ok? expr))
187 ((my-check-ec (nested q ...) ok? expr)
188 (my-check-ec-proc
189 '(every?-ec q ... ok?)
190 (lambda ()
191 (first-ec
192 'ok
193 (nested q ...)
194 (:let ok ok?)
195 (begin
196 (if ok
197 (set! my-check-correct (+ my-check-correct 1))
198 (set! my-check-wrong (+ my-check-wrong 1))))
199 (if (not ok))
200 (list expr)))
201 'expr))
202 ((my-check-ec q ok? expr)
203 (my-check-ec (nested q) ok? expr))))
204
205 (define (my-check-ec-proc expr thunk arg-counter-example)
206 (let ((my-check-correct-save my-check-correct))
207 (newline)
208 (my-pretty-write expr)
209 (display " => ")
210 (let ((result (thunk)))
211 (if (eqv? result 'ok)
212 (begin
213 (display "#t ; correct (")
214 (write (- my-check-correct my-check-correct-save))
215 (display " examples)")
216 (newline))
217 (begin
218 (display "#f ; *** wrong *** (after ")
219 (write (- my-check-correct my-check-correct-save))
220 (display " correct examples).")
221 (newline)
222 (display " ; Argument of the first counter example:")
223 (newline)
224 (display " ; ")
225 (write arg-counter-example)
226 (display " = ")
227 (write (car result)))))))
228
229 (define (my-check-summary)
230 (begin
231 (newline)
232 (newline)
233 (display "*** correct examples: ")
234 (display my-check-correct)
235 (newline)
236 (display "*** wrong examples: ")
237 (display my-check-wrong)
238 (newline)
239 (newline)))
240
241 ; =============================================================================
242
243 ; Abstractions etc.
244 ; =================
245
246 (define ci integer-compare) ; very frequently used
247
248 ; (result-ok? actual desired)
249 ; tests if actual and desired specify the same ordering.
250
251 (define (result-ok? actual desired)
252 (eqv? actual desired))
253
254 ; (my-check-compare compare increasing-elements)
255 ; evaluates (compare x y) for x, y in increasing-elements
256 ; and checks the result against -1, 0, or 1 depending on
257 ; the position of x and y in the list increasing-elements.
258
259 (define-syntax my-check-compare
260 (syntax-rules ()
261 ((my-check-compare compare increasing-elements)
262 (my-check-ec
263 (:list x (index ix) increasing-elements)
264 (:list y (index iy) increasing-elements)
265 (result-ok? (compare x y) (ci ix iy))
266 (list x y)))))
267
268 ; sorted lists
269
270 (define my-booleans '(#f #t))
271 (define my-chars '(#\a #\b #\c))
272 (define my-chars-ci '(#\a #\B #\c #\D))
273 (define my-strings '("" "a" "aa" "ab" "b" "ba" "bb"))
274 (define my-strings-ci '("" "a" "aA" "Ab" "B" "bA" "BB"))
275 (define my-symbols '(a aa ab b ba bb))
276
277 (define my-reals
278 (append-ec (:range xn -6 7)
279 (:let x (/ xn 3))
280 (list x (+ x (exact->inexact (/ 1 100))))))
281
282 (define my-rationals
283 (list-ec (:list x my-reals)
284 (and (exact? x) (rational? x))
285 x))
286
287 (define my-integers
288 (list-ec (:list x my-reals)
289 (if (and (exact? x) (integer? x)))
290 x))
291
292 (define my-complexes
293 (list-ec (:list re-x my-reals)
294 (if (inexact? re-x))
295 (:list im-x my-reals)
296 (if (inexact? im-x))
297 (make-rectangular re-x im-x)))
298
299 (define my-lists
300 '(() (1) (1 1) (1 2) (2) (2 1) (2 2)))
301
302 (define my-vector-as-lists
303 (map list->vector my-lists))
304
305 (define my-list-as-vectors
306 '(() (1) (2) (1 1) (1 2) (2 1) (2 2)))
307
308 (define my-vectors
309 (map list->vector my-list-as-vectors))
310
311 (define my-null-or-pairs
312 '(()
313 (1) (1 1) (1 2) (1 . 1) (1 . 2)
314 (2) (2 1) (2 2) (2 . 1) (2 . 2)))
315
316 (define my-objects
317 (append my-null-or-pairs
318 my-booleans
319 my-chars
320 my-strings
321 my-symbols
322 my-integers
323 my-vectors))
324
325 ; =============================================================================
326
327 ; The checks
328 ; ==========
329
330 (define (check:if3)
331
332 ; basic functionality
333
334 (my-check (if3 -1 'n 'z 'p) => 'n)
335 (my-check (if3 0 'n 'z 'p) => 'z)
336 (my-check (if3 1 'n 'z 'p) => 'p)
337
338 ; check arguments are evaluated only once
339
340 (my-check
341 (let ((x -1))
342 (if3 (let ((x0 x)) (set! x (+ x 1)) x0) 'n 'z 'p))
343 => 'n)
344
345 (my-check
346 (let ((x -1) (y 0))
347 (if3 (let ((x0 x)) (set! x (+ x 1)) x0)
348 (begin (set! y (+ y 1)) y)
349 (begin (set! y (+ y 10)) y)
350 (begin (set! y (+ y 100)) y)))
351 => 1)
352
353 (my-check
354 (let ((x 0) (y 0))
355 (if3 (let ((x0 x)) (set! x (+ x 1)) x0)
356 (begin (set! y (+ y 1)) y)
357 (begin (set! y (+ y 10)) y)
358 (begin (set! y (+ y 100)) y)))
359 => 10)
360
361 (my-check
362 (let ((x 1) (y 0))
363 (if3 (let ((x0 x)) (set! x (+ x 1)) x0)
364 (begin (set! y (+ y 1)) y)
365 (begin (set! y (+ y 10)) y)
366 (begin (set! y (+ y 100)) y)))
367 => 100)
368
369 ) ; check:if3
370
371 (define-syntax my-check-if2
372 (syntax-rules ()
373 ((my-check-if2 if-rel? rel)
374 (begin
375 ; check result
376 (my-check (if-rel? -1 'yes 'no) => (if (rel -1 0) 'yes 'no))
377 (my-check (if-rel? 0 'yes 'no) => (if (rel 0 0) 'yes 'no))
378 (my-check (if-rel? 1 'yes 'no) => (if (rel 1 0) 'yes 'no))
379
380 ; check result of 'laterally challenged if'
381 (my-check (let ((x #f)) (if-rel? -1 (set! x #t)) x) => (rel -1 0))
382 (my-check (let ((x #f)) (if-rel? 0 (set! x #t)) x) => (rel 0 0))
383 (my-check (let ((x #f)) (if-rel? 1 (set! x #t)) x) => (rel 1 0))
384
385 ; check that <c> is evaluated exactly once
386 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) -1) #t #f) n) => 1)
387 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) 0) #t #f) n) => 1)
388 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) 1) #t #f) n) => 1)
389 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) -1) #t) n) => 1)
390 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) 0) #t) n) => 1)
391 (my-check (let ((n 0)) (if-rel? (begin (set! n (+ n 1)) 1) #t) n) => 1)
392 ))))
393
394 (define (check:ifs)
395
396 (my-check-if2 if=? =)
397 (my-check-if2 if<? <)
398 (my-check-if2 if>? >)
399 (my-check-if2 if<=? <=)
400 (my-check-if2 if>=? >=)
401 (my-check-if2 if-not=? (lambda (x y) (not (= x y))))
402
403 ) ; check:if2
404
405 ; <? etc. macros
406
407 (define-syntax my-check-chain2
408 (syntax-rules ()
409 ((my-check-chain2 rel? rel)
410 (begin
411 ; all chains of length 2
412 (my-check (rel? ci 0 0) => (rel 0 0))
413 (my-check (rel? ci 0 1) => (rel 0 1))
414 (my-check (rel? ci 1 0) => (rel 1 0))
415
416 ; using default-compare
417 (my-check (rel? 0 0) => (rel 0 0))
418 (my-check (rel? 0 1) => (rel 0 1))
419 (my-check (rel? 1 0) => (rel 1 0))
420
421 ; as a combinator
422 (my-check ((rel? ci) 0 0) => (rel 0 0))
423 (my-check ((rel? ci) 0 1) => (rel 0 1))
424 (my-check ((rel? ci) 1 0) => (rel 1 0))
425
426 ; using default-compare as a combinator
427 (my-check ((rel?) 0 0) => (rel 0 0))
428 (my-check ((rel?) 0 1) => (rel 0 1))
429 (my-check ((rel?) 1 0) => (rel 1 0))
430 ))))
431
432 (define (list->set xs) ; xs a list of integers
433 (if (null? xs)
434 '()
435 (let ((max-xs
436 (let max-without-apply ((m 1) (xs xs))
437 (if (null? xs)
438 m
439 (max-without-apply (max m (car xs)) (cdr xs))))))
440 (let ((in-xs? (make-vector (+ max-xs 1) #f)))
441 (do-ec (:list x xs) (vector-set! in-xs? x #t))
442 (list-ec (:vector in? (index x) in-xs?)
443 (if in?)
444 x)))))
445
446 (define-syntax arguments-used ; set of arguments (integer, >=0) used in compare
447 (syntax-rules ()
448 ((arguments-used (rel1/rel2 compare arg ...))
449 (let ((used '()))
450 (rel1/rel2 (lambda (x y)
451 (set! used (cons x (cons y used)))
452 (compare x y))
453 arg ...)
454 (list->set used)))))
455
456 (define-syntax my-check-chain3
457 (syntax-rules ()
458 ((my-check-chain3 rel1/rel2? rel1 rel2)
459 (begin
460 ; all chains of length 3
461 (my-check (rel1/rel2? ci 0 0 0) => (and (rel1 0 0) (rel2 0 0)))
462 (my-check (rel1/rel2? ci 0 0 1) => (and (rel1 0 0) (rel2 0 1)))
463 (my-check (rel1/rel2? ci 0 1 0) => (and (rel1 0 1) (rel2 1 0)))
464 (my-check (rel1/rel2? ci 1 0 0) => (and (rel1 1 0) (rel2 0 0)))
465 (my-check (rel1/rel2? ci 1 1 0) => (and (rel1 1 1) (rel2 1 0)))
466 (my-check (rel1/rel2? ci 1 0 1) => (and (rel1 1 0) (rel2 0 1)))
467 (my-check (rel1/rel2? ci 0 1 1) => (and (rel1 0 1) (rel2 1 1)))
468 (my-check (rel1/rel2? ci 0 1 2) => (and (rel1 0 1) (rel2 1 2)))
469 (my-check (rel1/rel2? ci 0 2 1) => (and (rel1 0 2) (rel2 2 1)))
470 (my-check (rel1/rel2? ci 1 2 0) => (and (rel1 1 2) (rel2 2 0)))
471 (my-check (rel1/rel2? ci 1 0 2) => (and (rel1 1 0) (rel2 0 2)))
472 (my-check (rel1/rel2? ci 2 0 1) => (and (rel1 2 0) (rel2 0 1)))
473 (my-check (rel1/rel2? ci 2 1 0) => (and (rel1 2 1) (rel2 1 0)))
474
475 ; using default-compare
476 (my-check (rel1/rel2? 0 0 0) => (and (rel1 0 0) (rel2 0 0)))
477 (my-check (rel1/rel2? 0 0 1) => (and (rel1 0 0) (rel2 0 1)))
478 (my-check (rel1/rel2? 0 1 0) => (and (rel1 0 1) (rel2 1 0)))
479 (my-check (rel1/rel2? 1 0 0) => (and (rel1 1 0) (rel2 0 0)))
480 (my-check (rel1/rel2? 1 1 0) => (and (rel1 1 1) (rel2 1 0)))
481 (my-check (rel1/rel2? 1 0 1) => (and (rel1 1 0) (rel2 0 1)))
482 (my-check (rel1/rel2? 0 1 1) => (and (rel1 0 1) (rel2 1 1)))
483 (my-check (rel1/rel2? 0 1 2) => (and (rel1 0 1) (rel2 1 2)))
484 (my-check (rel1/rel2? 0 2 1) => (and (rel1 0 2) (rel2 2 1)))
485 (my-check (rel1/rel2? 1 2 0) => (and (rel1 1 2) (rel2 2 0)))
486 (my-check (rel1/rel2? 1 0 2) => (and (rel1 1 0) (rel2 0 2)))
487 (my-check (rel1/rel2? 2 0 1) => (and (rel1 2 0) (rel2 0 1)))
488 (my-check (rel1/rel2? 2 1 0) => (and (rel1 2 1) (rel2 1 0)))
489
490 ; as a combinator
491 (my-check ((rel1/rel2? ci) 0 0 0) => (and (rel1 0 0) (rel2 0 0)))
492 (my-check ((rel1/rel2? ci) 0 0 1) => (and (rel1 0 0) (rel2 0 1)))
493 (my-check ((rel1/rel2? ci) 0 1 0) => (and (rel1 0 1) (rel2 1 0)))
494 (my-check ((rel1/rel2? ci) 1 0 0) => (and (rel1 1 0) (rel2 0 0)))
495 (my-check ((rel1/rel2? ci) 1 1 0) => (and (rel1 1 1) (rel2 1 0)))
496 (my-check ((rel1/rel2? ci) 1 0 1) => (and (rel1 1 0) (rel2 0 1)))
497 (my-check ((rel1/rel2? ci) 0 1 1) => (and (rel1 0 1) (rel2 1 1)))
498 (my-check ((rel1/rel2? ci) 0 1 2) => (and (rel1 0 1) (rel2 1 2)))
499 (my-check ((rel1/rel2? ci) 0 2 1) => (and (rel1 0 2) (rel2 2 1)))
500 (my-check ((rel1/rel2? ci) 1 2 0) => (and (rel1 1 2) (rel2 2 0)))
501 (my-check ((rel1/rel2? ci) 1 0 2) => (and (rel1 1 0) (rel2 0 2)))
502 (my-check ((rel1/rel2? ci) 2 0 1) => (and (rel1 2 0) (rel2 0 1)))
503 (my-check ((rel1/rel2? ci) 2 1 0) => (and (rel1 2 1) (rel2 1 0)))
504
505 ; as a combinator using default-compare
506 (my-check ((rel1/rel2?) 0 0 0) => (and (rel1 0 0) (rel2 0 0)))
507 (my-check ((rel1/rel2?) 0 0 1) => (and (rel1 0 0) (rel2 0 1)))
508 (my-check ((rel1/rel2?) 0 1 0) => (and (rel1 0 1) (rel2 1 0)))
509 (my-check ((rel1/rel2?) 1 0 0) => (and (rel1 1 0) (rel2 0 0)))
510 (my-check ((rel1/rel2?) 1 1 0) => (and (rel1 1 1) (rel2 1 0)))
511 (my-check ((rel1/rel2?) 1 0 1) => (and (rel1 1 0) (rel2 0 1)))
512 (my-check ((rel1/rel2?) 0 1 1) => (and (rel1 0 1) (rel2 1 1)))
513 (my-check ((rel1/rel2?) 0 1 2) => (and (rel1 0 1) (rel2 1 2)))
514 (my-check ((rel1/rel2?) 0 2 1) => (and (rel1 0 2) (rel2 2 1)))
515 (my-check ((rel1/rel2?) 1 2 0) => (and (rel1 1 2) (rel2 2 0)))
516 (my-check ((rel1/rel2?) 1 0 2) => (and (rel1 1 0) (rel2 0 2)))
517 (my-check ((rel1/rel2?) 2 0 1) => (and (rel1 2 0) (rel2 0 1)))
518 (my-check ((rel1/rel2?) 2 1 0) => (and (rel1 2 1) (rel2 1 0)))
519
520 ; test if all arguments are type checked
521 (my-check (arguments-used (rel1/rel2? ci 0 1 2)) => '(0 1 2))
522 (my-check (arguments-used (rel1/rel2? ci 0 2 1)) => '(0 1 2))
523 (my-check (arguments-used (rel1/rel2? ci 1 2 0)) => '(0 1 2))
524 (my-check (arguments-used (rel1/rel2? ci 1 0 2)) => '(0 1 2))
525 (my-check (arguments-used (rel1/rel2? ci 2 0 1)) => '(0 1 2))
526 (my-check (arguments-used (rel1/rel2? ci 2 1 0)) => '(0 1 2))
527 ))))
528
529 (define-syntax my-check-chain
530 (syntax-rules ()
531 ((my-check-chain chain-rel? rel)
532 (begin
533 ; the chain of length 0
534 (my-check (chain-rel? ci) => #t)
535
536 ; a chain of length 1
537 (my-check (chain-rel? ci 0) => #t)
538
539 ; all chains of length 2
540 (my-check (chain-rel? ci 0 0) => (rel 0 0))
541 (my-check (chain-rel? ci 0 1) => (rel 0 1))
542 (my-check (chain-rel? ci 1 0) => (rel 1 0))
543
544 ; all chains of length 3
545 (my-check (chain-rel? ci 0 0 0) => (rel 0 0 0))
546 (my-check (chain-rel? ci 0 0 1) => (rel 0 0 1))
547 (my-check (chain-rel? ci 0 1 0) => (rel 0 1 0))
548 (my-check (chain-rel? ci 1 0 0) => (rel 1 0 0))
549 (my-check (chain-rel? ci 1 1 0) => (rel 1 1 0))
550 (my-check (chain-rel? ci 1 0 1) => (rel 1 0 1))
551 (my-check (chain-rel? ci 0 1 1) => (rel 0 1 1))
552 (my-check (chain-rel? ci 0 1 2) => (rel 0 1 2))
553 (my-check (chain-rel? ci 0 2 1) => (rel 0 2 1))
554 (my-check (chain-rel? ci 1 2 0) => (rel 1 2 0))
555 (my-check (chain-rel? ci 1 0 2) => (rel 1 0 2))
556 (my-check (chain-rel? ci 2 0 1) => (rel 2 0 1))
557 (my-check (chain-rel? ci 2 1 0) => (rel 2 1 0))
558
559 ; check if all arguments are used
560 (my-check (arguments-used (chain-rel? ci 0)) => '(0))
561 (my-check (arguments-used (chain-rel? ci 0 1)) => '(0 1))
562 (my-check (arguments-used (chain-rel? ci 1 0)) => '(0 1))
563 (my-check (arguments-used (chain-rel? ci 0 1 2)) => '(0 1 2))
564 (my-check (arguments-used (chain-rel? ci 0 2 1)) => '(0 1 2))
565 (my-check (arguments-used (chain-rel? ci 1 2 0)) => '(0 1 2))
566 (my-check (arguments-used (chain-rel? ci 1 0 2)) => '(0 1 2))
567 (my-check (arguments-used (chain-rel? ci 2 0 1)) => '(0 1 2))
568 (my-check (arguments-used (chain-rel? ci 2 1 0)) => '(0 1 2))
569 ))))
570
571 (define (check:predicates-from-compare)
572
573 (my-check-chain2 =? =)
574 (my-check-chain2 <? <)
575 (my-check-chain2 >? >)
576 (my-check-chain2 <=? <=)
577 (my-check-chain2 >=? >=)
578 (my-check-chain2 not=? (lambda (x y) (not (= x y))))
579
580 (my-check-chain3 </<? < <)
581 (my-check-chain3 </<=? < <=)
582 (my-check-chain3 <=/<? <= <)
583 (my-check-chain3 <=/<=? <= <=)
584
585 (my-check-chain3 >/>? > >)
586 (my-check-chain3 >/>=? > >=)
587 (my-check-chain3 >=/>? >= >)
588 (my-check-chain3 >=/>=? >= >=)
589
590 (my-check-chain chain=? =)
591 (my-check-chain chain<? <)
592 (my-check-chain chain>? >)
593 (my-check-chain chain<=? <=)
594 (my-check-chain chain>=? >=)
595
596 ) ; check:predicates-from-compare
597
598 ; pairwise-not=?
599
600 (define pairwise-not=?:long-sequences
601 (let ()
602
603 (define (extremal-pivot-sequence r)
604 ; The extremal pivot sequence of order r is a
605 ; permutation of {0..2^(r+1)-2} such that the
606 ; middle element is minimal, and this property
607 ; holds recursively for each binary subdivision.
608 ; This sequence exposes a naive implementation of
609 ; pairwise-not=? chosing the middle element as pivot.
610 (if (zero? r)
611 '(0)
612 (let* ((s (extremal-pivot-sequence (- r 1)))
613 (ns (length s)))
614 (append (list-ec (:list x s) (+ x 1))
615 '(0)
616 (list-ec (:list x s) (+ x ns 1))))))
617
618 (list (list-ec (: i 4096) i)
619 (list-ec (: i 4097 0 -1) i)
620 (list-ec (: i 4099) (modulo (* 1003 i) 4099))
621 (extremal-pivot-sequence 11))))
622
623 (define pairwise-not=?:short-sequences
624 (let ()
625
626 (define (combinations/repeats n l)
627 ; return list of all sublists of l of size n,
628 ; the order of the elements occur in the sublists
629 ; of the output is the same as in the input
630 (let ((len (length l)))
631 (cond
632 ((= n 0) '())
633 ((= n 1) (map list l))
634 ((= len 1) (do ((r '() (cons (car l) r))
635 (i n (- i 1)))
636 ((= i 0) (list r))))
637 (else (append (combinations/repeats n (cdr l))
638 (map (lambda (c) (cons (car l) c))
639 (combinations/repeats (- n 1) l)))))))
640
641 (define (permutations l)
642 ; return a list of all permutations of l
643 (let ((len (length l)))
644 (cond
645 ((= len 0) '(()))
646 ((= len 1) (list l))
647 (else (apply append
648 (map (lambda (p) (insert-every-where (car l) p))
649 (permutations (cdr l))))))))
650
651 (define (insert-every-where x xs)
652 (let loop ((result '()) (before '()) (after xs))
653 (let ((new (append before (cons x after))))
654 (cond
655 ((null? after) (cons new result))
656 (else (loop (cons new result)
657 (append before (list (car after)))
658 (cdr after)))))))
659
660 (define (sequences n max)
661 (apply append
662 (map permutations
663 (combinations/repeats n (list-ec (: i max) i)))))
664
665 (append-ec (: n 5) (sequences n 5))))
666
667 (define (colliding-compare x y)
668 (ci (modulo x 3) (modulo y 3)))
669
670 (define (naive-pairwise-not=? compare . xs)
671 (let ((xs (list->vector xs)))
672 (every?-ec (:range i (- (vector-length xs) 1))
673 (:let xs-i (vector-ref xs i))
674 (:range j (+ i 1) (vector-length xs))
675 (:let xs-j (vector-ref xs j))
676 (not=? compare xs-i xs-j))))
677
678 (define (check:pairwise-not=?)
679
680 ; 0-ary, 1-ary
681 (my-check (pairwise-not=? ci) => #t)
682 (my-check (pairwise-not=? ci 0) => #t)
683
684 ; 2-ary
685 (my-check (pairwise-not=? ci 0 0) => #f)
686 (my-check (pairwise-not=? ci 0 1) => #t)
687 (my-check (pairwise-not=? ci 1 0) => #t)
688
689 ; 3-ary
690 (my-check (pairwise-not=? ci 0 0 0) => #f)
691 (my-check (pairwise-not=? ci 0 0 1) => #f)
692 (my-check (pairwise-not=? ci 0 1 0) => #f)
693 (my-check (pairwise-not=? ci 1 0 0) => #f)
694 (my-check (pairwise-not=? ci 1 1 0) => #f)
695 (my-check (pairwise-not=? ci 1 0 1) => #f)
696 (my-check (pairwise-not=? ci 0 1 1) => #f)
697 (my-check (pairwise-not=? ci 0 1 2) => #t)
698 (my-check (pairwise-not=? ci 0 2 1) => #t)
699 (my-check (pairwise-not=? ci 1 2 0) => #t)
700 (my-check (pairwise-not=? ci 1 0 2) => #t)
701 (my-check (pairwise-not=? ci 2 0 1) => #t)
702 (my-check (pairwise-not=? ci 2 1 0) => #t)
703
704 ; n-ary, n large: [0..n-1], [n,n-1..1], 5^[0..96] mod 97
705 (my-check (apply pairwise-not=? ci (list-ec (: i 10) i)) => #t)
706 (my-check (apply pairwise-not=? ci (list-ec (: i 100) i)) => #t)
707 (my-check (apply pairwise-not=? ci (list-ec (: i 1000) i)) => #t)
708
709 (my-check (apply pairwise-not=? ci (list-ec (: i 10 0 -1) i)) => #t)
710 (my-check (apply pairwise-not=? ci (list-ec (: i 100 0 -1) i)) => #t)
711 (my-check (apply pairwise-not=? ci (list-ec (: i 1000 0 -1) i)) => #t)
712
713 (my-check (apply pairwise-not=? ci
714 (list-ec (: i 97) (modulo (* 5 i) 97)))
715 => #t)
716
717 ; bury another copy of 72 = 5^50 mod 97 in 5^[0..96] mod 97
718 (my-check (apply pairwise-not=? ci
719 (append (list-ec (: i 0 23) (modulo (* 5 i) 97))
720 '(72)
721 (list-ec (: i 23 97) (modulo (* 5 i) 97))))
722 => #f)
723 (my-check (apply pairwise-not=? ci
724 (append (list-ec (: i 0 75) (modulo (* 5 i) 97))
725 '(72)
726 (list-ec (: i 75 97) (modulo (* 5 i) 97))))
727 => #f)
728
729 ; check if all arguments are used
730 (my-check (arguments-used (pairwise-not=? ci 0)) => '(0))
731 (my-check (arguments-used (pairwise-not=? ci 0 1)) => '(0 1))
732 (my-check (arguments-used (pairwise-not=? ci 1 0)) => '(0 1))
733 (my-check (arguments-used (pairwise-not=? ci 0 2 1)) => '(0 1 2))
734 (my-check (arguments-used (pairwise-not=? ci 1 2 0)) => '(0 1 2))
735 (my-check (arguments-used (pairwise-not=? ci 1 0 2)) => '(0 1 2))
736 (my-check (arguments-used (pairwise-not=? ci 2 0 1)) => '(0 1 2))
737 (my-check (arguments-used (pairwise-not=? ci 2 1 0)) => '(0 1 2))
738 (my-check (arguments-used (pairwise-not=? ci 0 0 0 1 0 0 0 2 0 0 0 3))
739 => '(0 1 2 3))
740
741 ; Guess if the implementation is O(n log n):
742 ; The test is run for 2^e pairwise unequal inputs, e >= 1,
743 ; and the number of calls to the compare procedure is counted.
744 ; all pairs: A = Binomial[2^e, 2] = 2^(2 e - 1) * (1 - 2^-e).
745 ; divide and conquer: D = e 2^e.
746 ; Since an implementation can be randomized, the actual count may
747 ; be a random number. We put a threshold at 100 e 2^e and choose
748 ; e such that A/D >= 150, i.e. e >= 12.
749 ; The test is applied to several inputs that are known to cause
750 ; trouble in simplistic sorting algorithms: (0..2^e-1), (2^e+1,2^e..1),
751 ; a pseudo-random permutation, and a sequence with an extremal pivot
752 ; at the center of each subsequence.
753
754 (my-check-ec
755 (:list input pairwise-not=?:long-sequences)
756 (let ((compares 0))
757 (apply pairwise-not=?
758 (lambda (x y)
759 (set! compares (+ compares 1))
760 (ci x y))
761 input)
762 ; (display compares) (newline)
763 (< compares (* 100 12 4096)))
764 (length input))
765
766 ; check many short sequences
767
768 (my-check-ec
769 (:list input pairwise-not=?:short-sequences)
770 (eq?
771 (apply pairwise-not=? colliding-compare input)
772 (apply naive-pairwise-not=? colliding-compare input))
773 input)
774
775 ; check if the arguments are used for short sequences
776
777 (my-check-ec
778 (:list input pairwise-not=?:short-sequences)
779 (let ((args '()))
780 (apply pairwise-not=?
781 (lambda (x y)
782 (set! args (cons x (cons y args)))
783 (colliding-compare x y))
784 input)
785 (equal? (list->set args) (list->set input)))
786 input)
787
788 ) ; check:pairwise-not=?
789
790
791 ; min/max
792
793 (define min/max:sequences
794 (append pairwise-not=?:short-sequences
795 pairwise-not=?:long-sequences))
796
797 (define (check:min/max)
798
799 ; all lists of length 1,2,3
800 (my-check (min-compare ci 0) => 0)
801 (my-check (min-compare ci 0 0) => 0)
802 (my-check (min-compare ci 0 1) => 0)
803 (my-check (min-compare ci 1 0) => 0)
804 (my-check (min-compare ci 0 0 0) => 0)
805 (my-check (min-compare ci 0 0 1) => 0)
806 (my-check (min-compare ci 0 1 0) => 0)
807 (my-check (min-compare ci 1 0 0) => 0)
808 (my-check (min-compare ci 1 1 0) => 0)
809 (my-check (min-compare ci 1 0 1) => 0)
810 (my-check (min-compare ci 0 1 1) => 0)
811 (my-check (min-compare ci 0 1 2) => 0)
812 (my-check (min-compare ci 0 2 1) => 0)
813 (my-check (min-compare ci 1 2 0) => 0)
814 (my-check (min-compare ci 1 0 2) => 0)
815 (my-check (min-compare ci 2 0 1) => 0)
816 (my-check (min-compare ci 2 1 0) => 0)
817
818 (my-check (max-compare ci 0) => 0)
819 (my-check (max-compare ci 0 0) => 0)
820 (my-check (max-compare ci 0 1) => 1)
821 (my-check (max-compare ci 1 0) => 1)
822 (my-check (max-compare ci 0 0 0) => 0)
823 (my-check (max-compare ci 0 0 1) => 1)
824 (my-check (max-compare ci 0 1 0) => 1)
825 (my-check (max-compare ci 1 0 0) => 1)
826 (my-check (max-compare ci 1 1 0) => 1)
827 (my-check (max-compare ci 1 0 1) => 1)
828 (my-check (max-compare ci 0 1 1) => 1)
829 (my-check (max-compare ci 0 1 2) => 2)
830 (my-check (max-compare ci 0 2 1) => 2)
831 (my-check (max-compare ci 1 2 0) => 2)
832 (my-check (max-compare ci 1 0 2) => 2)
833 (my-check (max-compare ci 2 0 1) => 2)
834 (my-check (max-compare ci 2 1 0) => 2)
835
836 ; check that the first minimal value is returned
837 (my-check (min-compare (pair-compare-car ci)
838 '(0 1) '(0 2) '(0 3))
839 => '(0 1))
840 (my-check (max-compare (pair-compare-car ci)
841 '(0 1) '(0 2) '(0 3))
842 => '(0 1))
843
844 ; check for many inputs
845 (my-check-ec
846 (:list input min/max:sequences)
847 (= (apply min-compare ci input)
848 (apply min (apply max input) input))
849 input)
850 (my-check-ec
851 (:list input min/max:sequences)
852 (= (apply max-compare ci input)
853 (apply max (apply min input) input))
854 input)
855 ; Note the stupid extra argument in the apply for
856 ; the standard min/max makes sure the elements are
857 ; identical when apply truncates the arglist.
858
859 ) ; check:min/max
860
861
862 ; kth-largest
863
864 (define kth-largest:sequences
865 pairwise-not=?:short-sequences)
866
867 (define (naive-kth-largest compare k . xs)
868 (let ((vec (list->vector xs)))
869 ; bubble sort: simple, stable, O(|xs|^2)
870 (do-ec (:range n (- (vector-length vec) 1))
871 (:range i 0 (- (- (vector-length vec) 1) n))
872 (if>? (compare (vector-ref vec i)
873 (vector-ref vec (+ i 1)))
874 (let ((vec-i (vector-ref vec i)))
875 (vector-set! vec i (vector-ref vec (+ i 1)))
876 (vector-set! vec (+ i 1) vec-i))))
877 (vector-ref vec (modulo k (vector-length vec)))))
878
879 (define (check:kth-largest)
880
881 ; check extensively against naive-kth-largest
882 (my-check-ec
883 (:list input kth-largest:sequences)
884 (: k (- -2 (length input)) (+ (length input) 2))
885 (= (apply naive-kth-largest colliding-compare k input)
886 (apply kth-largest colliding-compare k input))
887 (list input k))
888
889 ) ;check:kth-largest
890
891 ; compare-by< etc. procedures
892
893 (define (check:compare-from-predicates)
894
895 (my-check-compare
896 (compare-by< <)
897 my-integers)
898
899 (my-check-compare
900 (compare-by> >)
901 my-integers)
902
903 (my-check-compare
904 (compare-by<= <=)
905 my-integers)
906
907 (my-check-compare
908 (compare-by>= >=)
909 my-integers)
910
911 (my-check-compare
912 (compare-by=/< = <)
913 my-integers)
914
915 (my-check-compare
916 (compare-by=/> = >)
917 my-integers)
918
919 ; with explicit arguments
920
921 (my-check-compare
922 (lambda (x y) (compare-by< < x y))
923 my-integers)
924
925 (my-check-compare
926 (lambda (x y) (compare-by> > x y))
927 my-integers)
928
929 (my-check-compare
930 (lambda (x y) (compare-by<= <= x y))
931 my-integers)
932
933 (my-check-compare
934 (lambda (x y) (compare-by>= >= x y))
935 my-integers)
936
937 (my-check-compare
938 (lambda (x y) (compare-by=/< = < x y))
939 my-integers)
940
941 (my-check-compare
942 (lambda (x y) (compare-by=/> = > x y))
943 my-integers)
944
945 ) ; check:compare-from-predicates
946
947
948 (define (check:atomic)
949
950 (my-check-compare boolean-compare my-booleans)
951
952 (my-check-compare char-compare my-chars)
953
954 (my-check-compare char-compare-ci my-chars-ci)
955
956 (my-check-compare string-compare my-strings)
957
958 (my-check-compare string-compare-ci my-strings-ci)
959
960 (my-check-compare symbol-compare my-symbols)
961
962 (my-check-compare integer-compare my-integers)
963
964 (my-check-compare rational-compare my-rationals)
965
966 (my-check-compare real-compare my-reals)
967
968 (my-check-compare complex-compare my-complexes)
969
970 (my-check-compare number-compare my-complexes)
971
972 ) ; check:atomic
973
974 (define (check:refine-select-cond)
975
976 ; refine-compare
977
978 (my-check-compare
979 (lambda (x y) (refine-compare))
980 '(#f))
981
982 (my-check-compare
983 (lambda (x y) (refine-compare (integer-compare x y)))
984 my-integers)
985
986 (my-check-compare
987 (lambda (x y)
988 (refine-compare (integer-compare (car x) (car y))
989 (symbol-compare (cdr x) (cdr y))))
990 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a) (3 . c)))
991
992 (my-check-compare
993 (lambda (x y)
994 (refine-compare (integer-compare (car x) (car y))
995 (symbol-compare (cadr x) (cadr y))
996 (string-compare (caddr x) (caddr y))))
997 '((1 a "a") (1 b "a") (1 b "b") (2 b "c") (2 c "a") (3 a "b") (3 c "b")))
998
999 ; select-compare
1000
1001 (my-check-compare
1002 (lambda (x y) (select-compare x y))
1003 '(#f))
1004
1005 (my-check-compare
1006 (lambda (x y)
1007 (select-compare x y
1008 (integer? (ci x y))))
1009 my-integers)
1010
1011 (my-check-compare
1012 (lambda (x y)
1013 (select-compare x y
1014 (pair? (integer-compare (car x) (car y))
1015 (symbol-compare (cdr x) (cdr y)))))
1016 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a) (3 . c)))
1017
1018 (my-check-compare
1019 (lambda (x y)
1020 (select-compare x y
1021 (else (integer-compare x y))))
1022 my-integers)
1023
1024 (my-check-compare
1025 (lambda (x y)
1026 (select-compare x y
1027 (else (integer-compare (car x) (car y))
1028 (symbol-compare (cdr x) (cdr y)))))
1029 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a) (3 . c)))
1030
1031 (my-check-compare
1032 (lambda (x y)
1033 (select-compare x y
1034 (symbol? (symbol-compare x y))
1035 (string? (string-compare x y))))
1036 '(a b c "a" "b" "c" 1)) ; implicit (else 0)
1037
1038 (my-check-compare
1039 (lambda (x y)
1040 (select-compare x y
1041 (symbol? (symbol-compare x y))
1042 (else (string-compare x y))))
1043 '(a b c "a" "b" "c"))
1044
1045 ; test if arguments are only evaluated once
1046
1047 (my-check
1048 (let ((nx 0) (ny 0) (nt 0))
1049 (select-compare (begin (set! nx (+ nx 1)) 1)
1050 (begin (set! ny (+ ny 1)) 2)
1051 ((lambda (z) (set! nt (+ nt 1)) #f) 0)
1052 ((lambda (z) (set! nt (+ nt 10)) #f) 0)
1053 ((lambda (z) (set! nt (+ nt 100)) #f) 0)
1054 (else 0))
1055 (list nx ny nt))
1056 => '(1 1 222))
1057
1058 ; cond-compare
1059
1060 (my-check-compare
1061 (lambda (x y) (cond-compare))
1062 '(#f))
1063
1064 (my-check-compare
1065 (lambda (x y)
1066 (cond-compare
1067 (((integer? x) (integer? y)) (integer-compare x y))))
1068 my-integers)
1069
1070 (my-check-compare
1071 (lambda (x y)
1072 (cond-compare
1073 (((pair? x) (pair? y)) (integer-compare (car x) (car y))
1074 (symbol-compare (cdr x) (cdr y)))))
1075 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a) (3 . c)))
1076
1077 (my-check-compare
1078 (lambda (x y)
1079 (cond-compare
1080 (else (integer-compare x y))))
1081 my-integers)
1082
1083 (my-check-compare
1084 (lambda (x y)
1085 (cond-compare
1086 (else (integer-compare (car x) (car y))
1087 (symbol-compare (cdr x) (cdr y)))))
1088 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a) (3 . c)))
1089
1090 (my-check-compare
1091 (lambda (x y)
1092 (cond-compare
1093 (((symbol? x) (symbol? y)) (symbol-compare x y))
1094 (((string? x) (string? y)) (string-compare x y))))
1095 '(a b c "a" "b" "c" 1)) ; implicit (else 0)
1096
1097 (my-check-compare
1098 (lambda (x y)
1099 (cond-compare
1100 (((symbol? x) (symbol? y)) (symbol-compare x y))
1101 (else (string-compare x y))))
1102 '(a b c "a" "b" "c"))
1103
1104 ) ; check:refine-select-cond
1105
1106
1107 ; We define our own list/vector data structure
1108 ; as '(my-list x[1] .. x[n]), n >= 0, in order
1109 ; to make sure the default ops don't work on it.
1110
1111 (define (my-list-checked obj)
1112 (if (and (list? obj) (eqv? (car obj) 'my-list))
1113 obj
1114 (error "expected my-list but received" obj)))
1115
1116 (define (list->my-list list) (cons 'my-list list))
1117 (define (my-empty? x) (null? (cdr (my-list-checked x))))
1118 (define (my-head x) (cadr (my-list-checked x)))
1119 (define (my-tail x) (cons 'my-list (cddr (my-list-checked x))))
1120 (define (my-size x) (- (length (my-list-checked x)) 1))
1121 (define (my-ref x i) (list-ref (my-list-checked x) (+ i 1)))
1122
1123 (define (check:data-structures)
1124
1125 (my-check-compare
1126 (pair-compare-car ci)
1127 '((1 . b) (2 . a) (3 . c)))
1128
1129 (my-check-compare
1130 (pair-compare-cdr ci)
1131 '((b . 1) (a . 2) (c . 3)))
1132
1133 ; pair-compare
1134
1135 (my-check-compare pair-compare my-null-or-pairs)
1136
1137 (my-check-compare
1138 (lambda (x y) (pair-compare ci x y))
1139 my-null-or-pairs)
1140
1141 (my-check-compare
1142 (lambda (x y) (pair-compare ci symbol-compare x y))
1143 '((1 . a) (1 . b) (2 . b) (2 . c) (3 . a)))
1144
1145 ; list-compare
1146
1147 (my-check-compare list-compare my-lists)
1148
1149 (my-check-compare
1150 (lambda (x y) (list-compare ci x y))
1151 my-lists)
1152
1153 (my-check-compare
1154 (lambda (x y) (list-compare x y my-empty? my-head my-tail))
1155 (map list->my-list my-lists))
1156
1157 (my-check-compare
1158 (lambda (x y) (list-compare ci x y my-empty? my-head my-tail))
1159 (map list->my-list my-lists))
1160
1161 ; list-compare-as-vector
1162
1163 (my-check-compare list-compare-as-vector my-list-as-vectors)
1164
1165 (my-check-compare
1166 (lambda (x y) (list-compare-as-vector ci x y))
1167 my-list-as-vectors)
1168
1169 (my-check-compare
1170 (lambda (x y) (list-compare-as-vector x y my-empty? my-head my-tail))
1171 (map list->my-list my-list-as-vectors))
1172
1173 (my-check-compare
1174 (lambda (x y) (list-compare-as-vector ci x y my-empty? my-head my-tail))
1175 (map list->my-list my-list-as-vectors))
1176
1177 ; vector-compare
1178
1179 (my-check-compare vector-compare my-vectors)
1180
1181 (my-check-compare
1182 (lambda (x y) (vector-compare ci x y))
1183 my-vectors)
1184
1185 (my-check-compare
1186 (lambda (x y) (vector-compare x y my-size my-ref))
1187 (map list->my-list my-list-as-vectors))
1188
1189 (my-check-compare
1190 (lambda (x y) (vector-compare ci x y my-size my-ref))
1191 (map list->my-list my-list-as-vectors))
1192
1193 ; vector-compare-as-list
1194
1195 (my-check-compare vector-compare-as-list my-vector-as-lists)
1196
1197 (my-check-compare
1198 (lambda (x y) (vector-compare-as-list ci x y))
1199 my-vector-as-lists)
1200
1201 (my-check-compare
1202 (lambda (x y) (vector-compare-as-list x y my-size my-ref))
1203 (map list->my-list my-lists))
1204
1205 (my-check-compare
1206 (lambda (x y) (vector-compare-as-list ci x y my-size my-ref))
1207 (map list->my-list my-lists))
1208
1209 ) ; check:data-structures
1210
1211
1212 (define (check:default-compare)
1213
1214 (my-check-compare default-compare my-objects)
1215
1216 ; check if default-compare refines pair-compare
1217
1218 (my-check-ec
1219 (:list x (index ix) my-objects)
1220 (:list y (index iy) my-objects)
1221 (:let c-coarse (pair-compare x y))
1222 (:let c-fine (default-compare x y))
1223 (or (eqv? c-coarse 0) (eqv? c-fine c-coarse))
1224 (list x y))
1225
1226 ; check if default-compare passes on debug-compare
1227
1228 (my-check-compare (debug-compare default-compare) my-objects)
1229
1230 ) ; check:default-compare
1231
1232
1233 (define (sort-by-less xs pred) ; trivial quicksort
1234 (if (or (null? xs) (null? (cdr xs)))
1235 xs
1236 (append
1237 (sort-by-less (list-ec (:list x (cdr xs))
1238 (if (pred x (car xs)))
1239 x)
1240 pred)
1241 (list (car xs))
1242 (sort-by-less (list-ec (:list x (cdr xs))
1243 (if (not (pred x (car xs))))
1244 x)
1245 pred))))
1246
1247 (define (check:more-examples)
1248
1249 ; define recursive order on tree type (nodes are dotted pairs)
1250
1251 (my-check-compare
1252 (letrec ((c (lambda (x y)
1253 (cond-compare (((null? x) (null? y)) 0)
1254 (else (pair-compare c c x y))))))
1255 c)
1256 (list '() (list '()) (list '() '()) (list (list '())))
1257 ;'(() (() . ()) (() . (() . ())) ((() . ()) . ())) ; Chicken can't parse this ?
1258 )
1259
1260 ; redefine default-compare using select-compare
1261
1262 (my-check-compare
1263 (letrec ((c (lambda (x y)
1264 (select-compare x y
1265 (null? 0)
1266 (pair? (pair-compare c c x y))
1267 (boolean? (boolean-compare x y))
1268 (char? (char-compare x y))
1269 (string? (string-compare x y))
1270 (symbol? (symbol-compare x y))
1271 (number? (number-compare x y))
1272 (vector? (vector-compare c x y))
1273 (else (error "unrecognized type in c" x y))))))
1274 c)
1275 my-objects)
1276
1277 ; redefine default-compare using cond-compare
1278
1279 (my-check-compare
1280 (letrec ((c (lambda (x y)
1281 (cond-compare
1282 (((null? x) (null? y)) 0)
1283 (((pair? x) (pair? y)) (pair-compare c c x y))
1284 (((boolean? x) (boolean? y)) (boolean-compare x y))
1285 (((char? x) (char? y)) (char-compare x y))
1286 (((string? x) (string? y)) (string-compare x y))
1287 (((symbol? x) (symbol? y)) (symbol-compare x y))
1288 (((number? x) (number? y)) (number-compare x y))
1289 (((vector? x) (vector? y)) (vector-compare c x y))
1290 (else (error "unrecognized type in c" x y))))))
1291 c)
1292 my-objects)
1293
1294 ; compare strings with character order reversed
1295
1296 (my-check-compare
1297 (lambda (x y)
1298 (vector-compare-as-list
1299 (lambda (x y) (char-compare y x))
1300 x y string-length string-ref))
1301 '("" "b" "bb" "ba" "a" "ab" "aa"))
1302
1303 ; examples from SRFI text for <? etc.
1304
1305 (my-check (>? "laugh" "LOUD") => #t)
1306 (my-check (<? string-compare-ci "laugh" "LOUD") => #t)
1307 (my-check (sort-by-less '(1 a "b") (<?)) => '("b" a 1))
1308 (my-check (sort-by-less '(1 a "b") (>?)) => '(1 a "b"))
1309
1310 ) ; check:more-examples
1311
1312
1313 ; Real life examples
1314 ; ==================
1315
1316 ; (update/insert compare x s)
1317 ; inserts x into list s, or updates an equivalent element by x.
1318 ; It is assumed that s is sorted with respect to compare,
1319 ; i.e. (apply chain<=? compare s). The result is a list with x
1320 ; replacing the first element s[i] for which (=? compare s[i] x),
1321 ; or with x inserted in the proper place.
1322 ; The algorithm uses linear insertion from the front.
1323
1324 (define (insert/update compare x s) ; insert x into list s, or update
1325 (if (null? s)
1326 (list x)
1327 (if3 (compare x (car s))
1328 (cons x s)
1329 (cons x (cdr s))
1330 (cons (car s) (insert/update compare x (cdr s))))))
1331
1332 ; (index-in-vector compare vec x)
1333 ; an index i such that (=? compare vec[i] x), or #f if there is none.
1334 ; It is assumed that s is sorted with respect to compare,
1335 ; i.e. (apply chain<=? compare (vector->list s)). If there are
1336 ; several elements equivalent to x then it is unspecified which
1337 ; these is chosen.
1338 ; The algorithm uses binary search.
1339
1340 (define (index-in-vector compare vec x)
1341 (let binary-search ((lo -1) (hi (vector-length vec)))
1342 ; invariant: vec[lo] < x < vec[hi]
1343 (if (=? (- hi lo) 1)
1344 #f
1345 (let ((mi (quotient (+ lo hi) 2)))
1346 (if3 (compare x (vector-ref vec mi))
1347 (binary-search lo mi)
1348 mi
1349 (binary-search mi hi))))))
1350
1351
1352 ; Run the checks
1353 ; ==============
1354
1355 (my-check-reset)
1356
1357 ; comment in/out as needed
1358 (check:atomic)
1359 (check:if3)
1360 (check:ifs)
1361 (check:predicates-from-compare)
1362 (check:pairwise-not=?)
1363 (check:min/max)
1364 (check:kth-largest)
1365 (check:compare-from-predicates)
1366 (check:refine-select-cond)
1367 (check:data-structures)
1368 (check:default-compare)
1369 (check:more-examples)
1370
1371 (my-check-summary) ; all examples (99486) correct?