在 lisp 中的第一次搜索下进行前向链接
Forward-chaining beneath first search in lisp
我正在尝试找出解决堆栈溢出问题的问题
算法很清楚，但是它和递归调用是在 if 语句中进行的，所以我不知道为什么它会变坏
(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))
而且我仍然不确定它是否真的在第一次搜索之下
并且我应该通过有一个变量来跟踪它何时通过的元素来证明这一点
提前致谢
这里是对您代码中一些错误的一般性评论，然后是关于如何实现前向链接的提示。
代码格式化
正确格式化代码很重要，否则您或您的同行将无法轻松阅读。参见示例 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 访问器函数来访问你的 rule 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 的重写，除了它总是 return 是一个只有一个元素的列表（你明白为什么了吗？）。这在稍后调用 append 时很有用，它与 rule-antecedent 一致，return 是一个列表。
规则的可操作性
return 为真或假的函数称为谓词，按照惯例在 Lisp 中以 -p 为后缀（在 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 or APPEND 的 return 值，这些函数保证不会改变其参数（不同于 DELETE 和 NCONC，甚至对于那些函数，只有 returned 值很重要，被授予改变现有存储的能力是实现定义的，只有在那里才能有效地重用内存）。
在某个分支你想return"yes"，在另一个nil； CL 可能是动态类型的，但这里不需要字符串 return 值。
一个return表格只存在于最里面的nil块。在您的情况下，这意味着您 return 来自 DOLIST, not the one from the 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 ... ... ...)))))
换句话说：要么目标已经是已知事实，要么存在可传递地达到目标的可操作规则。请注意，如果您的规则是非终止的，则可能会出现无限递归。
您访问规则的顺序决定了您的策略是深度优先（始终遵循最后尝试的规则并从该规则开始，使用规则列表作为堆栈），还是广度优先（应用所有给定事实的可激活规则，使用规则列表作为队列）。我不知道 "beneath"-first search 这个术语是从哪里来的，我没有找到它的严肃参考（有一篇论文在谈论时引用 Leiserson & Schardl 2010 beneath first search，但是referenced article没有提到它，只有breadth-first，这是众所周知的）。 =46=]
我正在尝试找出解决堆栈溢出问题的问题 算法很清楚，但是它和递归调用是在 if 语句中进行的，所以我不知道为什么它会变坏
(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))
而且我仍然不确定它是否真的在第一次搜索之下 并且我应该通过有一个变量来跟踪它何时通过的元素来证明这一点 提前致谢
这里是对您代码中一些错误的一般性评论，然后是关于如何实现前向链接的提示。
代码格式化
正确格式化代码很重要，否则您或您的同行将无法轻松阅读。参见示例 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 访问器函数来访问你的 rule 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 的重写，除了它总是 return 是一个只有一个元素的列表（你明白为什么了吗？）。这在稍后调用 append 时很有用，它与 rule-antecedent 一致，return 是一个列表。
规则的可操作性
return 为真或假的函数称为谓词，按照惯例在 Lisp 中以 -p 为后缀（在 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)))
正向链接
这里也有一些问题：
您不使用
REMOVEorAPPEND的 return 值，这些函数保证不会改变其参数（不同于DELETE和NCONC，甚至对于那些函数，只有 returned 值很重要，被授予改变现有存储的能力是实现定义的，只有在那里才能有效地重用内存）。在某个分支你想return
"yes"，在另一个nil； CL 可能是动态类型的，但这里不需要字符串 return 值。一个
return表格只存在于最里面的nil块。在您的情况下，这意味着您 return 来自DOLIST, not the one from theLOOP建立的隐式块。你可以给你的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 ... ... ...)))))
换句话说：要么目标已经是已知事实，要么存在可传递地达到目标的可操作规则。请注意，如果您的规则是非终止的，则可能会出现无限递归。
您访问规则的顺序决定了您的策略是深度优先（始终遵循最后尝试的规则并从该规则开始，使用规则列表作为堆栈），还是广度优先（应用所有给定事实的可激活规则，使用规则列表作为队列）。我不知道 "beneath"-first search 这个术语是从哪里来的，我没有找到它的严肃参考（有一篇论文在谈论时引用 Leiserson & Schardl 2010 beneath first search，但是referenced article没有提到它，只有breadth-first，这是众所周知的）。 =46=]