Commit | Line | Data |
---|---|---|
358663ca LC |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Guile Reference Manual. | |
44cd5575 | 3 | @c Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. |
358663ca LC |
4 | @c See the file guile.texi for copying conditions. |
5 | @c | |
6 | ||
7 | @c The pattern syntax is taken from the documentation available in | |
8 | @c Andrew K. Wright's implementation of `match.scm', which is in the | |
9 | @c public domain. See Guile before commit | |
10 | @c d967913f05301a35573c5d3f7217d0994bbb1016 (Thu Jun 17 2010) or | |
11 | @c <http://www.cs.indiana.edu/scheme-repository/code.match.html>. | |
12 | ||
13 | @c FIXME: This section is a bit rough on the edges. The introduction | |
14 | @c could be improved, e.g., by adding examples. | |
15 | ||
16 | @node Pattern Matching | |
17 | @section Pattern Matching | |
18 | ||
19 | @cindex pattern matching | |
20 | @cindex (ice-9 match) | |
21 | ||
22 | The @code{(ice-9 match)} module provides a @dfn{pattern matcher}, | |
23 | written by Alex Shinn, and compatible with Andrew K. Wright's pattern | |
24 | matcher found in many Scheme implementations. | |
25 | ||
26 | @cindex pattern variable | |
27 | A pattern matcher can match an object against several patterns and | |
28 | extract the elements that make it up. Patterns can represent any Scheme | |
85680678 | 29 | object: lists, strings, symbols, records, etc. They can optionally contain |
358663ca LC |
30 | @dfn{pattern variables}. When a matching pattern is found, an |
31 | expression associated with the pattern is evaluated, optionally with all | |
32 | pattern variables bound to the corresponding elements of the object: | |
33 | ||
34 | @example | |
35 | (let ((l '(hello (world)))) | |
36 | (match l ;; <- the input object | |
37 | (('hello (who)) ;; <- the pattern | |
38 | who))) ;; <- the expression evaluated upon matching | |
39 | @result{} world | |
40 | @end example | |
41 | ||
42 | In this example, list @var{l} matches the pattern @code{('hello (who))}, | |
43 | because it is a two-element list whose first element is the symbol | |
44 | @code{hello} and whose second element is a one-element list. Here | |
45 | @var{who} is a pattern variable. @code{match}, the pattern matcher, | |
85680678 | 46 | locally binds @var{who} to the value contained in this one-element |
44cd5575 LC |
47 | list---i.e., the symbol @code{world}. An error would be raised if |
48 | @var{l} did not match the pattern. | |
358663ca LC |
49 | |
50 | The same object can be matched against a simpler pattern: | |
51 | ||
52 | @example | |
53 | (let ((l '(hello (world)))) | |
54 | (match l | |
55 | ((x y) | |
56 | (values x y)))) | |
57 | @result{} hello | |
58 | @result{} (world) | |
59 | @end example | |
60 | ||
61 | Here pattern @code{(x y)} matches any two-element list, regardless of | |
62 | the types of these elements. Pattern variables @var{x} and @var{y} are | |
63 | bound to, respectively, the first and second element of @var{l}. | |
64 | ||
44cd5575 LC |
65 | Patterns can be composed, and nested. For instance, @code{...} |
66 | (ellipsis) means that the previous pattern may be matched zero or more | |
67 | times in a list: | |
68 | ||
69 | @example | |
70 | (match lst | |
71 | (((heads tails ...) ...) | |
72 | heads)) | |
73 | @end example | |
74 | ||
75 | @noindent | |
76 | This expression returns the first element of each list within @var{lst}. | |
77 | For proper lists of proper lists, it is equivalent to @code{(map car | |
78 | lst)}. However, it performs additional checks to make sure that | |
79 | @var{lst} and the lists therein are proper lists, as prescribed by the | |
80 | pattern, raising an error if they are not. | |
81 | ||
82 | Compared to hand-written code, pattern matching noticeably improves | |
83 | clarity and conciseness---no need to resort to series of @code{car} and | |
84 | @code{cdr} calls when matching lists, for instance. It also improves | |
85 | robustness, by making sure the input @emph{completely} matches the | |
86 | pattern---conversely, hand-written code often trades robustness for | |
87 | conciseness. And of course, @code{match} is a macro, and the code it | |
88 | expands to is just as efficient as equivalent hand-written code. | |
358663ca LC |
89 | |
90 | The pattern matcher is defined as follows: | |
91 | ||
df0a1002 BT |
92 | @deffn {Scheme Syntax} match exp clause1 clause2 @dots{} |
93 | Match object @var{exp} against the patterns in @var{clause1} | |
94 | @var{clause2} @dots{} in the order in which they appear. Return the | |
95 | value produced by the first matching clause. If no clause matches, | |
96 | throw an exception with key @code{match-error}. | |
97 | ||
98 | Each clause has the form @code{(pattern body1 body2 @dots{})}. Each | |
99 | @var{pattern} must follow the syntax described below. Each body is an | |
100 | arbitrary Scheme expression, possibly referring to pattern variables of | |
101 | @var{pattern}. | |
358663ca LC |
102 | @end deffn |
103 | ||
104 | @c FIXME: Document other forms: | |
105 | @c | |
106 | @c exp ::= ... | |
107 | @c | (match exp clause ...) | |
108 | @c | (match-lambda clause ...) | |
109 | @c | (match-lambda* clause ...) | |
110 | @c | (match-let ((pat exp) ...) body) | |
111 | @c | (match-let* ((pat exp) ...) body) | |
112 | @c | (match-letrec ((pat exp) ...) body) | |
113 | @c | (match-define pat exp) | |
114 | @c | |
115 | @c clause ::= (pat body) | (pat => exp) | |
116 | ||
117 | The syntax and interpretation of patterns is as follows: | |
118 | ||
119 | @verbatim | |
120 | patterns: matches: | |
121 | ||
122 | pat ::= identifier anything, and binds identifier | |
123 | | _ anything | |
124 | | () the empty list | |
125 | | #t #t | |
126 | | #f #f | |
127 | | string a string | |
128 | | number a number | |
129 | | character a character | |
130 | | 'sexp an s-expression | |
131 | | 'symbol a symbol (special case of s-expr) | |
132 | | (pat_1 ... pat_n) list of n elements | |
133 | | (pat_1 ... pat_n . pat_{n+1}) list of n or more | |
134 | | (pat_1 ... pat_n pat_n+1 ooo) list of n or more, each element | |
135 | of remainder must match pat_n+1 | |
136 | | #(pat_1 ... pat_n) vector of n elements | |
137 | | #(pat_1 ... pat_n pat_n+1 ooo) vector of n or more, each element | |
138 | of remainder must match pat_n+1 | |
139 | | #&pat box | |
85680678 LC |
140 | | ($ record-name pat_1 ... pat_n) a record |
141 | | (= field pat) a ``field'' of an object | |
358663ca LC |
142 | | (and pat_1 ... pat_n) if all of pat_1 thru pat_n match |
143 | | (or pat_1 ... pat_n) if any of pat_1 thru pat_n match | |
144 | | (not pat_1 ... pat_n) if all pat_1 thru pat_n don't match | |
145 | | (? predicate pat_1 ... pat_n) if predicate true and all of | |
146 | pat_1 thru pat_n match | |
147 | | (set! identifier) anything, and binds setter | |
148 | | (get! identifier) anything, and binds getter | |
149 | | `qp a quasi-pattern | |
7a1e1937 LC |
150 | | (identifier *** pat) matches pat in a tree and binds |
151 | identifier to the path leading | |
152 | to the object that matches pat | |
358663ca LC |
153 | |
154 | ooo ::= ... zero or more | |
155 | | ___ zero or more | |
7a1e1937 | 156 | | ..1 1 or more |
358663ca LC |
157 | |
158 | quasi-patterns: matches: | |
159 | ||
160 | qp ::= () the empty list | |
161 | | #t #t | |
162 | | #f #f | |
163 | | string a string | |
164 | | number a number | |
165 | | character a character | |
166 | | identifier a symbol | |
167 | | (qp_1 ... qp_n) list of n elements | |
168 | | (qp_1 ... qp_n . qp_{n+1}) list of n or more | |
169 | | (qp_1 ... qp_n qp_n+1 ooo) list of n or more, each element | |
170 | of remainder must match qp_n+1 | |
171 | | #(qp_1 ... qp_n) vector of n elements | |
172 | | #(qp_1 ... qp_n qp_n+1 ooo) vector of n or more, each element | |
173 | of remainder must match qp_n+1 | |
174 | | #&qp box | |
175 | | ,pat a pattern | |
176 | | ,@pat a pattern | |
177 | @end verbatim | |
178 | ||
179 | The names @code{quote}, @code{quasiquote}, @code{unquote}, | |
180 | @code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and}, | |
181 | @code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and | |
182 | @code{___} cannot be used as pattern variables. | |
183 | ||
85680678 LC |
184 | Here is a more complex example: |
185 | ||
186 | @example | |
187 | (use-modules (srfi srfi-9)) | |
188 | ||
189 | (let () | |
190 | (define-record-type person | |
191 | (make-person name friends) | |
192 | person? | |
193 | (name person-name) | |
194 | (friends person-friends)) | |
195 | ||
196 | (letrec ((alice (make-person "Alice" (delay (list bob)))) | |
197 | (bob (make-person "Bob" (delay (list alice))))) | |
198 | (match alice | |
199 | (($ person name (= force (($ person "Bob")))) | |
200 | (list 'friend-of-bob name)) | |
201 | (_ #f)))) | |
202 | ||
203 | @result{} (friend-of-bob "Alice") | |
204 | @end example | |
205 | ||
206 | @noindent | |
207 | Here the @code{$} pattern is used to match a SRFI-9 record of type | |
208 | @var{person} containing two or more slots. The value of the first slot | |
209 | is bound to @var{name}. The @code{=} pattern is used to apply | |
210 | @code{force} on the second slot, and then checking that the result | |
211 | matches the given pattern. In other words, the complete pattern matches | |
212 | any @var{person} whose second slot is a promise that evaluates to a | |
213 | one-element list containing a @var{person} whose first slot is | |
214 | @code{"Bob"}. | |
215 | ||
216 | Please refer to the @code{ice-9/match.upstream.scm} file in your Guile | |
217 | installation for more details. | |
358663ca LC |
218 | |
219 | Guile also comes with a pattern matcher specifically tailored to SXML | |
220 | trees, @xref{sxml-match}. |