Prolog 中的可逆数值计算

发布于 2024-09-02 21:52:03 字数 677 浏览 6 评论 0原文

在阅读 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）、一种新语法（C >is）并且问题是不可逆的（即，f(5,X) 按预期工作，但 f(X,120) 确实如此不是）。

天真地，我期望至少上面的 C is A-1, f(C, D) 可以替换为 f(A-1,D)，但是即使那样也行不通。

我的问题是：为什么我需要在数值计算中而不是在其他查询中执行这些额外的“操作”？

我确实理解（SICP 对此非常清楚），一般来说，有关“做什么”的信息不足以回答“如何做”的问题。因此（至少某些）数学问题中的陈述性知识不足以实际解决这些问题。但这引出了下一个问题：Prolog 中的这些额外“东西”如何帮助我将公式限制为仅解决“做什么”足以回答“如何做”的问题？

原文

While reading SICP I came across logic programming chapter 4.4. Then I started looking into the Prolog programming language and tried to understand some simple assignments in Prolog. I found that Prolog seems to have troubles with numerical calculations.

Here is the computation of a factorial in standard Prolog:

f(0, 1).
f(A, B) :- A > 0, C is A-1, f(C, D), B is A*D.

The issues I find is that I need to introduce two auxiliary variables (C and D), a new syntax (is) and that the problem is non-reversible (i.e., f(5,X) works as expected, but f(X,120) does not).

Naively, I expect that at the very least C is A-1, f(C, D) above may be replaced by f(A-1,D), but even that does not work.

My question is: Why do I need to do this extra "stuff" in numerical calculations but not in other queries?

I do understand (and SICP is quite clear about it) that in general information on "what to do" is insufficient to answer the question of "how to do it". So the declarative knowledge in (at least some) math problems is insufficient to actually solve these problems. But that begs the next question: How does this extra "stuff" in Prolog help me to restrict the formulation to just those problems where "what to do" is sufficient to answer "how to do it"?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

<逆流佳人身旁 2024-09-09 21:52:03

is/2 是非常低级且有限的。正如您所观察到的，它不能用于所有方向，因此不是真正的关系。

对于可逆算术，请使用 Prolog 系统的约束求解器。

例如，SWI-Prolog 的CLP(FD) 手册包含以下<的定义code>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 .

is/2 is very low-level and limited. As you correctly observe, it cannot be used in all directions and is therefore not a true relation.

For reversible arithmetic, use your Prolog system's constraint solvers.

For example, SWI-Prolog's CLP(FD) manual contains the following definition of 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).

The following example queries show that it can be used in all directions:

?- n_factorial(47, F).
F = 258623241511168180642964355153611979969197632389120000000000 ;
false.

?- n_factorial(N, 1).
N = 0 ;
N = 1 ;
false.

?- n_factorial(N, 3).
false.

Of course, this definition still relies on unification, and you can therefore not plug in arbitrary integer expressions. A term like 2-2 (which is -(2,2) in prefix notation) does not unfiy with 0. But you can easily allow this if you rewrite this to:

:- 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).

Example query and its result:

?- n_factorial(2-2, -4+5).
true .

回复收藏 0 原文

笔芯 2024-09-09 21:52:03

忘记变量，并认为 A 和 B - 只是可以放入该子句 (X :- Y) 中的值的名称。 使其可达。以表示数学表达式的数据结构的方式思考X = (2 + (3 * 4))。如果你要求 prolog 达到目标 f(A-1, B) 它会尝试找到这样的原子 f(A-1,B). 或规则 < code>(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 语言（其中所有非纯函数都“暂停”，直到统一未定义的值）。

Forget about variables and think that A and B - is just a name for value which can be placed into that clause (X :- Y). to make it reachable. Think about X = (2 + (3 * 4)) in the way of data structures which represent mathematical expression. If you will ask prolog to reach goal f(A-1, B) it will try to find such atom f(A-1,B). or a rule (f(A-1,B) :- Z), Z. which will be unified to "success".
is/2 tries to unify first argument with result of interpreting second argument as an expression. Consider eval/2 as variant of 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).

