Prolog是否使用急切评估? [英] Does Prolog use Eager Evaluation?

问题描述

因为即使找到答案(在本示例中只有一个解决方案)，Prolog仍使用按时间顺序回溯(来自Prolog Wikipedia页面)，这是否证明Prolog使用急切的评估是正确的?

Because Prolog uses chronological backtracking(from the Prolog Wikipedia page) even after an answer is found(in this example where there can only be one solution), would this justify Prolog as using eager evaluation?

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

具有以下输出:

?- sibling(sally, erica).
true ;
false.

推荐答案

总结以下与@WillNess进行的讨论，是，Prolog严格..但是，Prolog的执行模型和语义与通常标记为严格或非严格的语言.有关更多信息，请参见下文.

To summarize the discussion with @WillNess below, yes, Prolog is strict. However, Prolog's execution model and semantics are substantially different from the languages that are usually labelled strict or non-strict. For more about this, see below.

我不确定该问题是否真正适用于Prolog，因为它确实没有其他语言所具有的隐式评估顺序.在像Haskell这样的语言中真正发挥作用的地方，您可能会有这样的表达:

I'm not sure the question really applies to Prolog, because it doesn't really have the kind of implicit evaluation ordering that other languages have. Where this really comes into play in a language like Haskell, you might have an expression like:

f (g x) (h y)

在像ML这样的严格语言中，有一个定义的评估顺序:先评估g x，然后先评估h y和f (g x) (h y).在类似Haskell的语言中，g x和h y将仅根据需要进行评估(非严格"比惰性"更准确).但是在Prolog中，

In a strict language like ML, there is a defined evaluation order: g x will be evaluated, then h y, and f (g x) (h y) last. In a language like Haskell, g x and h y will only be evaluated as required ("non-strict" is more accurate than "lazy"). But in Prolog,

f(g(X), h(Y))

没有相同的含义，因为它没有使用功能符号.该查询将分为三个部分，分别为g(X, A)，h(Y, B)和f(A,B,C)，这些组成部分可以按任何顺序放置.评估策略 是严格的，因为在序列 中先出现的将在下一个出现之前进行评估，但是在没有任何意义的情况下，它是非严格的要求在评估可以进行之前将变量实例化为基本术语.统一是完美的内容，无需为每个变量提供值即可完成.我之所以提出这一点，是因为您必须将另一种语言中的一个复杂的嵌套表达式分解为Prolog中的几个表达式.

does not have the same meaning, because it isn't using a function notation. The query would be broken down into three parts, g(X, A), h(Y, B), and f(A,B,C), and those constituents can be placed in any order. The evaluation strategy is strict in the sense that what comes earlier in a sequence will be evaluated before what comes next, but it is non-strict in the sense that there is no requirement that variables be instantiated to ground terms before evaluation can proceed. Unification is perfectly content to complete without having given you values for every variable. I am bringing this up because you have to break down a complex, nested expression in another language into several expressions in Prolog.

据我所知，回溯与它无关.我认为回溯到最近的选择点并从那里恢复不会排除一种非严格的评估方法，而Prolog正是严格的.

Backtracking has nothing to do with it, as far as I can tell. I don't think backtracking to the nearest choice point and resuming from there precludes a non-strict evaluation method, it just happens that Prolog's is strict.

这篇关于Prolog是否使用急切评估?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！