| 1 | @c -*-texinfo-*- |
| 2 | @c This is part of the GNU Guile Reference Manual. |
| 3 | @c Copyright (C) 2010, 2011 Free Software Foundation, Inc. |
| 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 |
| 29 | object: lists, strings, symbols, records, etc. They can optionally contain |
| 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, |
| 46 | locally binds @var{who} to the value contained in this one-element |
| 47 | list---i.e., the symbol @code{world}. |
| 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 |
| 115 | | ($ record-name pat_1 ... pat_n) a record |
| 116 | | (= field pat) a ``field'' of an object |
| 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 |
| 125 | | (identifier *** pat) matches pat in a tree and binds |
| 126 | identifier to the path leading |
| 127 | to the object that matches pat |
| 128 | |
| 129 | ooo ::= ... zero or more |
| 130 | | ___ zero or more |
| 131 | | ..1 1 or more |
| 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 | |
| 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. |
| 193 | |
| 194 | Guile also comes with a pattern matcher specifically tailored to SXML |
| 195 | trees, @xref{sxml-match}. |