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

Question

因此，根据我对确定性谓词的理解：

确定性谓词=1解决方案

Non-deterministic谓词=多个解

对于如何检测谓词是否是其中一种或另一种，是否有任何类型的规则？比如看搜索树等等。

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除外)，只有在有多个答案时才会出现不确定性。但是，在一般情况下，所有这些都是无法确定的。

因此，每当您使用这些概念时，一定要确保事物的含义是什么级别的。更确切地说:多个答案，多个解决方案，没有(不必要的)选择点空缺。

Answer 2

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

因为Prolog中没有循环控制操作符，所以循环(不是递归)被构造为‘序列生成’谓词(undet)，后面跟着循环体。此外，您还可以将一些findall-group谓词作为列表存储解决方案，并在以后使用成员/2谓词进行循环。

因此，程序的任何部分要么是循环构造的一部分，要么是通常流的一部分。因此，在设计det和undet谓词时几乎在预期的用途上是有区别的。如果您可以处理一个序列，您总是执行undet并按此方式对其进行注释。swi中有一个很好的单元测试扩展，它可以检查谓词的平均值总是相同的det/semidet/undet ( undet用于使用的方式与undet相同，但作为'if‘结构的头)。

因此，区别在于预先设计，这个问题不应该与已有的谓词联系在一起。这是一个很好的实践，总是在注释中评论预期的用法，比如。

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

Answer 3

Deterministic：对于相同的输入，总是有一个相同的答案成功。假设一个包含三个项的静态列表，然后告诉您的函数返回一个值。你每次都会得到同样的答案。此外，还有算术功能。1+1=2.x+Y= Z.

Semi-deterministic：对于相同的输入，只有一个答案是相同的，但它可能会失败。假设一个函数接受一个数字列表，然后询问您的函数中是否存在某个数字。根据所给列表的内容和所询问的数字，它可以选择，也可以不使用。

Non-deterministic：成功的答案只有一个，但在不同的运行中可以表现出不同的行为，甚至对于相同的输入也是如此。想一想任何类似于math.random(min,max)的随机/3函数

本质上，这与选择点的概念完全不同，因为选择点是Prolog的一个功能。我认为这些术语的Prolog混淆之处在于，Prolog可以找到一个单一的答案，然后返回并尝试另一种解决方案，您必须使用剪切操作符!来告诉它，您想要显式地丢弃您的选择点。

在使用Prolog单元测试时知道这一点非常有用。