Prolog - 列表的不寻常 cons 语法

Question

我在 Lee Naish 的论文中遇到了一些不熟悉的 Prolog 语法 Higher-order logic programming in Prolog 。这是本文中的第一个代码示例:

% insertion sort (simple version)
isort([], []).
isort(A.As, Bs) :-
    isort(As, Bs1),
    isort(A, Bs1, Bs).

% insert number into sorted list
insert(N, [], [N]).
insert(N, H.L, N.H.L) :-
    N =< H.
insert(N, H.LO, H.L) :-
    N > H,
    insert(N, LO, L).

我的困惑在于isort(A.As, Bs) :-中的A.As。从上下文来看，它似乎是列表的替代 cons 语法，相当于 isort([A|As], Bs) :-。

此外，N.H.L 似乎是表示 [N|[H|L]] 的更方便的方式。

但是 SWI Prolog 不会接受这种不寻常的语法(除非我做错了什么)。

有人认识吗？我的假设正确吗？哪个 Prolog 解释器接受该语法作为有效语法？

Answer 1

点运算符用于 1972 年第一个 Prolog 系统中的列表，该系统是用 Algol-W 编写的，有时称为 Prolog 0 。它的灵感来自于 LISP 系统中类似的符号。下面的例子来自论文The birth of Prolog作者:Alain Colmerauer 和 Philippe Roussel——Prolog 的创始人。

+ELEMENT(*X, *X.*Y).
+ELEMENT(*X, *Y.*Z) -ELEMENT(*X, *Z).

当时，[]曾经是NIL。下一个版本中所有内容保持不变Prolog I由 Battani 和 Meloni 用 Fortran 语言编写。

然后 DECsystem 10 Prolog 使用大小写来区分原子和变量，并引入了方括号表示法，用 [] 替换 nil 和 X.Xs和 [X,..Xs]，在 DECsystem 10 的更高版本中接收 [X|Xs] 作为替代方案。在 ISO Prolog 中，只有 [X|Xs]、.(X,Xs) 以及规范语法 '.'(X,Xs).

请注意，点在 ISO Prolog 中具有许多不同的作用。它已经作为

• 结束标记，后跟 % 或空格、换行符、制表符等布局字符。

float 中的

• 小数点，例如3.14159

• 图形标记字符形成图形标记为=..

因此，如果您现在将 . 声明为中缀运算符，则必须非常小心。既包括您所写的内容，也包括 Prolog 系统将读取的内容。一个额外的空格可以改变术语的含义。考虑两种表示法的两个数字列表:

[1,2.3,4]. [5].
1 .2.3.4.[]. 5.[].

请注意，您必须在1后面添加一个空格。在这种情况下，数字前面的额外空格可能会改变术语的含义。就像这样:

[1|2.3]. [4]. 5. [].
1 .2.3. 4.[]. 5. [].

这是另一个可能更有说服力的例子:

[1,-2].
1.(-2).[].

负数需要在点列表中使用圆括号。

今天，只剩下 YAP 和 XSB 仍然默认提供中缀 . – 和 they do it differently 。 XSB 甚至无法识别上面的点语法:您需要用圆括号括住一些非负数。

您写道，N.H.L 似乎是表示 [N|[H|L]] 的更方便的方式。有一个简单的经验法则可以简化 ISO Prolog 中的此类表达式:每当您在列表中看到紧随其后的标记 | 和 [ 时，您可以将其替换它们由 , (并删除右侧相应的 ] )。所以你现在可以写:[N,H|L]，看起来还不错。

您也可以在另一个方向上使用该规则。如果我们有一个列表 [1,2,3,4,5] 我们可以使用 | 作为“ Razor Blade ”，如下所示:[1,2 ,3|[4,5]].

<小时/>

另一句话，因为您正在阅读 Naish 的论文:同时，它是 well understood只需要call/N! ISO Prolog 支持 call/1、call/2 直至 call/8。