Prolog 中的可逆数值计算 [英] Reversible numerical calculations in Prolog

问题描述

在阅读 SICP 时，我遇到了逻辑编程第 4.4 章.然后我开始研究 Prolog 编程语言并尝试理解 Prolog 中的一些简单任务.我发现 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.

这是标准 Prolog 中阶乘的计算:

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.

我发现的问题是我需要引入两个辅助变量(C 和 D)，一个新的语法(is)和问题是不可逆的(即，f(5,X) 按预期工作，但 f(X,120) 没有).

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

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

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?

我确实理解(SICP 对此非常清楚)一般而言，关于做什么"的信息不足以回答如何做"的问题.因此，(至少一些)数学问题中的陈述性知识不足以实际解决这些问题.但这引出了下一个问题:Prolog 中这些额外的东西"如何帮助我将公式限制在做什么"足以回答如何做"的那些问题上?

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

推荐答案

忘记变量，认为 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 的变体:

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

f(X,120) 不起作用的原因很简单，>/2 只有在它的参数被绑定时才起作用(即你不能比较尚未定义的东西，例如 X 和其他任何东西).要解决这个问题，您必须将该规则拆分为:

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

更新:(已修复f_rev/4)
您可能对有限域求解器感兴趣.有一个关于使用这些东西的问题.通过使用 #>/2 和 #=/2 你可以描述一些公式和限制然后解决它们.但是这些谓词使用一些 prolog 系统的特殊功能，允许将 name 与一些属性相关联，这可能有助于通过限制的交集来缩小可能值的集合.其他一些系统(通常相同)允许您重新排序处理目标的顺序(暂停").
member(X,[1,2,3,4,5,6,7]), f(X, 120) 可能与您的其他查询"所做的相同.

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.

如果您一般对逻辑语言感兴趣，您还可以查看 Curry 语言(所有非纯函数都暂停"，直到统一未定义的值).

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

这篇关于Prolog 中的可逆数值计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！