我想诸位应该都用过结构化绑定（structure bindings）吧。或者听说过“模式匹配”这个工具（我之前的一些文章中就用过）。

今天来聊聊这个有趣的语言特性。

依然先放代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#lang racket

(define-syntax pmatch-if
  (lambda (stx)
    (syntax-case stx (quote any/p ?)
      [(_ val any/p t f) #'t]
      [(_ val x t f)
       (identifier? #'x)
       #'(let ([x val])
           t)]

      [(_ val (? predicate pat) t f)
       #'(if (predicate val)
             (pmatch-if val pat t f)
             f)]

      [(_ val (quote x) t f)
       #'(if (equal? val 'x)
             t
             f)]

      [(_ val x t f)
       (not (pair? (syntax->datum #'x)))
       #'(if (equal? val 'x)
             t
             f)]

      [(_ val (pat1 . pat2) t f)
       #'(if (pair? val)
             (let ([x (car val)]
                   [y (cdr val)])
               (pmatch-if x pat1 (pmatch-if y pat2 t f) f))

             f)])))

(define-syntax pmatch-inner
  (syntax-rules ()
    [(_ v) (error "pmatch: match failed:" v)]
    [(_ v [pat body ...] rest ...)
     (let* ([tmp v]
            [failure (lambda () (pmatch-inner tmp rest ...))])
       (pmatch-if tmp pat (begin body ...) (failure)))]))

(define-syntax-rule (pmatch v clauses ...)
  (let ([tmp v])
    (pmatch-inner tmp clauses ...)))

什么是模式匹配

模式匹配并不是“字符串模式匹配”，它是一种语言特性。

依然是从各位非常熟悉的结构化绑定说起。结构化绑定可以让你便捷的解构一个结构体的值，并绑定到不同的变量上。

模式匹配则是它的升级版：我们可以使用描述化的写法判断一个值“是不是长这个样子”，如果是，就“将其中的对应部分绑定到给定变量上”，并执行对应的一段代码。

简单来说，结合了结构化绑定的数据解构能力和 cond/if 的条件分支能力。我们写 (match x [(human head body arm leg) head]) 来描述 x 是不是一个有头、身体、胳膊和腿的人，如果是，就返回他的头。

从 LOP（语言导向编程）的视角看，本质上是设计了一种 EDSL 来方便对数据形状的检查以及数据解构。

它有什么应用

想想结构化绑定有什么应用。模式匹配的应用更丰富：在写解释器等等的时候你常常需要检查数据的形状并进行解构。

更加常见的情形是处理 union type 等代数数据类型。你可能会遇到一个类型 Res<T, E> = Union<T, E>，它可以是返回值类型 T，也可能是函数执行出现问题时的异常类型 E。这时你就可以写

1
2
3

(match res
  [(T v) (process-result v)]
  [(E e) (catch-exception e)])

而不是一大堆麻烦的 if 和 let。

如何实现

这个东西看上去比较神秘，其实大概可以想到是利用列表的特性递归匹配。但是直接做非常不好做，你可能会想到类似于编译出一个过程判断是否符合模式，另一个过程绑定数据。这样常数很大而且很不优雅。

正确的方法是我们先不考虑完整的 match（更像 cond）而是考虑一个弱化版的 pmatch-if：接受一个值和一个模式，如果值符合模式就进行绑定并执行第一个分支，否则执行第二个分支。

假设已经实现了这个，那么完整的 pmatch 就好实现了：只需要把一串 pmatch-if 串起来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

(define-syntax pmatch-inner
  (syntax-rules ()
    [(_ v) (error "pmatch: match failed:" v)]
    [(_ v [pat body ...] rest ...)
     (let* ([tmp v]
            [failure (lambda () (pmatch-inner tmp rest ...))])
       (pmatch-if tmp pat (begin body ...) (failure)))]))

(define-syntax-rule (pmatch v clauses ...)
  (let ([tmp v])
    (pmatch-inner tmp clauses ...)))

也就是这堆东西的用处。不过注意一点：宏会将接受到的参数直接 copy 到它出现的位置。这可能导致重复求值，所以我用 pmatch 额外包了一层 let。

接下来考虑 pmatch-if，这是逻辑的核心。

我们要解构的东西是列表（scheme/racket 的核心语法骨架）。列表具备递归构造，这启示我们进行递归的模式匹配。

那么先考虑几种基础情况：模式是一个标识符、模式是一个原子数据、模式是一个用 quote 包起来的 cons pair、模式是 any/p。

这几种情况，标识符就直接绑定并匹配通过，any/p 无条件匹配（不过不绑定），原子数据或 quote 包装的就进行比较（equal?）。

然后接下来就是难点：cons pair 怎么做？

非常简单，递归匹配即可。我们的匹配条件相当于是数据是个 pair，且模式的 car 和 cdr 两个部分分别都能匹配数据的对应部分，然后模式的两部分的绑定合在一起。

这里很容易联想到 church encoding 中实现 and 的方法：

1
2
3
4

(define ((and b1) b2)
    (lambda (t)
        (lambda (f)
            ((b1 ((b2 t) f)) f))))

也即两层 if 嵌套。那么就搞定了。

如果你这么写了就会发生 () 惨案。因为 () 会进入对原子匹配的分支，然后就会生成 (if (equal? v ()) ...) 这样的代码，产生裸的 () 然后爆掉。正确的做法是多加一层 quote：

1
2
3

 #'(if (equal? val 'x) ; 注意是 'x 不是 x
             t
             f)

这样，原子有自求值的特性，多加一层 quote 不影响（会被运行时的 eval 弄掉）而 null（空链表 '()）则能多一层 quote 而避免报错。

那个 ? 的分支是一个小的扩展，类似于 racket 标准库的 ?。语法是 (? predicate pat)，意思是如果 v 满足 predicate 则匹配模式 pat，否则匹配失败。是 guard 的一种语法糖（不过这里没有实现 guard。留作习题 :P）。