理解Prolog中的递归规则

Question

我正在开始使用 Prolog，感谢“七周七种语言”，并且在理解 Prolog 如何处理递归方面遇到了一些困难。 给出以下代码：

sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum,Tail), Total is Head + Sum.

% executed in the Prolog interpreter:
sum(X, [1,2,3])
X = 6

我明白这段代码在做什么，但我对 Prolog 如何解析 

sum

的递归调用有点困惑。主要是，我很奇怪，

sum

内没有明确的“返回”。我的理解是会发生这样的事情：

A。解释器尝试通过调用 sum:

来统一规则 sum(X, [1,2,3])

0 Sum(X, [1, 2, 3])
1 Sum(Y, [2,3] 
2 Sum(Z, [3])
3 Sum(0, []) % our recursive base

B.一旦我们达到基本事实，它就会爬回递归“堆栈”：

3 Sum(0, []), Total = 0 % we start at our base fact
2 Sum(1, [3]), Total = 3
1 Sum(2, [2, 3]), Total = 5 
0 Sum(X, [1, 2, 3]) Total = 6 % sweet, sweet unification

我对其运作方式的理解是否正确？或者有没有更好的方法让我的命令式思维思考/表达上面发生的事情？

Answer 1

要理解 Prolog 执行，首先要做的就是认识到 Prolog 就像一个弱定理证明器。它会尽力使您的查询成立。所以，当你输入查询

?- sum(X, [1,2,3]).

时，Prolog会尽力使其成立。在这种情况下，正如我们将看到的，它将需要将

X

绑定到

6

，让我们看看如何操作。您给 Prolog 证明

sum(X, [1, 2, 3])

为真的唯一元素是

sum(0, []).

和

sum(Total, [Head|Tail]) :- sum(Sum,Tail), Total is Head + Sum.

显然，Prolog 对第一个子句无能为力，因为它无法统一 

[]

和

[1, 2, 3]

。因此它尝试使用第二个子句来证明您的查询。然后发生的事情是它试图依次证明

sum(Sum,Tail)

和

Total is Head + Sum

。证明这两个选项中的第一个将引发递归调用，最终将使用

Tail

=

[]

进行调用。此时，Prolog 将使用您提供的第一个子句并推断出

Sum

因此是

0

。现在，它将具有在递归的最后一步证明第二部分 (

Total is Head + Sum

) 的元素。然后递归会返回到您猜测的初始谓词。

Answer 2

sum/2

的谓词中空列表之和的独特方式来发挥的。

您可以通过在口译员处执行目标

sum(X,[ ])

来说服自己这一点。