7

我正在编写一个 prolog 程序来检查变量是否为 integer。我“返回”结果的方式很奇怪，但我认为这对于回答我的问题并不重要。

测试

我已经为此行为编写了通过单元测试；他们来了...

foo_test.pl

:- begin_tests('foo').
:- consult('foo').

test('that_1_is_recognised_as_int') :-
    count_ints(1, 1).

test('that_atom_is_not_recognised_as_int') :-
    count_ints(arbitrary, 0).

:- end_tests('foo').
:- run_tests.

编码

这是通过这些测试的代码......

foo.pl

count_ints(X, Answer) :-
  integer(X),
  Answer is 1.

count_ints(X, Answer) :-
  \+ integer(X),
  Answer is 0.

输出

测试通过了，这很好，但是当我运行它们时收到警告。这是运行测试时的输出...

?- ['foo_test'].
%  foo compiled into plunit_foo 0.00 sec, 3 clauses
% PL-Unit: foo 
Warning: /home/brandon/projects/sillybin/prolog/foo_test.pl:11:
        /home/brandon/projects/sillybin/prolog/foo_test.pl:4:
        PL-Unit: Test that_1_is_recognised_as_int: Test succeeded with choicepoint
. done
% All 2 tests passed
% foo_test compiled 0.03 sec, 1,848 clauses
true.
  • 我正在使用 SWI-Prolog（多线程，64 位，版本 6.6.6）
  • 我尝试count_ints使用 将这两个谓词合并为一个;，但它仍然会产生相同的警告。
  • 我在 Debian 8 上（我怀疑它会有所作为）。

问题

  • 这个警告是什么意思？和...
  • 我该如何预防？
4

2 回答 2

14

首先，让我们忘记整个测试框架，只考虑顶层的查询：

?- count_ints(1, 1)。
真的 ;
假的。

这个交互告诉你，在第一个解之后，剩下一个选择点。这意味着要尝试替代方案，并在回溯时对其进行尝试。在这种情况下，没有进一步的解决方案，但系统在实际尝试之前无法判断这一点。

all/1对测试用例使用选项

有几种方法可以修复警告。一个直截了当的方法是这样描述测试用例：

测试（'that_1_is_recognised_as_int'，所有（计数 = [1]））：-
    计数整数（1，计数）。

这隐含地收集了所有解决方案，然后立即对所有解决方案进行声明。

使用 if-then-else

一个更智能的解决方案是使count_ints/2自己具有确定性！

一种方法是使用 if-then-else，如下所示：

count_ints（X，答案）：-
        （整数（X）->答案= 1
        ; 答案 = 0
        ）。

我们现在有：

?- count_ints(1, 1)。
真的。

即，查询现在确定地成功。

纯解决方案：清洁数据结构

然而，最优雅的解决方案是使用干净的表示，这样您和 Prolog 引擎就可以通过模式匹配来区分所有情况。

例如，我们可以将整数表示为i(N)，而将其他所有内容表示为other(T)。

在这种情况下，我使用包装器i/1并other/1区分这些情况。

现在我们有：

count_ints(i(_), 1)。
count_ints（其他（_），0）。

测试用例可能如下所示：

测试（'that_1_is_recognised_as_int'）：-
    计数整数（我（1），1）。

测试（'that_atom_is_not_recognised_as_int'）：-
    count_ints（其他（任意），0）。

这也可以在没有警告的情况下运行，并且具有代码实际上可以用于生成答案的显着优势：

?- count_ints(Term, Count)。
项 = i(_1900),
计数 = 1 ;
术语 = 其他（_1900），
计数 = 0。

相比之下，我们有其他版本：

?- count_ints(Term, Count)。
计数 = 0。

不幸的是，这充其量只能考虑覆盖 50% 的可能情况......

更严格的约束

正如 Boris 在评论中正确指出的那样，我们可以通过将 terms的参数限制为integers来使代码更加严格。例如，我们可以写：i/1

count_ints(i(I), 1) :-我在 inf..sup 中。
count_ints（其他（_），0）。

现在，参数必须是一个整数，这通过以下查询变得清晰：

?- count_ints(X, 1)。
X = i( _1820 ),
 _1820 inf..sup。

?- count_ints(i(any), 1)。
错误：类型错误：预期为“整数”，发现“任何”（原子）

请注意，Boris 提到的示例在没有更严格的约束的情况下也会失败：

?- count_ints(X, 1), X = 任何东西。
假的。

尽管如此，在参数上添加更多约束通常很有用，如果您需要对整数进行推理，CLP(FD) 约束通常是显式声明类型约束的良好且通用的解决方案，否则这些约束仅在您的程序中是隐含的。

注意integer/1没有得到备忘录：

?- inf..sup 中的 X，整数（X）。
假的。

