2

代数を解くプログラムのソースコードを読んでいました。その一部は、0 から 9 までのすべての数字を試す手順です。これはそのソース コードです。

digit(0, 0) :- !.
digit(X, X).
digit(D, N) :-
  N2 is N - 1 ,
  digit(D, N2) .

これを実行して尋ねると、次のようになります。

?- digit(X, 9).
X = 9 ;
X = 8 ;
X = 7 ;
X = 6 ;
X = 5 ;
X = 4 ;
X = 3 ;
X = 2 ;
X = 1 ;
X = 0.

なぜ手続き桁がこれを行うのか、私にはよくわかりません。誰かが私にこれを説明してもらえますか?

回答ありがとうございます。

4

1 に答える 1

3

まず、いくつかの用語です。digitProlog では、「手続き」や「関数」ではなく「述語」と呼ばれます。これが重要なのは、「述語」が関数またはプロシージャーとまったく同じことをしないということです。述語は論理関係の記述であり、述語を呼び出すと、その関係によって定義された論理的な目標を満たすことが試みられます。この目標には、0、1、または多数の解が存在する可能性があります。目標を達成するために、インスタンス化されていない変数または項 (まだ値が割り当てられていないもの) をインスタンス化できます。

の動作を理解するにはdigit、述語が何をするかを理解した上で「読み」たいと思います。このコンテキストでの の意味digit(X, N)は、「X は 0 から N の範囲の数字である」ということです。が 0 の場合、その定義により、Nの答えは 1 つだけ (0) と予想Xされます。もしそうなら、真にN > 0なる答えが複数あると予想されdigit(X, N)ます。このために書かれた規則 (述語) は次のとおりです。

digit(0, 0) :- !.
digit(X, X).
digit(X, N) :- N2 is N - 1, digit(X, N2).

以下で説明するように、Prolog は指定された順序でこれらのルールを照合しようとするため、ここでの順序は重要です。

最初に宣言された事実は次のとおりです。

digit(0, 0) :- !.

これは、0 が 0 と 0 の間の唯一の数字であることを示しています。これは、カットが Prolog に、この目標を満たした後はこれ以上答えを探さないように指示するためです。それdigit(0, 0)が真実であり、目標digit(X, 0).は達成X = 0されます。

次にあります：

digit(X, X).

これは、Xが 0 から までの有効な数字であることを示していXます。カットはありませんので、このルールが満たされた後に後続のソリューションを探すことができます。willなどのゴールdigit(X, 9)はこのルールに一致し、 yield X = 9. digit(X, 9)と入力すると、最初に見つかった結果はX = 9、これが の要求された目標を満たす最初のルールに遭遇したためであることに注意してくださいdigit(X, 9)。

最後に、次のとおりです。

digit(X, N) :- N2 is N - 1, digit(X, N2).

これは、それがX0 から までの数字であるということです(は値をインスタンス化するために使用されます)。したがって、 goal を入力すると、まず上記のように満たされます。次に、そのルールにはカットがないため、Prolog がさらに解を求めてバックトラックするとき、すでに満たされているため、満たすために移動し、その過程で、のルールで説明されているように満たそうとします。これは新しいゴール (元のゴールではない) であるため、上から開始し、同じ論理によって、最初に遭遇し、によって満たされます。したがって、表示される 2 番目の解は(最初に与えられた解が だったことを思い出してください) になります。NX0N - 1N2N-1digit(X, 9)digit(X, X)digit(X, X)digit(X, 9)digit(X, 8)digit(X, N)digit(X, 9)digit(X, X)X = 8X = 8X = 9

このロジックは順番に続き、 、 などを満たしdigit(X, 7)、digit(X, 6)、 などの解を示し、X = 7最終X = 6的に に到達しdigit(X, 0)ます。上記のように、digit(X, 0)は最終的に によって満たされdigit(0, 0)、解決策が得られX = 0、その後、カットのために実行されます。この時点で、すべてのソリューションと仕上げを使い果たしました。

したがって、結果はX = 9, X = 8, ...,X = 0です。

これの鍵は、Prolog が、すべての可能性 (記述された規則によって述語として確立される) を見つけるまで、またはこれらの可能性がカットします。

于 2013-06-23T17:27:19.533 に答える