作为Prolog的新手,我在2012年末遇到了一个非常有趣的讨论.我注意到当时在Prolog社区中有两个"semidet"概念,即:
显然,第二个意味着第一个,但反之则不然.
阅读帖子,我明白第一个是Dr.Neumerkel的概念,第二个是Drs.Wielemaker,O'Keefe和其他人.
谷歌搜索,我看到一些数据库研究人员的意思是'半确定'一个查询,它最多可以回答一个等价类,更接近第一个概念.
Dr.Neumerkel说(参考call_semidet那里的谓词):
实施可能会得到改进,但在优化和标记之前,需要解决实际意义.
那么,意义已经解决了吗？
习惯上根据解决方案的数量对谓词进行分类.根据SWI-Prolog的定义(见下文),'det'可以进行完全非确定性(比如并行)计算,只要它提交到现在保证存在的解决方案.因此,通过类比我猜可能有两个'det'的概念:
第一个更符合逻辑,但在计算结束之前一般都是不可判定的.一旦找到解决方案,第二个很容易判定,但程序及其含义取决于Prolog采用的特定搜索策略,即深度优先搜索.
我想知道是否还没有社区的共识？为什么不区别这两个不同的概念呢？
以下是上面SWI-Prolog页面的摘录:
det [determinism]
确定性的缩写.
确定性
如果谓词在没有离开选择点的情况下成功完成一次,则谓词是确定性的.
semidet
半确定性的简写.
半确定性的
半确定性的谓词要么失败要么在没有选择点的情况下成功完成一次.另见确定性.
这是一个非常好的问题!
从Mercury确定性类别来看,这也是非常权威的解释:
6.1确定性类别
对于谓词或函数的每种模式,我们根据它可以成功的次数,以及在生成第一个解决方案之前它是否会失败来对该模式进行分类.
如果所有可能的调用返回到调用者的谓词或函数的特定模式(调用终止,不抛出异常并且不会导致致命的运行时错误)
- 只有一个解决方案,那么该模式是确定性的(det);
- 要么没有解决方案要么有一个解决方案,那么该模式是半决定的(半模式) ;
- 至少有一个解决方案,但可能有更多,然后该模式是多分辨率(多);
- 有零个或多个解决方案,那么该模式是不确定的(nondet); 在没有产生解决方案的情况下失败,那么该模式具有失败的确定性.
(强调我的)
注意,在该定义中甚至在整个部分中都没有提到是否留下选择点.Mercury与Prolog不同,但重点是该定义原则上也适用于Prolog 100%.显然,它对应于您的变体(1).
在我看来,这是正确的:是否留下选择点是相当无关紧要的,并且取决于 - 例如 - 系统的参数索引的强大和多样性.一个好的索引方案可能会阻止创建其他系统引入的选择点.依赖于特定Prolog系统的特定特性并且可能从一个版本突破到另一个版本(引入更好的参数索引等)的概念不是非常强大,并且没有多大价值.
确实,我们经常说"谓词是确定性的",当我们的意思是:"谓词是确定性的,没有留下任何选择点",但即便如此,主要观点几乎总是在这种情况下,谓词只能成功一次.请注意,"确定性"是一个相当过载的形容词,也有其他含义.在SWI文档中,这种模糊性延续到半确定性.然而,即使SWI在其他地方从这个相当面向实现的定义中回过头来:
2.2.2测试半确定性谓词
半确定性谓词是断言要么失败要么只成功一次,对于表现良好的谓词,不留任何选择点.
所以一个表现不佳的半确定性谓词(？)也可以留下选择点......
在讨论中,请特别注意以下内容:Ulrich在此使用较弱且更健壮的概念来获得适用于两种定义的谓词.
所以,无论你选择哪种变体,call_semidet/1都很有用!由此,引用的含义变得更加清晰.乌尔里希说:
(实施可能会有所改进,但在优化和标记之前,需要解决实际意义.)
显然并不意味着"semidet"的含义必须在两个变体之间得到解决,但首先应该明确call_semidet/1实际保证的内容:它比人们认为的 Ulrich发布的内容更有用.例如,Jan给出的定义:
call_semidet(Goal) :-
call_cleanup(Goal, Det=true),
( Det == true
-> true
; throw(error(mode_error(semidet,Goal),_))
).
工作只与你的"semidet"第二个定义.
目前正在使用的分类,例如在SWI-Prolog中,如提到的那样,取自Mercury.所使用的模式名称(det,semidet,multi和nondet)都很差(也不足)的选择.它们不仅是缩写,还需要新用户查找文档以了解其含义!具有讽刺意味的是,对这些模式的含义的描述已经表明了最好的非缩写和清晰的名称.记住,我们正在谈论的解决方案的数量:zero,one,zero_or_one,zero_or_more,one_or_more(也可能是由于它的实用性,error,它可以用来表示一个错误给定的呼叫模式的结果).顺便说一句,这些是Logtalk中使用的模式名称.
正如@mat所描述的那样,将谓词(在给定模式中)的解决方案数量的规范与剩余选择点的问题混合在一起也是一个不好的选择,带有模糊性.代码优化问题与解决方案数量的规范正交.此外,除zero解决方案耗尽外,任何其他模式都可能留下虚假的选择点.因此,这不仅仅是命名不佳det和semidet模式之间的区别.