如何在所有参数模式的后继算术中实现阶乘序列? [英] How to implement the factorial sequence in successor arithmetics for all argument modes?
问题描述
下面的 Prolog 程序定义了一个谓词 fact/2
,用于在后续算术中计算整数的阶乘:
事实(0,s(0)).事实(s(X),Y):-事实(X,Z),产品(s(X),Z,Y).产品(0,_,0).产品(s(U),V,W):-总和(V,X,W),产品(V,U,X).总和(0,Y,Y).总和(s(X),Y,s(Z)):-总和(X,Y,Z).
它适用于这种参数模式下的查询:
?- 事实(s(0), s(0)).真的;错误的.
它也适用于这种参数模式下的查询:
?- 事实(s(0), Y).Y = s(0);错误的.
它也适用于这种参数模式下的查询:
?- 事实(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))))));…
但是在这种参数模式下查询会耗尽资源:
?- 事实(X, s(0)).X = 0;X = s(0);超出堆栈限制 (0.2Gb)堆栈大小:本地:4Kb,全局:0.2Gb,跟踪:0Kb筹码深度:2,503,730,最后跟注:100%,选择点数:13在:[2,503,730] sum('<garbage_collected>',_1328,_1330)[38] prod('<garbage_collected>', <compound s/1>, '<garbage_collected>')[33] 事实('<garbage_collected>',<compound s/1>)[32] 事实('<garbage_collected>',<compound s/1>)[31] swish_trace:swish_call('<garbage_collected>')
如何在所有参数模式的后继算术中实现阶乘序列?
第一个问题一定是为什么?failure-slice 有助于理解问题:
<上一页>仅当给出第一个参数时,此片段才会终止.如果不是,则无法防止不终止,因为 Y
在可见部分不受任何限制.所以我们必须改变那部分.一个简单的方法是观察第二个参数不断增加.其实增长的挺快的,不过为了终止,一个就够了:
fact2(N, F) :-事实2(N,F,F).事实2(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).% 最佳.找到循环:[fact2(s(_),s(_))].NTI 耗时 0ms,73i,73i
但是,有一个警告......
如果只知道
F
,程序现在将需要与|F
| 成比例的时间空间!那不是感叹号,而是阶乘符号……
The following Prolog program defines a predicate fact/2
for computing the factorial of an integer in successor arithmetics:
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).
It works with queries in this argument mode:
?- fact(s(0), s(0)).
true
; false.
It also works with queries in this argument mode:
?- fact(s(0), Y).
Y = s(0)
; false.
It also works with queries in this argument mode:
?- 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))))))
; …
But it exhausts resources with queries in this argument mode:
?- 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>')
How to implement the factorial sequence in successor arithmetics for all argument modes?
The first question must be why? A failure-slice helps to understand the problem:
fact(0, s(0)) :- false. fact(s(X), Y) :- fact(X, Z), false,prod(s(X), Z, Y).
This fragment alone terminates only if the first argument is given. If it is not, then there is no way to prevent non-termination, as Y
is not restricted in any way in the visible part. So we have to change that part. A simple way is to observe that the second argument continually increases. In fact it grows quite fast, but for the sake of termination, one is enough:
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).
And, should I add, this can be even proved.
fact2(A,B)terminates_if b(A);b(B).
% optimal. loops found: [fact2(s(_),s(_))]. NTI took 0ms,73i,73i
But, there is a caveat...
If only
F
is known, the program will now require temporally space proprotional to |F
|! That is not an exclamation point but a factorial sign...
这篇关于如何在所有参数模式的后继算术中实现阶乘序列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!