12.87 util.match - Pattern matching

Module: util.match ¶

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.

Pattern matching API

Macro: match expr clause … ¶

{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.

Macro: match-lambda clause … ¶

{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))

Macro: match-lambda* clause … ¶

{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 …))

Macro: match-let ((pat expr) …) body-expr … ¶

Macro: match-let name ((pat expr) …) body-expr … ¶

Macro: match-let* ((pat expr) …) body-expr … ¶

Macro: match-letrec ((pat expr) …) body-expr … ¶

{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.

Macro: match-let1 pat expr body-expr … ¶

{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))

Macro: match-define pat expr ¶

{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)

Pattern syntax

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 ...

• A bare symbol is a "pattern variable"; it matches anything, and the matched part of the expression is bound to the symbol. The following symbols have special meanings and cannot be used as a pattern variable: _, quote, $, struct, @, object, =, and, or, not, ?, set!, get!, quasiquote, ..., ___, and ..k and __k where k is an integer.
• A symbol _ matches anything, without binding a pattern variable. It can be used to show "don’t care" placeholder.
• Literals such as emptylist, booleans, strings, numbers, characters and keywords match the same object (in the sense of equal?).
• Quoted expression matches the same expression (in the sense of equal?). You can use a quoted symbol to match the symbol itself.
• A keyword, without a quote, used to match the same keyword object. Since we’re in the process of unifying keywords and symbols, the user is recommended to write keywords with a quote in a pattern in order to match the keyword in the input. See Keyword and symbol integration, for the details.
• A list and a vector in general match a list or a vector whose elements matches the elements in the pattern recursively, unless the first element of the list is one of the special symbols listed above, it has a special meaning.

  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).

Pattern examples

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]))