递归另外在Prolog中

Question

知识库

add(0,Y,Y). // clause 1 
add(succ(X),Y,succ(Z)) :- add(X,Y,Z). // clause 2 

查询

add(succ(succ(succ(0))), succ(succ(0)), R) 

痕量

Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R) 
Call: (7) add(succ(succ(0)), succ(succ(0)), _G648) 
Call: (8) add(succ(0), succ(succ(0)), _G650) 
Call: (9) add(0, succ(succ(0)), _G652) 
Exit: (9) add(0, succ(succ(0)), succ(succ(0))) 
Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0)))) 
Exit: (7) add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0))))) 
Exit: (6) add(succ(succ(succ(0))), succ(succ(0)), succ(succ(succ(succ(succ(0)))))) 

我的问题

• 我看到如何在第递归调用2条的最外SUCC（） 在每个呼叫对参数1.
• 我看看它是如何在增加了一个外SUCC（）以3参数每次通话。
• 我看到当第一个参数作为这些递归调用 的结果达到0.此时，我看到1st子句如何将第二个参数 复制到第三个参数。

这是我困惑的地方。

1. 一旦执行第1条款，并在第2条自动 得到执行为好，然后加入SUCC（）第一个参数？

2. 另外，程序如何终止，为什么它不会仅仅保持 无限地为第一个和第三个参数添加succ（）？

从LearnPrologNow.com解释（我不知道）

让我们通过使用方式的Prolog来处理这个查询走一步看一步。下面给出了查询的跟踪和搜索树的 。

第一个参数不是0，这意味着只能使用add/3的第二个子句 。这导致递归调用add/3。将 最外面的succ函数从原始查询 的第一个参数中删除，结果将成为递归查询的第一个参数。第二个参数不变地传递给 递归查询，递归查询的第三个参数是一个 变量，下面给出的跟踪中的内部变量_G648。注意 _G648尚未实例化。但是它与R （我们用作原始 查询中的第三个参数的变量）共享值，因为当查询是 与第二个子句的头部统一时，R被实例化为succ（_G648）。但这意味着R是 不再是一个完全没有实际意义的变量。现在它是一个复杂的 术语，它有一个（未被证实的）变量作为它的参数。

接下来的两个步骤基本相同。随着每一步的第一个参数变成一个succ小一层;下面给出的跟踪和 搜索树都很好地显示了这一点。与此同时，在每一步都会向R添加一个仿函数，但始终将最内层的变量 变为无实际意义。在第一次递归调用R之后是 succ（_G648）。在第二次递归调用之后，_G648被succ（_G650）实例化为 ，所以R是succ（succ（_G650）。在第三次递归调用之后，_G650被succ（_G652）实例化并且因此 变为succ（succ （SUCC（_G652）））。搜索树显示这一步 一步实例。

在这个阶段，所有SUCC函子已经被扒掉第一 参数，我们可以应用基本条款。第三个参数是 等同于第二个参数，因此复数项R中的'hole'（未示例的 变量）最终被填充，并且我们通过。

Answer 1

让我们从术语开始。

这些都是条款，为你正确地指出：

 
add(0, Y, Y). 
add(succ(X), Y, succ(Z)) :- add(X, Y, Z). 

让我们先查看这个程序声明，只是为了确保我们正确理解其含义：

1. 0加Y是Y。这是有道理的。
2. 如果这是真的，X加Y是Z然后这是事实的X加  Y的接班人是  Z的继任者。

这是一个很好的方式来阅读这个定义，因为它是足够一般的涵盖各种使用模式。例如，让我们先从最一般的查询，所有的参数都是新鲜的变量：

 
?- add(X, Y, Z). 
X = 0, 
Y = Z ; 
X = succ(0), 
Z = succ(Y) ; 
X = succ(succ(0)), 
Z = succ(succ(Y)) . 

在这种情况下，有什么可“带”，因为没有一个参数被实例化。然而，Prolog仍然报告非常明智的答案，这些答案明确了关系拥有的条款。

在你的情况，你正在考虑不同的查询（不是“谓词定义”！），即查询：

 
?- add(succ(succ(succ(0))), succ(succ(0)), R). 
R = succ(succ(succ(succ(succ(0))))). 

这是一个简单的多特例上面显示的一般查询，以及程序的自然后果。

我们还可以去另一个方向和概括此查询。例如，这是一个概括，因为我们通过逻辑变量更换一个地说法：

 
?- add(succ(succ(succ(0))), B, R). 
R = succ(succ(succ(B))). 

如果您按照您发布的解释，你将使你的生活非常困难，到达在逻辑程序非常有限的观点：实际上，你只能够跟踪模式中，你可以使用谓词的一个小片段，因而程序读取属于很短的你实际上描述什么。

如果您确实坚持程序性阅读，请首先以开头。例如，让我们考虑：

 
?- add(succ(0), succ(0), R). 

要 “通过步” 程序上，我们可以进行如下操作：

1. 做的第一条比赛？ （请注意，“匹配”是已经阅读有限：序言实际上应用统一和程序化的解读，使我们远离这个普遍性。）
2. 答：没有，因为s(_)不0统一。所以只有第二个条款适用。
3. 第二子句仅保持如果其主体保持，并且在这种情况下，如果add(0, succ(0), Z)成立。而这个持有（通过应用第一条）如果Z是succ(0)和R是succ(Z)。
4. 因此，一个答案是R = succ(succ(0)).。这个答案是据报道。
5. 是否有其他解决方案？这些仅在回溯时报告。
6. 答：没有，有没有其他的解决方案，因为没有进一步的这条规则。

我把它作为一个练习，将这种艰辛的方法应用到本书中显示的更复杂的查询中。这样做很简单，但会越来越多地引导您远离逻辑程序的最有价值的方面，它们的概括性和优雅的声明性表达式。

你就终止问题是微妙和深刻见解。请注意，我们必须区分存在问题和通用在Prolog中终止。

例如，再上面显示的最一般的查询考虑：它得到答案，但它不会终止。对于要报告的答案，找到答案替换就足够了，它使查询  为真。你的例子就是这种情况。替代方案，如果有可能仍然存在，则尝试并报告回溯。

你总是可以尝试以下方法来测试你的查询终止：只需追加false/0，例如：

 
?- add(X, Y, Z), false. 
nontermination 

这可让您专注于终端性能，而无需关心具体的答案。也

注意add/3是关系一个可怕的名字：一个必要总是意味着方向，但其实这是更一般，也可以使用，如果没有的参数甚至实例！一个好的谓词名称应该反映这种一般性。