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
|
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.
@c
@c The pattern syntax is taken from the documentation available in
@c Andrew K. Wright's implementation of `match.scm', which is in the
@c public domain. See Guile before commit
@c d967913f05301a35573c5d3f7217d0994bbb1016 (Thu Jun 17 2010) or
@c <http://www.cs.indiana.edu/scheme-repository/code.match.html>.
@c FIXME: This section is a bit rough on the edges. The introduction
@c could be improved, e.g., by adding examples.
@node Pattern Matching
@section Pattern Matching
@cindex pattern matching
@cindex (ice-9 match)
The @code{(ice-9 match)} module provides a @dfn{pattern matcher},
written by Alex Shinn, and compatible with Andrew K. Wright's pattern
matcher found in many Scheme implementations.
@cindex pattern variable
A pattern matcher can match an object against several patterns and
extract the elements that make it up. Patterns can represent any Scheme
object: lists, strings, symbols, records, etc. They can optionally contain
@dfn{pattern variables}. When a matching pattern is found, an
expression associated with the pattern is evaluated, optionally with all
pattern variables bound to the corresponding elements of the object:
@example
(let ((l '(hello (world))))
(match l ;; <- the input object
(('hello (who)) ;; <- the pattern
who))) ;; <- the expression evaluated upon matching
@result{} world
@end example
In this example, list @var{l} matches the pattern @code{('hello (who))},
because it is a two-element list whose first element is the symbol
@code{hello} and whose second element is a one-element list. Here
@var{who} is a pattern variable. @code{match}, the pattern matcher,
locally binds @var{who} to the value contained in this one-element
list---i.e., the symbol @code{world}. An error would be raised if
@var{l} did not match the pattern.
The same object can be matched against a simpler pattern:
@example
(let ((l '(hello (world))))
(match l
((x y)
(values x y))))
@result{} hello
@result{} (world)
@end example
Here pattern @code{(x y)} matches any two-element list, regardless of
the types of these elements. Pattern variables @var{x} and @var{y} are
bound to, respectively, the first and second element of @var{l}.
Patterns can be composed, and nested. For instance, @code{...}
(ellipsis) means that the previous pattern may be matched zero or more
times in a list:
@example
(match lst
(((heads tails ...) ...)
heads))
@end example
@noindent
This expression returns the first element of each list within @var{lst}.
For proper lists of proper lists, it is equivalent to @code{(map car
lst)}. However, it performs additional checks to make sure that
@var{lst} and the lists therein are proper lists, as prescribed by the
pattern, raising an error if they are not.
Compared to hand-written code, pattern matching noticeably improves
clarity and conciseness---no need to resort to series of @code{car} and
@code{cdr} calls when matching lists, for instance. It also improves
robustness, by making sure the input @emph{completely} matches the
pattern---conversely, hand-written code often trades robustness for
conciseness. And of course, @code{match} is a macro, and the code it
expands to is just as efficient as equivalent hand-written code.
The pattern matcher is defined as follows:
@deffn {Scheme Syntax} match exp clause1 clause2 @dots{}
Match object @var{exp} against the patterns in @var{clause1}
@var{clause2} @dots{} in the order in which they appear. Return the
value produced by the first matching clause. If no clause matches,
throw an exception with key @code{match-error}.
Each clause has the form @code{(pattern body1 body2 @dots{})}. Each
@var{pattern} must follow the syntax described below. Each body is an
arbitrary Scheme expression, possibly referring to pattern variables of
@var{pattern}.
@end deffn
@c FIXME: Document other forms:
@c
@c exp ::= ...
@c | (match exp clause ...)
@c | (match-lambda clause ...)
@c | (match-lambda* clause ...)
@c | (match-let ((pat exp) ...) body)
@c | (match-let* ((pat exp) ...) body)
@c | (match-letrec ((pat exp) ...) body)
@c | (match-define pat exp)
@c
@c clause ::= (pat body) | (pat => exp)
The syntax and interpretation of patterns is as follows:
@verbatim
patterns: matches:
pat ::= identifier anything, and binds identifier
| _ anything
| () the empty list
| #t #t
| #f #f
| string a string
| number a number
| character a character
| 'sexp an s-expression
| 'symbol a symbol (special case of s-expr)
| (pat_1 ... pat_n) list of n elements
| (pat_1 ... pat_n . pat_{n+1}) list of n or more
| (pat_1 ... pat_n pat_n+1 ooo) list of n or more, each element
of remainder must match pat_n+1
| #(pat_1 ... pat_n) vector of n elements
| #(pat_1 ... pat_n pat_n+1 ooo) vector of n or more, each element
of remainder must match pat_n+1
| #&pat box
| ($ record-name pat_1 ... pat_n) a record
| (= field pat) a ``field'' of an object
| (and pat_1 ... pat_n) if all of pat_1 thru pat_n match
| (or pat_1 ... pat_n) if any of pat_1 thru pat_n match
| (not pat_1 ... pat_n) if all pat_1 thru pat_n don't match
| (? predicate pat_1 ... pat_n) if predicate true and all of
pat_1 thru pat_n match
| (set! identifier) anything, and binds setter
| (get! identifier) anything, and binds getter
| `qp a quasi-pattern
| (identifier *** pat) matches pat in a tree and binds
identifier to the path leading
to the object that matches pat
ooo ::= ... zero or more
| ___ zero or more
| ..1 1 or more
quasi-patterns: matches:
qp ::= () the empty list
| #t #t
| #f #f
| string a string
| number a number
| character a character
| identifier a symbol
| (qp_1 ... qp_n) list of n elements
| (qp_1 ... qp_n . qp_{n+1}) list of n or more
| (qp_1 ... qp_n qp_n+1 ooo) list of n or more, each element
of remainder must match qp_n+1
| #(qp_1 ... qp_n) vector of n elements
| #(qp_1 ... qp_n qp_n+1 ooo) vector of n or more, each element
of remainder must match qp_n+1
| #&qp box
| ,pat a pattern
| ,@pat a pattern
@end verbatim
The names @code{quote}, @code{quasiquote}, @code{unquote},
@code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and},
@code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and
@code{___} cannot be used as pattern variables.
Here is a more complex example:
@example
(use-modules (srfi srfi-9))
(let ()
(define-record-type person
(make-person name friends)
person?
(name person-name)
(friends person-friends))
(letrec ((alice (make-person "Alice" (delay (list bob))))
(bob (make-person "Bob" (delay (list alice)))))
(match alice
(($ person name (= force (($ person "Bob"))))
(list 'friend-of-bob name))
(_ #f))))
@result{} (friend-of-bob "Alice")
@end example
@noindent
Here the @code{$} pattern is used to match a SRFI-9 record of type
@var{person} containing two or more slots. The value of the first slot
is bound to @var{name}. The @code{=} pattern is used to apply
@code{force} on the second slot, and then checking that the result
matches the given pattern. In other words, the complete pattern matches
any @var{person} whose second slot is a promise that evaluates to a
one-element list containing a @var{person} whose first slot is
@code{"Bob"}.
Please refer to the @code{ice-9/match.upstream.scm} file in your Guile
installation for more details.
Guile also comes with a pattern matcher specifically tailored to SXML
trees, @xref{sxml-match}.
|
