Prolog 中的选择点和回溯。

Question

我曾在这里提问关于Prolog中何时使用新变量调用Redo，或者何时尝试使用相同变量。我认为我已经找到了答案。但是，在下面的代码片段中，我认为应该会调用另一个Redo，但事实并非如此。

我的知识库如下：

location(desk,office).
location(apple,kitchen).
location(flashlight,desk).
location('washing machine',cellar).
location(nani,'washing machine').
location(broccoli,kitchen).
location(crackers,kitchen).
location(computer,office).

edible(apple).
edible(crackers).

我的查询是

?-location(X,kitchen),edible(X).

具有以下跟踪：

   Call: (9) location(_5612, kitchen) ? creep
   Exit: (9) location(apple, kitchen) ? creep
   Call: (9) edible(apple) ? creep
   Exit: (9) edible(apple) ? creep
X = apple ;
   Redo: (9) location(_5612, kitchen) ? creep       <====
   Exit: (9) location(broccoli, kitchen) ? creep
   Call: (9) edible(broccoli) ? creep
   Fail: (9) edible(broccoli) ? creep
   Redo: (9) location(_5612, kitchen) ? creep
   Exit: (9) location(crackers, kitchen) ? creep
   Call: (9) edible(crackers) ? creep
   Exit: (9) edible(crackers) ? creep
X = crackers.

为什么第一个解决方案之后没有额外的Redo，类似于Redo: (9) edible(apple)（然后会失败，再继续下一个Redo），因为代码中还有另一个函数符号为edible的事实，这意味着会创建一个选择点？我在这里找到了相同查询的注释跟踪。我将发布其中的一个短片段，因为它具有我感觉在此处缺失的额外的Redo：

有人能指导我在这种情况下应该期望什么吗？

谢谢。

- milvala

---

感兴趣的内容：第一个参数索引 SO问答 - Guy Coder

有趣的内容：用户定义索引。该论文的开头概述了Prolog中索引是如何工作的。 - Guy Coder

有趣的内容：即时索引（JITI）实用工具 - Guy Coder

有趣的话题：干净的 vs. 默认的表示 - Guy Coder

有趣的内容：SLDNF Draw - SWI-Prolog软件包sldnfdraw。 - Guy Coder

Answer 1

这与索引有关。

来自SWI-Prolog术语词汇表

索引是一种技术，用于快速选择特定目标的谓词的候选子句。在大多数Prolog系统中，索引仅在头部的第一个参数上执行。如果此参数被实例化为原子、整数、浮点数或具有函数符号的复合项，则使用散列来快速选择所有子句，其中第一个参数可能与目标的第一个参数一致。SWI-Prolog支持即时和多参数索引。请参见第2.18节。

这是概念和实现分歧的情况之一。

可以这样想，如果您编写了Prolog的逻辑引擎，然后用户希望它运行得更快，您会添加使其更快的增强功能，但是在这样做的过程中，它的工作方式将不同于概念模型。

现在引擎已经有了增强功能，您应该确实有一个开关，在调试时关闭这些增强功能，以便看到实际发生的情况。

来自Prolog深度编程，作者
Michael A. Covington
Donald Nute
Andr´e Vellino

第4.14节 索引 第111页

当Prolog系统执行查询时，它不必在整个知识库中搜索匹配的子句。所有的Prolog都使用索引（哈希函数或查找表）直接转到正确的谓词。例如，对于FAMILY.PL，对mother/2的查询不会搜索father/2的子句。

大多数现代Prolog使用索引更进一步。他们不仅在谓词和arity上进行索引，还在第一个参数的主要函数上进行索引。例如，如果你有知识库

a(b).  
a(c).  

d(e).
d(f).  

那么查询‘?- d(f).’不仅不会搜索a/1的子句，也不会查找d(e)，它直接进入d(f)，这是唯一一个其谓词、arity和第一个参数与查询中匹配的子句。

