Prolog中的可逆数值计算

Question

在阅读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)取代，但即使这样也不起作用。

我的问题是:为什么我需要在数值计算中做额外的“事情”，而不是在其他查询中？

我确实理解(国际预防犯罪中心对此相当清楚)，一般来说，关于“该做什么”的信息不足以回答“如何做”的问题。因此，(至少有些)数学题中的陈述性知识不足以解决这些问题。但这引出了下一个问题: Prolog中的额外“内容”如何帮助我将公式限制在那些“做什么”足以回答“如何做”的问题上？

Answer 1

忘记变量，并认为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，您可以描述一些公式和限制，然后解决它们。但是这些谓词使用了一些prolog系统的特殊功能，允许将名称与某些属性相关联，这可能有助于通过约束的交集来缩小可能的值集。其他一些系统(通常相同)允许您重新排序处理目标的顺序(“挂起”)。

而且，member(X,[1,2,3,4,5,6,7]), f(X, 120)可能在做“其他查询”所做的同样的事情。

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

Answer 2

is/2是非常低水平和有限的.正如你正确地观察到的，它不能在所有的方向上使用，因此不是一个真正的关系。

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

例如，SWI的中电(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 .

Answer 3

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

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

这就是为什么您需要额外的变量C和D，而不能用f(A-1,D)代替C is A-1, f(C, D)。

(是的，我知道你不会在Prolog中打电话，而是评估目标，但我们从功能角度出发)