doc/ref/match.texi

   1 @c -*-texinfo-*-
   2 @c This is part of the GNU Guile Reference Manual.
   3 @c Copyright (C) 2010, 2011, 2012  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}.  An error would be raised if
  48 @var{l} did not match the pattern.
  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
  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.
  89
  90 The pattern matcher is defined as follows:
  91
  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}.
 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
 140       | ($ record-name pat_1 ... pat_n) a record
 141       | (= field pat)                   a ``field'' of an object
 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
 150       | (identifier *** pat)            matches pat in a tree and binds
 151                                         identifier to the path leading
 152                                         to the object that matches pat
 153
 154 ooo ::= ...                             zero or more
 155       | ___                             zero or more
 156       | ..1                             1 or more
 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
 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.
 218
 219 Guile also comes with a pattern matcher specifically tailored to SXML
 220 trees, @xref{sxml-match}.