归因variables:库接口/实现/可移植性

当我最近浏览一些序言相关的问题时,我偶然发现了@mat的这个答案,以问题如何在Prolog中直接访问相邻节点来表示有向循环图 。

到目前为止,我对Prolog中归因variables的个人经验非常有限。 但@mat给出的用例引发了我的兴趣。 所以我试着用它来回答另一个问题, 用约束逻辑编程sorting列表 。

首先,好消息是:我第一次使用属性variables就像我想要的那样。

然后,不是那么好的消息:当我通过回答发布时,我意识到在Prolog中有几个API和实现的归因variables。

我觉得我在这里头…特别是我想知道以下几点:

  • 什么API在广泛使用? 到目前为止,我发现了两个:SICStus和SWI。
  • 不同的归因variables实现提供哪些function? 同样的? 或者一个包含另一个?
  • 语义有差异吗?
  • 那实际的实现呢? 比别人更有效率吗?
  • 可以(或正在)使用属性variables的可移植性问题?

很多问号,在这里…请分享你的经验/立场? 先谢谢你!


编辑2015-04-22

这是上面提到的答案的代码片段:

init_att_var(X,Z) :- put_attr(Z,value,X). get_att_value(Var,Value) :- get_attr(Var,value,Value). 

到目前为止,我只“使用” put_attr/3get_attr/3 ,但是—根据SICStus Prolog关于归因variables的文档— SICStus提供了put_attr/2get_attr/2

所以即使这个非常浅的用例也 需要一些仿真层(单向或者其他)。

我想关注一下我在使用属性variables的不同接口时注意到的一个重要的一般观点:在为属性variablesdevise接口时,实现者还应该牢记以下内容:

  • [X,Y] = [0,1]推理同时统一时 ,是否可以考虑属性?

例如在SICStus Prolog中,这是可能的,因为在verify_attributes/3之前,这样的绑定是被撤消的 。 在由hProlog提供的接口( attr_unify_hook/2统一之后调用并且所有绑定已经就绪)时,在推理attr_unify_hook/2X的统一时很难考虑Y的(先前)属性,因为在这一点上, Y不再是一个variables! 对于只能根据基础值做出决定的求解者来说,这可能是足够的,但是对于求解者来说,这是一个严重的局限性,需要额外的数据,通常存储在属性中,以查看统一是否成功,哪些不再容易获得。 一个明显的例子:与决策图布尔统一。

截至2016年,SWI-Prolog的verify-attributes分支也支持verify_attributes/3 ,这要归功于Douglas Miles的大量实施工作。 该分支已经准备好进行testing,并且一旦正确和高效地工作,就打算将它合并到主分支中。 为了与hProlog兼容,分支还支持attr_unify_hook/2 :通过在编译时将这些定义重写为更一般的verify_attributes/3

从性能angular度来看,很明显verify_attributes/3可能有一个缺点,因为同时创build几个variables可能会让你更早地看到( attr_unify_hook/2 )统一无法成功。 但是,我会很乐意随时更换这种通常可以忽略不计的优势,以提高可靠性,易用性和增加function性,这是更一般的接口给你的,而且无论如何已经是SICStus Prolog中的标准行为了它的普遍性也是更快的Prolog系统之一。

SICStus Prolog还提供了一个称为project_attributes/2的重要谓词:它被顶层使用来投影约束来查询variables。 SWI-Prolog也支持最近的版本。

SWI接口还有一个巨大的优势: attribute_goals//1和因此copy_term/3给你的剩余目标总是一个列表 。 这有助于用户避免在代码中使用defaulty,并鼓励更多的声明性接口,因为纯约束目标列表不能包含控制结构

有趣的是,这两个接口都不允许你在语法上解释统一。 就个人而言,我认为在某些情况下,你可能想要以不同于语法的方式来解释统一,但是也可能有很好的反驳。

对于不同的系统来说,归属variables的其他接口谓词大多可以很容易地与简单的包装谓词交换。

Jekejeke Minlog具有无状态或薄的属性variables。 那么不完全是,一个属性variables可以有零个,一个或多个钩子,这些钩子被允许是闭包,因此可以带有一点状态。

但是通常一个实现pipe理其他状态。 为此,Jekejeke Minlog允许从variables创build引用types,以便它们可以用作表中的索引。

如果与尾随和/或向前链接相结合,则充分发挥其潜力。 作为一个例子,我们已经实施了CLP(FD)。 还有一个小解算器教程。

我们这种情况下的原始成分是:

1)无状态属性variables
2)尾随和variables键
3)延续队列

属性variables挂钩可能具有直到延长连续队列的绑定效果,但只能执行一次。 来自延续队列的目标可能是不确定的。

在实现应用程序之前还有一些额外的层次,这些层次主要是基元的集合以临时进行更改。

到目前为止,主要的应用程序在这里和这里是开源的:

a)有限域约束求解器
b)Herbrand限制
c)目标暂停

再见

您可以在ECLiPSe中find最古老和最精细的属性variables实现之一,它是实现约束求解器的更广泛基础架构的一部分。

这种devise的主要特点是:

  • 属性必须声明,作为回报,编译器支持高效的访问
  • 归属variables的语法,以便可以读取和写入
  • 为属性操作提供了一套更完整的处理程序,因此不仅要考虑统一属性,还要考虑其他通用操作,如术语复制和包含testing
  • 可变属性和暂停目标的概念之间的清晰分离
  • 在十几个ECLiPSe的图书馆中使用

本文(第4节)和ECLiPSe文档有更多的细节。

对属性variables库的另一个观点是每个模块可以定义多less个属性。 对于SWI-Prolog / YAP并引用SWI文档:

每个属性都与一个模块相关联,并在该模块中执行挂钩( attr_unify_hook/2 )。

这对于像CLP(FD)这样的图书馆实施者来说是一个严重的限制,因为它强制使用额外的模块来实现具有多个属性的唯一目的,而不是像在实现图书馆的模块中所要求的那样定义许多属性。 SICStus Prolog接口上不存在此限制,该接口提供指令attribute/1 ,允许为每个模块声明任意数量的属性。