util.match - Pattern matching ¶This module is a port of Andrew Wright’s pattern matching macro library.
It is widely used in the Scheme world, and ported to various Scheme
implementations, including Chez Scheme, PLT Scheme, Scheme48, Chicken,
and SLIB.
It is similar to, but more powerful than
Common Lisp’s destructuring-bind.
This version retains compatibility of the original Wright’s macro, except (1) box is not supported since Gauche doesn’t have one, and (2) structure matching is integrated to Gauche’s object system.
We show a list of APIs first, then the table of complete syntax of patterns, followed by examples.
{util.match}
Each clause is either one of the followings:
(pat body ...) (pat (=> identifier) body ...)
First, the expr is matched against pat of each clauses. The detailed syntax of the pattern is explained below.
If a matching pat is found, the pattern variables in
pat are bound to the corresponding elements in expr, then
body … are evaluated. Then match returns the value(s)
of the last expression of body ….
If the clause is the second form, identifier is also bound
to the failure continuation of the clause. It is a
procedure with no arguments, and when called, it jumps back to
the matcher as if the matching of pat is failed, and
match continues to try the rest of clauses.
So you can perform extra tests
within body … and if you’re not satisfied you can reject
the match by calling (identifier). See the examples
below for more details.
If no pat matches, match reports an error.
{util.match}
Creates a function that takes one argument and performs match on it,
using clause …. It’s functionally equivalent to the following
expression:
(lambda (expr) (match expr clause ...))
Example:
(map (match-lambda
((item price-per-lb (quantity 'lbs))
(cons item (* price-per-lb quantity)))
((item price-per-lb (quantity 'kg))
(cons item (* price-per-lb quantity 2.204))))
'((apple 1.23 (1.1 lbs))
(orange 0.68 (1.4 lbs))
(cantaloupe 0.53 (2.1 kg))))
⇒ ((apple . 1.353) (orange . 0.952)
(cantaloupe . 2.4530520000000005))
{util.match}
Like match-lambda, but performs match on the list of
whole arguments.
It’s functionally equivalent to the following expression:
(lambda expr (match expr clause ...))
{util.match}
Generalize let, let*, and letrec to allow
patterns in the binding position rather than just variables.
Each expr is evaluated, and then matched to pat,
and the bound pattern variables are visible in
body-expr ….
(match-let (
(((ca . cd) ...) '((a . 0) (b . 1) (c . 2)))
)
(list ca cd))
⇒ ((a b c) (0 1 2))
If you’re sick of parenthesis, try match-let1 below.
{util.match}
This is a Gauche extension and isn’t found in the original Wright’s code.
This one is equivalent to the following code:
(match-let ((pat expr)) body-expr ...)
Syntactically, match-let1 is very close to the Common Lisp’s
destructuring-bind.
(match-let1 ('let ((var val) ...) body ...)
'(let ((a b) (c d)) foo bar baz)
(list var val body))
⇒ ((a c) (b d) (foo bar baz))
{util.match}
Like toplevel define, but allows a pattern instead of variables.
(match-define (x . xs) (list 1 2 3)) x ⇒ 1 xs ⇒ (2 3)
Here’s a summary of pattern syntax. The asterisk (*)
after explanation means Gauche’s extension which does not present
in the original Wright’s code.
pat : patvar ;; anything, and binds pattern var
| _ ;; 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)
| (pat1 ... patN) ;; list of n elements
| (pat1 ... patN . patN+1) ;; list of n or more
| (pat1 ... patN patN+1 ooo) ;; list of n or more, each element
;; of remainder must match patN+1
| #(pat1 ... patN) ;; vector of n elements
| #(pat1 ... patN patN+1 ooo) ;; vector of n or more, each element
;; of remainder must match patN+1
| ($ class pat1 ... patN) ;; an object (patK matches in slot order)
| (struct class pat1 ... patN) ;; ditto (*)
| (@ class (slot1 pat1) ...) ;; an object (using slot names) (*)
| (object class (slot1 pat1) ...) ;; ditto (*)
| (= proc pat) ;; apply proc, match the result to pat
| (and pat ...) ;; if all of pats match
| (or pat ...) ;; if any of pats match
| (not pat ...) ;; if all pats don't match at all
| (? predicate pat ...) ;; if predicate true and all pats match
| (set! patvar) ;; anything, and binds setter
| (get! patvar) ;; anything, and binds getter
| `qp ;; a quasi-pattern
patvar : a symbol except _, quote, $, struct, @, object, =, and, or,
not, ?, set!, get!, quasiquote, ..., ___, ..k, __k.
ooo : ... ;; zero or more
| ___ ;; zero or more
| ..k ;; k or more, where k is an integer.
;; Example: ..1, ..2 ...
| __k ;; k or more, where k is an integer.
;; Example: __1, __2 ...
_, quote, $, struct,
@, object, =, and, or,
not, ?, set!, get!, quasiquote,
..., ___, and ..k and __k where k is
an integer.
_ matches anything, without binding a pattern variable.
It can be used to show "don’t care" placeholder.
equal?).
equal?).
You can use a quoted symbol to match the symbol itself.
As a special case, the last element of a vector or a list can be
followed by a symbol .... In that case, the pattern just before
the symbol ... can be applied repeatedly until it consumes all the
elements in the given expression. A symbol ___ can be used
in place of ...; it is useful when you want to produce a pattern
by syntax-rules macro.
For a list pattern, you can also use a symbol ..1, ..2,
…, which specifies the minimum number of repetition.
($ class pat1 …) matches an instance of a class class.
Each pattern pat1 … matches each value of slots,
in order of (class-slots class) by default.
(Records are exception; they match the same order as their
default constructor since 0.9.6.)
(struct class pat1 …) has the same meaning. Although
the original Wright’s code doesn’t have struct, PLT Scheme has
it in its extended match feature, and it is more descriptive.
This is an adaptation of the original feature that can match structures.
It is useful to match a simple instance that you know the order of
slots; for example, a simple record created by define-record-type
(see gauche.record - Record types) would be easy to match by positioned values.
If the instance’s class uses inheritances, it is a bit difficult to
match by positions. You can use @ or object pattern
below to match using slot names.
(object class (slot1 pat1) …) matches an instance
of a class class whose value of slot1 … matches
pat1 …. This is Gauche’s extension. @ can be
used in place of object, but object is recommended
because of descriptiveness.
(= proc pat) first applies proc to the corresponding
expression, then match the result with pat.
(and pat …) matches when all pat matches the
corresponding subtree. A common idiom to realize “as” matching,
with which you can bind the entire tree as well as its substrees,
can be written with and operator. For example,
(and (x . y) p) matches a pair, binding its cdr to x,
its car to y, and the entire pair to p.
(or pat …) tries to match each pat against
the corresponding subtree, and if any succeeds, the entire or
pattern succeeds. If no pat matches the subtree, the entire
or pattern fails.
If there’re pattern variables in pat, the set of variables
in each pat must be the same: That is,
(or (_ x y) (_ x y _)) is ok but (or (_ x _) (_ x y _)) is not.
It is because the latter may leave some of pattern variables
unbound even match succeeds.
(not pat …) matches when none of pat matches
the corresponding subtree.
(? predicate pat …) first applies a predicate to the
corresponding expression, and if it returns true, applies each
pat … to the expression.
(set! patvar) matches anything, and binds an one-argument
procedure to a pattern variable patvar. If the procedure is
called, it replaces the value of matched pattern for the given argument.
(get! patvar) matches anything, and binds a zero-argument
procedure to a pattern variable patvar. If the procedure is
called, it returns the matched value.
`qp is a quasipattern. qp is quoted, in the sense
that it matches itself, except the pattern that is unquoted.
(Don’t confuse quasipattern to quasiquote, though the functions are
similar. Quasiquote turns off evaluation except unquoted subtree.
Quasiquote turns off the special pattern syntax except unquoted subtree.
See the examples below).
A simple structure decomposition:
(match '(0 (1 2) (3 4 5)) [(a (b c) (d e f)) (list a b c d e f)]) ⇒ (0 1 2 3 4 5)
Using predicate patterns:
(match 123 [(? string? x) (list 'string x)] [(? number? x) (list 'number x)]) ⇒ (number 123)
Extracting variables and expressions from let.
Uses repetition and predicate patterns:
(define let-analyzer
(match-lambda
[('let (? symbol?)
((var expr) ...)
body ...)
(format "named let, vars=~s exprs=~s" var expr)]
[('let ((var expr) ...)
body ...)
(format "normal let, vars=~s exprs=~s" var expr)]
[_
(format "malformed let")]))
(let-analyzer '(let ((a b) (c d)) e f g))
⇒ "normal let, vars=(a c) exprs=(b d)"
(let-analyzer '(let foo ((x (f a b)) (y (f c d))) e f g))
⇒ "named let, vars=(x y) exprs=((f a b) (f c d))"
(let-analyzer '(let (a) b c d))
⇒ "malformed let"
Using = function application. The pattern variable m
is matched to the result of application of the regular expression.
(match "gauche-ref.texi" ((? string? (= #/(.*)\.([^.]+)$/ m)) (format "base=~a suffix=~a" (m 1) (m 2)))) ⇒ "base=gauche-ref suffix=texi"
An example of quasipattern. In the first expression, the
pattern except value is quoted, so the symbols the,
answer, and is are not pattern variables but literal
symbols. The second expression shows that; input symbol was
does not match the literal symbol is in the pattern.
If we don’t use quasiquote, all symbols in the pattern are pattern
variables, so any four-element list matches as the third expression shows.
(match '(the answer is 42) [`(the answer is ,value) value] [_ #f]) ⇒ 42 (match '(the answer was 42) [`(the answer is ,value) value] [_ #f]) ⇒ #f (match '(a b c d) [(the answer is value) value] [_ #f]) ⇒ d
An example of matching records. The following code implements “rotation” operation to balance a red-black tree.
(define-record-type T #t #t
color left value right)
(define (rbtree-rotate t)
(match t
[(or ($ T 'B ($ T 'R ($ T 'R a x b) y c) z d)
($ T 'B ($ T 'R a x ($ T 'R b y c)) z d)
($ T 'B a x ($ T 'R ($ T 'R b y c) z d))
($ T 'B a x ($ T 'R b y ($ T 'R c z d))))
(make-T 'R (make-T 'B a x b) y (make-T 'B c z d))]
[_ t]))