Prolog后继符号产生不完整的结果和无限循环

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

这是我在Prolog中写皮纳诺公理的地方。

见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))))))). 

这意味着基本上find6的因素。

这是结果。

 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然后select中止。

所以…我的问题是:

  1. 这是为什么? 我试着转换“prod”和“sum”。 最终的代码给了我所有的结果。 而且,为什么呢? 但它仍然死循环。
  2. 如何解决这个问题?

我读了无限循环的另一个答案。 但我会很感激有人回答这个情况。 这对我很有帮助。

如果你想深入研究终止属性,使用后继algorithm的程序是一个理想的研究对象:你知道他们应该描述什么,所以你可以专注于更多的技术细节。 你需要了解几个概念。

通用终止

解释它最简单的方法是考虑Goal, false 。 如果Goal普遍终止,这就终止了。 那就是:看着跟踪者是最没有效率的方法 – 他们只会向你显示一个执行path。 但是你需要马上理解所有的东西! 当你想要通用终止的时候也不要看答案,他们只会分散你的注意力。 你已经看到上面:你有三个整齐正确的答案,只有你的程序循环。 所以更好地“closures”与false答案。 这消除了所有的分心。

失败片

你需要的下一个概念是失败的一部分 。 采取一个纯粹的单调逻辑程序,并抛出一些目标false 。 如果生成的失败片没有终止(普遍),原始程序也不会。 以你为例,考虑一下:

 prod(0,M,0): - false 。
 prod(s(N),M,P): - 
     prod(N,M,K), false,
     总和(K,M,P)

这些false目标有助于删除程序中不相关的装饰:其余部分清楚地告诉你,为什么prod(X,Y,s(s(s(s(s(s(0))))))). 不终止。 它并没有终止,因为这个片段根本不关心P ! 你希望第三个参数有助于终止产品,但是这个片段显示了这一切都是徒劳的,因为P不会出现在任何目标中。 不需要聊天跟踪器。

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

如果你想改进程序,你必须修改上面片段中可见部分的程序! 只要你不改变,问题就会持续下去。 故障切片因此是您的程序非常相关的部分。

终止推断

这是您需要的最后一件事情:终止推理(或分析器),如cTI将帮助您快速识别终止条件。 看看prod/3的推断终止条件和改进的prod2/3 在这里 !


编辑:因为这是一个功课的问题,我没有贴出最后的解决scheme。 但是要说清楚,这里是到目前为止获得的终止条件:

     (A,B,C)终止_if b(A),b(B)。
     prod2(A,B,C)终止_if b(A),b(B);  b(A),b(C)

所以新的prod2/3比原来的程序严格得多!

现在,你要find最后的节目。 其终止条件是:

    prod3(A,B,C)终止_if b(A),b(B); b(C)。

首先,尝试findprod2(A,B,s(s(s(s(s(s(0)))))))的失败片prod2(A,B,s(s(s(s(s(s(0))))))) ! 我们期望它终止,但它仍然没有。 所以采取程序和手动添加false目标! 剩下的部分将显示你的关键!

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


编辑:根据请求,这里是prod2(A,B,s(s(s(s(s(s(0)))))))的失败片prod2(A,B,s(s(s(s(s(s(0)))))))

 prod2(0,_,0): - false 。
 prod2(s(N),M,P): - 
    sum(M,K,P),
    prod2(N,M,K), false 。

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

请注意sum/3的明显简化的定义。 它只是说:0加上任何东西。 不再。 因此,即使更专业化的prod2(A,0,s(s(s(s(s(s(0)))))))将循环,而prod2(0,X,Y)优雅地终止…

第一个问题(WHY)很容易被发现,特别是如果知道左recursion 。 当C被绑定时, sum(A,B,C) 绑定 A和B,但是原始的程序prod(A,B,C)不使用那个绑定,而是用静止的A和Brecursion。

如果我们交换总和,那么从recursion调用中总共得到2个有用的绑定:

 sum(M, K, P) 

现在M被绑定,并将被用来终止左recursion。 我们可以交换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)),当prod3被调用P unknown时,我们再次有一个非终止循环,但总之。

 ?- 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. 

(A),B(B); b(A),b(C)。

Interesting Posts