match.ss: Pattern Matching

To load: (require (lib "match.ss"))

This library provides functions for pattern-matching Scheme values. (This chapter adapted from Andrew K. Wright and Bruce Duba's original manual, entitled Pattern Matching for Scheme. The PLT Scheme port was originally done by Bruce Hauman and is maintained by Sam Tobin-Hochstadt.) The following forms are provided:

(match expr clause ...)
(match-lambda clause ...)
(match-lambda* clause ...)
(match-let ((pat expr) ...) expr ···1)
(match-let* ((pat expr) ...) expr ···1)
(match-letrec ((pat expr) ...) expr ···1)
(match-let var ((pat expr) ...) expr ···1)
(match-define pat expr)

clause is one of
 (pat expr ···1)
 (pat (=> identifier) expr ···1)

Figure 1 gives the full syntax for pat patterns.

pat     ::= identifier                        Match anything, bind identifier as a variable  
         |  _                                 Match anything                                 
         |  literal                           Match literal                                  
         |  'datum                            Match equal? datum                             
         |  'symbol                           Match equal? symbol (special case of datum)    
         |  (lvp ...)                         Match sequence of lvps                         
         |  (lvp ... . pat)                   Match sequence of lvps consed onto a pat       
         |  #(lvp ...)                        Match vector of pats                           
         |  #&pat                             Match boxed pat                                
         |  ($ struct-name pat ...)           Match struct-name instance with matching fields
         |  (and pat ...)                     Match when all pats match                      
         |  (or pat ...)                      Match when any pat match                       
         |  (not pat ...)                     Match when no pat match                        
         |  (= expr pat)                      Match when result of applying expr matches pat 
         |  (? expr pat ...)                  Match if expr is true and all pats match       
         |  (set! identifier)                 Match anything, bind identifier as a setter    
         |  (get! identifier)                 Match anything, bind identifier as a getter    
         |  `qp                               Match quasipattern                             
literal ::= #t                                Match true                                     
         |  #f                                Match false                                    
         |  string                            Match equal? string                            
         |  number                            Match equal? number                            
         |  character                         Match equal? character                         
lvp     ::= pat ooo                           Greedily match pat instances                   
         |  pat                               Match pat                                      
ooo     ::= ...                               Zero or more (where ... is a keyword)          
         |  ___                               Zero or more                                   
         |  ..k                               k or more, where k is a non-negative integer   
         |  __k                               k or more, where k is a non-negative integer   
qp      ::= literal                           Match literal                                  
         |  identifier                        Match equal? symbol                            
         |  (qp ...)                          Match sequences of qps                         
         |  (qp ... . qp)                     Match sequence of qps consed onto a qp         
         |  (qp ... qp ooo)                   Match qps consed onto a repeated qp            
         |  #(qp ...)                         Match vector of qps                            
         |  #&qp                              Match boxed qp                                 
         |  ,pat                              Match pat                                      
         |  ,@pat                             Match pat, spliced                             

Figure 1:  Pattern Syntax

The next subsection describes the various patterns.

The match-lambda and match-lambda* forms are convenient combinations of match and lambda, and can be explained as follows:

(match-lambda (pat expr ···1) ...) =(lambda (x) (match x (pat expr ···1) ...))
(match-lambda* (pat expr ···1) ...) =(lambda x (match x (pat expr ···1) ...))
where x is a unique variable. The match-lambda form is convenient when defining a single argument function that immediately destructures its argument. The match-lambda* form constructs a function that accepts any number of arguments; the patterns of match-lambda* should be lists.

The match-let, match-let*, match-letrec, and match-define forms generalize Scheme's let, let*, letrec, and define expressions to allow patterns in the binding position rather than just variables. For example, the following expression:

(match-let ([(x y z) (list 1 2 3)]) body)

binds x to 1, y to 2, and z to 3 in the body. These forms are convenient for destructuring the result of a function that returns multiple values. As usual for letrec and define, pattern variables bound by match-letrec and match-define should not be used in computing the bound value.

The match, match-lambda, and match-lambda* forms allow the optional syntax (=> identifier) between the pattern and the body of a clause. When the pattern match for such a clause succeeds, the identifier is bound to a failure procedure of zero arguments within the body. If this procedure is invoked, it jumps back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match. The body must not mutate the object being matched, otherwise unpredictable behavior may result.

25.1  Patterns

Figure 1 gives the full syntax for patterns. Explanations of these patterns follow.

If no clause matches the value, an exn:misc:match exception is raised.

25.2  Extending Match

There are two ways to extend or alter the behavior of match.

The match-equality-test parameter controls the behavior of non-linear patterns:

(match-equality-test [expr])      PROCEDURE

When a variable appears more than once in a pattern, the values matched by each instance are constrained to be the same in the sense of the runtime value of match-equality-test. The default value of this parameter is equal?.

The define-match-expander form extends the syntax of match patterns:

(define-match-expander id proc-expr)      SYNTAX

(define-match-expander id proc-expr proc-expr)      SYNTAX

(define-match-expander id proc-expr proc-expr proc-expr)      SYNTAX

This form binds an identifier to a pattern transformer.

The first proc-expr subexpression must evaluate to a transformer that produces a pattern in the syntax of Chapter 32. Whenever id appears as the beginning of a pattern in a the context of the pattern matching forms defined in Chapter 32, this transformer is given, at expansion time, a syntax object corresponding to the entire pattern (including id). The pattern is the replaced with the result of the transformer.

If a second proc-expr subexpression is provided, it must produce a similar transformer, but in the context of patterns written in the syntax of the current chapter.

A transformer produced by a third proc-expr subexpression is used when the id keyword is used in a traditional macro use context. In this way, id can be given meaning both inside and outside patterns.

25.3  Examples

This section illustrates the convenience of pattern matching with some examples. The following function recognizes some s-expressions that represent the standard Y operator:

(define Y?
  (match-lambda
    [('lambda (f1)
       ('lambda (y1)
         ((('lambda (x1) (f2 ('lambda (z1) ((x2 x3) z2))))
           ('lambda (a1) (f3 ('lambda (b1) ((a2 a3) b2)))))
          y2)))
     (and (symbol? f1) (symbol? y1) (symbol? x1) (symbol? z1) (symbol? a1) (symbol? b1)
          (eq? f1 f2) (eq? f1 f3) (eq? y1 y2)
          (eq? x1 x2) (eq? x1 x3) (eq? z1 z2)
          (eq? a1 a2) (eq? a1 a3) (eq? b1 b2))]
    [_ #f]))

Writing an equivalent piece of code in raw Scheme is tedious.

The following code defines abstract syntax for a subset of Scheme, a parser into this abstract syntax, and an unparser.

(define-struct Lam (args body))
(define-struct Var (s))
(define-struct Const (n))
(define-struct App (fun args))

(define parse
  (match-lambda
    [(and s (? symbol?) (not 'lambda))
     (make-Var s)]
    [(? number? n)
     (make-Const n)]
    [('lambda (and args ((? symbol?) ...) (not (? repeats?))) body)
     (make-Lam args (parse body))]
    [(f args ...)
     (make-App
       (parse f)
       (map parse args))]
    [x (error 'syntax "invalid expression")]))

(define repeats?
  (lambda (l)
    (and (not (null? l))
         (or (memq (car l) (cdr l)) (repeats? (cdr l))))))

(define unparse
  (match-lambda
    [($ Var s) s]
    [($ Const n) n]
    [($ Lam args body) `(lambda ,args ,(unparse body))]
    [($ App f args) `(,(unparse f) ,@(map unparse args))]))

With pattern matching, it is easy to ensure that the parser rejects all incorrectly formed inputs with an error message.

With match-define, it is easy to define several procedures that share a hidden variable. The following code defines three procedures, inc, value, and reset, that manipulate a hidden counter variable:

(match-define (inc value reset)
  (let ([val 0])
    (list
      (lambda () (set! val (add1 val)))
      (lambda () val)
      (lambda () (set! val 0)))))

Although this example is not recursive, the bodies could recursively refer to each other. The following code illustrates the creation of a match-expander that works for both (lib "match.ss") and (lib "plt-match.ss") syntax.

(require (prefix plt: (lib "plt-match.ss")))
(define-struct point (x y))
(define-match-expander Point
  (lambda (stx)
    (syntax-case stx ()
      ((Point a b) #'(struct point (a b)))))
  (lambda (stx)
    (syntax-case stx ()
      ((Point a b) #'($ point a b))))
  (lambda (stx)
    (syntax-case stx ()
      ((Point a b) #'(make-point a b)))))

(define p (Point 3 4))

(match p
   ((Point x y) (+ x y)))
;; => 7
(plt:match p
   ((Point x y) (* x y)))
;; => 12