部分字典/记录统一？

Question

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

例如,在core.logic/miniKanren的语法中:

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

这将返回单个结果,其中q绑定为1.

Prologs会给这个操作或这个部分结构起一个名字吗？

Answer 1

一般来说,一种方法是以标准的方式解决Prolog中基本数据类型选择不当的问题:通过添加库和使用接口.SWI-Prolog的,例如,自带的assoc库实现的基于树的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)).

如果Left关联是Right关联的子集,则此谓词将为true,如上所述.我们可以测试它,看它是否正在做我们想要的:

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 2

一些 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

再见