summaryrefslogtreecommitdiff
path: root/doc/ref/match.texi
diff options
context:
space:
mode:
Diffstat (limited to 'doc/ref/match.texi')
-rw-r--r--doc/ref/match.texi308
1 files changed, 308 insertions, 0 deletions
diff --git a/doc/ref/match.texi b/doc/ref/match.texi
new file mode 100644
index 000000000..0fc5105d1
--- /dev/null
+++ b/doc/ref/match.texi
@@ -0,0 +1,308 @@
+@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"}.
+
+The @code{(ice-9 match)} module also provides the following convenient
+syntactic sugar macros wrapping around @code{match}.
+
+@deffn {Scheme Syntax} match-lambda exp clause1 clause2 @dots{}
+Create a procedure of one argument that matches its argument against
+each clause, and returns the result of evaluating the corresponding
+expressions.
+
+@example
+(match-lambda clause1 clause2 @dots{})
+@equiv{}
+(lambda (arg) (match arg clause1 clause2 @dots{}))
+@end example
+@end deffn
+
+@example
+((match-lambda
+ (('hello (who))
+ who))
+ '(hello (world)))
+@result{} world
+@end example
+
+@deffn {Scheme Syntax} match-lambda* exp clause1 clause2 @dots{}
+Create a procedure of any number of arguments that matches its argument
+list against each clause, and returns the result of evaluating the
+corresponding expressions.
+
+@example
+(match-lambda* clause1 clause2 @dots{})
+@equiv{}
+(lambda args (match args clause1 clause2 @dots{}))
+@end example
+@end deffn
+
+@example
+((match-lambda*
+ (('hello (who))
+ who))
+ 'hello '(world))
+@result{} world
+@end example
+
+@deffn {Scheme Syntax} match-let ((pattern expression) @dots{}) body
+Match each pattern to the corresponding expression, and evaluate the
+body with all matched variables in scope. Raise an error if any of the
+expressions fail to match. @code{match-let} is analogous to named let
+and can also be used for recursive functions which match on their
+arguments as in @code{match-lambda*}.
+
+@example
+(match-let (((x y) (list 1 2))
+ ((a b) (list 3 4)))
+ (list a b x y))
+@result{}
+(3 4 1 2)
+@end example
+@end deffn
+
+@deffn {Scheme Syntax} match-let variable ((pattern init) @dots{}) body
+Similar to @code{match-let}, but analogously to @dfn{named let}, locally
+bind VARIABLE to a new procedure which accepts as many arguments as
+there are INIT expressions. The procedure is initially applied to the
+results of evaluating the INIT expressions. When called, the procedure
+matches each argument against the corresponding PATTERN, and returns the
+result(s) of evaluating the BODY expressions. @xref{while do,
+Iteration}, for more on @dfn{named let}.
+@end deffn
+
+@deffn {Scheme Syntax} match-let* ((variable expression) @dots{}) body
+Similar to @code{match-let}, but analogously to @code{let*}, match and
+bind the variables in sequence, with preceding match variables in scope.
+
+@example
+(match-let* (((x y) (list 1 2))
+ ((a b) (list x 4)))
+ (list a b x y))
+@equiv{}
+(match-let (((x y) (list 1 2)))
+ (match-let (((a b) (list x 4)))
+ (list a b x y)))
+@result{}
+(1 4 1 2)
+@end example
+@end deffn
+
+@deffn {Scheme Syntax} match-letrec ((variable expression) @dots{}) body
+Similar to @code{match-let}, but analogously to @code{letrec}, match and
+bind the variables with all match variables in scope.
+@end deffn
+
+Guile also comes with a pattern matcher specifically tailored to SXML
+trees, @xref{sxml-match}.