prolog - Prolog 中的选择点和重做

Question

提问后here关于何时在 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)可食用(apple)(然后在继续之前会失败)到下一个重做)，因为代码中还有一个带有仿函数edible的事实，这意味着创建了一个选择点？我发现了同一查询的带注释的跟踪 here 。我将发布其中的一个简短片段，因为它具有我认为此处缺少的附加 Redo:

有人能指出我在这种情况下预期的正确方向吗？

谢谢。

Answer 1

它与Indexing有关.

摘自 SWI-Prolog 术语表

Indexing is a technique used to quickly select candidate clauses of apredicate for a specific goal. In most Prolog systems, indexing isdone (only) on the first argument of the head. If this argument isinstantiated to an atom, integer, float or compound term with functor,hashing is used to quickly select all clauses where the first argumentmay unify with the first argument of the goal. SWI-Prolog supportsjust-in-time and multi-argument indexing. See section 2.18.

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

这样想，如果您要为 Prolog 编写逻辑引擎，然后用户希望它运行得更快，您将添加增强功能以​​使其更快，但这样做时，它的工作方式将不再是与概念模型相同。

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

来自Prolog Programming in Depth通过
迈克尔·A·卡温顿
唐纳德·努特
安德烈·韦利诺

秒。 4.14。索引页。 111

When a Prolog system executes a query, it doesn’t have to search the entire knowledge base for a matching clause. All Prologs use INDEXING (a hashing function or lookup table) to go directly to the right predicate. For example, with FAMILY.PL, a query to mother/2 does not search the clauses for father/2.

Most modern Prologs use indexing to go further than that. They index, not only on the predicate and arity, but also on the principal functor of the first argument. For example, if you have the knowledge base

a(b).  
a(c).  

d(e).
d(f).  

then the query ‘?- d(f).’ not only won’t search the clauses for a/1, it also won’t look at d(e). It goes straight to d(f), which is the only clause whose predicate, arity, and first argument match those in the query.

评论中的问题

Is there some kind of 'vanilla' or 'standard' Prolog environment for beginners where those kinds of enhancements are limited, in order to see more clearly how all the small details work and interact?

元解释器

来自:A Couple of Meta-interpreters in Prolog

An interpreter for a language similar or identical to its own implementation language is called meta-interpreter (MI).

了解 Prolog MI 是了解 Prolog 工作原理的绝佳方式，并且还可以了解非常有用的 MI，例如

Use of Prolog for developing a new programming language

以另一种语言实现

了解统一如何工作的另一种方法是使用统一算法和以另一种语言实现的回溯，然后使用它来增强代码输出您想要看到的信息。有一个miniProlog用 OCaml 编写，但我不怀疑很多人都了解 OCaml。

许多有关人工智能的更广泛的书籍都实现了它。

"Paradigms of Artificial Intelligence Programming"作者:Perter Norvig (Lisp)

"Artificial Intelligence Structures and Strategies for Complex Problem Solving"作者:George F Luger(伪代码)

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

对于统一理论，有经典

"Handbook of automated reasoning"第8章

Unification theory作者:弗兰兹·巴德和韦恩·斯奈德

推导树

参见:Prolog derivation trees, choices, and unification