Commit | Line | Data |
---|---|---|
358663ca LC |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Guile Reference Manual. | |
85680678 | 3 | @c Copyright (C) 2010, 2011 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 LC |
46 | locally binds @var{who} to the value contained in this one-element |
47 | list---i.e., the symbol @code{world}. | |
358663ca LC |
48 | |
49 | The same object can be matched against a simpler pattern: | |
50 | ||
51 | @example | |
52 | (let ((l '(hello (world)))) | |
53 | (match l | |
54 | ((x y) | |
55 | (values x y)))) | |
56 | @result{} hello | |
57 | @result{} (world) | |
58 | @end example | |
59 | ||
60 | Here pattern @code{(x y)} matches any two-element list, regardless of | |
61 | the types of these elements. Pattern variables @var{x} and @var{y} are | |
62 | bound to, respectively, the first and second element of @var{l}. | |
63 | ||
64 | ||
65 | The pattern matcher is defined as follows: | |
66 | ||
67 | @deffn {Scheme Syntax} match exp clause ... | |
68 | Match object @var{exp} against the patterns in the given @var{clause}s, | |
69 | in the order in which they appear. Return the value produced by the | |
70 | first matching clause. If no @var{clause} matches, throw an exception | |
71 | with key @code{match-error}. | |
72 | ||
73 | Each @var{clause} has the form @code{(pattern body)}. Each | |
74 | @var{pattern} must follow the syntax described below. Each @var{body} | |
75 | is an arbitrary Scheme expression, possibly referring to pattern | |
76 | variables of @var{pattern}. | |
77 | @end deffn | |
78 | ||
79 | @c FIXME: Document other forms: | |
80 | @c | |
81 | @c exp ::= ... | |
82 | @c | (match exp clause ...) | |
83 | @c | (match-lambda clause ...) | |
84 | @c | (match-lambda* clause ...) | |
85 | @c | (match-let ((pat exp) ...) body) | |
86 | @c | (match-let* ((pat exp) ...) body) | |
87 | @c | (match-letrec ((pat exp) ...) body) | |
88 | @c | (match-define pat exp) | |
89 | @c | |
90 | @c clause ::= (pat body) | (pat => exp) | |
91 | ||
92 | The syntax and interpretation of patterns is as follows: | |
93 | ||
94 | @verbatim | |
95 | patterns: matches: | |
96 | ||
97 | pat ::= identifier anything, and binds identifier | |
98 | | _ anything | |
99 | | () the empty list | |
100 | | #t #t | |
101 | | #f #f | |
102 | | string a string | |
103 | | number a number | |
104 | | character a character | |
105 | | 'sexp an s-expression | |
106 | | 'symbol a symbol (special case of s-expr) | |
107 | | (pat_1 ... pat_n) list of n elements | |
108 | | (pat_1 ... pat_n . pat_{n+1}) list of n or more | |
109 | | (pat_1 ... pat_n pat_n+1 ooo) list of n or more, each element | |
110 | of remainder must match pat_n+1 | |
111 | | #(pat_1 ... pat_n) vector of n elements | |
112 | | #(pat_1 ... pat_n pat_n+1 ooo) vector of n or more, each element | |
113 | of remainder must match pat_n+1 | |
114 | | #&pat box | |
85680678 LC |
115 | | ($ record-name pat_1 ... pat_n) a record |
116 | | (= field pat) a ``field'' of an object | |
358663ca LC |
117 | | (and pat_1 ... pat_n) if all of pat_1 thru pat_n match |
118 | | (or pat_1 ... pat_n) if any of pat_1 thru pat_n match | |
119 | | (not pat_1 ... pat_n) if all pat_1 thru pat_n don't match | |
120 | | (? predicate pat_1 ... pat_n) if predicate true and all of | |
121 | pat_1 thru pat_n match | |
122 | | (set! identifier) anything, and binds setter | |
123 | | (get! identifier) anything, and binds getter | |
124 | | `qp a quasi-pattern | |
7a1e1937 LC |
125 | | (identifier *** pat) matches pat in a tree and binds |
126 | identifier to the path leading | |
127 | to the object that matches pat | |
358663ca LC |
128 | |
129 | ooo ::= ... zero or more | |
130 | | ___ zero or more | |
7a1e1937 | 131 | | ..1 1 or more |
358663ca LC |
132 | |
133 | quasi-patterns: matches: | |
134 | ||
135 | qp ::= () the empty list | |
136 | | #t #t | |
137 | | #f #f | |
138 | | string a string | |
139 | | number a number | |
140 | | character a character | |
141 | | identifier a symbol | |
142 | | (qp_1 ... qp_n) list of n elements | |
143 | | (qp_1 ... qp_n . qp_{n+1}) list of n or more | |
144 | | (qp_1 ... qp_n qp_n+1 ooo) list of n or more, each element | |
145 | of remainder must match qp_n+1 | |
146 | | #(qp_1 ... qp_n) vector of n elements | |
147 | | #(qp_1 ... qp_n qp_n+1 ooo) vector of n or more, each element | |
148 | of remainder must match qp_n+1 | |
149 | | #&qp box | |
150 | | ,pat a pattern | |
151 | | ,@pat a pattern | |
152 | @end verbatim | |
153 | ||
154 | The names @code{quote}, @code{quasiquote}, @code{unquote}, | |
155 | @code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and}, | |
156 | @code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and | |
157 | @code{___} cannot be used as pattern variables. | |
158 | ||
85680678 LC |
159 | Here is a more complex example: |
160 | ||
161 | @example | |
162 | (use-modules (srfi srfi-9)) | |
163 | ||
164 | (let () | |
165 | (define-record-type person | |
166 | (make-person name friends) | |
167 | person? | |
168 | (name person-name) | |
169 | (friends person-friends)) | |
170 | ||
171 | (letrec ((alice (make-person "Alice" (delay (list bob)))) | |
172 | (bob (make-person "Bob" (delay (list alice))))) | |
173 | (match alice | |
174 | (($ person name (= force (($ person "Bob")))) | |
175 | (list 'friend-of-bob name)) | |
176 | (_ #f)))) | |
177 | ||
178 | @result{} (friend-of-bob "Alice") | |
179 | @end example | |
180 | ||
181 | @noindent | |
182 | Here the @code{$} pattern is used to match a SRFI-9 record of type | |
183 | @var{person} containing two or more slots. The value of the first slot | |
184 | is bound to @var{name}. The @code{=} pattern is used to apply | |
185 | @code{force} on the second slot, and then checking that the result | |
186 | matches the given pattern. In other words, the complete pattern matches | |
187 | any @var{person} whose second slot is a promise that evaluates to a | |
188 | one-element list containing a @var{person} whose first slot is | |
189 | @code{"Bob"}. | |
190 | ||
191 | Please refer to the @code{ice-9/match.upstream.scm} file in your Guile | |
192 | installation for more details. | |
358663ca LC |
193 | |
194 | Guile also comes with a pattern matcher specifically tailored to SXML | |
195 | trees, @xref{sxml-match}. |