doc/ref/match.texi

   1 @c -*-texinfo-*-
   2 @c This is part of the GNU Guile Reference Manual.
   3 @c Copyright (C) 2010  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, 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 list,
  47 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       | ($ struct-name pat_1 ... pat_n) a structure
 116       | (= field pat)                   a field of a structure
 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
 126 ooo ::= ...                             zero or more
 127       | ___                             zero or more
 128       | ..k                             k or more
 129       | __k                             k or more
 130
 131         quasi-patterns:                 matches:
 132
 133 qp  ::= ()                              the empty list
 134       | #t                              #t
 135       | #f                              #f
 136       | string                          a string
 137       | number                          a number
 138       | character                       a character
 139       | identifier                      a symbol
 140       | (qp_1 ... qp_n)                 list of n elements
 141       | (qp_1 ... qp_n . qp_{n+1})      list of n or more
 142       | (qp_1 ... qp_n qp_n+1 ooo)      list of n or more, each element
 143                                           of remainder must match qp_n+1
 144       | #(qp_1 ... qp_n)                vector of n elements
 145       | #(qp_1 ... qp_n qp_n+1 ooo)     vector of n or more, each element
 146                                           of remainder must match qp_n+1
 147       | #&qp                            box
 148       | ,pat                            a pattern
 149       | ,@pat                           a pattern
 150 @end verbatim
 151
 152 The names @code{quote}, @code{quasiquote}, @code{unquote},
 153 @code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and},
 154 @code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and
 155 @code{___} cannot be used as pattern variables.
 156
 157
 158 Guile also comes with a pattern matcher specifically tailored to SXML
 159 trees, @xref{sxml-match}.