为了账号安全,请及时绑定邮箱和手机立即绑定

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

/ 猿问

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

我开始学习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

此结果有两个问题:


并未显示所有结果,请注意缺少结果X = 6,Y = 1。

除非我按Ctrl + C然后选择中止,否则它不会停止。

所以...我的问题是:


这是为什么?我尝试切换“ prod”和“ sum”。结果代码为我提供了所有结果。再说一遍,为什么呢?它仍然死循环。

如何解决?

我读了无限循环上的另一个答案。但是我希望有人根据这种情况做出回答。这对我有很大帮助。


查看完整描述

2 回答

?
慕森王

如果要深入研究端接属性,则使用后继算法的程序是理想的研究对象:先验地了解它们应描述的内容,因此您可以专注于更多的技术细节。您将需要理解几个概念。


通用终端

解释它的最简单方法是考虑Goal, false。如果Goal通用终止,则此终止。也就是说:查看跟踪器是最无效的方法-它们只会向您显示单个执行路径。但是您需要一次了解所有这些内容!当您想要通用终止时也不要看答案,它们只会分散您的注意力。您已经在上面看到了:您得到了三个简洁而正确的答案,只有这样,您的程序才会循环运行。因此,用更好的“关闭”答案false。这消除了所有的干扰。


失败切片

您需要的下一个概念是故障切片。采用纯单调逻辑程序并提出一些目标false。如果产生的故障片未(通用)终止,则原始程序也不会终止。以您的示例为例:


PROD(0,M,0): - 假。

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任何目标都不会发生。无需健谈追踪器。


通常,要找到最小的故障片段并不容易。但是,一旦找到一个,就很难确定其终止或非终止属性。一段时间后,您可以凭直觉想象一个切片,然后可以使用您的理由检查该切片是否相关。


故障切片的概念如此显着是这样的:如果要改进程序,则必须在上面片段中可见的部分中修改程序!只要您不更改它,问题就会一直存在。因此,故障切片是程序中非常重要的部分。


终止推断

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


编辑:并且由于这是一个家庭作业问题,我还没有发布最终解决方案。但是要明确地说,这是到目前为止获得的终止条件:


    prod(A,B,C)终止于b(A),b(B)。

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

因此,新版prod2/3绝对比原始程序好!


现在,由您决定最终的程序。其终止条件为:


   prod3(A,B,C)terminates_if 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):- 假。

prod2(s(N),M,P):-

   总和(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)优雅地终止...


查看完整回答
反对 回复 2019-10-21
?
慕瓜9086354

第一个问题(WHY)相当容易发现,特别是如果知道左递归。sum(A,B,C) 结合当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)),当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.

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


查看完整回答
反对 回复 2019-10-21

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信