在lisp中的第一次搜索下进行前向链接

Question

我试图找到问题,在堆栈溢出流量问题上alogrithm是明确的但它和递归调用是在一个if satetment所以我无法弄清楚为什么它会变坏

(defparameter BF '(B C) )
(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)
                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))
(defun chain_av (BF BR F)
(loop 
    (unless (member F BF)
      (dolist (R  BR)
        (when (actionable  R BF)
          (remove R BR)
          (append BF (conclusion-part R)))
      (if (member F BF) (return "yes")
        (or(chain_av BF BR F) (return nil)))))))


(defun conclusion-part( r)
(caddr r)
)
(write (chain_av BF BR 'H ))
    (defun actionable (r facts)
        (let ((ok t))
            (dolist (p (cadr r) ok)
                (if (not (member p facts))
                    (setq ok nil)))
                ok))

我仍然不确定它是否真的在第一次搜索之下,并且应该通过一个变量跟踪它所在的元素并提前感谢来证明

Answer 1

以下是有关代码中某些错误的一般性说明,后面是有关如何实现正向链接的提示.

代码格式

正确格式化代码非常重要,否则您或您的同行将无法轻松阅读.请参阅https://lisp-lang.org/style-guide/:

(defun conclusion-part( r)
(caddr r)
)

上面有各自的括号,这不是惯用语.此外,Common Lisp具有一个THIRD比CADDR大多数人更容易理解的功能.正确缩进并将括号放在最后.使用像Emacs这样的编辑器可以自动缩进代码:这有助于识别您编写的内容与您要编写的内容不同的情况,因为自动缩进遵循列表结构,可以帮助发现错位的括号.

(defun conclusion-part (rule)
  (third rule))

访问器功能

您所做的就是定义一个conclusion-part访问器函数来访问规则 ad-hoc数据结构的一部分.拥有一组与特定实现无关的独特访问器会有所帮助,并且是引入有意义名称的好机会.您应该对规则的所有部分执行相同操作(您可以在其他地方直接使用CADR,这不是很干净).

例如(随意找到更好的名字):

(defun rule-name (rule) (first rule))
(defun rule-antecedent (rule) (second rule))
(defun rule-consequent (rule) (cddr rule))

请注意,这rule-consequent是我的重写conclusion-part,除了它总是返回一个包含单个元素的列表(你能看出原因吗？).这在以后调用时非常有用append,并且与rule-antecedent返回列表一致.

规则的可操作性

返回true或false的函数称为谓词,并且按照惯例-p在Lisp(以及-?Scheme)中后缀.您可能会也可能不会遵循该规则,但请引入更有意义的变量名称.以下是如何重写它:

(defun actionablep (rule facts)
  (dolist (term (rule-antecedent rule) t)
    (unless (member term facts)
      (return nil))))

既然你已经知道了loop,你也可以写:

(defun actionablep (rule facts)
  (loop
    :for term :in (rule-antecedent rule)
    :always (member term facts)))

正向链接

这里也存在一些问题:

• 你不使用的返回值REMOVE或者APPEND,这是保证不发生变异他们的论据(不像函数DELETE和NCONC,甚至为这些功能仅返回值的问题,被授予变异现有的存储能力是实现定义并且只在那里允许有效地重用内存).

• 在某些分支中,您希望返回"yes"另一个分支nil; CL可能是动态类型的,但这里不需要字符串返回值.

• 甲return形式只存在最里面nil块.在你的情况下,这意味着你从建立的隐式块返回DOLIST,而不是从LOOP.你可以说出你的名字loop但实际上这里没有必要,你可以不用写出整篇文章return.更一般地说,您可以使用纯粹的功能方法.

暗示

我写了一个forward-chaining函数,并追踪它; 在REPL中:

CL-USER> (trace forward-chaining)

以下是我测试实现的方法:

(forward-chaining '(B C)
                  '((R1 (B D E) F)
                    (R2 (D G) A)
                    (R3 (C F) A)
                    (R4 (C) D)
                    (R5 (D) E)
                    (R6 (A) H)
                    (R7 (B) X)
                    (R8 (X C) A))
                  'H)

我正在使用SBCL测试代码,实际输出可能在您的Lisp实现中有所不同:

  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)
            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)
            5: FORWARD-CHAINING returned (H)
          4: FORWARD-CHAINING returned (H)
        3: FORWARD-CHAINING returned (H)
      2: FORWARD-CHAINING returned (H)
    1: FORWARD-CHAINING returned (H)
  0: FORWARD-CHAINING returned (H)

该计划的基本结构是:

(defun forward-chaining (rules facts goal)
  (or ...
      (loop 
        for ... in ...
        thereis (and (actionablep ... ...)
                     (forward-chaining ... ... ...))))) 

换句话说:要么目标已经是已知的事实,要么存在一个可行的规则,通过该规则可以传递目标.请注意,如果规则是非终止的,则可能会有无限递归.

您访问规则的顺序决定了您的策略是否为深度优先(始终遵循最后尝试过的规则并从该策略开始,使用规则列表作为堆栈),或广度优先(应用所有可激活规则的给定)实际上,使用规则列表作为队列).我不知道"第一次搜索"这个术语来自哪里,我没有发现它的严重参考(有一篇文章在第一次搜索时讨论了Leiserson&Schardl 2010,但引用的文章没有提及它,只有广度优先,这是众所周知的).