Prolog 后继符号产生不完整的结果和无限循环 [英] Prolog successor notation yields incomplete result and infinite loop
问题描述
我开始学习 Prolog 并首先了解了后继符号.
这就是我了解如何在 Prolog 中编写 Peano 公理的地方.
请参阅 PDF 的第 12 页:
sum(0, M, M).总和(s(N)，M，s(K)):-总和(N，M，K).产品(0，M，0).产品(s(N)，M，P):-产品(N，M，K)，总和(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)) ?;无限循环这个结果有两个问题:
- 未显示所有结果，请注意缺少结果 X=6,Y=1.
- 它不会停止，除非我 Ctrl+C 然后选择 abort.
所以...我的问题是:
- 这是为什么呢?我尝试切换prod"和sum".结果代码给了我所有的结果.再说一次，为什么会这样?但它仍然是死循环.
- 如何解决?
我阅读了关于无限循环的另一个答案.但我很感激有人根据这种情况回答.这对我有很大帮助.
如果你想深入研究终止属性，使用 successor-arithmetics 是一个理想的研究对象:您先验知道它们应该描述什么，因此您可以专注于更多的技术细节.您需要了解几个概念.
通用终止
解释它的最简单方法是考虑 Goal, false.如果 Goal 普遍终止，这将终止.那就是:查看跟踪器是最无效的方法 - 它们只会向您显示单个执行路径.但是您需要一次了解所有这些！当您想要通用终止时，也永远不要看答案，它们只会分散您的注意力.你已经在上面看到了:你得到了三个简洁而正确的答案，然后你的程序才循环.所以最好用 false 来关闭"答案.这消除了所有的干扰.
失败切片
您需要的下一个概念是 故障片.拿一个纯单调的逻辑程序并抛出一些目标false.如果生成的故障片没有终止(普遍地)，那么原始程序也不会终止.在您的示例中，请考虑:
这些 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))))))) 的失败片段::
请注意 sum/3 的显着简化定义.它只说:0加上任何东西就是任何东西.不再.因此，即使是更专业的 prod2(A,0,s(s(s(s(s(s(0))))))) 也会循环 whileprod2(0,X,Y) 优雅地终止 ...
I start to learn Prolog and first learnt about the successor notation.
And this is where I find out about writing Peano axioms in Prolog.
See page 12 of the PDF:
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).
I put the multiplication rules into Prolog. Then I do the query:
?- prod(X,Y,s(s(s(s(s(s(0))))))).
Which means finding the factor of 6 basically.
Here are the results.
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
This result has two problems:
- Not all results are shown, note that the result X=6,Y=1 is missing.
- It does not stop unless I Ctrl+C then choose abort.
So... my questions are:
- WHY is that? I tried switching "prod" and "sum" around. The resulting code gives me all results. And again, WHY is that? It still dead-loops though.
- HOW to resolve that?
I read the other answer on infinite loop. But I'd appreciate someone answer basing on this scenario. It greatly helps me.
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.
Universal termination
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.
Failure slice
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).
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.
Termination inference
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!
Edit: 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).
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).
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.
Edit: 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).
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屋！
