41

私はPrologを学び始め、最初に後継表記について学びました。

そして、これは私がプロローグでペアノの公理を書くことについて知るところです。

PDFの12ページを参照してください。

sum(0, M, M).
sum(s(N), M, s(K)) :-
    sum(N,M,K).

prod(0,M,0).
prod(s(N), M, P) :-
    prod(N,M,K),
    sum(K,M,P).

掛け算のルールをPrologに入れました。次に、クエリを実行します。

?- prod(X,Y,s(s(s(s(s(s(0))))))).

つまり、基本的に6の因数を見つけることを意味します。

結果は次のとおりです。

X = s(0),
Y = s(s(s(s(s(s(0)))))) ? ;
X = s(s(0)),
Y = s(s(s(0))) ? ;
X = s(s(s(0))),
Y = s(s(0)) ? ;
infinite loop

この結果には2つの問題があります。

  1. すべての結果が表示されているわけではありません。結果X=6、Y=1が欠落していることに注意してください。
  2. Ctrl + Cを押してから中止を選択しない限り、停止しません。

だから...私の質問は：

  1. 何故ですか？「prod」と「sum」を入れ替えてみました。結果のコードは私にすべての結果を与えます。そして繰り返しますが、それはなぜですか？それでもデッドループです。
  2. それを解決する方法は？

私は無限ループに関する他の答えを読みました。しかし、私は誰かがこのシナリオに基づいて答えてくれることを感謝します。それは私を大いに助けます。

4

2 に答える 2

36

終了プロパティを詳細に調査する場合は、を使用するプログラムが理想的な調査オブジェクトです。それらが何を記述すべきかを事前に知っているので、より技術的な詳細に集中できます。いくつかの概念を理解する必要があります。

ユニバーサルターミネーション

それを説明する最も簡単な方法は、を検討することGoal, falseです。これは、Goalユニバーサルに終了する場合に終了します。つまり、トレーサーを確認するのが最も効果的な方法ではありません。トレーサーは単一の実行パスのみを表示します。しかし、それらすべてを一度に理解する必要があります！また、普遍的な終了が必要な場合は、答えを見ないでください。気が散るだけです。あなたはそれを上で見ました：あなたは3つのきちんとした正しい答えを得ました、そしてあなたのプログラムはループします。したがって、で答えを「オフ」にする方がよいでしょうfalse。これはすべての気晴らしを取り除きます。

失敗スライス

次に必要な概念は、障害スライスの概念です。純粋な単調論理プログラムを取り、いくつかの目標を投入しfalseます。結果として生じる失敗スライスが（普遍的に）終了しない場合、元のプログラムも終了しません。たとえば、次のことを考慮してください。

prod（0、M、0）：- false。
prod（s（N）、M、P）：-
    prod（N、M、K）、false、
    sum（K、M、P）。

これらのfalse目標は、プログラム内の無関係な装飾を削除するのに役立ちます。残りの部分は、prod(X,Y,s(s(s(s(s(s(0))))))).終了しない理由を明確に示しています。そのフラグメントはまったく気にしないので、それは終了しませんP！3番目の引数が終了に役立つことを期待していますが、どのゴールでも発生しないためprod/3、フラグメントはそれがすべて無駄であることを示しています。Pおしゃべりなトレーサーは必要ありません。

多くの場合、最小限の障害スライスを見つけるのはそれほど簡単ではありません。しかし、1つを見つけたら、その終了または非終了プロパティを決定することは簡単です。しばらくすると、直感を使ってスライスを想像し、その理由を使ってそのスライスが関連性があるかどうかを確認できます。

失敗スライスの概念について非常に注目に値するのは、これです。プログラムを改善したい場合は、上記のフラグメントに表示されている部分でプログラムを変更する必要があります。変更しない限り、問題は解決しません。したがって、失敗スライスはプログラムの非常に関連性の高い部分です。

終了推論

これが最後に必要なことです。cTIのような終了推論機能（またはアナライザー）は、終了条件を迅速に特定するのに役立ちます。の推定終了条件を見て、ここprod/3で改善されました！prod2/3

編集：そしてこれは宿題の質問だったので、私は最終的な解決策を投稿していません。ただし、明確にするために、これまでに取得した終了条件は次のとおりです。

    prod（A、B、C）terminates_if b（A）、b（B）。
    prod2（A、B、C）terminates_if b（A）、b（B）; b（A）、b（C）。

したがって、新しいprod2/3プログラムは元のプログラムよりも厳密に優れています。

さて、最終的なプログラムを見つけるのはあなた次第です。その終了条件は次のとおりです。

   prod3（A、B、C）terminates_if b（A）、b（B）; b（C）。

prod2(A,B,s(s(s(s(s(s(0)))))))まず、 ！の失敗スライスを見つけてください。終了することを期待していますが、それでも終了しません。だから、プログラムを取り、手動でfalse目標を追加してください！残りの部分はあなたに鍵を示します！

最後のヒントとして：1つの追加の目標と1つの事実を追加する必要があります。

編集：リクエストに応じて、ここに失敗スライスがありますprod2(A,B,s(s(s(s(s(s(0)))))))：

prod2（0、_、0）：- false。
prod2（s（N）、M、P）：-
   sum（M、K、P）、
   prod2（N、M、K）、false。

sum（0、M、M）。
sum（s（N）、M、s（K））：- false、
    sum（N、M、K）。

の定義が大幅に簡略化されていることに注意してくださいsum/3。それはただ言う：0プラス何でも何でも。もういや。結果として、より専門的なものでさえ、エレガントに終了prod2(A,0,s(s(s(s(s(s(0)))))))する間にループします...prod2(0,X,Y)

于 2012-04-13T12:51:43.237 に答える
17

最初の質問（WHY）は、特に左再帰について知っている場合は、見つけるのがかなり簡単です。Cがsum(A,B,C) バインドされるとAとBをバインドしますが、元のプログラムprod（A、B、C）はそのバインドを使用せず、代わりにA、Bをバインドせずに再帰します。

sum、prodを交換すると、再帰呼び出しのsumから2つの有用なバインディングが得られます。

sum(M, K, P)

これでMがバインドされ、左再帰を終了するために使用されます。製品が可換であることを知っているので、NとMを入れ替えることができます。

sum(0, M, M).
sum(s(N), M, s(K)) :-
    sum(N, M, K).

prod3(0, _, 0).
prod3(s(N), M, P) :-
    sum(M, K, P),
    prod3(M, N, K).

M、K（つまり、sum（K、M、P））を交換する場合、prod3が不明なPで呼び出されると、非終了ループが再び発生しますが、合計になります。

?- prod3(X,Y,s(s(s(s(s(s(0))))))).
X = s(s(s(s(s(s(0)))))),
Y = s(0) ;
X = s(s(s(0))),
Y = s(s(0)) ;
X = s(s(0)),
Y = s(s(s(0))) ;
X = s(0),
Y = s(s(s(s(s(s(0)))))) ;
false.

OT私はcTIレポートに困惑しています：prod3（A、B、C）terminates_if b（A）、b（B）; b（A）、b（C）。

于 2012-04-18T17:20:19.457 に答える