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)).如果您要求序言达到目标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，您可以描述一些公式和限制，然后加以解决.但是这些谓词使用某些序言系统的特殊功能，该功能允许将 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屋！