Prolog 是否使用 Eager 评估? [英] 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 这样的严格语言中，有一个定义的评估顺序:gx 将被评估，然后是 hy，然后是 f (gx) (hy) 最后.在像 Haskell 这样的语言中，g x 和 h y 只会根据需要进行评估(non-strict"比lazy"更准确).但在 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 是否使用 Eager 评估?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！