3

我整天都在想这个。我终于承认，我对 Prolog 的理解并没有我想象的那么好。

在一天开始的时候，我在实现一个后继算法时遇到了麻烦，它乘以 2 个 s 数，它的结构是这样的：

nat(0).
nat(s(X)):-nat(X).

我的第一次尝试是这样的：

 mul(0,_,0).
 mul(s(F1),F2,P):-mul(F1,F2,Tmp),add(F2,Tmp,P)

这有效，但查询mul(X,Y,s(0)) 以无限循环结束。为什么？我已阅读以下帖子：Prolog 后继符号产生不完整的结果和无限循环

我从中了解到：如果我在调用 add 之前调用 mul，并且我在 mul/3 谓词中有变量，这些变量在两个 mul/3 调用中都没有使用，Prolog 会尝试为它未绑定的变量寻找新的可能性。因此它进入了一个无限循环。

为了解决这个问题，我先调用了add：

mul(0,_,0).
mul(s(F1),F2,P):-add(F2,Tmp,P),mul(F2,F1,Tmp).

做到了。然后我尝试实现幂函数，并想“嗯，现在很容易，第一次尝试是：

pow(_,0,s(0)).
pow(B,s(E),R):-pow(B,E,Tmp), mul(Tmp,B,R).

但是，我必须把 mul 放在第一位，以防止 R 和 Tmp 的左递归。

简单！”男孩，我错了。我不知道如何在不进入无限循环的情况下实现它，即使我把 mul 放在前面。

任何建议都将受到高度赞赏。您可以节省我周六的工作量并提高我的自尊心！先感谢您。

编辑：添加了我缺少的总和谓词：

add(0, Y, Y).
add(s(S1), S2, s(Sum)):-  add(S1,S2,Sum).
4

1 回答 1

4

我们希望以下终止条件成立：

pow(B, E, P) terminates_if b(B), b(E).
pow(B, E, P) terminates_if b(P).

或简要

pow(B, E, P) terminates_if b(B), b(E) ; b(P).

我们不能要求更多。不止于此，将b(B)独自一人或b(E)独自一人。但在这些情况下，我们需要无数个暗示不终止的答案。当然，我们可以采用一个总是终止的定义，并且对于所有测试用例都成功，比如

战俘（_B，_E，_P）。

唉，这个定义也适用于我们不想要的任何其他情况。因此，除非您只会接受成功测试，否则您必须采取更详细的定义。

避免不终止的另一种方法是诉诸自然数的另一种定义。使用library(clpz)（SWIlibrary(clpfd)是较弱的前体）

pow(B, E, P) :-
   B #>= 0,
   E #>= 0,
   P #= B^E.

但目前，我们坚持使用后继算法。CapelliC 已经为您提供了一个终止于b(B), b(E). 因此，让我们尝试改进它！一种方法是以某种方式将P推论的数量限制为有限数量。一种方法是考虑论点之间的关系。

的论点之间有什么有趣的关系pow/3吗？我真的很想这样：

b e ≥ e, b e ≥ b 对于 e, b ≥ 0

这几乎是真的。它实际上通过添加 b ≥ 2 成立。

只是为了确保我会检查我没有完全错，我会试试这个1：

?- M #= 10^150, [B,E,P]ins 0..M, P #= B^E, B #>= 2, P #< E.
false.

我会认为这是一个证据，尽管它不是一个。

现在来定义。这个想法是通过添加额外的参数来限制递归次数来处理一般情况。一个限制LP，pow一个限制LM。mult这些参数由额外的空格分隔，以明确添加它们的位置。

pow(_, 0, s(0)).
pow(0, s(_), 0).
pow(s(B), s(0), s(B)).
pow(s(0), s(s(_)), s(0)).
pow(B, E, P) :-
   B = s(s(_)), E = s(s(_)), P = s(s(s(s(_)))), 
   powx(B, E, P,     P, P).
%                    ^^^^^ added arguments to limit pow and mult

sum(0, M, M).
sum(s(N), M, s(K)) :-
    sum(N, M, K).

mul(0,_,0,_).
mul(s(F1),F2,P,    s(LM)) :-
   mul(F1,F2,Tmp,    LM),
   sum(Tmp, F2, P).   % note: arguments exchanged!

powx(_,0,s(0),    _, _).
powx(B,s(E),R,    s(LP), LM) :-
   powx(B,E,Tmp,     LP, LM),
   mul(Tmp,B,R,      LM).

对于简单的情况pow(b,b,f)，开销应该是最小的。对于新案例，pow(f,f,b)可以通过以某种方式降低限制来减少开销。

脚注

1 我只用 10 150试了一下。没有普遍的证据。让我们希望它没事。出于某种原因，较大的值会产生 stackoverflow™。P #< E这是导致大量重新计算的最后一个目标。否则，它最多可以工作 10 10 7。

于 2016-10-16T18:02:37.340 回答