Prolog中的"semidet"概念是否已解决? [英] Has the notion of 'semidet' in Prolog been settled?

问题描述

成为Prolog的新手，我遇到了一个非常有趣的

1. 一次最多成功的计算.
2. 一种计算，一旦成功，将不会留下任何选择点.

很明显，第二个隐含着第一个，反之亦然.

阅读线程，我知道第一个是纽马克(Neumerkel)博士的想法，第二个是维勒梅克博士(Wielemaker)，奥基夫(O'Keefe)博士和其他人.

谷歌搜索，我已经看到一些数据库研究人员的意思是半确定性"查询，最多可以回答一个等价问题类，更接近第一个概念.

博士Neumerkel说(在此引用谓词 call_semidet ):

实施可能会有所改善，但在进行优化和标记实际含义需要解决.

那么，含义已经解决了吗?

"det"怎么样?

习惯上根据谓词的数量对谓词进行分类解决方案.根据 SWI-Prolog的定义(见下文)，"det'可以充分发挥作用非确定性(例如并行)计算，只要它承诺现在保证存在的解决方案.因此，以此类推，我猜在那里可能是"det"的两个概念:

1. 一次成功执行的计算.
2. 一次完全成功的计算 ，成功后离开没有选择点.

第一个比较合乎逻辑，但总体上不确定，直到最后计算.一旦找到解决方案，第二个很容易决定，但是程序及其含义取决于特定的搜索策略进行深度优先搜索.

我想知道是否还没有一个社区的共识?为什么不命名这两个不同的概念有何不同?

这是上面SWI-Prolog页面的摘录:

det [确定性]

确定性的简短内容.

确定性

谓词是确定性的，如果它恰好成功一次没有留下选择点.

semidet

速记半确定性

半确定性

半确定性谓词失败或成功一次没有选择点.另请参阅确定性.

解决方案

这是一个非常好的问题！

来自 汞确定性类别> ，其中对此也有相当权威的解释:

6.1确定性类别

对于谓词或函数的每种模式，我们将根据成功的次数对该模式进行分类，以及在产生第一个解决方案之前该模式是否会失败.

如果对谓词或函数的特定模式的所有可能的调用均返回给调用者(终止的调用，则不会引发异常，也不会导致致命的运行时错误)

• 只有一个解决方案，那么该模式是确定性的(det)；
• 要么没有解决方案，要么只有一个解决方案，那么该模式是半确定性的(semidet)；
• 至少有一个解决方案，但可能有更多解决方案，那么该模式为多解决方案(multi)；
• 具有零个或多个解，那么该模式是不确定的(nondet)；
• 具有完全为零的解决方案，即失败而不产生解决方案，则该模式具有确定性的失败(失败).

(重点是我的)

请注意，在此定义中甚至在整个部分中都没有提到是否留下选择点.水星与Prolog不同，但要点是该定义原则上也100％适用于Prolog.显然，它对应于您的变体(1).

我认为这是正确的:是否保留选择点并不重要，例如，取决于系统参数的功能强大和通用性索引是.好的索引方案可能会阻止其他系统引入的选择点的创建.依赖于特定Prolog系统的特定特质并可能从一个版本过渡到另一个版本(引入更好的参数索引等)的概念不是很可靠，也没有太大价值.

的确，我们经常说谓词是确定性的".当我们的意思是:谓词是确定性的且没有选择点时"，但是即使这样，在谓词恰好成功一次的情况下，主点也几乎总是存在.注意，确定性"是指确定性的".也是一个带有其他含义的超负荷形容词.在SWI文档中，这种歧义会延续到半确定性.但是，即使SWI在其他地方:

2.2.2测试半确定性谓词

半确定性谓词是一次失败或仅一次成功的谓词，对于表现良好的谓词，不保留任何选择点.

所以行为不完善的半确定性谓词(?)也会留下选择点...

在讨论中，请特别注意以下几点:乌尔里希(Ulrich)在这里使用较弱且更健壮的概念来获得同时适用于两个定义的谓词.

因此，无论您选择哪种变体， call_semidet/1 都是有用的！由此，报价的含义变得更加清晰.当乌尔里希说:

(可能会改进实现，但在优化和标记实际含义之前，需要先解决该问题.)

很显然，不是是指"semidet"的含义.必须在这两个变体之间解决，但首先应该弄清楚 call_semidet/1 的实际保证:它比人们所想的 Ulrich发布.例如，Jan给出的定义:

call_semidet(目标):-call_cleanup(Goal，Det = true)，(Det == true->真实;投掷(错误(mode_error(塞米德，目标)，_))).

仅仅适用于您的"semidet"的第二个定义.

Being new to Prolog, I came across a very interesting discussion that happened in late 2012. What I noticed was that there were, at the time, two notions of 'semidet' in Prolog community, namely:

1. A computation that succeeds at most once.
2. A computation that, upon success, leaves no choice points open.

Clearly the second one implies the first, but not vice versa.

Reading the thread, I understood that the first one was Dr.Neumerkel's notion, and the second was Drs.Wielemaker, O'Keefe, and others'.

Googling around, I've seen some database researchers mean by 'semi-deterministic' a query that would answer at most one equivalence class, nearer to the first notion.

Dr. Neumerkel says (refering to the predicate called call_semidet there):

The implementation might be improved, but prior to optimizing and bechnmarking the actual meaning needs to be settled.

So, has the meaning been settled?

How about 'det'?

It seems customary to classify predicates according to their number of solutions. According to the SWI-Prolog's definition (see below), a 'det' can do fully nondeterministic (say parallel) computations, provided it commits to a solution which is now guaranteed to exist. So, by analogy I guess there may be two notions of 'det':

1. A computation which succeeds exactly once.
2. A computation which succeeds exactly once and which, upon success, leaves no choice points.

The first one is more logical but undecidable in general until the end of the computation. The second is easily decidable once a solution is found, but procedural and its meaning depends on the particular search strategy Prolog employs, i.e. the depth first search.

I wonder if there is not a community's consensus yet? Why not name these two different concepts differently?

Here's the excerpt from the SWI-Prolog's page above:

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.

解决方案

That's a really excellent question!

From the Mercury determinism categories where this is also explained quite authoritatively:

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).