这表明，尽管在这个例子中X毫无疑问地被限制为整数integer(X)，但仍然没有成功。因此，您不能使用诸如integer/1etc. 之类的谓词作为可靠的类型检测器。依靠模式匹配和使用约束来增加程序的通用性要好得多。

于 2016-11-21T02:58:45.183 回答
9

首先要做的事情是：SWI-Prolog Prolog 单元测试包的文档非常好。不同的模式在第 2.2 节中解释。编写测试体。2.2.1中的相关语句是：

确定性谓词是必须只成功一次的谓词，对于表现良好的谓词，不留下选择点。[强调我的]

什么是选择点？

在过程式编程中，当你调用一个函数时，它可以返回一个值，也可以是一组值；它可以修改状态（本地或全局）；不管它做什么，它只会做一次。

在 Prolog 中，当您评估谓词时，会在证明树中搜索解决方案。可能有不止一种解决方案！假设你between/3这样使用：

对于x = 1，x在 [0, 1, 2] 中吗？

?- between(0, 2, 1).
true.

但你也可以问：

枚举所有x使得x在 [0, 1, 2] 中。

?- between(0, 2, X).
X = 0 ;
X = 1 ;
X = 2.

在获得第一个解决方案后X = 0，Prolog 停止并等待；这表示：

该查询between(0, 2, X)至少有一个解决方案，X = 0。它可能有进一步的解决方案；按下;，Prolog 将在证明树中搜索下一个解决方案。

选择点是 Prolog 在找到解决方案后放在搜索树中的标记。它将从该标记继续搜索下一个解决方案。

警告“选择点测试成功”表示：

Prolog 找到的解决方案是测试预期的解决方案；但是，它在那里留下了一个选择点，因此它不是“乖巧”。

选择点有问题吗？

您没有故意放在那里的选择点可能是一个问题。如果不详细介绍，它们可能会阻止某些优化并导致效率低下。没关系，但有时只有第一个解决方案是您（程序员）想要的解决方案，而下一个解决方案可能会产生误导或错误。或者，众所周知，在给你一个有用的答案之后，Prolog 可以进入一个无限循环。

同样，如果您知道这一点，这很好：当您评估此谓词时，您永远不会要求多个解决方案。您可以将其包装在 中once/1，如下所示：

?- once( between(0, 2, X) ).

或者

?- once( count_ints(X, Answer) ).

如果其他人使用您的代码，尽管所有赌注都已关闭。选择点成功可能意味着从“还有其他有用的解决方案”到“没有更多的解决方案，现在这将失败”到“其他解决方案，但不是你想要的那种”到“现在进入无限循环！”

摆脱选择点

举个具体的例子：你有一个内置的 ,integer/1它将成功或失败而不会留下选择点。因此，原始定义中的这两个子句对于 的任何值count_ints/2都是互斥的：X

count_ints(X, Answer) :-
  integer(X), ...

count_ints(X, Answer) :-
  \+ integer(X), ...

然而，Prolog 并不知道这一点。它只查看子句标题，这两个是相同的：

count_ints(X, Answer) :- ...

count_ints(X, Answer) :- ...

两个头是相同的，Prolog 不会再看子句头来决定另一个子句是否值得尝试，因此即使第一个参数确实是整数，它也会尝试第二个子句（这是“选择点”在您收到的警告中），并且总是失败。

因为你知道这两个子句是互斥的，所以告诉 Prolog 忘记另一个子句是安全的。您可以使用once/1，如上所示。当第一个参数确实是整数时，您还可以剪切证明树的其余部分：

count_ints(X, 1) :- integer(X), !.
count_ints(_, 0).

完全相同的操作语义，但 Prolog 编译器可能更容易优化：

count_ints(X, Answer) :-
    (   integer(X)
    ->  Answer = 1
    ;   Answer = 0
    ).

...就像垫子的回答一样。至于使用模式匹配，一切都很好，但是如果X来自其他地方，而不是来自您自己编写的代码，您仍然需要在某个时候进行此检查。你最终会得到类似的东西：

variable_tagged(X, T) :-
    (   integer(X) -> T = i(X)
    ;   float(X)   -> T = f(X)
    ;   atom(X)    -> T = a(X)
    ;   var(X)     -> T = v(X)
    % and so on
    ;   T = other(X)
    ).

那时你可以count_ints/2按照 mat 的建议编写你的，Prolog 会通过查看子句标题知道你的两个子句是互斥的。

我曾经问过一个问题，归结为相同的 Prolog 行为以及如何处理它。mat的回答推荐了同样的方法。mat 对我在答案下方的评论的评论与答案本身一样重要（至少如果您正在编写真正的程序）。

于 2016-11-21T03:47:07.357 回答