prolog回溯/搜索总是遵循相同的方案吗？

Question

下面的prolog代码为句子(句子=对象+动词+主题)建立了一个非常简单的语法，并提供了一些小词汇表。

% Example 05 - Generating Sentences

% subjects, verbs and objects
subject(john). 
subject(jane).
verb(eats). 
verb(washes).
object(apples). 
object(spinach).

% sentence = subject + verb + object
sentence(X,Y,Z) :- subject(X),  verb(Y),  object(Z). 

% sentence as a list
sentence(S) :- S=[X, Y, Z],  subject(X),  verb(Y),  object(Z).

当被要求生成有效句子时，swish.swi(特别是swish.swi-prolog.org)按照以下顺序生成它们：

?- sentence(S).

S = [john, eats, apples]
S = [john, eats, spinach]
S = [john, washes, apples]
S = [john, washes, spinach]
S = [jane, eats, apples]
S = [jane, eats, spinach]
S = [jane, washes, apples]
S = [jane, washes, spinach]

问题

以上所示，prolog总是从连接查询的右向左返回。对所有的程序都是这样吗？是规范的一部分吗？如果没有，它是否足够普遍，值得信赖？

Notes

为了清晰，从右边回溯，我的意思是Z是不束缚和反弹，找到所有的可能性，给出X和Y的第一场比赛。然后在这些都已经用尽之后，Y是解除束缚和反弹，对于每一个Y，不同的Z被测试。最后，X是无界的，然后反弹到新的值，对于每一个X，Y和Z的组合再次生成。

Answer 1

简短回答:是的。Prolog总是使用同样定义良好的方案，也称为时间回溯和(一个特定实例)的SLD-分辨率。

但这需要详细说明。

Prolog系统坚持这一策略，因为它是相当有效的实现，并在许多情况下直接导致预期的结果。对于那些Prolog工作良好的情况，在许多任务中，它与命令式编程语言相当有竞争力。有些系统甚至转换成机器代码，其中最突出的是sicstus prolog的实时编译器.

然而，正如您可能已经遇到过的那样，有些情况下，这种策略会导致不理想的低效率甚至不终止，而另一种策略则会产生一个答案。那么，在这种情况下该怎么办呢？

首先，可以重新定义问题的精确编码。以你的语法为例，我们甚至有一种特定的形式主义，叫做肯定从句语法，dcg。它非常紧凑，在许多情况下都能高效地解析和生成。这种洞察力(以及精确的编码)在相当长的一段时间内都不那么明显。Prolog诞生的确切时刻(确切地说是) 50年前正是在这一点上被理解的。在示例中，一个列表中只有3个标记，但大多数情况下，这个数字可能会有所不同。它是DCG形式主义的光辉之处，仍然可以用来分析和生成句子。在您的示例中，假设您还希望包含长度不受限制的主题，如[the,boy]、[the,nice,boy]、[the,nice,and,handsome,boy]、.

有许多这样的编码技术需要学习。

Prolog策略进一步改进的另一种方法是提供更灵活的选择策略，包括内置的freeze/2、when/2和类似的协同方法。虽然这种扩展已经存在了相当长的时间，但它们很难使用。尤其是因为理解不终止变得更加复杂。

更成功的扩展是约束(约束规划)，最突出的是clpz/clpfd，它主要用于组合问题。虽然时间回溯仍然存在，但它只是作为最后手段使用labeling/2来确保解决方案的正确性，或者当没有更好的方法来表达实际问题时。

最后，您可能需要以更基本的方式重新考虑Prolog的策略。这一切都是有可能的，通过元解释。从某种意义上说，这是一个全新的实现，但它通常可以使用很多Prolog的基础设施，从而使这样的元口译员与其他编程语言相比相当紧凑。而且，它不仅可用于实现其他策略，甚至还可用于原型和实现其他编程语言。最突出的例子是二郎，它最初是作为Prolog元解释器存在的，它的语法仍然很原始。

Prolog作为一种编程语言，还包含许多不适合这种纯视图的特性，比如put_char/1之类的内置功能，这显然是元解释中的一个障碍。但是，在许多这样的情况下，可以通过限制它们仅用于特定的模式并产生实例化错误来缓解这种情况。想想(基于非约束的)算法，如果不能立即确定结果，则会产生错误，但在与实例化参数(如

?-         X > 0, X = -1.
   error(instantiation_error,(is)/2).
?- X = -1, X > 0.
   false.
?- X = 2, X > 0.
   X = 2.

最后，一个关于不终止的话。不终止通常被视为Prolog的一个基本弱点。但对此还有另一种看法。另外，其他更老的系统或引擎也会受到离家出走的影响。它们还在使用中。在编程语言的情况下，逃逸是其通用性的基本结果。而且，非终止查询仍然比不正确但终止的查询更可取。