(emphases mine)

Note that whether or not a choice point is left is not even mentioned in this definition, nor in the whole section. Mercury is not the same as Prolog, but the point is that this definition is in principle 100% applicable also to Prolog. Clearly, it then corresponds to your variant (1).

In my opinion, this is right in this way: Whether or not a choice point is left is rather immaterial, and depends on—for example—how powerful and versatile your system's argument indexing is. A good indexing scheme may prevent the creation of choice points that other systems introduce. A notion that depends on particular idiosyncrasies of a specific Prolog system and may break from one version to the next (with the introduction of better argument indexing etc.) is not very robust, and not of much value.

It is true that we often say "the predicate is deterministic" when we mean: "the predicate is deterministic and no choice points are left", but even so the main point is almost always also in such cases that the predicate succeeds exactly once. Note that "deterministic" is a rather overloaded adjective with other meanings too. In the SWI documentation, this ambiguity carries over to semi deterministic. However, even SWI back-pedals a bit from this rather implementation-oriented definition in 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.

So a semi-deterministic predicate that is not well behaved (?) can also leave choice points...

In the discussion, note especially the following: Ulrich is here using the weaker and more robust notion to obtain a predicate that is applicable for both definitions.

So, no matter which variant you pick, call_semidet/1 is useful! From this, the meaning of the quote becomes clearer. When Ulrich says:

(The implementation might be improved, but prior to optimizing and bechnmarking the actual meaning needs to be settled.)

it is evidently not meant that the meaning of "semidet" must be settled between the two variants, but that it should first be clear what call_semidet/1 actually guarantees: It is a lot more useful than what people thought Ulrich posted. For example, the definition that Jan gives:

call_semidet(Goal) :- 
        call_cleanup(Goal, Det=true), 
        (   Det == true 
        ->  true 
        ;   throw(error(mode_error(semidet,Goal),_)) 
        ). 

works only with your second definition of "semidet".

这篇关于Prolog中的"semidet"概念是否已解决?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！