部分字典/记录统一？

Question

我知道一些Prolog支持开箱即用的类似字典的关联数据结构。对于这样做的实现，它们是否支持与另一个实际上不包含所有键的结构的部分统一的概念？

例如，在core.logic/miniKanren的语法中：

(run* [q]
  (== {:foo 1 :bar 2} (partial-map :foo q)))

这将返回一个结果，其中q被绑定到1。

Prolog给这个操作或者这个局部结构起名字了吗？

Answer 1

有些Prolog系统，比如Eclipse，有一种记录符号。当您预先知道地图的可能密钥时，可以使用此方法。但是它需要一个类型声明。记录符号也可以在Prolog派生语言中找到，比如Erlang。

这个想法非常简单。首先声明一个记录类型(这里发明了一些语法)：

:- rectype T{K1,...,Kn}.

现在你可以在你的Prolog程序记录中使用，只需写下(同样是这里发明的一些语法)：

... T{F1 = V1, .., Fn = Vm} ...

在编译类型中，记录将被转换为复合类型，然后可以很容易地在正常的统一中使用。转换根据记录类型声明重新排序键值对，然后删除键并仅使用位置。未使用的位置将由匿名变量替换，如果记录类型声明也包含此位置，则默认替换为默认值。

... T(W1, ..., Wn) ...

您的示例将按如下方式工作：

:- rectype myrec{foo, bar}

?- myrec{foo=1,bar=2} = myrec{foo=q}

后一个查询将在内部执行，如下所示：

?- myrec(1,2) = myrec(q,_).

有关Eclipse如何做到这一点的更多详细信息，请参见此处的示例：

http://www.eclipseclp.org/doc/bips/kernel/syntax/struct-1.html

对于键集不是静态的动态映射，您可以实现动态数据结构，如另一篇关于SWI-Prolog AVL树的文章所示。或者向你的Prolog系统索要一个特定数据结构的句柄。使用FFI (外部函数接口)实现这些功能，或者访问已经与Prolog系统捆绑在一起的这些功能。例如Eclipse捆绑了一对，请参阅下面文章中的“描述”部分：

http://www.eclipseclp.org/doc/bips/kernel/record/index.html

再见

Answer 2

一般来说，人们可以通过标准方式解决Prolog中基础数据类型选择不佳的问题:通过添加库和使用接口。例如，SWI-Prolog附带的assoc library实现了一种基于AVL树的关联数据结构。(顺便说一句，在函数和逻辑编程中，平衡树比哈希表更常见，因为在树上创建“持久”数据结构比在哈希表上创建“持久”数据结构更容易--在共享内部结构的FP意义上持久。)

使用这个库看起来像这样：

?- [library(assoc)].
% library(assoc) compiled into assoc 0.00 sec, 97 clauses
true.

?- empty_assoc(Assoc).
Assoc = t.

?- empty_assoc(Assoc), get_assoc(test, Assoc, V).
false.

?- empty_assoc(Assoc), put_assoc(test, Assoc, foo, Assoc2).
Assoc = t,
Assoc2 = t(test, foo, -, t, t).

?- empty_assoc(Assoc), 
   put_assoc(test, Assoc, foo, Assoc2), 
   get_assoc(test, Assoc2, Value).
Assoc = t,
Assoc2 = t(test, foo, -, t, t),
Value = foo.

一旦你有了这样一个接口，你就可以在它上面定义各种逻辑关系。一旦您有了逻辑关系，Prolog的常规统一机制将负责其余部分-不需要对这种或那种数据类型提供特殊支持。根据您的需求，我认为您想要的类似于子集关系，除了检查一个关联的所有关联都在另一个关联中，并且它们都具有相同的值。我猜它应该是这样的：

association_subset(Left, Right) :-
  forall(gen_assoc(Assoc, Left, Value), get_assoc(Assoc, Right, Value)).

如上所述，只有当左关联是右关联的子集时，此谓词才为真。我们可以测试它，看看它是否在做我们想要的事情：

simple(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, foo_test, V1),
  put_assoc(bar, V1, bar_test, Assoc).

complex(Assoc) :-
  simple(Assoc1),
  put_assoc(baz, Assoc1, bazzle, Assoc).

unrelated(Assoc) :-
  empty_assoc(Empty),
  put_assoc(baz, Empty, bazzle, Assoc).

..。

?- simple(X), complex(Y), association_subset(X, Y).
X = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t),
Y = t(baz, bazzle, -, t(bar, bar_test, -, t, t), t(foo, foo_test, -, t, t)).

?- simple(X), simple(Y), association_subset(X, Y).
X = Y, Y = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t).

?- simple(X), unrelated(Y), association_subset(X, Y).
false.

?- complex(X), simple(Y), association_subset(X, Y).
false.

我们可以将其翻译为您的问题，如下所示：

left(Assoc) :- 
  empty_assoc(Empty),
  put_assoc(foo, Empty, 1, Assoc).

right(Assoc) :-
  left(Assoc1),
  put_assoc(bar, Assoc1, 2, Assoc).

?- left(L), right(R), association_subset(L, R), get_assoc(foo, L, Q).
L = t(foo, 1, -, t, t),
R = t(foo, 1, <, t(bar, 2, -, t, t), t),
Q = 1.

我知道这个答案并没有真正回答你提出的问题，但我希望它能回答问题下面的问题。换句话说，这些数据结构不需要特殊的支持--上面的谓词也可以在关联列表上定义，你可以看到，你所需要的只是建立空关联、添加、测试和生成关联的键/值的常用方法，而底层数据结构变得无关紧要了。无论是在数据结构方面还是在统一方面，都不需要特殊的支持。特殊的语法肯定会让它看起来更好！但是没有必要获得你想要的行为。

Answer 3

我不太清楚你真正想要的是什么(你已经去掉了散列方面)，但也许你更想要的是功能术语或功能结构？

它们很受语言学家的欢迎，已经成为生活的一部分。

可以在属性变量的帮助下实现它们，但到目前为止，我还没有看到太多对它们的需求。

你也可以用语法统一来模拟它们，有点笨拙。它很笨拙，因为您需要用单独的参数来表示每个特征(您可以稍微做得更好，但也会更复杂)。因此，如果你的程序包含n个特征，那么一个特征结构将包含n个不同的参数，其中大多数永远不会被触及。然而，统一将直接按照预期的方式工作。