3

我目前正在研究 SICP 关于逻辑编程的部分,但我陷入了有关逻辑推导的示例中,尤其是附加到表单规则。它们是如何工作的?我不太明白的是第二条规则如何 cdr-downs 第一个列表。例如,给定:

(规则(附加到表单()?y?y))

(规则(附加到表单 (?u . ?v) ?y (?u . ?z))(附加到表单 ?v ?y ?z))

a) 我们如何到达:

;;; Query input:
(append-to-form (a b) (c d) ?z)

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

b) 这个呢:

;;; Query input:
(append-to-form (a b) ?y (a b c d))

to

;;; Query results:
(append-to-form (a b) (c d) (a b c d))

c) 最后:

;;; Query input:
(append-to-form ?x ?y (a b c d))

to

;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))

我会对执行规则匹配所需的具体心理步骤感兴趣。

先感谢您。

4

1 回答 1

3

通过拿一张纸并写下每一步来扮演口译员。对于每一步,您都写下/可以触发哪个规则以及哪些变量绑定到什么值。

例如:

(append-to-form (a b) (c d) ?z)

触发规则

(rule (append-to-form (?u . ?v) ?y (?u . ?z)) 
  (append-to-form ?v ?y ?z))

?u = a, ?v = (b), ?y = (c d), ?z = (a . ?z_2)

注意:原始查询中的?z 应该是与规则正文中的?z 不同的变量,因此将规则的?z 重命名为?z_2。当与 (?a . ?b) 匹配时,列表 (1 2 3) 会产生 ?a = 1, ?b = (2 3),就像 car/cdr'ing 列表时一样。

这些绑定被应用到规则的主体(append-to-form ?v ?y ?z)所以我们得到

(append-to-form (b) (c d) ?z_2)

这又变成了

(append-to-form () (c d) ?z_3)

并触发不同的规则: (rule (append-to-form () ?y ?y))将 ?z_3 绑定到 (cd)。然后递归开始,?z_2 被定义为 (b . ?z_3),?z 被定义为 (a . ?z2)

原始查询(append-to-form (a b) (c d) ?z)应用于 ?z = (a . (b . (cd))) 的绑定并返回(append-to-form (a b) (c d) (a b c d))

其余的练习留给读者;)

这里的关键概念是模式匹配和统一,可以在第 4.2.2 节中找到。整个查询评估器确实是 SICP 中最困难的部分,所以不要气馁。这是非常值得的。尝试运行代码(在 R5RS 方案中)并修改它,例如添加跟踪。

于 2010-12-11T17:40:19.810 回答