-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsrfi-257.html
1393 lines (1199 loc) · 63 KB
/
srfi-257.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<!--
SPDX-FileCopyrightText: 2024 Sergei Egorov
SPDX-License-Identifier: MIT
-->
<head>
<meta charset="utf-8">
<title>SRFI 257: Simple extendable pattern matcher with backtracking</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">
<meta name="viewport" content="width=device-width, initial-scale=1">
<style>
small { font-size: 14px; vertical-align: 2px; }
body { line-height: 24px; }
pre { font-family: inherit; line-height: 20px; }
</style>
</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>257: Simple extendable pattern matcher with backtracking</h1>
<p>by Sergei Egorov</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+257+at+srfi+dotschemers+dot+org">srfi-257@<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-257/">archive</a>.</p>
<ul>
<li>Received: 2024-12-27</li>
<li>60-day deadline: 2024-02-27</li>
<li>Draft #1 published: 2024-12-29</li>
</ul>
<h2 id="toc">Table of contents</h2>
<ul>
<li><a href="#rationale">Rationale</a></li>
<li>
<a href="#examples">Examples</a>
<ul>
<li><a href="#srfi-204-examples">SRFI-204 Examples</a></li>
<li>
<a href="#advanced-examples">Advanced Examples</a>
<ul>
<li><a href="#backtracking">Backtracking</a></li>
<li><a href="#custom-match-forms">Custom match forms</a></li>
</ul>
</li>
</ul>
</li>
<li>
<a href="#specification">Specification</a>
<ul>
<li><a href="#basic-patterns">Basic patterns</a></li>
<li><a href="#value-pattern">The Value pattern</a></li>
<li><a href="#list-patterns">List patterns</a></li>
<li><a href="#vector-patterns">Vector patterns</a></li>
<li><a href="#string-patterns">String patterns</a></li>
<li><a href="#conversion-patterns">Conversion patterns</a></li>
<li><a href="#predicate-patterns">Predicate patterns</a></li>
<li><a href="#logical-patterns">Logical patterns</a></li>
<li><a href="#compatibility-patterns">Compatibility patterns</a></li>
<li><a href="#core-patterns">Core patterns</a></li>
<li><a href="#pattern-language-construction-patterns">Pattern language construction patterns</a></li>
<li><a href="#defining-new-patterns">Defining new patterns</a></li>
<li><a href="#elements-of-templating">Elements of templating</a></li>
</ul>
</li>
<li>
<a href="#appendix">Appendix</a>
<ul>
<li><a href="#derived-pattern-types">Derived pattern types</a></li>
</ul>
</li>
<li><a href="#implementation">Implementation</a></li>
<li><a href="#acknowledgements">Acknowledgements</a></li>
</ul>
<h2 id="abstract">Abstract</h2>
<p>
Pattern matching extends Scheme's repertoire of conditional constructs, allowing
decomposition of compound data structures and binding their parts to variables.
This SRFI proposes one such construct, <code>match</code>, which provides all
common-denominator functionality described in <a href="https://srfi.schemers.org/srfi-200/">SRFI-200</a>,
adding on top of it support for non-linear patterns and backtracking. Also, the
proposed construct is modular, and allows for convenient extension via the
<code>define-match-pattern</code> mechanism.
</p>
<h2 id="issues">Issues</h2>
<p>Currently, none.</p>
<h2 id="rationale">Rationale</h2>
<p>
This SRFI proposes a construct with functionality similar to the one of “Wright-style”
pattern matcher (see <a href="https://srfi.schemers.org/srfi-204/">SRFI-204</a>), with the following
differences: it supports backtracking, and it is designed in a modular way, allowing user extensions
not only in the form of new types of patterns, but also new pattern matching languages, such as
the Dybvig-Friedman-Hilsdale matcher (<a href="https://srfi.schemers.org/srfi-241/">SRFI-241</a>).
</p>
<p>
This proposal is influenced by the design of the Gerbil matcher
(<a href="https://gerbil.scheme.org/reference/gerbil/prelude/macros.html#pattern_matching">see here</a>).
It features patterns resembling corresponding constructors, e.g. <code>(vector (cons x y))</code>,
unlike most other designs, where patterns resemble printed representation of data, e.g. <code>#((x . y))</code>,
or mix both forms to support pattern combinators such as <code>and</code>. However, while in most other designs
the set of constructor-like pattern forms is fixed, and their names are hardwired in the design,
the proposed construct makes constructor-like pattern forms “first-class” components that
can be created/imported/exported independently; they are just macros, implementing an
internal protocol.
</p>
<p>
The downside of this approach is that one can no longer name pattern matchers after regular
constructors as they cannot share the same namespace. To stay within the bounds of what can be
implemented via regular <code>syntax-rules</code>, the choice was made to use tilde-prefixed names,
so the above pattern becomes <code>(~vector (~cons x y))</code>. This convention is used for all
forms of patterns except for <code>quote</code> and <code>quasiquote</code>, which have convenient
reader abbreviations and thus are built into the matcher.
</p>
<p>
Traditional patterns, resembling printed representations, are supported “under quasiquote”,
as proposed in (withdrawn) <a href="https://srfi.schemers.org/srfi-200/">SRFI-200</a>.
New types of patterns as well as new forms of pattern languages can be built via
<code>define-match-pattern</code> form, which provides a <code>syntax-rules</code> -like
mechanism for pattern rewriting.
</p>
<h2 id="examples">Examples</h2>
<h3 id="srfi-204-examples">SRFI-204 Examples</h3>
<p>
The examples below are taken from <a href="https://srfi.schemers.org/srfi-204/">SRFI-204</a>
and adapted to demonstrate the same functionality using the proposed pattern syntax in its
constructor-like and quasiquoted forms:
</p>
<p> Literal patterns: </p> <pre><code>(<b>let</b> ([ls (list 'a "b" #f 2 '() #\c '#(1))])
(list (<b>match</b> ls [(~list 'a "b" #f 2 '() #\c #(1)) 'ok])
(<b>match</b> ls [`(a "b" #f 2 () #\c #(1)) 'ok])))
⟹ (ok ok)
</code></pre> <p> Pattern variables: </p> <pre><code>(<b>match</b> (list 1 2 3) [(~list a b c) b]) ⟹ 2
(<b>match</b> (list 1 2 3) [(~list _ b _) b]) ⟹ 2
(<b>match</b> (list 1 2 3) [`(a ,b c) b] [_ 'fail]) ⟹ fail
(<b>match</b> (list 1 2 3) [`(1 ,b ,_) b] [_ 'fail]) ⟹ 2
</code></pre> <p> Nonlinear patterns: </p> <pre><code>(<b>match</b> (list 'A 'B 'A) [(~list a b a) a] [_ 'fail]) ⟹ A
(<b>match</b> (list 'A 'B 'A) [`(,a b ,a) a] [_ 'fail]) ⟹ fail
(<b>match</b> (list 'A 'B 'A) [`(,a B ,a) a] [_ 'fail]) ⟹ A
(<b>match</b> (list 'A 'B 'A) [`(,a ,b ,a) a] [_ 'fail]) ⟹ A
</code></pre> <p> In this proposal, quasiquoted and regular patterns can be arbitrarily combined: </p>
<pre><code>(<b>let</b> ([x '(1 2 3 4)])
(list (<b>match</b> x [(~cons a (~append b (~list c))) (list a b c)])
(<b>match</b> x [(~cons a `(,@b ,@(~list c))) (list a b c)])
(<b>match</b> x [(~cons a `(,@b ,c)) (list a b c)])
(<b>match</b> x [`(,a ,@b ,c) (list a b c)])))
⟹ ((1 (2 3) 4) (1 (2 3) 4) (1 (2 3) 4) (1 (2 3) 4))
</code></pre> <p> Ellipsis (<code>~etc</code>) and tail patterns: </p> <pre><code>(<b>match</b> (list 1 2) [(~list* 1 2 (~etc 3)) #t]) ⟹ #t
(<b>match</b> (list 1 2 3) [(~list* 1 2 (~etc 3)) #t]) ⟹ #t
(<b>match</b> (list 1 2 3 3 3) [(~list* 1 2 (~etc 3)) #t]) ⟹ #t
(<b>match</b> '((a time) (stitch saves) (in nine)) [(~etc (~list x y)) (list x y)])
⟹ ((a stitch in) (time saves nine))
(<b>match</b> '((a b) (c d) (e f)) [(~etc (~list x y)) (list x y)])
⟹ ((a c e) (b d f))
(<b>define</b> (transpose x)
(<b>match</b> x [(~etc (~cons a (~etc b))) (cons a (transpose b))] [_ '()]))
(transpose '((1 2 3) (4 5 6))) ⟹ ((1 4) (2 5) (3 6))
(<b>define</b> (palindrome? str)
(<b>let</b> loop ([chars (filter char-alphabetic?
(string->list (string-foldcase str)))])
(<b>match</b> chars
['() #t]
[(~list a) #t]
[(~cons a (~append (~etc b) (~list a))) (loop b)]
[_ #f])))
(palindrome? "Able was I, ere I saw Elba.") ⟹ #t
(palindrome? "Napoleon") ⟹ #f
(<b>define</b> (first-column x)
(<b>match</b> x [(~etc (~cons a (~etc _))) a]))
(first-column '((1 2 3) (4 5 6) (7 8 9))) ⟹ (1 4 7)
</code></pre> <p> This proposal disagrees with “Wright-style” matcher (WSM) on <code>quasiquote</code> <code>unquote-splicing</code> patterns; in this proposal, they are
treated in accordance with the regular quasiquote rules, rather than being turned into <code>...</code> repeats: </p> <pre><code>(<b>match</b> (list 1 2) [`(1 2 ,@3) #t] [_ #f]) ⟹ #f ;</code> WSM returns <code>#t
(<b>match</b> '(1 2 . 3) [`(1 2 ,@3) #t] [_ #f]) ⟹ #t ;</code> WSM returns <code>#f
(<b>match</b> (list 1 2 3 3 3) [`(1 2 ,@3) #t] [_ #f]) ⟹ #f ;</code> WSM returns <code>#t
</code></pre> <p> WSM-compatible behavior can be imitated by explicit insertion of <code>~etc</code>: </p>
<pre><code>(<b>match</b> (list 1 2) [`(1 2 ,@(~etc 3)) #t] [_ #f]) ⟹ #t
(<b>match</b> '(1 2 . 3) [`(1 2 ,@(~etc 3)) #t] [_ #f]) ⟹ #f
(<b>match</b> (list 1 2 3 3 3) [`(1 2 ,@(~etc 3)) #t] [_ #f]) ⟹ #t
</code></pre> <p> Unlike WSM, this proposal supports non-linearity in and out of “ellipsis” patterns: </p>
<pre><code>(<b>match</b> '((1 2 3 4) ((1) (2) (3) (4)) (1 2 3 4))
[(~list a* (~etc (~list a*)) a*) a*])
⟹ (1 2 3 4)
</code></pre>
<p>Some WSM postfix operators do not have built-in equivalents, but can be easily defined.
An analog of WSM <code>**1</code> can be defined as follows: </p> <pre><code>(<b>define-match-pattern</b> ~etc+ ()
[(~etc+ p) (~pair? (~etc p))])
(<b>match</b> (list 1 2) [(~list* a b (~etc+ c)) c] [_ #f]) ⟹ #f
(<b>match</b> (list 1 2 3) [(~list* a b (~etc+ c)) c] [_ #f]) ⟹ (3)
</code></pre> <p> An analog of WSM <code>=..</code> <i>k</i> can be defined as follows: </p> <pre><code>(<b>define-match-pattern</b> ~etc= ()
[(~etc= k p)
(~and (~list? (~prop length => k))
(~etc p))])
(<b>match</b> '((a b) (c d) (e f))
[(~etc= 3 (~list x y)) (list x y)]
[_ 'fail])
⟹ ((a c e) (b d f))
(<b>match</b> '((a b) (c d) (e f) (g h))
[(~etc= 3 (~list x y)) (list x y)]
[_ 'fail])
⟹ fail
</code></pre> <p> An analog of WSM <code>*..</code> <i>k</i> <i>j</i> can be defined as follows: </p> <pre><code>(<b>define-match-pattern</b> ~etc** ()
[(~etc** k j p)
(~and (~list? (~prop length => (~and (~test >= (k)) (~test <= (j)))))
(~etc p))])
(<b>match</b> '((a b) (c d) (e f))
[(~etc** 2 4 (~list x y)) (list x y)]
[_ 'fail])
⟹ ((a c e) (b d f))
(<b>match</b> '((a b) (c d) (e f) (g h))
[(~etc** 2 4 (~list x y)) (list x y)]
[_ 'fail])
⟹ ((a c e g) (b d f h))
(<b>match</b> '((a b) (c d) (e f) (g h) (i j))
[(~etc** 2 4 (~list x y)) (list x y)]
[_ 'fail])
⟹ fail
</code></pre> <p> Tail patterns will match dotted pairs, and ellipsis patterns won't: </p> <pre><code>(<b>define</b> (keys x)
(<b>match</b> x [(~etc (~cons a (~etc _))) a] [_ 'fail]))
(keys '((a 1) (b 2) (c 3))) ⟹ (a b c)
(keys '((a . 1) (b . 2) (c . 3))) ⟹ fail
(<b>define</b> (keys x)
(<b>match</b> x [(~etc (~cons a _)) a] [_ 'fail]))
(keys '((a 1) (b 2) (c 3))) ⟹ (a b c)
(keys '((a . 1) (b . 2) (c . 3))) ⟹ (a b c)
</code></pre> <p> Logical patterns: </p> <pre><code>(<b>match</b> 1 [(~and) #t]) ⟹ #t
(<b>match</b> 1 [(~and x) x]) ⟹ 1
(<b>match</b> 1 [(~and x 1) x]) ⟹ 1
(<b>match</b> #f [(~and) #t] [_ #f]) ⟹ #t
(<b>match</b> #f [(~and x) (=> fail) (<b>if</b> x #t (fail))] [_ #f]) ⟹ #f
(<b>match</b> 1 [(~or) #t] [_ #f]) ⟹ #f
(<b>match</b> 1 [(~or x) x]) ⟹ 1
(<b>match</b> 1 [(~or x 2) x]) ⟹ 1
(<b>define</b> (last-matches-one-of-first-three x)
(<b>match</b> x [`(,a ,a) #t]
[`(,a ,b ,@c ,(~or a b)) #t]
[`(,a ,b ,c ,@d ,c) #t]
[_ #f]))
(last-matches-one-of-first-three '(1 2 3 4 5 1)) ⟹ #t
(last-matches-one-of-first-three '(1 2 3 4 5 2)) ⟹ #t
(last-matches-one-of-first-three '(1 2 3 4 5 3)) ⟹ #t
(last-matches-one-of-first-three '(1 2 3 4 5 6)) ⟹ #f
(<b>define</b> (last-matches-one-of-first-three2 x)
(<b>match</b> x
[`(,a ,a) #t]
[`(,a ,b ,@c ,d) (=> fail)
(<b>if</b> (or (equal? d a) (equal? d b)) #t (fail))]
[`(,a ,b ,c ,@d ,e) (equal? c e)]
[_ #f]))
(last-matches-one-of-first-three2 '(1 2 3 4 5 1)) ⟹ #t
(last-matches-one-of-first-three2 '(1 2 3 4 5 2)) ⟹ #t
(last-matches-one-of-first-three2 '(1 2 3 4 5 3)) ⟹ #t
(last-matches-one-of-first-three2 '(1 2 3 4 5 6)) ⟹ #f
</code></pre> <p> This proposal explicitly assigns <code>#f</code> to undefined <code>~or</code> variables: </p> <pre><code>(<b>match</b> '(0 1 2 3 4 5 6 7)
[(~etc (~or 2 6 rest)) rest])
⟹ (0 1 #f 3 4 5 #f 7)
</code></pre> <p>Single-argument <code>~not</code> patterns are supported.
It is an error for a pattern to refer to the same variable inside and outside of a <code>~not</code> pattern. </p> <pre><code>(<b>match</b> 1 [(~and x (~not #f)) x] [_ 'fail]) ⟹ 1
(<b>match</b> #f [(~and x (~not #f)) x] [_ 'fail]) ⟹ fail
(<b>match</b> 1 [(~not 2) #t]) ⟹ #t
</code></pre> <p> Predicates and fields are supported via <code>~?</code> and <code>~=</code>
respectively.
It is an error to refer to pattern variables in non-subpattern parts of these patterns.
</p>
<pre><code>(<b>match</b> 1 [(~? odd? x) x]) ⟹ 1
(<b>match</b> '(a) [(~= car x) x]) ⟹ a
</code></pre> <p>Tests that use more than one pattern variable should be implemented
in the body of the corresponding rule:
</p>
<pre><code>(<b>define</b> (fibby? x)
(<b>match</b> x
[(~list* a b c rest)
(<b>if</b> (= (+ a b) c) (fibby? (cons b (cons c rest))) #f)]
[(~list a b) #t]
[(~list a) #t]
['() #t]
[_ #f]))
(fibby? '(4 7 11 18 29 47)) ⟹ #t
</code></pre>
<h3 id="advanced-examples">Advanced Examples</h3>
<p>
This section contains examples specific to new functionality proposed in this SRFI.
</p>
<h4 id="backtracking">Backtracking</h4>
<p>
Some patterns marked as “iterative” in this proposal may match the input object
in multiple ways, or “solutions”, backtracking to the next solution if the current
one causes downstream patterns to fail (structurally or because of a disagreement
in values of shared pattern variables). This process may be time-consuming, but
is associated only with iterative patterns, causing no overhead if they are not
used.</p>
<p>
Iteration strategies vary between pattern types.
Regular versions of append matchers are greedy, giving preference
to long leftmost segments:
</p>
<pre><code>(<b>define</b> (pr* p . x*)
(for-each (<b>lambda</b> (x) (display x p)) x*))
(<b>let</b> ([p (open-output-string)])
(<b>match</b> "abc"
[(~string-append a (~string b) c)
(=> next) (pr* p "1:" a "+" b "+" c ";") (next)]
[(~string-append a c)
(=> next) (pr* p "2:" a "+" c ";") (next)]
[x (get-output-string p)]))
⟹ "1:ab+c+;2:abc+;"
</code></pre>
<p> Non-greedy appends give preference to short leftmost segments: </p>
<pre><code>(<b>let</b> ([p (open-output-string)])
(<b>match</b> "abc"
[(~string-append/ng a (~string b) c)
(=> next) (pr* p "1:" a "+" b "+" c ";") (next)]
[(~string-append/ng a c)
(=> next) (pr* p "2:" a "+" c ";") (next)]
[x (get-output-string p)]))
⟹ "1:+a+bc;2:+abc;"
</code></pre>
<p> Backtracking can be triggered explicitly from the body; calling “back”
guard formal retries starting from the current pattern's most recent backtracking
point or next rule if none left: </p>
<pre><code>(<b>let</b> ([p (open-output-string)])
(<b>match</b> "abc"
[(~string-append a (~string b) c)
(=> next back) (pr* p "1:" a "+" b "+" c ";") (back)]
[(~string-append a c)
(=> next back) (pr* p "2:" a "+" c ";") (back)]
[x (get-output-string p)]))
⟹ "1:ab+c+;1:a+b+c;1:+a+bc;2:abc+;2:ab+c;2:a+bc;2:+abc;"
</code></pre>
<h4 id="custom-match-forms">Custom match forms</h4>
<p>
It is relatively easy to define custom match forms with a different pattern grammar
using a combination of “converter” patterns defined via <code>define-match-pattern</code>
and regular <code>syntax-rule</code> -based macro for the form itself. This process is
facilitated by a collection of special-purpose patterns, as shown below.
</p>
<p>
Defining an analog of Dybvig-Friedman-Hilsdale matcher with support for catamorphism feature:
</p>
<pre><code>(<b>define-match-pattern</b> ~cmp->p (<...> <_> unquote ->)
[(_ l ,(x)) (~prop l => x)]
[(_ l ,(f -> x ...)) (~prop f => x ...)]
[(_ l ,(x ...)) (~prop l => x ...)]
[(_ l ,<_>) _]
[(_ l ,x) x]
[(_ l ()) '()]
[(_ l (x <...>)) (~etc (~cmp->p l x))] ; optimization
[(_ l (x <...> . y)) (~append/t y (~etc (~cmp->p l x)) (~cmp->p l y))]
[(_ l (x . y)) (~cons (~cmp->p l x) (~cmp->p l y))]
[(_ l #(x ...)) (~list->vector (~cmp->p l (x ...)))]
[(_ l other) 'other])
(<b>define-syntax</b> cm-match
(<b>syntax-rules</b> (guard)
[(_ () l x () (c ...))
(<b>match</b> x c ... [_ (error "cm-match error" x)])]
[(_ () l x ([cmp (guard . e*) . b] cmc ...) (c ...))
(<b>cm-match</b> () l x (cmc ...)
(c ... [(~replace-specials <...> <_> (~cmp->p l cmp))
(=> n) (<b>if</b> (<b>and</b> . e*) (<b>let</b> () . b) (n))]))]
[(_ () l x ([cmp . b] cmc ...) (c ...))
(<b>cm-match</b> () l x (cmc ...)
(c ... [(~replace-specials <...> <_> (~cmp->p l cmp))
(<b>let</b> () . b)]))]
[(_ x cmc ...)
(<b>let</b> l ([v x]) (<b>cm-match</b> () l v (cmc ...) ()))]))
</code></pre>
<p>
Note the use of <code>~replace-specials</code> pattern that substitutes
<code><...> <_></code> for special <code>... _</code> identifiers
to allow them to have their regular meaning inside <code>define-match-pattern</code>.
It also uses the <code>~append/t</code> pattern, a non-iterative list append
that takes the length of the tail segment from its first argument.
</p>
<p>
Defined in this manner, <code>cm-match</code> can be used as D-F-H <code>match</code>
w.r.t. matching functionality (no enhanced right-hand-side <code>quasiquote</code>):
</p>
<pre><code>(<b>let</b> ([simple-eval
(<b>lambda</b> (x)
(<b>cm-match</b> x
[,i (guard (integer? i)) i]
[(+ ,[x*] ...) (apply + x*)]
[(* ,[x*] ...) (apply * x*)]
[(- ,[x] ,[y]) (- x y)]
[(/ ,[x] ,[y]) (/ x y)]
[,x (error "invalid expression" x)]))])
(simple-eval '(+ (- 0 1) (+ 2 3))))
⟹
4
(<b>let</b> ([split
(<b>lambda</b> (lis)
(<b>cm-match</b> lis
[() (values '() '())]
[(,x) (values `(,x) '())]
[(,x ,y . ,[odds evens])
(values `(,x . ,odds)
`(,y . ,evens))]))])
(split '(a b c d e f)))
⟹
(a c e)
(b d f)
</code></pre> <p> Defining a <code>syntax-rules</code> -like matcher with explicit list of literal identifiers: </p>
<pre><code>(<b>define-match-pattern</b> ~srp->p (<...> <_>)
[(_ l* ()) '()]
[(_ l* (x <...>)) (~etc (~srp->p l* x))] ; optimization
[(_ l* (x <...> . y)) (~append/t y (~etc (~srp->p l* x)) (~srp->p l* y))]
[(_ l* (x . y)) (~cons (~srp->p l* x) (~srp->p l* y))]
[(_ l* #(x ...)) (~list->vector (~srp->p l* (x ...)))]
[(_ l* <_>) _]
[(_ l* a) (~if-id-member a l* 'a a)])
(<b>define-syntax</b> sr-match
(<b>syntax-rules</b> (=>)
[(_ () l* v () (c ...))
(<b>match</b> v c ... [_ (error "sr-match error" v)])]
[(_ () l* v ([srp . b] src ...) (c ...))
(sr-match () l* v (src ...) (c ...
[(~replace-specials <...> <_> (~srp->p l* srp)) . b]))]
[(_ x (l ...) src ...)
(<b>let</b> ([v x]) (sr-match () (l ...) v (src ...) ()))]))
</code></pre>
<p> Note the use of <code>~if-id-member</code> pattern to check if an atom is a literal. </p>
<pre><code>(sr-match '(begin (a 5) (b 6) (c 7) (d 8))
(begin)
[(begin (x* y*) ...) (list x* y*)])
⟹ ((a b c d) (5 6 7 8))
(sr-match '((a b c d) (e f g) (h i) (j))
()
[((x* y** ...) ...) (list x* y**)])
⟹ ((a e h j) ((b c d) (f g) (i) ()))
</code></pre>
<h2 id="specification">Specification</h2>
<p>
The grammar rules for the <code>match</code> form are:
</p>
<p>
⟨<i>match expression</i> ⟩ ⟶ <br>
<code> </code> <code>(match</code> ⟨<i>expression</i> ⟩ ⟨<i>match rule</i> ⟩*<code>)</code><br>
<br>
⟨<i>match rule</i> ⟩ ⟶<br>
<code> </code> <code>(</code> ⟨<i>match pattern</i> ⟩ <code>(=></code> ⟨<i>next id</i> ⟩ ⟨<i>back id</i> ⟩<code>)</code> ⟨<i>body</i> ⟩ <code>)</code><br>
<code>|</code> <code>(</code> ⟨<i>match pattern</i> ⟩ <code>(=></code> ⟨<i>next id</i> ⟩<code>)</code> ⟨<i>body</i> ⟩ <code>)</code><br>
<code>|</code> <code>(</code> ⟨<i>match pattern</i> ⟩ ⟨<i>body</i> ⟩ <code>)</code><br>
<br>
⟨<i>match pattern</i> ⟩ ⟶ <br>
<code> </code> ⟨<i>underscore</i> ⟩<br>
<code>|</code> ⟨<i>match pattern identifier</i> ⟩<br>
<code>|</code> ⟨<i>atomic datum</i> ⟩<br>
<code>|</code> <code>(quote</code> ⟨<i>datum</i> ⟩<code>)</code> <br>
<code>|</code> <code>(quasiquote</code> ⟨<i>match quasipattern</i> ⟩<code>)</code> <br>
<code>|</code> <code>(</code>⟨<i>match pattern name</i> ⟩ ⟨<i>match pattern argument</i> ⟩*<code>)</code> <br>
<br>
⟨<i>match quasipattern</i> ⟩ ⟶<br>
<code> </code> <code>()</code><br>
<code>|</code> ⟨<i>atomic datum</i> ⟩<br>
<code>|</code> ⟨<i>match quasipattern symbol</i> ⟩<br>
<code>|</code> <code>(unquote</code> ⟨<i>match pattern</i> ⟩<code>)</code><br>
<code>|</code> <code>((unquote-splicing</code> ⟨<i>match pattern</i> ⟩<code>)</code> <code>.</code> ⟨<i>match quasipattern</i> ⟩<code>)</code><br>
<code>|</code> <code>(</code>⟨<i>match quasipattern</i> ⟩ <code>.</code> ⟨<i>match quasipattern</i> ⟩<code>)</code><br>
<code>|</code> <code>#(</code>⟨<i>match quasipattern</i> ⟩*<code>)</code><br>
<br>
⟨<i>atomic datum</i> ⟩ ⟶<br>
<code>|</code> ⟨<i>boolean</i> ⟩<br>
<code>|</code> ⟨<i>number</i> ⟩<br>
<code>|</code> ⟨<i>character</i> ⟩<br>
<code>|</code> ⟨<i>string</i> ⟩<br>
<code>|</code> ⟨<i>bytevector</i> ⟩<br>
<br>
⟨<i>match pattern name</i> ⟩ ⟶<br>
<code> </code> ⟨<i>any identifier except </i> <code>quote</code><i> and </i> <code>quasiquote</code>⟩<br>
<br>
⟨<i>match pattern argument</i> ⟩ ⟶<br>
<code> </code> ⟨<i>match pattern</i> ⟩<br>
<code>|</code> ⟨<i>expression</i> ⟩<br>
<br>
⟨<i>match pattern identifier</i> ⟩ ⟶ <br>
<code> </code> ⟨<i>any identifier except </i> <code>_</code><i> and </i> <code>...</code>⟩<br>
<br>
⟨<i>next id</i> ⟩ ⟶ <br>
<code> </code> ⟨<i>identifier</i> ⟩<br>
<br>
⟨<i>back id</i> ⟩ ⟶ <br>
<code> </code> ⟨<i>identifier</i> ⟩<br>
<br>
⟨<i>match quasipattern symbol</i> ⟩ ⟶ <br>
<code> </code> ⟨<i>any identifier except </i> <code>unquote</code><i> and </i> <code>unquote-splicing</code> ⟩<br>
<br>
⟨<i>underscore</i> ⟩ ⟶<br>
<code> </code> ⟨<i>the identifier _</i> ⟩<br>
<br>
</p>
<p>Note: <code>_</code> <code>...</code> and <code>=></code> in this specification are auxiliary syntaxes
identical to the like-named syntaxes exported by the standard libraries.
</p>
<p>
The <code>match</code> form behaves as follows. First, its ⟨<i>expression</i> ⟩
argument is evaluated. It should return a single value, which is subsequently tested against match
rules in the order they are written until a matching rule is found. If no matching rules are found,
<code>match</code> returns an undefined value.
</p>
<p>
A rule matches if the application of its pattern to the input object is successful and there is
no “guard clause” (a list of the <code>=></code> keyword followed by one or two identifiers). If a guard
clause is present, it binds the identifiers to procedures allowing advanced control over the matching
process. The first procedure, bound within the body to ⟨<i>next id</i> ⟩, allows
one to skip the current rule as if its pattern match was unsuccessful. In two-identifier guard clauses,
the second procedure, bound within the body to ⟨<i>back id</i> ⟩, allows one to
tell the matcher that the current pattern should consider another way to match, or, if no such way exists,
to skip the pattern as if its attempts to match were unsuccessful.
Both procedures accept no arguments and can be called from any <i>tail position</i> within the
body. If these procedures are called in a different way, the behavior is undefined.
</p>
<p>
Patterns may contain <i>pattern variables</i>, which, if the application of a pattern succeeds, become
bound in the corresponding body to parts of the input object. The values of these variables may be
used to reject the match via the guard clause mechanism described above.
</p>
<p>
Any pattern containing pattern variables may use the same variable in more than one place within the
pattern. In such cases all the corresponding sub-objects, assigned to the repeated variable,
should “agree”, i.e. to be the same according to the <code>equal?</code> predicate.
</p>
<p>
Some patterns, marked as <i>(iterative)</i> in the pattern entry's header line, may match the input
object in multiple ways. The matcher tries these different matches in the order specified in the
pattern description. The two common orders are <i>(iterative, greedy)</i> , maximizing the number
of input elements matched by sub-patterns on the left, and <i>(iterative, non-greedy)</i> , maximizing
the number of input elements matched by sub-patterns on the right. When iterative patterns are
nested, the matcher acts as if the outer pattern has full control over the decomposition of the input object,
allowing its immediate sub-patterns to work with the parts in the order the outer pattern supplies them.
</p>
<h3 id="basic-patterns">Basic patterns</h3>
<p>
⟨<i>atomic datum</i> ⟩ <i>match pattern</i><br>
Literal patterns, ⟨<i>boolean</i> ⟩, …,
⟨<i>bytevector</i> ⟩, match equal objects (in terms of
Scheme <code>equal?</code> predicate).
</p>
<p>
<code><b>_</b></code> <i>match pattern</i><br>
The ⟨<i>underscore</i> ⟩ pattern matches anything. It is
not a variable, so it produces no bindings visible in the body of the rule.
</p>
<p>
⟨<i>match pattern identifier</i> ⟩ <i>match pattern</i><br>
The ⟨<i>match pattern identifier</i> ⟩ pattern acts like a
pattern variable. A pattern variable will match any value and can be repeated.
If repeated, all subsequent like-named variables will only match the value that
is <code>equal?</code> to the value matched by the first. This value is made
available inside ⟨<i>body</i> ⟩ as if a local identifier
with the same name is bound to this value via the <code>let</code> form surrounding
the body. It is an error to refer to pattern identifiers in expressions within
the same pattern, or to use them as ⟨<i>match pattern name</i> ⟩s.
</p>
<p>
<code>(<b>quote</b></code> ⟨<i>datum</i> ⟩<code>)</code> <i>match pattern</i><br>
The <code>quote</code> pattern matches ⟨<i>datum</i> ⟩. Again, the Scheme <code>equal?</code>
predicate is used for comparison.
</p>
<p>
<code>(<b>quasiquote</b></code> ⟨<i>match quasipattern</i> ⟩<code>)</code> <i>match pattern</i><br>
The <code>quasiquote</code> pattern can be understood in terms of regular patterns. It is translated
into combinations of basic patterns and data patterns (see below). The translation
function T[⟨<i>match quasipattern</i> ⟩] ⟹ ⟨<i>match pattern</i> ⟩
resembles simplified translation of the regular <code>quasiquote</code> form (shown in
abbreviated form, first matching rule is chosen):
</p>
<table>
<tbody><tr><td>T[<code>()</code>]</td> <td> ⟹ </td> <td><code>(quote ())</code></td></tr>
<tr><td>T[⟨<i>atomic datum</i> ⟩]</td> <td> ⟹ </td> <td>⟨<i>atomic datum</i> ⟩</td></tr>
<tr><td>T[<code>(unquote</code> ⟨<i>mp</i> ⟩<code>)</code>]</td>
<td> ⟹ </td> <td>⟨<i>mp</i> ⟩</td></tr>
<tr><td>T[<code>((unquote-splicing</code> ⟨<i>mp</i> ⟩<code>))</code>]</td>
<td> ⟹ </td> <td>⟨<i>mp</i> ⟩</td></tr>
<tr><td>T[<code>((unquote-splicing</code> ⟨<i>mp</i> ⟩<code>)</code> <code>.</code>
⟨<i>mqp</i> ⟩<code>)</code>]</td>
<td> ⟹ </td> <td><code>(<b>~append</b></code> ⟨<i>mp</i> ⟩
T[⟨<i>mqp</i> ⟩]<code>)</code></td></tr>
<tr><td>T[<code>(</code>⟨<i>mqp</i> <sub>1</sub>⟩ <code>.</code>
⟨<i>mqp</i> <sub>2</sub>⟩<code>)]</code></td>
<td> ⟹ </td> <td><code>(<b>~cons</b></code> T[⟨<i>mqp</i> <sub>1</sub>⟩]
T[⟨<i>mqp</i> <sub>2</sub>⟩]<code>)</code></td></tr>
<tr><td>T[<code>#(</code>⟨<i>mqp</i> ⟩*)]</td>
<td> ⟹ </td> <td><code>(<b>~vector</b></code>
T[⟨<i>mqp</i> <sub>1</sub>⟩]*<code>)</code></td></tr>
</tbody></table>
<h3 id="value-pattern">The Value pattern</h3>
<p>
<code>(<b>~value</b></code> ⟨<i>expression</i> ⟩<code>)</code> <i>match pattern</i><br>
The <code>~value</code> pattern matches if the input object is equal to the result of
⟨<i>expression</i> ⟩, calculated during the match. The Scheme <code>equal?</code>
predicate is used for comparison. This is a convenient way to match against non-pattern variables
bound outside the <code>match</code> form.
</p>
<h3 id="list-patterns">List patterns</h3>
<p>List patterns match various types of pairs/lists, disassembling them into sub-expressions
and applying to them sub-patterns. They are named to resemble the corresponding Scheme constructors,
and can be combined in a similar manner. Their names are not built into the matcher, but
are defined via <code>define-syntax</code> or its equivalent, so they need to be imported
if used explicitly.
</p>
<p>
<code>(<b>~cons</b></code> ⟨<i>mp</i> <sub>a</sub>⟩ ⟨<i>mp</i> <sub>d</sub>⟩<code>)</code>
<i>match pattern</i><br>
The <code>~cons</code> pattern matches a pair whose <i>car</i> matches
⟨<i>mp</i> <sub>a</sub>⟩ and whose <i>cdr</i> matches
⟨<i>mp</i> <sub>d</sub>⟩.
</p>
<p>
<code>(<b>~list</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
The <code>~list</code> pattern matches a proper list, with as many elements
as there are sub-patterns ⟨<i>mp</i> ⟩ … The elements
should match the corresponding patterns.
</p>
<p>
<code>(<b>~append</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, greedy)</i><br>
The <code>~append</code> pattern matches a (possibly improper) list, breaking it into
sub-list segments that can match the corresponding patterns
⟨<i>mp</i> ⟩ … If the list is improper, the last
pattern is applied to its improper tail segment.<br>
<i>Note:</i> This is an example of a <i>iterative</i>
pattern that may match the target list in many different ways; all “solutions” are equally good,
as long as the segments can be appended via <code>append</code> to make a list equal to the original.<br>
The solutions are tried starting with ones maximizing the length of the leftmost
segment, then the segment after it, etc.
</p>
<p>
<code>(<b>~append/ng</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, non-greedy)</i><br>
The <code>~append/ng</code> pattern is a “non-greedy” variant of the
<code>~append</code> pattern. The solutions are tried starting with the ones maximizing
the length of the rightmost segment, then the segment before it, etc.
</p>
<p>
<code>(<b>~append/t</b></code> ⟨<i>datum</i> ⟩ ⟨<i>mp</i> <sub>1</sub>⟩ ⟨<i>mp</i> <sub>2</sub>⟩<code>)</code>
<i>match pattern</i><br>
The <code>~append/t</code> pattern matches a (possibly improper) list, breaking it
into two sub-list segments to be matched against ⟨<i>mp</i> <sub>1</sub>⟩ and
⟨<i>mp</i> <sub>2</sub>⟩ sub-patterns.<br>
The number of pairs in the “spine”
of the second segment is assumed to be equal to the number of “spine” pairs in the
⟨<i>datum</i> ⟩ argument. The pattern fails if the input list is
too short to be broken in this way.<br>
<i>Note:</i> This is a non-iterative pattern, providing
a degree of efficiency where the length of the tail pattern is known at macroexpand time.
</p>
<p>
<code>(<b>~etc</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
The <code>~etc</code> pattern matches a proper list such that every one
of its elements matches ⟨<i>mp</i> ⟩. If this sub-pattern
contains pattern vars, they will be bound to lists of values obtained via
individual element matches in the order of their appearance in the input
list. This pattern can be compared to the postfix ellipsis (<code>...</code>)
notation popularized by <code>syntax-rules</code>.<br>
<i>Note:</i> If one or more sub-pattern
variables are also used outside <code>~etc</code> in the same rule-level pattern,
the non-linear “agreement” rule is applied to the final list values collected
by <code>~etc</code> pattern on a successful match.
</p>
<h3 id="vector-patterns">Vector patterns</h3>
<p>
A limited set of vector patterns is provided. Advanced matching of vectors
can be performed either by combining list patterns with <code>~list->vector</code>
converter pattern, or by using core patterns described further below.
</p>
<p>
<code>(<b>~vector</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
The <code>~vector</code> pattern matches a vector with as many elements
as there are sub-patterns ⟨<i>mp</i> ⟩ … The elements
should match the corresponding patterns.
</p>
<p>
<code>(<b>~vector-append</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, greedy)</i><br>
The <code>~vector-append</code> pattern matches a vector, breaking it into
sub-vector segments that can match the corresponding patterns
⟨<i>mp</i> ⟩ … <br>
<i>Note:</i> This is another example of an <i>iterative</i>
pattern that may match the target vector in many different ways; the “solutions” are attempted starting
with ones maximizing the length of the leftmost segment, then the segment after it, etc.
</p>
<p>
<code>(<b>~vector-append/ng</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, non-greedy)</i><br>
The <code>~vector-append/ng</code> pattern is a “non-greedy” variant of the
<code>~vector-append</code> pattern. The solutions are attempted starting with the ones maximizing
the length of the rightmost segment, then the segment before it, etc.
</p>
<h3 id="string-patterns">String patterns</h3>
<p>
A limited set of string patterns is provided. Advanced matching of strings
can be performed either by combining list patterns with the <code>~list->string</code>
converter pattern, or by using core patterns described further below.
</p>
<p>
<code>(<b>~string</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
The <code>~string</code> pattern matches a string with as many characters
as there are sub-patterns ⟨<i>mp</i> ⟩ … The characters
should match the corresponding patterns.
</p>
<p>
<code>(<b>~string-append</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, greedy)</i><br>
The <code>~string-append</code> pattern matches a string, breaking it into
sub-string segments that can match the corresponding patterns
⟨<i>mp</i> ⟩ … <br>
This is an iterative pattern; the “solutions” are attempted starting
with ones maximizing the length of the leftmost segment, then the segment after it, etc.
</p>
<p>
<code>(<b>~string-append/ng</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative, non-greedy)</i><br>
The <code>~string-append/ng</code> pattern is a “non-greedy” variant of the
<code>~string-append</code> pattern. The solutions are attempted starting with the ones maximizing
the length of the rightmost segment, then the segment before it, etc.
</p>
<h3 id="conversion-patterns">Conversion patterns</h3>
<p>
These patterns extend the functionality of the matcher, allowing it to deal with
numbers and symbols as strings, strings and chars as numbers, etc. They are named
as the corresponding constructors, so they match the types of objects on the right-hand
side of <code>-></code>, e.g. <code>~list->vector</code> matches vectors, but
applies its sub-pattern to the result of converting it to the list. They should be read
as converters for the <i>patterns</i> : <code>~list->vector</code> makes
a vector pattern from a list pattern, and so on.
</p>
<p>
<code>(<b>~vector->list</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~string->list</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~list->vector</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~list->string</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~string->symbol</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~symbol->string</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
Convert a pattern built to match objects of the type on the left side of <code>-></code>
to the pattern able to match objects of the type on the right side of <code>-></code>,
applying the “reverse” converter function internally. E.g. if ⟨<i>mp</i> ⟩
can match lists of characters, <code>(<b>~list->string</b></code> ⟨<i>mp</i> ⟩<code>)</code>
will be able to match strings containing the same characters.
</p>
<p>
<code>(<b>~string->number</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~string->number</b></code> ⟨<i>mp</i> ⟩ ⟨<i>rx</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~number->string</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
<code>(<b>~number->string</b></code> ⟨<i>mp</i> ⟩ ⟨<i>rx</i> ⟩<code>)</code>
<i>match pattern</i><br>
These patterns convert between number and string patterns, accepting an optional
⟨<i>rx</i> ⟩ argument. This additional argument is an expression that is evaluated
when the pattern is applied, and should produce a radix, suitable for Scheme
<code>string->number</code> / <code>number->string</code> procedures.
</p>
<h3 id="predicate-patterns">Predicate patterns</h3>
<p>
The role of predicate patterns is to “guard” their optional sub-patterns, making sure
that the input object belongs to a certain Scheme type. Their set is limited, but new
ones can be easily defined, as explained in the section on derived patterns below.
</p>
<p>
<code>(<b>~null?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~pair?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~list?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~boolean?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~number?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~integer?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~vector?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~string?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~symbol?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
<code>(<b>~char?</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
These patterns match if the input object satisfies the like-named Scheme predicate, and
if there are sub-patterns, <em>all</em> sub-patterns match the same input object, as if
combined with the <code>~and</code> pattern combinator (see below).
</p>
<h3 id="logical-patterns">Logical patterns</h3>
<p>
These patterns apply their sub-patterns to the same input object, combining the
results of individual sub-pattern matches.
</p>
<p>
<code>(<b>~and</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
This pattern matches if <em>all</em> its sub-patterns match the input object. If
sub-patterns contain pattern values, all of them are bound on a successful match. If there
are no sub-patterns, the <code>(~and)</code> pattern matches any object.
</p>
<p>
<code>(<b>~or</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern (iterative)</i><br>
This pattern matches if <em>any</em> of its sub-patterns matches the input object. The
sub-patterns are tried in the order they are written, and the process stops on
the first sub-pattern that matches successfully (but see the note below). If sub-patterns
contain pattern values, all of them are bound on a match, but only the ones
belonging to the “successful” sub-pattern will have their values bound to the
corresponding sub-values. The remaining variables are bound to <code>#f</code>.
If there are no sub-patterns, the <code>(~or)</code> pattern fails on every object.<br>
<i>Note:</i> this pattern is iterative in the following
sense: if backtracking exhausts all possible match solutions for one sub-pattern, the next
one is tried, then the next one, etc.
</p>
<p>
<code>(<b>~not</b></code> ⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
This pattern matches if its sub-pattern fails to match the input object. If
it contains pattern variables, none of them are bound on a successful match
(i.e. when the sub-pattern fails).
</p>
<h3 id="compatibility-patterns">Compatibility patterns</h3>
<p>
These patterns provide functionality popularized by the “Wright-style” family of matchers.
</p>
<p>
<code>(<b>~list*</b></code> ⟨<i>mp</i> ⟩ … ⟨<i>mp</i> <sub>t</sub>⟩<code>)</code>
<i>match pattern</i><br>
The <code>~list*</code> pattern matches a (possibly improper) list with at least as many elements
as there are sub-patterns ⟨<i>mp</i> ⟩ … The elements
should match the corresponding patterns; the remaining part of the list should match the
last pattern, ⟨<i>mp</i> <sub>t</sub>⟩.
</p>
<p>
<code>(<b>~list-no-order</b></code> ⟨<i>mp</i> ⟩ …<code>)</code>
<i>match pattern</i><br>
This pattern matches a proper list with as many elements
as there are sub-patterns ⟨<i>mp</i> ⟩ … It iterates through
all possible permutations of the input list looking for one with elements that
match the corresponding sub-patterns.
</p>
<p>
<code>(<b>~list-no-order*</b></code> ⟨<i>mp</i> ⟩ … ⟨<i>mp</i> <sub>t</sub>⟩<code>)</code>
<i>match pattern</i><br>
This pattern matches a (possibly improper) list with at least as many elements
as there are sub-patterns ⟨<i>mp</i> ⟩ … The elements,
in some permutation of the original order, should match the corresponding patterns;
the remaining part of the list should match the
last pattern, ⟨<i>mp</i> <sub>t</sub>⟩.
</p>
<p>
<code>(<b>~=</b></code> ⟨<i>fn</i> ⟩
⟨<i>mp</i> ⟩<code>)</code>
<i>match pattern</i><br>
In this pattern, ⟨<i>fn</i> ⟩ is not a pattern. The pattern
binds its input value to a fresh variable ⟨<i>iv</i> ⟩,
and then evaluates the <code>(</code>⟨<i>fn</i> ⟩
⟨<i>iv</i> ⟩<code>)</code> expression; its result is matched
against the ⟨<i>mp</i> ⟩ sub-pattern.<br>
<i>Note:</i> ⟨<i>fn</i> ⟩ does not have
to name a function; it can be of any form. The combined expression is evaluated