Prolog 中的递归函数是如何工作的？

Question

我正在阅读 prolog 中的递归函数，returns 列表中所有元素的总和如下：

sum([ ], 0).
sum( [Elem | Tail], S):- sum(Tail, S1),
                         S is S1 + Elem.

有两个问题我不明白：

1：在“:-”的左侧，我们有目标。这意味着所有的计算都将在“:-”的右侧完成，然后我们可以将 Goal 作为普通函数使用。意思是我们给我们的参数和变量，结果会放在上面，右边负责计算。

但是这段代码中的Goal，本身就是在计算Head和Tail。我的意思是在我看来代码应该是这样的（但是它不起作用！）：

sum(Tail, S1):-sum( [Elem | Tail], S),........

因为目标应该给出参数，右边负责计算

2：我无法理解这段代码是如何一步步运行的。谁能给我一个非常简单的例子，比如它如何计算 [1,2,3] 的总和？

Answer 1

你对执行过程中发生的事情的猜测很奇怪。根本不涉及任何功能。

对于目标sum([1,2,3], X)的评估，选择了第二个子句，因为[1,2,3]（目标的第一个参数）和[]（在头部第一条）。

匹配实例化 Elem=1、Tail=[2,3] 和 S = X。然后评估目标 sum([2,3], S1)，并成功（递归后），返回替换 S1=5。然后S=5+1绑定S到6.

Answer 2

序言的一个重要部分是匹配（更一般地说，统一）。当 Prolog 运行-time 遇到像 sum(X,Y) 这样的目标时，它会尝试将该术语与求和规则的左侧（头部）匹配，按照它们出现的顺序。如果第一条规则失败，则系统将移至第二条规则，依此类推。

在这种情况下，只有当 X 是空列表时，第一个头才会匹配。如果不为空，匹配失败，尝试下一个头。只要 X 是任何非空列表，这就会成功。它不仅会成功，而且会将列表的第一个元素绑定到 Elem ，列表的其余部分（可能为空）绑定到 Tail。由于此规则头部的第二个参数是一个变量，因此它将绑定到任何 Y。

让我们来看一些例子：

sum([],X)?

第一个头部匹配，将 X 绑定到 0。

sum([1],X)?

第一个头不匹配，因为 [1] 不匹配 []。第二个是 Elem <- 1, Tail<-[]。因此，我们可以继续规则的右侧：

sum(Tail,S1), S is S1 + Elem

由于 Tail<-[] ，目标 sum(Tail,S1) 将产生绑定 S1<-0（见上文）。所以当 Elem<-1 且 S1<-0 时，S1+Elem = 1.

等等。希望这里有足够的内容供您完成剩下的工作。

Answer 3

在:-的左边你有一个规则的头像；在右侧，您有规则的主体。当缺少 :- 边和正文时，规则变为 fact.

说只在正文中进行计算是不正确的，因为Prolog的决策过程对规则的两边都起作用。规则头起重要作用的概念是统一，语言决定哪些子句适用于查询，并对规则中的变量进行检查和临时赋值的过程规则指向部分查询（"unifies"）。

例如，当你查询sum([1,2,3], X)时，Prolog检查了两个sum子句，并决定查询只与第二个子句统一，因为[]不能与[统一=15=].

现在它需要统一 [1,2,3] 和 [Elem | Tail]，方法是进行临时分配，只要我们在规则主体中，该分配就会持续：Elem=1，并且 Tail = [2,3]。此时它尝试再次求解 sum，将 [2,3] 作为第一个参数传递。第一条规则不匹配，所以又临时分配了 Elem=2 和 Tail=[3]。在第三级递归中，我们到达了赋值 Elem=3 和 Tail=[]。这是我们遇到第一个规则时，产生了 S1=0 的赋值。第三级调用添加3；第二级添加 2。第一级加1，returns，X设置为6。

Prolog 中的递归函数是如何工作的？

How do recursive functions work in Prolog?

prolog