包含 in 或不等式的 CLPFD 域声明

CLPFD domain declaration with in or inequalities

?- X in 1..100.
X in 1..100.

?- X #> 0, X #< 101.
X in 1..100.

目前一切顺利!

现在假设 X 的上界取决于 Y in 100..200

?- Y in 100..200, X #> 0, X #=< Y.
Y in 100..200,
Y#>=X,
X in 1..200.

X 的域正确传播到 1..200,约束在 XY 之间。

但是……

?- Y in 100..200, X in 1..Y.
ERROR: Arguments are not sufficiently instantiated

我认为 in 等同于不等式声明,但显然不是。

关于为什么 in 要求两个边界都接地,是否有任何隐藏的原因?

这是个很好的问题。它有一个直截了当的答案,乍一看似乎很深奥,但一旦您熟悉了 声明式调试 开始变得更广泛可用的方法,就真的很容易理解。

声明式调试依赖于我们知道始终持有的逻辑程序的属性。纯逻辑程序的一个关键属性(参见)是单调性:

Generalizing a goal can at meast increase the set of solutions.

这是一个例子:

?- append([a], [b], [c]).
false.

为什么会失败?我们想找到失败的实际原因解释为什么这不会成功。从程序的角度思考并 trace 执行很诱人,但这很快就会变得极其复杂,并没有真正向我们展示 essence 的原因.

相反,我们可以通过系统地概括目标来达到本质。例如,以下成功

?- append([a], [b], Cs).

我通过将术语 [c] 替换为包含它的 Cs 来概括查询。

您可以自动执行此操作,请参阅 Ulrich Neumerkel 的 library(diadem),尤其是 GUPU 系统,在该系统中,这些想法得到了充分发展,极大地帮助定位了 Prolog 程序中错误的精确位置。

要最大限度地应用此类技术,您必须致力于在程序中保留尽可能多的有趣属性,本质上是保持 Prolog 的纯单调核心。我说 "essentially" 是因为这些技术在 class 很难正式 class 的程序上也能在一定程度上超出这个子集。另请注意,正在进行的逻辑编程方面的大部分工作旨在尽可能增加 Prolog 的纯单调子集,因此随着时间的推移,限制变得越来越不严格。

现在考虑 (in)/2 的细节:(in)/2 的域参数在其中带有一个声明性缺陷,因为它使用 默认 表示域.有几种方法可以看出这一点,尤其是从以下情况来看:假设我告诉你一个域的形式是 inf..High,那么 High 是什么?它可以是以下之一:

  • sup
  • 一个整数.

我们无法清楚地区分这些情况的事实告诉您这种表示是默认的。

一个干净的边界表示如下:

  • inf, sup 表示无穷大
  • n(N)表示整数N.

有了这样的表示,我可以告诉你域看起来像这样:inf..n(N),你知道 N 必须是一个整数.

再举个例子:

?- X in 1..0.
false.

为什么会失败?让我们再归纳一下论点,找个理由:

?- X in Low..0.

现在假设 (in)/2 将其接受为可接受的查询。那什么是Low呢?同样,它可以是 整数, 原子 inf。不幸的是,没有以这种方式约束 Low 的明智方法:将其约束为 整数 将使 CLP(FD) 约束最合适,因此很容易回答:

X in Low..0,
Low in inf..0

但这当然太多了,因为它排除了 Low = inf:

?- Low in inf..0, Low = inf.
Type error: `integer' expected, found `inf' (an atom)

知道在这种情况下我们无法确定术语 Low 的类型,并且缺乏合理的方式来说明这一点,因此引发 实例化错误 以指示这种概括是不可接受的。

从这些考虑,整体答案真的很简单:

(in)/2 cannot be easily generalized due to the defaulty representation of domains.

不变的是,使用此类表示的原因只有两个:

  • 它们更容易打字
  • 它们更易于阅读。

当然,最大的缺点是它们极大地阻碍了对程序的声明性推理。

请注意,在内部,SWI-Prolog 的 CLP(FD) 系统 确实 使用域的干净表示。这也可以传递给用户端,这样我们就可以写:

?- X in n(Low)..0.

声明完全有效的答案:

X in n(Low)..0,
Low in inf..0.

随着时间的推移,这种更简洁的符号一定会找到适合用户的方式。现在,至少以我的经验来看,这个要求有点过分了。

在你举的具体例子中,域边界已经约束为整数,当然可以区分大小写和这会自动转化为不等式。然而,这并不能消除默认的核心问题,交换目标仍然会引发实例化错误。