评论中的问题

是否有一种适合初学者的“香草”或“标准”Prolog环境，其中这些增强功能受到限制，以便更清楚地了解所有小细节如何工作和相互作用？

元解释器

来自： Prolog中的一对元解释器 解释器对于类似于其自身实现语言的语言被称为元解释器（MI）。

学习Prolog MIs是理解Prolog工作原理和学习极其有用的MIs的绝佳方式，例如： 使用Prolog开发新编程语言

在另一种语言中实现

另一种了解统一的方式是使用实现了回溯的统一算法的其他语言，并使用它来增强输出您想要查看的信息的代码。有一个用OCaml编写的miniProlog，但我不认为很多人知道OCaml。

许多更广泛的人工智能书籍都实现了它。 《人工智能编程范例》，作者Perter Norvig（Lisp） 《人工智能结构和复杂问题求解策略》，作者George F Luger（伪代码）

在GitHub上可以找到Prolog实现。 smallProlog非常基础且用C完成。

至于统一理论，则有经典著作。

"自动推理手册" 第8章

统一理论，作者：Franz Baader 和 Wayne Snyder

推导树

参见：Prolog 推导树、选择和统一

- Guy Coder

Answer 2

你可以通过Byrd的盒子模型来可视化重做，在这个模型中，一个谓词调用P有4个端口：

            +-------+
--- call -->|       |--- exit -->
            |   P   | 
<-- fail ---|       |<-- redo ---
            +-------+

通常情况下，如果每个出口都没有剪枝，就需要重新执行。而对于每个调用，在 SWI-Prolog（和其他一些 Prolog 系统？）中最终都会失败：

• 当 P 确定性成功时，redo 被抑制
• 当 P 确定性成功时，fail 被抑制

确定性成功通常是指索引花束中的最后一个子句，并且在非调试顶层中看到分号提示被抑制。另请参见此处：

明确 Prolog 目标的“确定性成功”

在 Jekejeke Prolog 中，这种“优化”尚未实现调试器。它也具有确定性成功，但当调试器开启时不具备此功能，因此存在两个不同的跟踪：

SWI-Prolog 跟踪：

Welcome to SWI-Prolog (threaded, 64 bits, version 7.5.8)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- location(X,kitchen),edible(X).
   Call: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(apple, kitchen) ? creep
   Call: (9) edible(apple) ? creep
   Exit: (9) edible(apple) ? creep
X = apple 
   Redo: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(broccoli, kitchen) ? creep
   Call: (9) edible(broccoli) ? creep
   Fail: (9) edible(broccoli) ? creep
   Redo: (9) location(_3980, kitchen) ? creep
   Exit: (9) location(crackers, kitchen) ? creep
   Call: (9) edible(crackers) ? creep
   Exit: (9) edible(crackers) ? creep
X = crackers.

Jekejeke Prolog跟踪：

Jekejeke Prolog 2, Development Environment 1.2.2
(c) 1985-2017, XLOG Technologies GmbH, Switzerland

?- location(X,kitchen),edible(X).
    0 Call location(X, kitchen) ? 
    0 Exit location(apple, kitchen) ? 
    0 Call edible(apple) ? 
    0 Exit edible(apple) ? 
X = apple ;
    0 Redo edible(apple) ? 
    0 Fail edible(apple) ? 
    0 Redo location(apple, kitchen) ? 
    0 Exit location(broccoli, kitchen) ? 
    0 Call edible(broccoli) ? 
    0 Fail edible(broccoli) ? 
    0 Redo location(broccoli, kitchen) ? 
    0 Exit location(crackers, kitchen) ? 
    0 Call edible(crackers) ? 
    0 Exit edible(crackers) ? 
X = crackers ;
    0 Redo edible(crackers) ? 
    0 Fail edible(crackers) ? 
    0 Redo location(crackers, kitchen) ? 
    0 Fail location(X, kitchen) ? 
No

- user502187