when/2 和 ground/1 的逻辑纯度

Question

问题

我有一个与逻辑纯度相关的问题。

这个程序是纯的吗？

when(ground(X), X > 2).

关于上下文的一些[ir]相关细节

我正在尝试编写具有良好终止属性的纯谓词。例如，我想写一个谓词 list_length/2 来描述列表与其长度之间的关系。我想实现与内置谓词 length/2.

相同的终止行为

我的问题旨在确定以下谓词是否是纯谓词：

list_length([], 0).
list_length([_|Tail], N):-
    when(ground(N), (N > 0, N1 is N - 1)),
    when(ground(N1), N is N1 + 1),
    list_length(Tail, N1).

我可以通过 clpfd 实现我的目标 ...

:- use_module(library(clpfd)).
:- set_prolog_flag(clpfd_monotonic, true).

list_length([], 0).
list_length([_|Tail], N):-
    ?(N) #> 0,
    ?(N1) #= ?(N) - 1,
    list_length(Tail, N1).

... 或者我可以使用 var/1、nonvar/1 和 !/0，但随后是来证明谓词是纯的。

list_length([],0).
list_length([_|Tail], N):-
    nonvar(N), !,
    N > 0,
    N1 is N - 1,
    list_length(Tail, N1).
list_length([_|Tail], N):-
    list_length(Tail, N1),
    N is N1 + 1.

Answer 1

Logical purity of when/2 and ground/1

请注意，内置的 ISO ground/1 与 nonvar/1 一样不纯。但是您似乎更愿意谈论 when/2 的条件。事实上，when/2 的任何接受条件都是尽可能纯粹的。所以这不仅适用于 ground/1.

Is this program pure?
when(ground(X), X > 2).

是的，就目前的纯净度而言。也就是说，与将 library(clpfd) 视为纯的意义相同。在逻辑编程和 Prolog 的早期，比如说在 1970 年代，一个纯粹的程序只有当它为真时才会成功，如果它为假则失败。没有别的。

但是，今天，我们接受 ISO errors 类类型错误代替静默失败。事实上，从实际的角度来看，这更有意义。想想 X = non_number, when(ground(X), X > 2 )。请注意，此错误系统引入 Prolog 的时间相对较晚。

虽然 Prolog I 明确报告了内置函数的错误¹ 随后的 DEC10-Prolog（例如 1978 年、1982 年）和 C-Prolog 都不包含可靠的错误报告系统。相反，打印了一条消息并且谓词失败，从而将错误与逻辑错误混淆。从这个时候开始，仍然有 Prolog 标志 unknown (7.11.2.4 in ISO/IEC 13211-1:1995) 的值 warning 导致尝试执行未定义的谓词打印警告并失败。

那么问题在哪里呢？考虑

?- when(ground(X), X> 2), when(ground(X), X < 2).
when(ground(X), X>2),
when(ground(X), X<2).

这些 when/2 虽然完全正确，但现在对产生不一致的答案有很大帮助。毕竟，上面写着：

Yes, the query is true, provided the very same query is true.

将此与 SICStus 或 SWI 的对比 library(clpfd)：

| ?- X #> 2, X #< 2.
no

所以 library(clpfd) 能够检测到这种不一致，而 when/2 必须等到它的参数被证实。

得到这样的有条件的答案往往是非常混乱的。事实上，在许多情况下，许多人更喜欢更普通的实例化错误，而不是更干净的 when。

对此没有明显的通用答案。毕竟，许多有趣的约束理论是不可判定的。是的，看起来非常无害的 library(clpfd) 已经允许您制定不可判定的问题了！所以我们将不得不忍受这种不包含解决方案的条件答案。

但是，一旦您获得了一个纯粹的无条件解决方案，或者一旦您遇到真正的失败，您就会知道这会成立。

`list_length/2`

您使用 library(clpfd) 的定义实际上稍微好一些 w.r.t。比 Prolog 序言的 agreed upon 终止。考虑：

?- N in 1..3, list_length(L, N).

此外，目标 length(L,L) 以一种非常自然的方式产生类型错误。也就是说，没有任何显式测试。

您使用 when/2 的版本有一些 "natural" 不规范，例如 length(L,0+0) 失败但 length(L,1+0) 成功。否则它似乎没问题 - 仅通过构造。

1) 最早的记载是 G. Battani, H. Meloni 的第 9 页。 Interpréteur du langage de programmation Prolog。融洽 D.E.A。 d'informatique appliquée，1973 年。在那里，一个内置的错误被一个从未解决的目标所取代。在 II-3-6 a 的当前术语 plus/3 中，第 13 页将在当前系统中使用 freeze/2:

plus(X, Y, Z) :-
   (  integer(X), integer(Y), ( var(Z) ; integer(Z) )
   -> Z is X+Y
   ;  freeze(_,erreur(plus(X,Y,Z)))
   ).

所以 plus/3 不是 "multi-directional"。

when/2 和 ground/1 的逻辑纯度

Logical purity of when/2 and ground/1

prolog

logical-purity

list_length/2

`list_length/2`