是否可以在 Prolog 中编写一个空列表作为差异列表?

Is it possible to write an empty list as a difference list in Prolog?

对于像我这样的 Prolog 初学者来说,空列表……很奇怪。我会说不可能将空列表 [] 写成差异列表 T1-T2 就像不可能将原子写成差异列表一样。但是,我猜想要使用递归,必须有一种方法可以在差异列表设置中使用 [] 。我已经 Google 解决了这个问题,但我找不到答案,而 Bratko(Prolog Programming for AI)只是简单地触及了这个主题。

那么,是否可以在 Prolog 中编写一个空列表作为差异列表,如果是这样,它如何以及何时有用?

理解这个主题的问题通常是由于使用了误导性术语

根据 tutorial.pdf and especially pap95.pdf 中的建议,使用例如 list difference 或简单地 difference.

Teaching beginners Prolog 的第 5 节包含相关原因。

空列表由 atom[] 唯一表示。

请注意,列表差异始终意味着对 两个 个列表进行推理,并且由于单个列表和多个列表之间的这种分类差异,您最多可以找到一些对应关系或类比,但是空列表和列表差异不相同

我完全支持上述论文中表达的观点,即您应该专注于使用 DCG,至少在一开始是这样。稍后您会自然而然地对差异进行明确推理。

追加两个列表差异意味着第一个差异的结束指针与第二个差异的头部的统一。对于常规列表,它需要回溯第一个列表的整个列表结构。因此,右边的重复串联 linear 使用列表差异技术,而 quadratic 使用普通列表。

当所有预期的连接都完成后,为了 return 整个结构作为调用者的普通列表,我们只需将 "end pointer" logvar 与 [].[=19= 统一起来]

在 C 术语中,列表差异是 singly-linked 列表的一部分,我们在其中维护两个变量:它的头指针和尾指针:

// typedef struct { int payload; node* next } node;
typedef struct { node** head; node** tail } list_diff;

现在每个连接只是结束指针的赋值:

void diff_concat( list_diff* a, list_diff* b)
{
    *(a -> tail) -> next = *(b -> head);
    a -> tail = b -> tail;
}

最终确定是

void diff_finalize( list_diff* a)
{
    *(a -> tail) = NULL;  // or some sentinel value, whatever
}

在 Prolog 中,我们可以将其表示为二进制项,例如 -/2,例如-(A,B)A-B

但是(就像在 C 中一样)实际上没有必要在内存中构建一个实际的结构来保存这两个指针;我们可以单独维护两个 logvars。或者让 DCG 为我们做。

以上是列表差异技术的励志介绍,"what are they good for?"。也明确了空差的表示是

list_diff* d;
*(d -> head) = *(d -> tail);

或者在Prolog中,一对统一的logvars:L-L, var(L)。要了解原因,请查看当空差异在其右侧附加一些其他差异时会发生什么(总是在右侧 我们附加内容,从而在 [=37] 中增加列表=]top-down方式)。我的 C 可能不在这里,想法是通过设置尾部附加到一个空的 diff 也会更新它的头部。