Prolog 延迟评估:后进先出或先进先出唤醒



许多Prolog系统都有一个freeze/2谓词,一个谓词它可能应该有名字geler/2因为它是甚至在Prolog-II之前发明。

假设我对同一个变量有一个条件,但是两个不同的目标,即:

 ?- freeze(X, G1), freeze(X, G2), X=1.

首选唤醒策略是什么,G1 是先执行的吗还是 G2 首先执行?如果 G1 和 G2 确实产生了新的冻结,也被唤醒:

 G1 :- freeze(Y, G3), Y=1.
 G2 :- freeze(Z, G4), Z=1. 

G3 或 G4 是否总是在 G1 和 G2 之间执行,或者可能是G3 或 G4 是在 G1 和 G2 之后执行的,甚至是以后的任何时间?

再见

这取决于 freeze/2 是如何在引擎盖下实现的。可以发挥作用的两种主要类型的属性变量接口是类型 1 和关于唤醒的类型 2。即:

类型 1:统一
后唤醒将在 X 实例化并且当前目标成功之后发生,然后调用下一个目标。使用这种类型,冻结的目标将看到任何实例化,但执行不是立即的,也不是总是如此。

类型 2:预统一
唤醒将在统一期间实例化 X 之前发生。预统一对于 freeze/2 没有任何意义,因为这样冻结的目标就不会看到任何实例化。

在上面的示例中,成功的目标是 X=1,下一个目标是查询结束的伪目标。从变量的属性值中读出的唤醒目标被推送到列表中,以便它们可用于下一个目标。

让我们看看这个列表是否是FIFO:

SWI-Prolog:

?- freeze(X, write('ha ')), freeze(X, write('tschi ')), X=1, nl.
ha tschi 
X = 1.
?- freeze(X, write('ha ')), freeze(X, write('tschi ')), (X=1; X=2), nl.
ha tschi 
X = 1 ;
ha tschi 
X = 2.

Jekejeke Prolog与Minlog扩展:

?- use_module(library(term/suspend)).
% 5 consults and 0 unloads in 90 ms.
Yes
?- freeze(X, write('ha ')), freeze(X, write('tschi ')), X=1, nl.
ha tschi 
X = 1
?- freeze(X, write('ha ')), freeze(X, write('tschi ')), (X=1; X=2), nl.
ha tschi 
X = 1 ;
ha tschi 
X = 2

所以这个列表是一个FIFO。如此冰冷,立即醒来,在上述两个Prolog系统中给出从左到右的执行。由此还可以推断出,如果目标进一步冻结并立即自行唤醒会发生什么。

最新更新