还没有人谈论差异列表。
差异列表
差异列表表示为L-E
,这只是一个方便的符号,用于由一个列表组成的一对列表L
,其最后一个 cons-cellE
的尾部为:
L = [ V1, ..., Vn | E]
空差异列表是E-E
, 带有E
一个变量。E
每当您想细化列表时,您就可以统一起来。比如要添加一个元素X
,可以统一如下:
E = [X|F]
然后,L-F
是新列表。同样,您可以在恒定时间内附加列表。如果您F
与“正常”列表统一,特别是[]
,您将关闭您的开放式列表。在所有操作期间,您通过 保留对整个列表的引用L
。当然,您仍然可以L
使用通常的[W1, ..., Wm |L]-E
符号在前面添加元素。
您是否需要差异列表是另一个问题。如果在末尾添加元素实际上是您的常见操作并且您正在操作大型列表,那么它们很有趣。
定从句文法
DCG是在 Prolog 中编写语法规则的一种便捷方式。它们通常被实现为阅读器宏,将-->
表单转换为实际的谓词。由于语法的目的是在解析过程中构建结构(又名产生式),因此到实际谓词的翻译涉及差异列表。因此,尽管这两个概念在理论上是不相关的,但差异列表通常是 DCG 的构建材料。
维基百科上的示例以:
sentence --> noun_phrase, verb_phrase.
...被翻译为:
sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3).
语法提供了很多“管道”(有点像 monads)。被“构建”的对象sentence/2
是S1,它是由谓词连接在一起的不同部分构建的。S1被传递给noun_phrase
,它根据需要构建/扩展它并“返回” S2,这可以看作是“扩展S1的任何东西”。这个值被传递给verb_phrase
更新它并给出S3,也就是扩展S2。S3是 的一个参数sentence
,因为根据我们的规则,它也是“扩展S1的任何东西”。但是,这是 Prolog,所以S1,S3不一定是输入或输出,它们在整个过程中是统一的,在此过程中也会发生回溯(可以解析模棱两可的语法)。它们最终与列表统一。
当我们遇到箭头右侧的列表时,差异列表就会发挥作用:
det --> [the].
上面的规则翻译为:
det([the|X], X).
这意味着它将det/2
它的第一个参数与一个开放式列表统一起来,其中 tail 是X
; 其他规则会统一X
。通常,您会找到 与 关联的epsilon[]
规则。
以上所有操作都是使用宏完成的,一个典型的错误是尝试对数据调用辅助谓词,但由于转换添加了两个参数而失败(调用helper(X)
实际上是调用helper(X,V,W)
)。您必须将实际的实体括在大括号之间{ ... }
以避免将谓词视为规则。