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