41

我开始学习 Prolog 并首先了解了后继符号。

这就是我发现在 Prolog 中编写 Peano 公理的地方。

请参阅PDF的第 12 页：

sum(0, M, M).
sum(s(N), M, s(K)) :-
    sum(N,M,K).

prod(0,M,0).
prod(s(N), M, P) :-
    prod(N,M,K),
    sum(K,M,P).

我将乘法规则放入 Prolog。然后我进行查询：

?- prod(X,Y,s(s(s(s(s(s(0))))))).

这意味着基本上找到了 6 的因数。

这是结果。

X = s(0),
Y = s(s(s(s(s(s(0)))))) ? ;
X = s(s(0)),
Y = s(s(s(0))) ? ;
X = s(s(s(0))),
Y = s(s(0)) ? ;
infinite loop

这个结果有两个问题：

  1. 并未显示所有结果，请注意结果 X=6,Y=1 缺失。
  2. 它不会停止，除非我 Ctrl+C 然后选择中止。

所以......我的问题是：

  1. 这是为什么？我尝试切换“prod”和“sum”。结果代码给了我所有的结果。再说一次，为什么会这样？虽然它仍然是死循环。
  2. 如何解决？

我读了关于无限循环的另一个答案。但我很感激有人根据这种情况回答。它对我有很大帮助。

4

2 回答 2

36

如果您想深入研究终止属性，使用的程序是一个理想的研究对象：您先验地知道它们应该描述什么，因此您可以专注于更多技术细节。您将需要了解几个概念。

通用端接

解释它的最简单方法是考虑Goal, false. 这终止了当且仅当Goal普遍终止。那就是：查看跟踪器是最无效的方法 - 它们只会向您显示单个执行路径。但是您需要一次了解所有这些！当您想要通用终止时，也永远不要看答案，它们只会分散您的注意力。你已经在上面看到了：你得到了三个简洁而正确的答案，然后你的程序才循环。所以更好的“关闭”答案false。这消除了所有的干扰。

故障切片

您需要的下一个概念是故障切片。取一个纯单调逻辑程序并输入一些目标false。如果生成的故障片没有终止（普遍地），那么原始程序也不会终止。在您的示例中，请考虑：

产品（0，M，0）：-假。
产品（s（N），M，P）：-
    产品（N，M，K），假，
    总和（K，M，P）。

这些false目标有助于删除程序中不相关的修饰：剩余部分清楚地向您展示，为什么prod(X,Y,s(s(s(s(s(s(0))))))).不终止。它不会终止，因为那个片段根本不关心P！您希望第三个参数有助于prod/3终止，但该片段向您显示这一切都是徒劳的，因为P不会出现在任何目标中。不需要健谈的示踪剂。

通常，要找到最小的故障片并不容易。但是一旦你找到了一个，确定它的终止或非终止属性几乎是微不足道的。一段时间后，你可以用你的直觉想象一个切片，然后你可以用你的理由来检查那个切片是否相关。

失败片的概念如此引人注目的地方在于：如果你想改进程序，你必须在上面片段中可见的部分修改你的程序！只要你不改变它，问题就会一直存在。因此，故障片是程序中非常相关的部分。

终止推断

这是您需要的最后一件事：像cTI这样的终止推断器（或分析器）将帮助您快速识别终止条件。看看推断的终止条件prod/3和改进的prod2/3 这里！

编辑：由于这是一个家庭作业问题，我没有发布最终解决方案。但为了清楚起见，这里是迄今为止获得的终止条件：

    prod(A,B,C)terminates_if b(A),b(B)。
    prod2(A,B,C)terminates_if b(A),b(B); b(A),b(C)。

所以新prod2/3的严格比原来的程序好！

现在，由您决定最终程序。其终止条件为：

   prod3(A,B,C) 终止_如果 b(A),b(B);b(C)。

首先，尝试找到prod2(A,B,s(s(s(s(s(s(0)))))))! 我们预计它会终止，但它仍然没有。所以采取程序并手动添加false目标！剩下的部分会告诉你关键！

最后提示：您需要添加一个额外的目标和一个事实。

编辑：根据要求，这里是失败切片prod2(A,B,s(s(s(s(s(s(0)))))))：

prod2(0,_,0) :-假。
产品 2（s（N），M，P）：-
   总和（M，K，P），
   产品 2（N，M，K），假。

总和（0，M，M）。
sum(s(N), M, s(K)) :- false , 
    sum(N,M,K)。

请注意显着简化的定义sum/3。它只说：0加上任何东西就是任何东西。不再。因此，即使是更专业的也会在优雅地终止prod2(A,0,s(s(s(s(s(s(0)))))))时循环......prod2(0,X,Y)

于 2012-04-13T12:51:43.237 回答
17

第一个问题（为什么）很容易发现，特别是如果知道左递归。在绑定 C时sum(A,B,C) 绑定A 和 B ，但原始程序 prod(A,B,C) 不使用该绑定，而是在 A,B 未绑定的情况下进行递归。

如果我们交换 sum,prod，我们会从 sum 中得到 2 个有用的绑定，用于递归调用：

sum(M, K, P)

现在 M 已绑定，并将用于终止左递归。我们可以交换 N 和 M，因为我们知道乘积是可交换的。

sum(0, M, M).
sum(s(N), M, s(K)) :-
    sum(N, M, K).

prod3(0, _, 0).
prod3(s(N), M, P) :-
    sum(M, K, P),
    prod3(M, N, K).

请注意，如果我们交换 M,K（即 sum(K,M,P)），当使用 P unknown 调用 prod3 时，我们再次有一个非终止循环，但总和。

?- prod3(X,Y,s(s(s(s(s(s(0))))))).
X = s(s(s(s(s(s(0)))))),
Y = s(0) ;
X = s(s(s(0))),
Y = s(s(0)) ;
X = s(s(0)),
Y = s(s(s(0))) ;
X = s(0),
Y = s(s(s(s(s(s(0)))))) ;
false.

OT我对 cTI 报告感到困惑：prod3(A,B,C)terminates_if b(A),b(B);b(A),b(C)。

于 2012-04-18T17:20:19.457 回答