如何使用Prolog代码检查确定性 [英] How instrument Prolog code to check determinism

查看:108
本文介绍了如何使用Prolog代码检查确定性的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我们想通过自动确定性来检测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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