如何使用Prolog代码检查确定性 [英] How instrument Prolog code to check determinism
问题描述
我们想通过自动确定性来检测Prolog代码检查.因此,本着Ciao断言的精神,我们将宣布:-pred< functor>/< arity>是< determinism>
,其中< determinism>
可以采用以下值:
值 | 说明 |
---|---|
det | 只有一种解决方案,那么该模式是确定性的 |
semidet | 没有解决方案或只有一个解决方案,那么该模式是半确定性的 |
multi | 至少有一个解决方案,但可能会有更多解决方案,那么该模式就是多解决方案 |
nondet | 具有零个或多个解决方案,则该模式是不确定的 |
使用注释调试Prolog
M.Kula-2000年出版
https://pdfs.semanticscholar.org/0d14/e5c3d88cf280ca5b37fae15b58fa998.
但是我们只是使用软剪切:
(调用*-> true; assertion_failure)
对于多个解决方案,我们使用call_nth/2,同时在许多Prolog系统中也可以找到它:
call_nth(Call,Count),(Count> 1-> assertion_failure; true)
最后给出了带有相应重写的代码链接.最后还给出了示例集合.我们可以再显示两个示例.进行以下Prolog文本输入:
:-pred p/1是半成品.p(b).个人电脑).个人电脑).:-pred q/1是det.q(b).q(c).q(c).
包装器产生以下结果:
?-p(a).不□-p(b).是的?- 个人电脑).是的 ;错误:未知模式:assertion_failure(semidet)?-q(a).错误:未知模式:assertion_failure(det)q/1--q(b).是的--q(c).是的 ;错误:未知模式:assertion_failure(det)
开源:
断言包装器
https://gist.github.com/jburse/d5e95099e3d83f6f09b2cb2a91er719pl
断言演示
https://gist.github.com/jburse/d5e95099e3d83f6f09b2cb2a91-emo719pl
We want to instrument our Prolog code by automatic determinism
checks. So in the spirit of Ciao assertions we would declare
:- pred <functor>/<arity> is <determinism>
, where <determinism>
can take the values:
Value | Description |
---|---|
det | have exactly one solution, then that mode is deterministic |
semidet | either have no solutions or have one solution, then that mode is semideterministic |
multi | have at least one solution but may have more, then that mode is multisolution |
nondet | have zero or more solutions, then that mode is nondeterministic |
https://www.mercurylang.org/information/doc-latest/mercury_ref/Determinism-categories.html
Here is an example expected behaviour, take this Prolog text input:
:- pred r/1 is multi.
r(b).
r(c).
r(c).
And then this query output:
?- r(a).
Error: Unknown pattern: assertion_failure(multi)
?- r(b).
Yes
?- r(c).
Yes ;
Yes
Since most Prolog systems have term expansion and goal expansion, it seems to be a suitable language to inject such assertions at compile time by some Prolog code itself. How would one go about and implement such an instrumentation?
We can analyse the determinism categories by the errors situations they need to detect. There are two different error situations which span all the determinism categories. The error situations refer to the goal that is called with the given predicate indicator:
Value | Finite Failure | Multiple Solutions |
---|---|---|
det | Forbidden | Forbidden |
semidet | Allowed | Forbidden |
multi | Forbidden | Allowed |
nondet | Allowed | Allowed |
For the determinism categories 'nondet', nothing needs to be done. For the other determinism categories we install a wrapper. This wrapper will have the given predicate indicator and call a auxiliary predicate that collects the rules of the given predicate indicator. For finite failure we find this suggestion in the literature:
Debugging Prolog Using Annotations
M. Kula - Published 2000
https://pdfs.semanticscholar.org/0d14/e5c3d88cf280ca5b37fae15b58fde9986544.pdf
But we simply use the soft cut instead:
(Call *-> true; assertion_failure)
For multiple solutions we use call_nth/2, which is also found in many Prolog systems meanwhile:
call_nth(Call, Count), (Count > 1 -> assertion_failure; true)
A link to the code with the corresponding rewriting is given at the end. Also collection of examples is given at the end. We can show two more of the examples. Take this Prolog text input:
:- pred p/1 is semidet.
p(b).
p(c).
p(c).
:- pred q/1 is det.
q(b).
q(c).
q(c).
The wrapper produces these results:
?- p(a).
No
?- p(b).
Yes
?- p(c).
Yes ;
Error: Unknown pattern: assertion_failure(semidet)
?- q(a).
Error: Unknown pattern: assertion_failure(det)
q/1
?- q(b).
Yes
?- q(c).
Yes ;
Error: Unknown pattern: assertion_failure(det)
Open source:
Assertion Wrapper
https://gist.github.com/jburse/d5e95099e3d83f6f09b2cb2a91da719c#file-assertion-pl
Assertion Demo
https://gist.github.com/jburse/d5e95099e3d83f6f09b2cb2a91da719c#file-demo-pl
这篇关于如何使用Prolog代码检查确定性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!