1

我正在尝试使用下面的代码实现求幂，但是像 2^1 ( ex(s(s(0)), s(0), Z).) 这样的简单查询会永远挂起。

nat(0).
nat(s(X)) :- nat(X).
su(0, X, X) :- nat(X).
su(s(X), Y, s(Z)) :- su(X, Y, Z).

mu(0, _, 0).
mu(s(X), Y, Z) :- su(Y, A, Z), mu(X, Y, A).

ex(_, 0, s(0)).
ex(X, s(Y), Z) :- mu(X, A, Z), ex(X, Y, A).
4

1 回答 1

1

据我所知，它效率不高，因为使用两个自由变量mu/3调用。确实：

ex(X, s(Y), Z) :- mu(X, A, Z), ex(X, Y, A).

两者A和在那一刻Z都是未知的（我已将它们以粗体显示）。

现在您mu/2无法正确处理此问题。如果我们mu/3用查询mu(s(0), A, Z)，我们得到：

?- mu(s(0), A, Z).
A = Z, Z = 0 ;
ERROR: Out of global stack

所以它也陷入了无限递归。

这是因为它将采用 , 的第二个子句mu/3，并且：

mu(s(X), Y, Z) :- su(Y, A, Z), mu(X, Y, A).

su/3用三个未知变量调用。这样做的效果是su/3可以“直到时间结束”不断提出价值：

?- su(A, B, C).
A = B, B = C, C = 0 ;
A = 0,
B = C, C = s(0) ;
A = 0,
B = C, C = s(s(0)) ;
A = 0,
...

即使递归mu(X, Y, A)拒绝所有这些建议，su/3也永远不会停止提出新的解决方案。

mu/3因此，当我们为和设计谓词时，最好记住这一点ex/3。

例如，我们可以在这里使用累加器来累加值并返回最终产品。这样做的好处是，我们在su/3调用时使用真实值，例如：

mu(A, B, C) :-
    mu(A, B, 0, C).

mu(0, _, 0, S, S).
mu(s(X), Y, I, Z) :-
    su(Y, I, J),
    mu(X, Y, J, Z).

现在，如果我们mu/3只输入固定的第一个参数，我们会看到：

?- mu(s(0), X, Y).
X = Y, Y = 0 ;
X = Y, Y = s(0) ;
X = Y, Y = s(s(0)) ;
X = Y, Y = s(s(s(0))) ;
...
?- mu(s(s(0)), X, Y).
X = Y, Y = 0 ;
X = s(0),
Y = s(s(0)) ;
X = s(s(0)),
Y = s(s(s(s(0)))) ;
X = s(s(s(0))),
Y = s(s(s(s(s(s(0)))))) ;
...
...

所以这意味着我们现在至少不会陷入mu/3只固定第一个参数的循环中。

我们可以使用相同的策略来定义ex/3谓词：

ex(X, Y, Z) :-
    ex(X, Y, s(0), Z).

ex(X, 0, Z, Z).
ex(X, s(Y), I, Z) :-
    mu(X, I, J),
    ex(X, Y, J, Z).

然后我们设法计算像2 1和2 2这样的指数：

?- ex(s(s(0)), s(0), Z).
Z = s(s(0)) ;
false.
?- ex(s(s(0)), s(s(0)), Z).
Z = s(s(s(s(0)))) ;
false.

请注意，上面仍然存在一些缺陷，例如计算该值的幂4仍然会循环：

?- ex(X, Y, s(s(s(s(0))))).
ERROR: Out of global stack

通过重写谓词，我们也可以避免这种情况。但我把它留作练习。

于 2018-09-26T08:29:16.413 回答