終了プロパティを詳細に調査する場合は、後継演算を使用するプログラムが理想的な調査オブジェクトです。それらが何を記述すべきかを事前に知っているので、より技術的な詳細に集中できます。いくつかの概念を理解する必要があります。
ユニバーサルターミネーション
それを説明する最も簡単な方法は、を検討すること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)