dif/2 等谓词的实施指南

Guidelines for implementing predicates like dif/2

假设我有一个谓词 foo/2,它定义了第一个和第二个参数之间的关系。

更改 foo/2 实现的最惯用且最有效的方法是什么:

换句话说,如何正确实现 dif/2 表现出的行为,但具有任何类型的用户定义关系?

listing(dif/2). 帮助不大。

不同的 Prolog 实现提供不同的功能来实现这一点。该机制被称为 coroutiningdelayed goalsconstraints,您的 Prolog 系统手册将提供更多信息。

这里有两个变体,它们在 SICStus Prolog 和其他一些系统中可用。

block/1 指令

在 SICStus Prolog(可能还有一些其他系统)中,一种将 user-defined 谓词提升到这种受限版本的方法可通过声明式 block declaration.

获得

有趣的是,这个不需要对谓词本身进行任何更改

假设您有一个不纯的 dif/2 版本,使用 non-monotonic (\=)/2 谓词:

madif(X, Y) :-
    X \= Y.

然后你可以把它变成一个 delayed 版本,例如:

:- block madif(-, ?),
         madif(?, -).

madif(X, Y) :-
    X \= Y.

示例查询和答案:

| ?- madif(a, b).
yes
| ?- madif(a, X).
user:madif(a,X) ? ;
no
| ?- madif(a, X), X = b.
X = b ? ;
no
| ?- madif(X, Y).
user:madif(X,Y) ? ;
no

根据需要,目标的评估被延迟,直到 两个 参数都被实例化。

when/2

使用 SICStus Prolog(以及提供此功能的其他系统)实现此目的的第二种方法是使用 when/2。这需要对谓词本身进行更改。

例如,使用when/2,你可以这样实现madif/2

madif(X, Y) :-
    when((ground(X),
          ground(Y)), X \= Y).

示例查询和答案:

| ?- madif(X, a).
prolog:trig_ground(X,[],[X],_A,_A),
prolog:when(_A,(ground(X),ground(a)),user:(X\=a)) ? ;
no
| ?- madif(X, a), X = b.
X = b ? ;
no

首先,

站在用户的角度

...而不是实施者的。这一点常常被忽略——在现有的约束实现中也是如此。它显示了。因此,这里是需要考虑的最突出的方面。

正确性

显然这应该成立。产生干净的错误(主要是实例化错误)总是更好,永远挣扎更好,永远循环比错误地失败更好。如果一切都失败了,你可以用 freeze(_, G_0) 结束你的尝试。请注意,您确实需要一个工作的顶层才能真正看到这些困难重重的目标。 SICStus 有这样一个顶层 1,在 SWI 中你需要将查询包装为 call_residue_vars(Query_0, Vs) 以查看所有附加的约束。

一致性

接下来你要确保你的约束尽可能保证一致性。有许多一致性概念,例如域和边界一致性。为了满足您的精确要求,请考虑 difgrn/2 并将其与 built-in dif/2:

进行比较
difgrn(X, Y) :-
   when((ground(X), ground(Y)), X \== Y).

| ?- difgrn(X, X).
prolog:trig_ground(X,[],[X],_A,_B),
prolog:trig_ground(X,[],[X],_A,_C),
prolog:trig_and(_C,[],_A,_B,_A),
prolog:when(_A,(ground(X),ground(X)),user:(X\==X)) ? ;
no
| ?- dif(X, X).
no


| ?- difgrn([], [_]).
prolog:trig_ground(_A,[],[_A],_B,_C),
prolog:trig_and(_C,[],_B,1,_B),
prolog:when(_B,(ground([]),ground([_A])),user:([]\==[_A]))

| ?- dif([], [_]).
yes

全面实施 dif/2 的一种方法是使用非常特殊的条件 (?=)/2:

difwh(X,Y) :- when(?=(X,Y), X\==Y).

哪个应该尽可能最好地回答您的问题:

In other words, how to correctly implement the behaviour exhibited by dif/2 but with any kind of user-defined relation?

但不幸的是,这不会扩展到任何其他内容。

如果考虑各种约束之间的一致性,情况会变得更加复杂。想想X in 1..2, dif(X, 1), dif(X, 2).

答案预测

(找不到更好的词。)有时您希望在顶层清楚地看到您的约束 - 最好的方法是将它们表示为目标,这些目标本身将重新建立表示答案所需的确切状态。 见上面 trig_ground 个答案,当然可以美化一下。

可变预测

与答案预测相同,但可以在任何时间点通过 frozen/2copy_term/3

包含检查

这对于诊断目的和循环检查很有用。 对于纯句法术语,subsumes_term/2 会忽略约束。执行有效测试的先决条件是将每个涉及的变量与实际约束联系起来。考虑目标 freeze(X, Y = a) 并想象一些使用 Y 作为参数的包含检查。如果 Y 不再附加到信息中(因为它通常与 freeze/2 的当前实现一起使用),您将得出错误的结论,即此 Y 包含 b

请注意 dif/2 的实际示例,这是有史以来的第一个约束(1972 年,Prolog 0)。更详尽的描述给出了 L'anatomie de Prolog,InterÉditions 1986 中的 Michel van Caneghem 和关于 MU-Prolog.

的论文中的 Lee Naish

1 Half-true。 library(clpfd) 你需要 assert(clpfd:full_answer).