3

以下 Prolog 程序定义了一个谓词fact/2，用于在后继算术中计算整数的阶乘：

fact(0, s(0)).
fact(s(X), Y) :-
  fact(X, Z),
  prod(s(X), Z, Y).

prod(0, _, 0).
prod(s(U), V, W) :-
  sum(V, X, W),
  prod(V, U, X).

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

它适用于此参数模式下的查询：

?- fact(s(0), s(0)).
   true
;  false.

它也适用于这种参数模式下的查询：

?- fact(s(0), Y).
   Y = s(0)
;  false.

它也适用于这种参数模式下的查询：

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

但它会在这种参数模式下通过查询耗尽资源：

?- fact(X, s(0)).
   X = 0
;  X = s(0)
;
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 4Kb, global: 0.2Gb, trail: 0Kb
  Stack depth: 2,503,730, last-call: 100%, Choice points: 13
  In:
    [2,503,730] sum('<garbage_collected>', _1328, _1330)
    [38] prod('<garbage_collected>', <compound s/1>, '<garbage_collected>')
    [33] fact('<garbage_collected>', <compound s/1>)
    [32] fact('<garbage_collected>', <compound s/1>)
    [31] swish_trace:swish_call('<garbage_collected>')

如何在所有参数模式的后继算术中实现阶乘序列？

4

2 回答 2

3

第一个问题一定是为什么？有助于理解问题：

事实（0，s（0））：-假。
fact(s(X), Y) :- fact(X, Z), false , prod(s(X), Z, Y)。

仅当给出第一个参数时，此片段才会终止。如果不是，则无法防止不终止，因为Y在可见部分中不受任何限制。所以我们必须改变那部分。一个简单的方法是观察第二个参数不断增加。事实上它增长得相当快，但为了终止，一个就足够了：

fact2(N, F) :-
   fact2(N, F, F).

fact2(0, s(0), _).
fact2(s(X), Y, s(B)) :- fact2(X, Z, B), prod(s(X), Z, Y).

而且，我应该补充一点，这甚至可以证明。

fact2(A,B)terminates_if b(A);b(B).
    % optimal. loops found: [fact2(s(_),s(_))]. NTI took    0ms,73i,73i

但是，有一个警告...

如果只F知道，程序现在将需要与 | 成比例的时间空间。F|！这不是感叹号，而是阶乘符号...

于 2021-08-19T17:00:58.413 回答
1

我认为当第二个参数是基本术语时，您可以使用 cut 来避免回溯。

fact(0, s(0)).
fact(s(X), Y) :-
  fact(X, Z),
  prod(s(X), Z, W),
  (ground(Y) ->
    !,
    Y = W
  ; Y = W).

prod(0, _, 0).
prod(s(U), V, W) :- sum(V, X, W), prod(V, U, X).

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

例子：

?- fact(N, 0).
   false.

?- fact(N, s(s(s(0)))).
   false.

?- fact(X, s(0)).
   X = 0
;  X = s(0)
;  false.

?- fact(s(s(s(0))), s(s(s(s(s(s(0))))))).
   true
;  false.

?- fact(s(s(s(0))), s(s(s(s(s(0)))))).
;  false.

?- fact(s(s(s(0))), Y).
   Y = s(s(s(s(s(s(0))))))
;  false.

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

?- fact(s(s(X)), s(s(Y))).
   X = Y, Y = 0
;  X = s(0), Y = s(s(s(s(0))))
;  …
于 2021-08-20T14:48:10.380 回答