@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
@c Copyright (C) 2010, 2011, 2012  Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.
@c

@c The pattern syntax is taken from the documentation available in
@c Andrew K. Wright's implementation of `match.scm', which is in the
@c public domain.  See Guile before commit
@c d967913f05301a35573c5d3f7217d0994bbb1016 (Thu Jun 17 2010) or
@c <http://www.cs.indiana.edu/scheme-repository/code.match.html>.

@c FIXME: This section is a bit rough on the edges.  The introduction
@c could be improved, e.g., by adding examples.

@node Pattern Matching
@section Pattern Matching

@cindex pattern matching
@cindex (ice-9 match)

The @code{(ice-9 match)} module provides a @dfn{pattern matcher},
written by Alex Shinn, and compatible with Andrew K. Wright's pattern
matcher found in many Scheme implementations.

@cindex pattern variable
A pattern matcher can match an object against several patterns and
extract the elements that make it up.  Patterns can represent any Scheme
object: lists, strings, symbols, records, etc.  They can optionally contain
@dfn{pattern variables}.  When a matching pattern is found, an
expression associated with the pattern is evaluated, optionally with all
pattern variables bound to the corresponding elements of the object:

@example
(let ((l '(hello (world))))
  (match l           ;; <- the input object
    (('hello (who))  ;; <- the pattern
     who)))          ;; <- the expression evaluated upon matching
@result{} world
@end example

In this example, list @var{l} matches the pattern @code{('hello (who))},
because it is a two-element list whose first element is the symbol
@code{hello} and whose second element is a one-element list.  Here
@var{who} is a pattern variable.  @code{match}, the pattern matcher,
locally binds @var{who} to the value contained in this one-element
list---i.e., the symbol @code{world}.  An error would be raised if
@var{l} did not match the pattern.

The same object can be matched against a simpler pattern:

@example
(let ((l '(hello (world))))
  (match l
    ((x y)
     (values x y))))
@result{} hello
@result{} (world)
@end example

Here pattern @code{(x y)} matches any two-element list, regardless of
the types of these elements.  Pattern variables @var{x} and @var{y} are
bound to, respectively, the first and second element of @var{l}.

Patterns can be composed, and nested.  For instance, @code{...}
(ellipsis) means that the previous pattern may be matched zero or more
times in a list:

@example
(match lst
  (((heads tails ...) ...)
   heads))
@end example

@noindent
This expression returns the first element of each list within @var{lst}.
For proper lists of proper lists, it is equivalent to @code{(map car
lst)}.  However, it performs additional checks to make sure that
@var{lst} and the lists therein are proper lists, as prescribed by the
pattern, raising an error if they are not.

Compared to hand-written code, pattern matching noticeably improves
clarity and conciseness---no need to resort to series of @code{car} and
@code{cdr} calls when matching lists, for instance.  It also improves
robustness, by making sure the input @emph{completely} matches the
pattern---conversely, hand-written code often trades robustness for
conciseness.  And of course, @code{match} is a macro, and the code it
expands to is just as efficient as equivalent hand-written code.

The pattern matcher is defined as follows:

@deffn {Scheme Syntax} match exp clause1 clause2 @dots{}
Match object @var{exp} against the patterns in @var{clause1}
@var{clause2} @dots{}  in the order in which they appear.  Return the
value produced by the first matching clause.  If no clause matches,
throw an exception with key @code{match-error}.

Each clause has the form @code{(pattern body1 body2 @dots{})}.  Each
@var{pattern} must follow the syntax described below.  Each body is an
arbitrary Scheme expression, possibly referring to pattern variables of
@var{pattern}.
@end deffn

@c FIXME: Document other forms:
@c
@c exp ::= ...
@c       | (match exp clause ...)
@c       | (match-lambda clause ...)
@c       | (match-lambda* clause ...)
@c       | (match-let ((pat exp) ...) body)
@c       | (match-let* ((pat exp) ...) body)
@c       | (match-letrec ((pat exp) ...) body)
@c       | (match-define pat exp)
@c
@c clause ::= (pat body) | (pat => exp)

The syntax and interpretation of patterns is as follows:

@verbatim
        patterns:                       matches:

pat ::= identifier                      anything, and binds identifier
      | _                               anything
      | ()                              the empty list
      | #t                              #t
      | #f                              #f
      | string                          a string
      | number                          a number
      | character                       a character
      | 'sexp                           an s-expression
      | 'symbol                         a symbol (special case of s-expr)
      | (pat_1 ... pat_n)               list of n elements
      | (pat_1 ... pat_n . pat_{n+1})   list of n or more
      | (pat_1 ... pat_n pat_n+1 ooo)   list of n or more, each element
                                          of remainder must match pat_n+1
      | #(pat_1 ... pat_n)              vector of n elements
      | #(pat_1 ... pat_n pat_n+1 ooo)  vector of n or more, each element
                                          of remainder must match pat_n+1
      | #&pat                           box
      | ($ record-name pat_1 ... pat_n) a record
      | (= field pat)                   a ``field'' of an object
      | (and pat_1 ... pat_n)           if all of pat_1 thru pat_n match
      | (or pat_1 ... pat_n)            if any of pat_1 thru pat_n match
      | (not pat_1 ... pat_n)           if all pat_1 thru pat_n don't match
      | (? predicate pat_1 ... pat_n)   if predicate true and all of
                                          pat_1 thru pat_n match
      | (set! identifier)               anything, and binds setter
      | (get! identifier)               anything, and binds getter
      | `qp                             a quasi-pattern
      | (identifier *** pat)            matches pat in a tree and binds
                                        identifier to the path leading
                                        to the object that matches pat

ooo ::= ...                             zero or more
      | ___                             zero or more
      | ..1                             1 or more

        quasi-patterns:                 matches:

qp  ::= ()                              the empty list
      | #t                              #t
      | #f                              #f
      | string                          a string
      | number                          a number
      | character                       a character
      | identifier                      a symbol
      | (qp_1 ... qp_n)                 list of n elements
      | (qp_1 ... qp_n . qp_{n+1})      list of n or more
      | (qp_1 ... qp_n qp_n+1 ooo)      list of n or more, each element
                                          of remainder must match qp_n+1
      | #(qp_1 ... qp_n)                vector of n elements
      | #(qp_1 ... qp_n qp_n+1 ooo)     vector of n or more, each element
                                          of remainder must match qp_n+1
      | #&qp                            box
      | ,pat                            a pattern
      | ,@pat                           a pattern
@end verbatim

The names @code{quote}, @code{quasiquote}, @code{unquote},
@code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and},
@code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and
@code{___} cannot be used as pattern variables.

Here is a more complex example:

@example
(use-modules (srfi srfi-9))

(let ()
  (define-record-type person
    (make-person name friends)
    person?
    (name    person-name)
    (friends person-friends))

  (letrec ((alice (make-person "Alice" (delay (list bob))))
           (bob   (make-person "Bob" (delay (list alice)))))
    (match alice
      (($ person name (= force (($ person "Bob"))))
       (list 'friend-of-bob name))
      (_ #f))))

@result{} (friend-of-bob "Alice")
@end example

@noindent
Here the @code{$} pattern is used to match a SRFI-9 record of type
@var{person} containing two or more slots.  The value of the first slot
is bound to @var{name}.  The @code{=} pattern is used to apply
@code{force} on the second slot, and then checking that the result
matches the given pattern.  In other words, the complete pattern matches
any @var{person} whose second slot is a promise that evaluates to a
one-element list containing a @var{person} whose first slot is
@code{"Bob"}.

Please refer to the @code{ice-9/match.upstream.scm} file in your Guile
installation for more details.

Guile also comes with a pattern matcher specifically tailored to SXML
trees, @xref{sxml-match}.