diff options
Diffstat (limited to 'doc/ref/match.texi')
-rw-r--r-- | doc/ref/match.texi | 308 |
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}. |