Prolog是否使用Eager评估？

Question

因为Prolog使用按时间顺序回溯(来自Prolog维基百科页面)甚至在找到答案后(在这个例子中只能有一个解决方案),这是否可以证明Prolog使用急切的评估？

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.

Answer 1

总结下面与@WillNess的讨论,是的,Prolog是严格的.但是,Prolog的执行模型和语义与通常标记为严格或非严格的语言有很大不同.有关详细信息,请参阅下文.

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

f (g x) (h y)

在像ML严格的语言,有一个定义的计算顺序:g x将被评估,然后h y和f (g x) (h y)持续.在象Haskell一种语言,g x并且h y将只根据需要进行评估("非严格"比"懒"更准确).但在Prolog,

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

具有相同的含义,因为它没有使用函数表示法.查询将被分解成三个部分,g(X, A),h(Y, B),和f(A,B,C),这些成分可以被放置在任何顺序.评估策略是严格的,因为序列中较早出现的内容将在接下来的内容之前进行评估,但是在评估可以继续之前不要求变量被实例化为基础术语的意义上它是非严格的.统一是完美的内容,无需给出每个变量的值.我提出这个问题是因为你必须将另一种语言中复杂的嵌套表达式分解为Prolog中的几个表达式.

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

Answer 2

Prolog在给出问题的几个正确答案之后暂停,这与懒惰无关; 它是其用户交互协议的一部分.每个答案都是急切地计算出来的.

有时会只有一个答案,但Prolog事先并不知道,所以它等待我们;继续搜索,希望找到另一个解决方案.有时它能够提前推断它并且会立即停止,但有时只是停止.

更新:

Prolog本身没有评估.所有术语都未被评估,就像在Lisp中"引用"一样.

Prolog将按照书面形式展开您的谓词定义,并且非常乐意让您的数据结构充满未评估的未经实例化的漏洞,如果您的谓词定义如此.

在请求输出时,Haskell不需要用户所做的任何值.

同样,Prolog根据用户请求逐个生成解决方案.

Prolog甚至可以被看作比Haskell更懒惰,其中所有算术都是严格的,即立即,而在Prolog中你必须明确地请求算术评估is/2.

所以也许这个问题是不合适的.Prolog的运营模式太不同了.一个人没有"结果"或"功能"; 但从另一个角度来看,一切都是结果,谓词是"多"功能.