Prolog中 'semidet' 的概念已经解决了吗？
Has the notion of 'semidet' in Prolog been settled?
作为 Prolog 的新手，我在 2012 年底遇到了一件非常有趣的事情 discussion。
我注意到当时有两种概念
'semidet' 在 Prolog 社区中，即：
- 最多成功一次的计算。
- 一种计算，一旦成功，就不会留下任何选择点。
显然第二个意味着第一个，但反之则不然。
看了帖子，我知道第一个是
Dr.Neumerkel 的观点，第二个是 Drs.Wielemaker、O'Keefe 等人的观点。
谷歌搜索，我看到一些数据库研究人员的意思是
'semi-deterministic' 最多能回答一个等价的查询
class，更接近第一个概念。
博士。 Neumerkel 说（指的是那里称为 call_semidet 的谓词）：
The implementation might be improved, but prior to optimizing and
bechnmarking the actual meaning needs to be settled.
那么，意思定下来了吗？
'det'怎么样？
习惯上 class根据谓词的数量来确定谓词
的解决方案。根据SWI-Prolog's definition（见下文），一个'det'完全可以做到
非确定性（比如并行）计算，前提是它承诺
现在保证存在的解决方案。所以，通过类比，我猜
可能是'det'的两个概念：
- 只成功一次的计算。
- 只成功一次的计算和，成功后离开
没有选择点。
第一个更合乎逻辑，但一般情况下无法确定，直到最后
计算。一旦找到解决方案，第二个很容易确定，但是
程序及其含义取决于特定的搜索策略 Prolog
采用，即深度优先搜索。
不知道社区还没有达成共识吗？为什么不叫名字
这两个不同的概念有什么不同？
以上是 SWI-Prolog 页面的摘录：
det [determinism]
Short for deterministic.
deterministic
A predicate is deterministic if it succeeds exactly one time
without leaving a choice point.
semidet
Shorthand for semi deterministic.
semi deterministic
A predicate that is semi deterministic either fails or succeeds
exactly once without a choice point. See also deterministic.
这真是个好问题！
来自Mercury determinism categories 那里也有相当权威的解释：
6.1 Determinism categories
For each mode of a predicate or function, we categorise that mode according to how many times it can succeed, and whether or not it can fail before producing its first solution.
If all possible calls to a particular mode of a predicate or function which return to the caller (calls which terminate, do not throw an exception and do not cause a fatal runtime error)
- have exactly one solution, then that mode is deterministic (det);
- either have no solutions or have one solution, then that mode is semideterministic (semidet);
- have at least one solution but may have more, then that mode is multisolution (multi);
- have zero or more solutions, then that mode is nondeterministic (nondet);
- have exactly zero solutions, i.e, fail without producing a solution, then that mode has a determinism of failure (failure).
(强调我的)
请注意，这个定义中甚至没有提到是否留下一个选择点，整个部分也没有提到。 Mercury 与 Prolog 不同，但关键是这个定义原则上 100% 也适用于 Prolog。显然，它对应于您的变体 (1)。
在我看来，这样说是对的：是否留下选择点并不重要，而是取决于——例如——你的能力和多才多艺系统的参数索引是。一个好的索引方案可以防止创建其他系统引入的选择点。一个依赖于特定 Prolog 系统的特殊特性并且可能从一个版本到下一个版本（引入更好的参数索引等）的概念不是很稳健，也没有多大价值。
的确，我们经常说“谓词是确定性的”，意思是：“谓词是确定性的，没有选择点”，但即便如此，要点几乎总是在这种情况下谓词 恰好成功一次 。请注意，“确定性”是一个相当重载的形容词，还有其他含义。在 SWI 文档中，这种歧义延续到半确定性。然而，即使是 SWI 也从 other places:
中这个相当面向实现的定义中退缩了一点
2.2.2 Testing semi-deterministic predicates
Semi-deterministic predicates are predicates that either fail or succeed exactly once and, for well behaved predicates, leave no choicepoints.
所以一个不表现良好 (?) 的半确定性谓词也可以留下选择点...
在讨论中，请特别注意以下内容：Ulrich 在这里使用较弱但更稳健 的概念来获得适用于两种定义的谓词.
因此，无论您选择哪种变体，call_semidet/1 都是有用的！由此，这句话的意思就更加清楚了。当乌尔里希说：
(The implementation might be improved, but prior to optimizing and bechnmarking the actual meaning needs to be settled.)
显然不是意味着“semidet”的含义必须在两个变体之间确定，但首先应该清楚call_semidet/1 实际上保证：它比人们 认为 Ulrich 发布的有用得多。比如Jan给出的定义：
call_semidet(Goal) :-
call_cleanup(Goal, Det=true),
( Det == true
-> true
; throw(error(mode_error(semidet,Goal),_))
).
仅适用于您对“semidet”的第二个定义。
当前使用的分类，例如如@mat 所述，SWI-Prolog 中的内容取自 Mercury。使用的模式名称（det、semidet、multi 和 nondet）是非常糟糕（而且也不充分）的选择。它们不仅是缩写，而且需要新用户查找文档才能理解它们的含义！具有讽刺意味的是，对这些模式中每一个的含义的描述已经暗示了最好的非缩写和清晰的名称。请记住，我们正在谈论解决方案的数量：zero、one、zero_or_one、zero_or_more、one_or_more（并且可能，由于其有用性，error，可用于指示给定的调用模式导致错误）。顺便说一句，这些是 Logtalk 中使用的模式名称。
将谓词（在给定模式下）的解决方案数量的规范与剩余选择点的问题混合在一起也是一个糟糕的选择，充满歧义，正如@mat 也描述的那样。代码优化问题与解决方案数量的规范正交。此外，当解决方案用尽时，除 zero 之外的任何模式都可能留下虚假的选择点。因此，这比命名不当的 det 和 semidet 模式之间的区别更普遍。
作为 Prolog 的新手，我在 2012 年底遇到了一件非常有趣的事情 discussion。 我注意到当时有两种概念 'semidet' 在 Prolog 社区中，即：
- 最多成功一次的计算。
- 一种计算，一旦成功，就不会留下任何选择点。
显然第二个意味着第一个，但反之则不然。
看了帖子，我知道第一个是 Dr.Neumerkel 的观点，第二个是 Drs.Wielemaker、O'Keefe 等人的观点。
谷歌搜索，我看到一些数据库研究人员的意思是 'semi-deterministic' 最多能回答一个等价的查询 class，更接近第一个概念。
博士。 Neumerkel 说（指的是那里称为 call_semidet 的谓词）：
The implementation might be improved, but prior to optimizing and bechnmarking the actual meaning needs to be settled.
那么，意思定下来了吗？
'det'怎么样？
习惯上 class根据谓词的数量来确定谓词 的解决方案。根据SWI-Prolog's definition（见下文），一个'det'完全可以做到 非确定性（比如并行）计算，前提是它承诺 现在保证存在的解决方案。所以，通过类比，我猜 可能是'det'的两个概念：
- 只成功一次的计算。
- 只成功一次的计算和，成功后离开 没有选择点。
第一个更合乎逻辑，但一般情况下无法确定，直到最后 计算。一旦找到解决方案，第二个很容易确定，但是 程序及其含义取决于特定的搜索策略 Prolog 采用，即深度优先搜索。
不知道社区还没有达成共识吗？为什么不叫名字 这两个不同的概念有什么不同？
以上是 SWI-Prolog 页面的摘录：
det [determinism]
Short for deterministic.
deterministic
A predicate is deterministic if it succeeds exactly one time without leaving a choice point.
semidet
Shorthand for semi deterministic.
semi deterministic
A predicate that is semi deterministic either fails or succeeds exactly once without a choice point. See also deterministic.
这真是个好问题！
来自Mercury determinism categories 那里也有相当权威的解释：
6.1 Determinism categories
For each mode of a predicate or function, we categorise that mode according to how many times it can succeed, and whether or not it can fail before producing its first solution.
If all possible calls to a particular mode of a predicate or function which return to the caller (calls which terminate, do not throw an exception and do not cause a fatal runtime error)
- have exactly one solution, then that mode is deterministic (det);
- either have no solutions or have one solution, then that mode is semideterministic (semidet);
- have at least one solution but may have more, then that mode is multisolution (multi);
- have zero or more solutions, then that mode is nondeterministic (nondet);
- have exactly zero solutions, i.e, fail without producing a solution, then that mode has a determinism of failure (failure).
(强调我的)
请注意，这个定义中甚至没有提到是否留下一个选择点，整个部分也没有提到。 Mercury 与 Prolog 不同，但关键是这个定义原则上 100% 也适用于 Prolog。显然，它对应于您的变体 (1)。
在我看来，这样说是对的：是否留下选择点并不重要，而是取决于——例如——你的能力和多才多艺系统的参数索引是。一个好的索引方案可以防止创建其他系统引入的选择点。一个依赖于特定 Prolog 系统的特殊特性并且可能从一个版本到下一个版本（引入更好的参数索引等）的概念不是很稳健，也没有多大价值。
的确，我们经常说“谓词是确定性的”，意思是：“谓词是确定性的，没有选择点”，但即便如此，要点几乎总是在这种情况下谓词 恰好成功一次 。请注意，“确定性”是一个相当重载的形容词，还有其他含义。在 SWI 文档中，这种歧义延续到半确定性。然而，即使是 SWI 也从 other places:
中这个相当面向实现的定义中退缩了一点2.2.2 Testing semi-deterministic predicates
Semi-deterministic predicates are predicates that either fail or succeed exactly once and, for well behaved predicates, leave no choicepoints.
所以一个不表现良好 (?) 的半确定性谓词也可以留下选择点...
在讨论中，请特别注意以下内容：Ulrich 在这里使用较弱但更稳健 的概念来获得适用于两种定义的谓词.
因此，无论您选择哪种变体，call_semidet/1 都是有用的！由此，这句话的意思就更加清楚了。当乌尔里希说：
(The implementation might be improved, but prior to optimizing and bechnmarking the actual meaning needs to be settled.)
显然不是意味着“semidet”的含义必须在两个变体之间确定，但首先应该清楚call_semidet/1 实际上保证：它比人们 认为 Ulrich 发布的有用得多。比如Jan给出的定义：
call_semidet(Goal) :-
call_cleanup(Goal, Det=true),
( Det == true
-> true
; throw(error(mode_error(semidet,Goal),_))
).
仅适用于您对“semidet”的第二个定义。
当前使用的分类，例如如@mat 所述，SWI-Prolog 中的内容取自 Mercury。使用的模式名称（det、semidet、multi 和 nondet）是非常糟糕（而且也不充分）的选择。它们不仅是缩写，而且需要新用户查找文档才能理解它们的含义！具有讽刺意味的是，对这些模式中每一个的含义的描述已经暗示了最好的非缩写和清晰的名称。请记住，我们正在谈论解决方案的数量：zero、one、zero_or_one、zero_or_more、one_or_more（并且可能，由于其有用性，error，可用于指示给定的调用模式导致错误）。顺便说一句，这些是 Logtalk 中使用的模式名称。
将谓词（在给定模式下）的解决方案数量的规范与剩余选择点的问题混合在一起也是一个糟糕的选择，充满歧义，正如@mat 也描述的那样。代码优化问题与解决方案数量的规范正交。此外，当解决方案用尽时，除 zero 之外的任何模式都可能留下虚假的选择点。因此，这比命名不当的 det 和 semidet 模式之间的区别更普遍。