Prolog后继符表示法产生不完整的结果和无限循环 [英] Prolog successor notation yields incomplete result and infinite loop
问题描述
我开始学习Prolog，首先学习了后继符号.
I start to learn Prolog and first learnt about the successor notation.
这就是我在Prolog中编写Peano公理的地方.
And this is where I find out about writing Peano axioms in 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中.然后我执行查询:
I put the multiplication rules into Prolog. Then I do the query:
?- prod(X,Y,s(s(s(s(s(s(0))))))).
这意味着基本上找到6的因数.
Which means finding the factor of 6 basically.
这是结果.
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
此结果有两个问题:
- 未显示所有结果，请注意缺少结果X = 6，Y = 1.
- 除非我按Ctrl + C然后选择中止"，否则它不会停止.
所以...我的问题是:
So... my questions are:
- 那是为什么?我尝试切换"prod"和"sum".结果代码为我提供了所有结果.再说一遍，这是为什么?但是它仍然死循环.
- 如何解决?
我读了无限循环上的另一个答案.但是我希望有人根据这种情况做出回答.这对我有很大帮助.
I read the other answer on infinite loop. But I'd appreciate someone answer basing on this scenario. It greatly helps me.
推荐答案
如果您想深入研究终止属性，请使用 successor-arithmetics 是理想的研究对象:您知道先验应该描述什么，因此您可以专注于更多的技术细节.您将需要理解几个概念.
If you want to study termination properties in depth, programs using successor-arithmetics are an ideal study object: You know a priori what they should describe, so you can concentrate on the more technical details. You will need to understand several notions.
最简单的解释方法是考虑Goal, false.如果Goal通用终止，则终止.也就是说:查看跟踪器是最无效的方法-它们只会向您显示单个执行路径.但是您需要一次了解所有这些内容！当您想要通用终止时，也不要看答案，它们只会分散您的注意力.您已经在上面看到了:您得到了三个简洁而正确的答案，只有这样，您的程序才会循环运行.因此，使用false更好地关闭"答案.这样可以消除所有的干扰.
The easiest way to explain it, is to consider Goal, false. This terminates iff Goal terminates universally. That is: Looking at tracers is the most ineffective way - they will show you only a single execution path. But you need to understand all of them at once! Also never look at answers when you want universal termination, they will only distract you. You have seen it above: You got three neat and correct answers, only then your program loops. So better "turn off" answers with false. This removes all distraction.
您需要的下一个概念是失败切片的概念.采用纯单调逻辑程序并提出一些目标false.如果结果失败片没有(普遍)终止，则原始程序也不会终止.在您的示例中，请考虑:
The next notion you need is that of a failure slice. Take a pure monotonic logic program and throw in some goals false. If the resulting failure slice does not terminate (universally), also the original program won't. In your exemple, consider:
prod(0,M,0) :- false.
prod(s(N), M, P) :-
prod(N,M,K), false,
sum(K,M,P).
这些false目标有助于消除程序中无关的装饰:其余部分向您清楚说明了为什么prod(X,Y,s(s(s(s(s(s(0))))))).不终止.它不会终止，因为该片段根本不关心P！您希望第三个参数将有助于使prod/3终止，但是该片段显示这都是徒劳的，因为P不会在任何目标中发生.无需聊天记录器.
These false goals help to remove irrelevant adornments in your program: The remaining part shows you clearly, why prod(X,Y,s(s(s(s(s(s(0))))))). does not terminate. It does not terminate, because that fragment does not care about P at all! You are hoping that the third argument will help to make prod/3 terminate, but the fragment shows you it is all in vain, since P does not occur in any goal. No need for chatty tracers.
通常很难找到最小的故障片.但是，一旦找到一个，就很难确定其终止或非终止属性.一段时间后，您可以凭直觉想象切片，然后可以使用原因检查该切片是否相关.
Often it is not so easy to find minimal failure slices. But once you found one, it is next to trivial to determine its termination or rather non-termination properties. After some time you can use your intuition to imagine a slice, and then you can use your reason to check if that slice is of relevance or not.
关于故障切片的概念如此引人注目的是:如果要改进程序，您必须在上面片段中可见的部分中修改您的程序！只要您不更改它，问题就会一直存在.因此，故障切片是程序中非常重要的部分.
What is so remarkable about the notion of a failure slice is this: If you want to improve the program, you have to modify your program in the part visible in above fragment! As long as you do not change it, the problem will persist. A failure slice is thus a very relevant part of your program.
这是您需要的最后一件事:终止推断器(或分析器)，例如 cTI 将帮助您快速确定终止条件.查看prod/3的推断终止条件和改进的prod2/3
That is the final thing you need: A termination inferencer (or analyzer) like cTI will help you to identify the termination condition rapidly. Look at the inferred termination conditions of prod/3 and the improved prod2/3 here!
既然这是一个家庭作业问题，我还没有发布最终解决方案.但要明确地说，这是到目前为止获得的终止条件:
And since this was a homework question I have not posted the final solution. But to make it clear, here are the termination conditions obtained so far:
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绝对比原始程序好！
So the new prod2/3 is strictly better than the original program!
现在，由您决定最终的程序.其终止条件为:
Now, it is up to you to find the final program. Its termination condition is:
prod3(A,B,C)terminates_if b(A),b(B);b(C).
首先，尝试查找prod2(A,B,s(s(s(s(s(s(0)))))))的故障切片！我们希望它终止，但它不会终止.因此，请采用该程序并手动添加false目标！其余部分将向您显示密钥！
To start with, try to find the failure slice for prod2(A,B,s(s(s(s(s(s(0)))))))! We expect it to terminate, but it still does not. So take the program and add manuallyfalse goals! The remaining part will show you the key!
作为最后的提示:您需要添加一个额外的目标和一个事实.
As a final hint: You need to add one extra goal and one fact.
根据要求，这是prod2(A,B,s(s(s(s(s(s(0)))))))的失败切片:
Upon request, here is the failure slice for 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)) :- false,
sum(N,M,K).
请注意大大简化了sum/3的定义.它只说:0加任何东西就是任何东西.不再.结果，即使更专业的prod2(A,0,s(s(s(s(s(s(0)))))))也会循环播放，而prod2(0,X,Y)会优雅地终止...
Please note the significantly simplified definition of sum/3. It only says: 0 plus anything is anything. No more. As a consequence even the more specialized prod2(A,0,s(s(s(s(s(s(0))))))) will loop whileprod2(0,X,Y) elegantly terminates ...
这篇关于Prolog后继符表示法产生不完整的结果和无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
