2016-10-03 12 views
2

非常に詳細なDraft proposal for setup_call_cleanup/3があります。`setup_call_cleanup/3`は決定性を移植可能に検出しますか?

私は私の質問のための関連部分を引用してみましょう:

c)のクリーンアップハンドラが1回だけ呼び出されます。遅くともG.の障害発生時よりも以前の瞬間がありません:

Gはtrueまたはfalseの場合、Cは最後の解決策の後と

G.

の最後の観察可能な効果の後に実装依存の瞬間に呼ばれ

そして、この例:統一は backtrackable目標ですので、私の理解で

setup_call_cleanup(S=1,G=2,write(S+G)). 
    Succeeds, unifying S = 1, G = 2. 
    Either: outputs '1+2' 
    Or: outputs on backtracking '1+_' prior to failure. 
    Or (?): outputs on backtracking '1+2' prior to failure. 

が、これは基本的にあります。それは単に再実行で失敗します。したがって、それは、(目標のこれ以上の観察可能な 効果があるでしょうので)ちょうど 拳の実行後にクリーンアップを呼び出す、または の実行されるまで延期するかどうかを決定するために実装次第 です目標は今失敗する。

だから、これは確定性を検出するためには使用できません。 true,fail! などのような組み込みの構造体は、ほんの遡及できません。

目標を2回実行せずに確定性をチェックする方法はありますか? 私は現在SWI-prologのdeterministic/1を使用していますが、確かに は移植性を高く評価しています。

+0

したがって、決定論はどういう意味ですか?選択ポイントの存在 - それは明らかに**実装に依存します**!全く同じ実装で同じ結果に頼ることさえできません。 SWIは、JIT索引付けを時々実行する傾向がありますが、再現性の高い方法で実行するのは困難です。 – false

+0

@false:私は論理的な意味を持っていましたが、トップレベルでは 'X = 2'が確定的であることを意味する限り、誰でもやります。 – mnish

答えて

2

番号setup_call_cleanup/3は、可搬性の方法で決定性を検出することができません。このためには、その自由の実装を制限するでしょう。システムには、インデックス作成の実装方法が異なります。彼らは異なるトレードオフを持っています。最初の引数の索引付けのみを持つものもあれば、それ以上のものもあります。しかし、「より良い」索引付けを提供するシステムは、しばしば全くランダムに動作します。いくつかのシステムでは、非変数の場合にのみ索引付けを行い、他のシステムでは、変数が頭に単純に入るという条項も許されます。 safe tests prior to cutsで「マニュアル」選択肢回避を行う人もあれば、これを省略した人もいます。要するに、これは実際には機能しない問題であり、この分野での移植性を主張することは、システムを遅くすることと同じです。

しかし、それでもなお、次のことがあります。setup_call_cleanup/3が確定性を検出した場合、決定論を決定するために第2の目標を使用する必要はありません!したがって、より効率的に決定論的検出を実装するために使用できます。しかし、一般的なケースでは、目標を2回実行する必要があります。

setup_call_cleanup/3current definitionも、実装が不必要な選択肢も動的に削除できるように作られています。

Callが成功し、choicepointが内部に存在すると、インプリメンテーションは現在の選択ポイントを調べ、決定性が検出された場合にそれらを削除する可能性があります(このような実装は見ていません)。もう1つの可能性は、非同期ガベージコレクションをその間で実行することです。これらのオプションはすべて、現在の仕様でを除外していないです。それらが実装されるかどうかは不明ですが、一部のアプリケーションがそのような機能に依存すると、それが起こる可能性があります。これはPrologで既に数回起こっているので、繰り返しは完全に幻想的ではありません。実際に私はhelp DCGsに特定のケースを考えています。誰が知っている、多分あなたはその道を行くだろう!ここで

はSWIにおけるインデックスは、以前のクエリの歴史にどのように依存するかの例である:ここでは

?- [user]. 
p(_,a). p(_,b). end_of_file. 

true. 

?- p(1,a). 
true ; 
false. 

?- p(_,a). 
true. 

?- p(1,a). 
true.  % now, it's determinate! 

は、第二引数のインデックスは最初の引数のインデックスよりも厳密に弱くなるか、例を次に示します。

?- [user]. 
q(_,_). q(0,0). end_of_file. 

true. 

?- q(X,1). 
true ;   % weak 
false. 

?- q(1,X). 
true. 
+0

ありがとうございました。私はいくつかのよく振る舞う実装の格子について考えていなかったので、選択肢と決定論の存在が規則正しい方法で推論できるようになった。物事はそれよりはるかに関わっていることが判明しました!最適化として使用するあなたのアドバイスはいいです、私は自分のコードでそれを行います。 – mnish

+0

@mnish:ある代数的な傾きがある場合は、[tag:failure-slice]という概念を見ることをお勧めします。あなたはそれをすべて持っている:格子、反鎖、あなたはそれに名前をつける! [ここから](http://stackoverflow.com/a/10141181/772868)。 – false

+0

今は物事がはっきりしています! '切り取り'は実装依存のオブジェクトではなく、スコープ内で保留中の「成功と観測可能な影響」を削減することのみが保証されていると言うのは正しいですか?たとえば 'call(((true; long_failing_branch),!))'では、この '!'は実際にはノーオペレーションですか? – mnish

1

あなたは移植性に興味を持っているとして、Logtalkのlgtunitツールがサポートされ、バックエンドのPrologコンパイラの10のためのポータブルdeterministic/1述語を定義しています

異なるシステムは、異なる組み込み述語その 近似意図された機能を使用すること

注(線1051の周りに開始)

http://logtalk.org/library/lgtunit_0.html

+0

'deterministic((X = 1; X = 2))'と 'deterministic(false)'の場合はどうなりますか? – false

+1

10の実装をサポートしています!私は必ずLogTalkを調べます。 Prolog用QuickCheckもあります。エラー報告は常に難しいです;-) – mnish

+0

@falseサポートされているバックエンドPrologコンパイラの幅広い選択肢と、上記のリンクされているドキュメントでは、あなた自身の質問に対する答えを見つけることができないのはなぜですか? –

関連する問題