The reason why f(X,120) doesn't work is simple >/2 works only when its arguments is bound (i.e. you can't compare something not yet defined like X with anything else). To fix that you have to split that rule into:

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).

Update: (fixed f_rev/4)
You may be interested in finite-domain solver. There was a question about using such things. By using #>/2 and #=/2 you can describe some formula and restrictions and then resolve them. But these predicates uses special abilities of some prolog systems which allows to associate name with some attributes which may help to narrow set of possible values by intersection of restriction. Some other systems (usually the same) allows you to reorder sequence of processing goals ("suspend").
Also member(X,[1,2,3,4,5,6,7]), f(X, 120) is probably doing the same thing what your "other queries" do.

If you are interested in logical languages in general you may also look at Curry language (there all non-pure functions is "suspended" until not-yed-defined value is unified).

回复收藏 0 原文

梦幻的味道 2024-09-09 21:52:03

在此答案中，我们使用 clpfd，就像之前的答案做到了。

:- 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'oh！ 第一个查询不会终止，第二个查询则会终止。
多么加速啊！ :)

让我们做一些经验性的运行时间测量！

?- 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 的阶乘，请考虑使用另一种方法。
使用clpfd！

In this answer we use clpfd, just like this previous answer did.

:- use_module(library(clpfd)).

For easy head-to-head comparison (later on), we call the predicate presented here 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).

Like in this previous answer, n_fac/2 admits the use of arithmetic expressions.

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"

The helper predicate n_facAux/2 delegates any "real" work to 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).

Let's compare n_fac/2 and 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

OK! Identical, so far... Why not do a little brute-force testing?

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

No differences for the first few hundred values of N in 2..sup... Good!

Moving on: How about the following (suggested in a comment to this answer)?

?- n_factorial(N,N), false.
false.
?- n_fac(N,N), false.
false.

Doing fine! Identical termination behaviour... More?

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

Alright! Still identical termination properties! Let's dig a little deeper! How about the following?

?- 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'oh! The first query does not terminate, the second does.
What a speedup! :)

Let's do some empirical runtime measurements!

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

Wow! Some more?

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

The bottom line?

The code presented in this answer is as low-level as you should go: Forget is/2!
Redundant constraints can and do pay off.
The order of arithmetic operations (counting "up" vs "down") can make quite a difference, too.
If you want to calculate the factorial of some "large" N, consider using a different approach.
Use clpfd!

回复收藏 0 原文

一身软味 2024-09-09 21:52:03

在查看 Prolog 时，您必须记住一些事情：

调用谓词时没有隐式返回值。如果您想从调用中获取值，则需要添加可用于“返回”值的额外参数，即 f/2 谓词中的第二个参数。虽然更详细，但它确实具有易于返回许多值的优点。
这意味着在调用中自动“评估”参数实际上毫无意义，因为没有可返回的值并且还没有完成。所以不存在嵌套调用，在这方面Prolog是平坦的。因此，当您调用 f(A-1, D) 时，f/2 的第一个参数是结构 A-1< /code>，或者实际上是 -(A, 1)，因为 - 是一个中缀运算符。因此，如果您想将从对 foo 的调用中获取值到对 bar 的调用中，您必须显式地使用变量来执行此操作，如下所示：
foo(..., X), bar(X, ...),
所以你需要一个特殊的谓词来强制算术计算，is/2。它的第二个参数是一个结构，表示一个算术表达式，它解释、计算结果并将结果与其第一个参数统一，第一个参数可以是变量或数值。
虽然原则上你可以向后运行大多数你不能做的事情。通常，它只是对可能的结构起作用的简单谓词，尽管有一些非常有用的情况是可能的。 is/2 不能向后运行，如果可以的话那就很例外了。