5

我需要使用自然数为 2 的幂创建一个 Prolog 谓词。自然数是：0、s(0)、s(s(0)) 等等。

例如：

?- pow2(s(0),P).
P = s(s(0));
false.
?- pow2(P,s(s(0))).
P = s(0);
false.

这是我的代码：

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  pow2(N,Z),
  times2(Z,Y).

它与第一个示例完美配合，但在第二个示例中进入无限循环。
我该如何解决这个问题？

4

2 回答 2

8

这是一个终止于第一个或第二个参数被绑定的版本：

pow2(E,X) :-
  pow2(E,X,X)。

pow2(0,s(0),s(_))。
pow2(s(N),Y,s(B)) :-
   pow2(N,Z,B),
   添加（Z，Z，Y）。

您可以使用 cTI确定其终止条件。

那么，我是如何想出这个解决方案的呢？这个想法是找到一种方法，第二个参数如何确定第一个参数的大小。关键思想是对于所有i ∈ N : 2 i > i。

所以我添加了一个进一步的论据来表达这种关系。也许你可以进一步加强它？

这就是原始程序不终止的原因。我将原因作为。有关更多详细信息和其他示例，请参见标签。

?- pow2(P,s(s(0))),假。

pow2(0,s(0)) :-假。
pow2(s(N),Y) :-
  pow2(N,Z)，假，
   times2(Z,Y)。

正是这个微小的片段是不终止的源泉！看看Z哪个是新变量！要解决此问题，必须以某种方式修改此片段。

这就是@Keeper 的解决方案不会终止的原因pow2(s(0),s(N))。

?- pow2(s(0),s(N)),假。

添加（0，Z，Z）：-假。
添加（s（X），Y，s（Z））：-
  添加（X，Y，Z），假。

次2（X，Y）：-
  添加（X，X，Y），假。

pow2(0,s(0)) :-假。
pow2(s(N),Y) :- false ,
   var(Y) ,
   pow2(N,Z) ,
   times2(Z,Y)。
pow2(s(N),Y) :-
  非变量（Y），
  次2（Z，Y），假，
   pow2（N，Z）。
于 2012-03-16T17:10:18.913 回答
4

这是因为 pow2 的评估顺序。如果你切换 pow2 的顺序，你会让第一个例子陷入无限循环。所以你可以先检查 Y 是 avar还是nonvar。

像这样：

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  var(Y),
  pow2(N,Z),
  times2(Z,Y).
pow2(s(N),Y) :-
  nonvar(Y),
  times2(Z,Y),
  pow2(N,Z).
于 2012-03-16T15:41:06.463 回答