2

我有一个非常简单的问题：编写一个实现 append Prolog 函数的 Prolog 程序，它连接两个字符串并以下列方式工作：

  1. 追加（[a，b]，[c，d]，X）。---> X = [a,b,c,d]
  2. 追加（[a，b]，X，[a，b，c，d]）。---> X = [c,d]
  3. 追加（[a,b],[X,d],[a,b,c,d]）。---> X=c
  4. 追加（X，Y，[a，b，c，d]）。---> X=[] 和 Y=[a,b,c,d)

所以我有以下两种解决方案，我不太确定我的声明性解释是否正确：

1）解决方案1：

myappend1([],L,L).

myappend1([X|L1],L2,[X|L3]) :- myappend1(L1,L2,L3).

我认为我可以以声明性方式阅读它，如下所示：

事实是：如果第一个列表 (L1) 为空且第二个列表 (L2) 不为空，则L1*L2 的串联为 L2为 TRUE

如果事实不正确，则意味着第一个列表不为空，因此第一个列表和第二个列表的连接不正确，即第二个列表

所以，让我称第一个列表 L1、第二个列表 L2 和第三个列表 L3 如果 L3 是 L1 和 L2 的串联，则规则响应 TRUE，否则返回 false

我认为这条规则的声明性含义是：如果规则的主体为真，则规则的头部为真。

  • 在头部从L1列表和L3列表中提取第一个X元素（并尝试统一，如果匹配则继续，否则意味着第三个列表它不是第一个和第二个列表的串联）
  • 在正文中调用第一个没有 X 元素的列表、第二个列表和 L3 列表（表示连接）上的函数

当它达到我已证明的事实myappend1([],L,L) 的基本情况时。这是真的，程序在前一个过去进行回溯，并且因为第一个列表的 X 元素与第三个列表的 X 元素统一它可以做到这一点，这个计算通过它是 TRUE 并返回直到到达第一个断言

这是一个正确的声明性解释吗？

2）第二种解决方案：

myappend2([],L,L).

myappend2(L1,L2,L3) :-  L1=[X|T],               % Dimostra questo predicato AND
                    L3=[X|L4],      % Dimostra questo predicato AND
            myappend2(T,L2,L4).     % Dimostra questa funzione

与前面的解决方案一样，事实简单地说：如果第一个列表 (L1) 为空且第二个列表 (L2) 不为空，则L1*L2 的串联为 L2为 TRUE

如果事实不正确，则意味着第一个列表不为空，因此第一个列表和第二个列表的连接不正确，即第二个列表

如果事实不正确，则 Prolog 调用规则，该规则意味着：如果规则主体为真，则规则的头部为真。

在这种情况下，我可以这样阅读：

如果满足以下条件，则 L1 和 L2 的串联 L3 为 TRUE：

  • L1 的当前第一个 X 元素与连接列表的当前第一个元素和 myappend2 在第一个子列表、L2 和第三个子列表上调用它是 true

这是对的吗？

对我来说，以声明的方式进行推理是如此困难:-(

4

2 回答 2

2

当你试图弄清楚一个谓词的声明性含义时，你会问：这个谓词适用于哪些解决方案？

Prolog 的1子句独立地为解决方案集做出贡献。因此，在条款之间建立任何联系都需要进行一些额外的审查。很容易做出一些并非如此的假设：

myappend1([],L,L). 如果事实并非如此，则意味着第一个列表不为空，因此...

考虑一个目标，myappend1([],[],[a]).事实并不适用，第一个列表仍然是空的。在这里，您正在尝试操作该子句的含义。这样做非常诱人，因为编程语言的大部分内容只能通过想象事情是如何一步步发生的来理解的。Prolog 的困难在于试图忽略这些细节，而不是完全忽略程序方面。

myappend1([X|L1],L2,[X|L3]) :- myappend1(L1,L2,L3).

要阅读规则，特别是递归规则，查看:-1970 年代 ← 的渲染会很有帮助。所以它是一个箭头，但它是从右到左的。因此，您可以按如下方式阅读此规则，从右侧开始：

假设myappend(L1,L2,L3)成立，现在越过:-左侧也myappend([X|L1],L2,[X|L3])成立。

有时，阅读此类规则的更好方法是完全遮住头部并询问

??? :- myappend1(L1,L2,L3).

假设，我知道一些L1，我能从L2中L3得出myappend1(L1,L2,L3).什么结论？有什么有趣的吗？有什么相关的东西我可以很容易地从这 3 个值中构建出来吗？

这是一开始有点令人反感的事情，因为你可能会说：但是我怎么知道这样的存在呢？好吧，你没有。你只是假设它存在。如果它永远不会存在，那么您将永远无法得出这个结论。

许多人试图从左到右阅读规则，但虽然 Prolog 实际上是从左到右执行它们，但它们所涵盖的含义更容易理解为结论方向。当 Prolog 从左到右执行规则时，它不知道这是否会成功。因此，执行可能完全是推测性的。想想append(L1,[z],[a,b,c,d,e])。在这里，Prolog 将对列表的每个元素应用此规则。但所有这些申请都是徒劳的。也就是说，最终它会失败。

印刷精美

1 实际上，Prolog 的纯单调子集。

于 2013-03-19T19:48:38.253 回答
2

与上次一样，您正在添加代码中不存在的限制。不要为此感到难过，Prolog 非常不同，需要时间来适应它。

开始吧。

append([], L, L).

你说：

如果第一个列表 (L1) 为空且第二个列表 (L2) 不为空，则 L1*L2 的串联为 L2 为 TRUE

事实上，这条规则并没有说明 L2 是否为空——甚至是一个列表！——或者不是。它只是说附加到其他东西的空列表是其他东西。观察：

?- append([], foo, X).
X = foo.

这里的声明性阅读是“附加到 L 的空列表是 L”。

如果事实不正确，则意味着第一个列表不为空，因此第一个列表和第二个列表的连接不正确，即第二个列表

是的，这是正确的，但 Prolog 并没有深入研究身体。它只是说“第一个列表不为空，因此此规则不匹配；继续前进。”

下一条规则：

myappend1([X|L1], L2, [X|L3]) :- myappend1(L1,L2,L3).

你的评论对我来说似乎过于复杂。我想说这条规则说：“如果列表 L1 到 L2 的 myappend1 是 L3，则列表 [X 后跟 L1] 到 L2 的 myappend1 是列表 [X 后跟 L3]。” 然而，这种阅读的后果与你所描述的完全一样。

因此，您对第一个版本中发生的事情的理解是正确的。

第二种解决方案在机械上与第一种解决方案完全相同。唯一的区别是我们将统一从子句的头部移到了主体。在我看来，这个版本明显逊色，因为它所做的只是为读者创造了额外的工作。

到目前为止，我认为您遇到的问题是您的声明性推理与 Prolog 的计算引擎密切相关。像我提供的那些更纯粹的声明性阅读更简单，看起来更像 Prolog 所说的（并且与它的评估方式无关）。

你需要练习来区分这些概念，但我认为它会帮助你变得更好（显然这是你关心的事情）。与此同时，来这里寻求帮助并没有错，就像你在困惑时所做的那样。:)

让我知道我是否可以提供更多帮助！

于 2013-03-19T18:58:11.230 回答