use*_*472 13 prolog factorial clpfd
在阅读SICP时,我遇到了逻辑编程第4.4章.然后我开始研究Prolog编程语言并尝试理解Prolog中的一些简单的任务.我发现Prolog似乎在数值计算方面遇到麻烦.
这是标准Prolog中的阶乘计算:
f(0, 1).
f(A, B) :- A > 0, C is A-1, f(C, D), B is A*D.
我发现的问题是我需要引入两个辅助变量(C和D),一个新的语法(is),并且问题是不可逆的(即,f(5,X)按预期工作,但f(X,120)不能).
天真的,我希望至少C is A-1, f(C, D)可以用上面的东西代替f(A-1,D),但即使这样也行不通.
我的问题是:为什么我需要在数值计算中做这些额外的"东西",而不是在其他查询中呢？
我明白(并且SICP非常清楚),一般来说,"做什么"的信息不足以回答"如何做"的问题.因此,(至少一些)数学问题的陈述性知识不足以真正解决这些问题.但这引出了下一个问题:Prolog中这些额外的"东西"如何帮助我将制定局限于那些"做什么"足以回答"如何做"的问题？
is/2是非常低级和有限的.正如您所正确观察到的那样,它不能在所有方向上使用,因此不是真正的关系.
对于可逆算术,请使用Prolog系统的约束求解器.
例如,SWI-Prolog的CLP(FD)手册包含以下定义n_factorial/2:
:- use_module(library(clpfd)).
n_factorial(0, 1).
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).
以下示例查询显示它可以在所有方向上使用:
?- n_factorial(47, F).
F = 258623241511168180642964355153611979969197632389120000000000 ;
false.
?- n_factorial(N, 1).
N = 0 ;
N = 1 ;
false.
?- n_factorial(N, 3).
false.
当然,这个定义仍然依赖于统一,因此您不能插入任意整数表达式.像2-2(-(2,2)在前缀表示法中)这样的术语并不适合0.但是,如果您将其重写为:
:- use_module(library(clpfd)).
n_factorial(N, F) :- N #= 0, F #= 1.
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).
示例查询及其结果:
?- n_factorial(2-2, -4+5).
true .
忘记变量并认为- A和B- 只是值的名称,可以放入该子句(X :- Y). 以使其可访问.考虑X = (2 + (3 * 4))代表数学表达式的数据结构.如果你要求prolog达到目标f(A-1, B),它将试图找到这样的原子f(A-1,B).或(f(A-1,B) :- Z), Z.统一到"成功"的规则.
is/2尝试将第一个参数与将第二个参数解释为表达式的结果统一起来.考虑eval/2作为变体is/2:
eval(0, 1-1). eval(0, 2-2). eval(1,2-1).
eval(Y, X-0):- eval(Y, X).
eval(Y, A+B):- eval(ValA, A), eval(ValB, B), eval(Y, ValA + ValB).
eval(4, 2*2).
eval(0, 0*_). eval(0, _*0).
eval(Y, X*1):- eval(Y, X).
eval(Y, 1*X):- eval(Y, X).
eval(Y, A*B):- eval(ValA, A), eval(ValB, B), eval(Y, ValA * ValB).
之所以f(X,120)不起作用的原因很简单,>/2只有当它的参数被绑定时(即你无法比较尚未定义的X东西).要解决此问题,您必须将该规则拆分为:
f(A,B) :- nonvar(A), A > 0, C is A-1, f(C, D), B is A*D.
f(A,B) :- nonvar(B), f_rev(A, B, 1, 1).
% f_rev/4 - only first argument is unbound.
f_rev(A, B, A, B). % solution
f_rev(A, B, N, C):- C < B, NextN is (N+1), NextC is (C*NextN), f_rev(A, B, NextN, NextC).
更新 :(已修复f_rev/4)
您可能对有限域求解器感兴趣.关于使用这些东西有一个问题.通过使用#>/2,#=/2您可以描述一些公式和限制,然后解决它们.但是这些谓词使用某些序言系统的特殊能力,这些能力允许将名称与某些属性相关联,这些属性可能有助于通过限制的交集来缩小可能值的集合.其他一些系统(通常是相同的)允许您重新排序处理目标序列("暂停").
也member(X,[1,2,3,4,5,6,7]), f(X, 120)可能是做什么的"其他查询"做同样的事情.
如果您对逻辑语言感兴趣,您也可以查看Curry语言(所有非纯函数都被"暂停",直到非定义的值统一为止).
:- use_module(library(clpfd)).
为了便于进行头对头比较(稍后),我们将这里的谓词称为n_fac/2:
n_fac(N_expr,F_expr) :-
N #= N_expr, % eval arith expr
F #= F_expr, % eval arith expr
n_facAux(N,F).
与之前的答案一样,n_fac/2承认使用算术表达式.
n_facAux(0,1). % 0! = 1
n_facAux(1,1). % 1! = 1
n_facAux(2,2). % 2! = 2
n_facAux(N,F) :-
N #> 2,
F #> N, % redundant constraint
% to help `n_fac(N,N)` terminate
n0_n_fac0_fac(3,N,6,F). % general case starts with "3! = 6"
帮助器谓词n_facAux/2将任何"真实"工作委托给n0_n_fac0_fac/4:
n0_n_fac0_fac(N ,N,F ,F).
n0_n_fac0_fac(N0,N,F0,F) :-
N0 #< N,
N1 #= N0+1, % count "up", not "down"
F1 #= F0*N1, % calc `1*2*...*N`, not `N*(N-1)*...*2*1`
F1 #=< F, % enforce redundant constraint
n0_n_fac0_fac(N1,N,F1,F).
让我们比较n_fac/2和n_factorial/2!
?- n_factorial(47,F).
F = 258623241511168180642964355153611979969197632389120000000000
; false.
?- n_fac(47,F).
F = 258623241511168180642964355153611979969197632389120000000000
; false.
?- n_factorial(N,1).
N = 0
; N = 1
; false.
?- n_fac(N,1).
N = 0
; N = 1
; false.
?- member(F,[3,1_000_000]), ( n_factorial(N,F) ; n_fac(N,F) ).
false. % both predicates agree
好!同样的,到目前为止......为什么不做一点暴力测试呢？
?- time((F1 #\= F2,n_factorial(N,F1),n_fac(N,F2))). % 57,739,784 inferences, 6.415 CPU in 7.112 seconds (90% CPU, 9001245 Lips) % Execution Aborted ?- time((F1 #\= F2,n_fac(N,F2),n_factorial(N,F1))). % 52,815,182 inferences, 5.942 CPU in 6.631 seconds (90% CPU, 8888423 Lips) % Execution Aborted ?- time((N1 #> 1,N2 #> 1,N1 #\= N2,n_fac(N1,F),n_factorial(N2,F))). % 99,463,654 inferences, 15.767 CPU in 16.575 seconds (95% CPU, 6308401 Lips) % Execution Aborted ?- time((N1 #> 1,N2 #> 1,N1 #\= N2,n_factorial(N2,F),n_fac(N1,F))). % 187,621,733 inferences, 17.192 CPU in 18.232 seconds (94% CPU, 10913552 Lips) % Execution Aborted
前几百个值没有差别N in 2..sup ...... 好!
继续:以下内容(在对此答案的评论中建议)？
?- n_factorial(N,N), false.
false.
?- n_fac(N,N), false.
false.
过得不错!相同的终止行为...更多？
?- N #< 5, n_factorial(N,_), false.
false.
?- N #< 5, n_fac(N,_), false.
false.
?- F in 10..100, n_factorial(_,F), false.
false.
?- F in 10..100, n_fac(_,F), false.
false.
好的!仍然相同的终止属性!让我们深入挖掘一下!以下怎么样？
?- F in inf..10, n_factorial(_,F), false. ... % Execution Aborted % does not terminate universally ?- F in inf..10, n_fac(_,F), false. false. % terminates universally
D'哦!第一个查询没有终止,第二个查询没有终止.真是个加速!:)
让我们做一些经验运行时测量!
?- member(Exp,[6,7,8,9]), F #= 10^Exp, time(n_factorial(N,F)) ; true. % 328,700 inferences, 0.043 CPU in 0.043 seconds (100% CPU, 7660054 Lips) % 1,027,296 inferences, 0.153 CPU in 0.153 seconds (100% CPU, 6735634 Lips) % 5,759,864 inferences, 1.967 CPU in 1.967 seconds (100% CPU, 2927658 Lips) % 22,795,694 inferences, 23.911 CPU in 23.908 seconds (100% CPU, 953351 Lips) true. ?- member(Exp,[6,7,8,9]), F #= 10^Exp, time(n_fac(N,F)) ; true. % 1,340 inferences, 0.000 CPU in 0.000 seconds ( 99% CPU, 3793262 Lips) % 1,479 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 6253673 Lips) % 1,618 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 5129994 Lips) % 1,757 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 5044792 Lips) true.
哇!多一点？
?- member(U,[10,100,1000]), time((N in 1..U,n_factorial(N,_),false)) ; true. % 34,511 inferences, 0.004 CPU in 0.004 seconds (100% CPU, 9591041 Lips) % 3,091,271 inferences, 0.322 CPU in 0.322 seconds (100% CPU, 9589264 Lips) % 305,413,871 inferences, 90.732 CPU in 90.721 seconds (100% CPU, 3366116 Lips) true. ?- member(U,[10,100,1000]), time((N in 1..U,n_fac(N,_),false)) ; true. % 3,729 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 2973653 Lips) % 36,369 inferences, 0.004 CPU in 0.004 seconds (100% CPU, 10309784 Lips) % 362,471 inferences, 0.036 CPU in 0.036 seconds (100% CPU, 9979610 Lips) true.
is/2!N,请考虑使用不同的方法.