data-structures - Prolog 中的自定义数据结构语法

Question

在序言中，[H|T]是以H开头的列表以及其余元素在列表中的位置 T (内部用 '.'(H, '.'(…)) 表示)。

是否可以用类似的方式定义新语法？例如，是否可以定义 [T~H]是以 H 结尾的列表以及其余元素在列表中的位置 T ，然后像[H|T]一样自由使用它在谓词的头部和主体中？是否也可以定义例如<H|T>与列表结构不同？

Answer 1

可以从字面上解释您的问题。一种类似列表的数据结构，可以在没有任何辅助谓词的情况下表达对尾部的访问。好吧，这些是已经在第一个 Prolog 系统中使用的负列表——有时被称为 Prolog 0 并且是用 Algol-W 编写的。来自 the original report, p.32 的示例音译成 ISO Prolog:

t(X-a-l, X-a-u-x). 

?- t(nil-m-e-t-a-l, Pluriel).
   Pluriel = nil-m-e-t-a-u-x.

所以基本上您可以使用任何左结合运算符。

但是，我怀疑这不是您想要的。您可能想要列表的扩展。

已经有几次尝试这样做，最近的一次是 Prolog III/Prolog IV .然而，与约束非常相似，您将不得不面对如何定义这些运算符的相等性。换句话说，您需要超越句法统一到 E-unification。 .这个问题一开始听起来很简单，但它却复杂得可怕。 Prolog IV 中的一个简单示例:

>> L = [a] o M, L = M o [z].
M ~ list,
L ~ list.

显然这是一个不一致。也就是说，系统应该响应 false. 根本就没有这样的 M，但是 Prolog IV 无法推断出这一点。您至少必须解决此类问题或以某种方式与它们相处。

如果您真的想深入研究这个问题，请考虑从 J. Makanin 的开创性工作开始的研究:

^{The Problem of Solvability of Equations in a Free Semi-Group, Akad. Nauk SSSR, vol.233, no.2, 1977.}

也就是说，可能有更简单的方法来获得您想要的东西。也许不需要完全关联的列表运算符。

尽管如此，与我们在 Prolog 中的 DCG 相比，不要期望这种扩展具有太多的表现力。特别是，一般的左递归仍然是文法终止的问题。