常见的 lisp：匹配列表中的 acons？

Question

我正在学习 Steven Tanimoto 的 The Elements of Artificial Intelligence Using Common Lisp，但我无法理解他的 match 程序。到目前为止，想法是逐步改进自滚动列表 match，从不太好开始

(defun match1 (p s) (equalp p s))

这是match3：

 (defun match3 (p s)
      (cond
        ((null p) (null s))            ;null clause
        ((or (atom p) (atom s)) nil)   ;atom clause
        ((equalp (first p) (first s))  ;equal CAR clause
         (match3 (rest p) (rest s)))   
        ((eql (first p) '?)            ; joker clause  
         (match3 (rest p) (rest s)))
        (t nil)))                      ;extremal clause

所谓的joker子句应该匹配，即

(match3 '(a b ? d) '(a b c d))  ; yields t

但是下个版本应该"match"这个

(match4 '((? x) b c (? y)) '(a b c d))

我引用

This would permit, for example, the (above) form to not only return true, but also return the association of a with x and the association of d with y. In that way, if the match is used as a condition in a production rule, the action part of the rule can manipulate the values matching the variable elements in the pattern.

...然后它继续谈论列表的事情。然后重写 match:

(defun4 match4 (p s)
      (cond
        ((and (null p) (null s))
         '((:yes . :yes)))
        ((or (atom p) (atom s)) nil)
        ((equalp (first p) (first s))
         (match4 (rest p) (rest s)))

        ((and
          (equalp (length (first p)) 2)
          (eql (first (first p)) '?)
          (let ((rest-match
                 (match4 (rest p) (rest s))))
            (if rest-match
                (acons (first (rest (first p)))
                       (first s)
                       rest-match)))))
        (t nil)))

...因此，如果有人可以首先告诉我为什么我们要在上面的示例中比较 (? x) 和 a，那将会有所帮助。基本上，我不清楚这里的目标是什么。如果有人能解释这背后的动机，我想我可以拆开代码。否则，我完全迷路了。

Answer 1

我有谷本的书，但最早要到明天才能拿到，不过引用中提到的例子其实很好：

in that way, if the match is used as a condition in a production rule, the action part of the rule can manipulate the values matching the variable elements in the pattern.

Production rule systems 是说明这种匹配在哪里有用的一个很好的例子。它让规则编写者专注于领域知识，并使处理规则的算法保持独立。

一些函数式编程方法也大量使用模式匹配。但是，编程语言支持各不相同。不过，Common Lisp 使您可以轻松编写自己的语言。

Answer 2

match3 在两个列表之间引入了简单的模式匹配，其中第一个列表中的符号 ? 可以匹配第二个列表中的任何单个符号。为此函数 returns T 或 NIL 表示匹配过程的成功或失败。

然后在 match4 中引入了一种新的匹配，通过使用似乎是匹配变量的东西。 (? x) 只是引入匹配变量的一种方式，在其他语言中可以写成 ?x 或类似的东西。这个想法是这个变量“捕获”在第二个列表中匹配的符号，这样，例如，你可以稍后以类似于这样的方式使用它：

(match '(a (? x) (? y) (? x) b) '(a c d c b)) ; yes, since ‘c’ matches ‘?x’
(match '(a (? x) (? y) (? x) b) '(a c d e b)) ; no, since ‘c’ and ‘e’ are different

为了有效地使用它，函数 match 必须在找到匹配时给出值 T，而不是简单的值 (match variable, symbol matched)，并构建它是找到的匹配项的关联列表。因此，match4 returns 这样的列表通过使用 acons，在 cond 的最后一个分支中（首先它得到 rest-match，而不是“aconses”在它上面给定的对通过匹配变量和找到的符号）。特殊对 (:yes . :yes) 只是终止此匹配列表的一种方式。

我想本书稍后会介绍另一个版本的匹配函数，其中找到的匹配项将用于该过程的后续部分。

常见的 lisp：匹配列表中的 acons？

common lisp: acons in matching lists?

common-lisp