Prolog：如何判断谓词是否是确定性的

Question

据我所了解，关于确定性谓词：

确定性谓词= 一个解决方案

非确定性谓词= 多个解决方案

有没有什么规则可以用来检测谓词是属于哪一种？比如查看搜索树等。

- John Smith

---

它是非确定性的。 - false

感兴趣的内容：编程语言 - Mercury 确定性类别 - Guy Coder

Answer 1

关于这些概念，目前没有清晰且广泛接受的共识。但是，它们通常更基于观察到的答案而不是基于解决方案的数量。在某些情况下，这些概念与实现非常相关。非确定性可能意味着: 仍有选择点未确定。有时，确定性的意思是：甚至从不创建选择点。

答案与解决方案

为了看出区别，请考虑目标length(L, 1)。它有多少解决方案？L = [a]是一个，L = [23]是另一个......但所有这些解决方案都可以用单个答案替换紧凑地表示：L = [_]，因此包含无限多个解决方案。 在任何情况下，在我所知道的所有实现中，length(L, 1)都是一种确定性目标。

现在考虑目标repeat，它只有一个解决方案，但有无限多个答案。这个目标被认为是非确定性的。

如果您感兴趣的是约束条件，事情会变得更加复杂。在library(clpfd)中，目标X #> Y, Y #> X没有解决方案，但仍有一个答案。将其与repeat结合起来：无限多个答案和没有解决方案。

此外，目标append(Xs, Ys, [])只有一个解决方案，也只有一个答案，但在许多实现中被认为是非确定性的，因为它会留下一个选择点。

在理想情况下，没有解决方案的答案（除了false），并且只有在有多个答案时才有非确定性。但是，在一般情况下所有这些东西大多都不可判定。

因此，无论何时使用这些概念，请确保知道它们所涉及的级别。最好明确地说明：多个答案，多个解决方案，不会留下（不必要的）选择点。

- false

Answer 2

你需要理解det、semidet和undet之间的区别，这不仅仅是解决方案数量的问题。

由于Prolog中没有循环控制运算符，循环（而不是递归）被构建为“序列生成”谓词（undet），后跟循环体。此外，您可以使用一些findall-group谓词将解决方案存储为列表，并稍后使用member/2谓词进行循环。

因此，您程序的任何部分都是循环结构或通常流程的一部分。因此，在设计det和undet谓词时，几乎意味着预期用法有所不同。如果您可以使用序列，则始终执行undet并将其注释为如此。在swi-prolog中有一个很好的单元测试扩展，可以检查您的谓词是否始终具有相同的det/semidet/undet含义（semidet用于与undet相同的方式使用，但作为“if”结构的头）。

因此，差异是预先设计的，对于已经存在的谓词，不应该提出这个问题。在注释中始终注明预期用法是一个好习惯。

% member(?El, ?List) is undet.

- Sergei Lodyagin

Answer 3

确定性：始终成功并返回一个单一的答案，对于相同的输入始终是相同的。想象一下一个静态列表有三个项目，你告诉你的函数返回值为1。每次你都会得到相同的答案。此外，算术函数也是如此。1 + 1 = 2. X + Y = Z。

半确定性：成功返回一个单一的答案，对于相同的输入始终是相同的，但它可能会失败。想象一下一个函数接受一个数字列表，你询问你的函数是否存在某个数字在列表中。根据给定的列表内容和所询问的数字，它要么存在，要么不存在。

非确定性：成功返回一个单一的答案，但在不同的运行中可能表现出不同的行为，即使是相同的输入。想象任何一种类似于math.random(min,max)函数，比如random/3

本质上，这与选择点的概念完全无关，因为选择点是 Prolog 的一个函数。我认为 Prolog 对这些术语的混淆源于它可以找到一个单一的答案，然后返回并尝试另一个解决方案，你必须使用剪切运算符 ! 显式地告诉它要放弃你的选择点。当使用 Prolog 单元测试 时，了解这一点非常有用。

- G_V

---

在 Prolog 的上下文中，non-deterministic 的使用不当！你提供的例子（真实的 RNG）被认为是超逻辑的。 - repeat