如何实现模式匹配？

· · 科技·工程

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

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

你也可以在这里查看。

依然先放代码：

#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。这时你就可以写

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

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

如何实现

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

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

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

(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 的方法：

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

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

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

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

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

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