15.2 匹配 (Matching)

我们需要有一个函数来做模式匹配以完成我们的反向链接 (back-chaining) 程序，这个函数能够比较两个包含变量的列表，它会检查在给变量赋值后是否可以使两个列表相等。举例，如果 ?x 和 ?y 是变量，那么下面两个列表：

  1. (p ?x ?y c ?x)
  2. (p  a  b c  a)

当 ?x = a 且 ?y = b 时匹配，而下面两个列表：

  1. (p ?x b ?y a)
  2. (p ?y b  c a)

当 ?x = ?y = c 时匹配。

我们有一个 match 函数，它接受两棵树，如果这两棵树能匹配，则返回一个关联列表（assoc-list）来显示他们是如何匹配的：

  1. (defun match (x y &optional binds)
  2.   (cond
  3.    ((eql x y) (values binds t))
  4.    ((assoc x binds) (match (binding x binds) y binds))
  5.    ((assoc y binds) (match x (binding y binds) binds))
  6.    ((var? x) (values (cons (cons x y) binds) t))
  7.    ((var? y) (values (cons (cons y x) binds) t))
  8.    (t
  9.     (when (and (consp x) (consp y))
  10.       (multiple-value-bind (b2 yes)
  11.                            (match (car x) (car y) binds)
  12.         (and yes (match (cdr x) (cdr y) b2)))))))
  14. (defun var? (x)
  15.   (and (symbolp x)
  16.        (eql (char (symbol-name x) 0) #\?)))
  18. (defun binding (x binds)
  19.   (let ((b (assoc x binds)))
  20.     (if b
  21.         (or (binding (cdr b) binds)
  22.             (cdr b)))))

图 15.1: 匹配函数。

  1. > (match '(p a b c a) '(p ?x ?y c ?x))
  2. ((?Y . B) (?X . A))
  3. T
  4. > (match '(p ?x b ?y a) '(p ?y b c a))
  5. ((?Y . C) (?X . ?Y))
  6. T
  7. > (match '(a b c) '(a a a))
  8. NIL

当 match 函数逐个元素地比较它的参数时候，它把 binds 参数中的值分配给变量，这被称为绑定 (bindings)。如果成功匹配， match 函数返回生成的绑定；否则，返回 nil 。当然并不是所有成功的匹配都会产生绑定，我们的 match 函数就像 gethash 函数那样返回第二个值来表明匹配成功：

  1. > (match '(p ?x) '(p ?x))
  2. NIL
  3. T

如果 match 函数像上面那样返回 nil 和 t ，表明这是一个没有产生绑定的成功匹配。下面用中文来描述 match 算法是如何工作的：

  1. 如果 x 和 y 在 eql 上相等那么它们匹配；否则，
  2. 如果 x 是一个已绑定的变量，并且绑定匹配 y ，那么它们匹配；否则，
  3. 如果 y 是一个已绑定的变量，并且绑定匹配 x ，那么它们匹配；否则，
  4. 如果 x 是一个未绑定的变量，那么它们匹配，并且为 x 建立一个绑定；否则，
  5. 如果 y 是一个未绑定的变量，那么它们匹配，并且为 y 建立一个绑定；否则，
  6. 如果 x 和 y 都是 cons ，并且它们的 car 匹配，由此产生的绑定又让 cdr 匹配，那么它们匹配。

下面是一个例子，按顺序来说明以上六种情况：

  1. > (match '(p ?v  b ?x  d (?z ?z))
  2.          '(p  a ?w  c ?y ( e  e))
  3.          '((?v . a) (?w . b)))
  4. ((?Z . E) (?Y . D) (?X . C) (?V . A) (?W . B))
  5. T

match 函数通过调用 binding 函数在一个绑定列表中寻找变量（如果有的话）所关联的值。这个函数必须是递归的，因为有这样的情况 “匹配建立一个绑定列表，而列表中变量只是间接关联到它的值： ?x 可能被绑定到一个包含 (?x . ?y) 和 (?y . a) 的列表”：

  1. > (match '(?x a) '(?y ?y))
  2. ((?Y . A) (?X . ?Y))
  3. T

先匹配 ?x 和 ?y ，然后匹配 ?y 和 a ，我们间接确定 ?x 是 a 。