Prolog中的可逆数值计算

忘记变量,想想 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 )
您可能对有限域解算器感兴趣。有一个 question 关于使用这些东西。通过使用 #>/2 和 #=/2 您可以描述一些公式和限制,然后解决它们。但是这些谓词使用一些prolog系统的特殊功能,这些功能允许 名称 具有一些属性,这些属性有助于通过限制的交叉来缩小可能的值集。其他一些系统(通常相同)允许您重新排序处理目标序列(“挂起”)。
阿尔索 member(X,[1,2,3,4,5,6,7]), f(X, 120) 可能与您的“其他查询”所做的相同。

如果您对一般逻辑语言感兴趣,您也可以查看curry语言(所有非纯函数都是“挂起的”,直到非yed定义的值被统一为止)。

is/2 是非常低级和有限的。正如你正确地观察到的,它不能用于所有方向,因此不是一个真正的关系。

对于可逆算法,使用prolog系统的 约束解算器 .

例如,swi prolog的 CLP(FD) manual 包含以下定义 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 .

在这个答案中,我们使用 clpfd ,就像 this previous answer 做。

:- 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 … 好!

继续:下面怎么样(在评论中建议 this answer )?

?- 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

哦! 第一个查询不终止,第二个查询终止。 多快啊!:)

让我们做一些经验运行时测量!

?- 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 ,考虑使用 a different approach .
• 使用 慢性淋巴细胞性白血病 !

在查看Prolog时,您必须记住一些事情:

• 没有隐含的 返回值 调用谓词时。如果要从调用中获取值,则需要添加可用于“返回”值的额外参数,即 f/2 谓语。虽然更加冗长,但它的好处是很容易返回许多值。

• 这意味着在调用中自动“评估”参数实际上是毫无意义的,因为没有要返回的值,也没有完成。所以没有嵌套调用,在这方面prolog是平面的。所以当你打电话的时候 f(A-1, D) 第一个论点 F/2 是 结构 A-1 还是真的 -(A, 1) 作为 - 是中缀运算符。因此,如果您想从调用中获取值 foo 打电话给 bar 您必须显式地使用一个变量来执行以下操作:

  foo(..., X), bar(X, ...),

• 所以你需要一个特殊的谓词来强制算术运算, is/2 . 第二个论点是 结构 表示一个算术表达式,它解释、计算并将结果与其第一个参数(可以是变量或数值)统一。

• 原则上,你可以用大多数你做不到的东西来倒转。通常,它只是简单的谓词在可能的结构上工作,尽管在可能的情况下有一些非常有用的情况。 IS/2 不会倒着工作,如果倒着工作的话会很特别。

这就是为什么你需要额外的变量 C 和 D 无法替代 C is A-1, f(C, D) 通过 f(A-1,D) .

(是的,我知道您不在Prolog中进行调用,而是评估目标,但我们从功能角度出发)