バックトラッキングの Prolog 述語から一連の値を生成する方法を理解しようとしています。組み込みの述語between/3は、範囲内のすべての整数をバックトラッキングで一度に 1 つずつ生成するため、その記述方法の例が私の仕事に役立つかもしれません。
既存の Prolog システムでの実装を探しましたが、between/3GNU Prolog の実装は C 関数であり、別の C 関数 "Pl_Create_Choice_Point" を呼び出して、バックトラッキングで追加の値を生成できるようにするトリックがあります。
bet(N, M, K) :- N =< M, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).
実際に:
$ swipl
?- [bet].
% bet compiled 0.00 sec, 1,064 bytes
true.
?- bet(1,5, K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5 n
false.
カットを使用すると、最終的な検索の失敗を防ぎ、組み込みの between/3 動作を正確に回復できます。
bet(N, M, K) :- N < M, K = N.
bet(N, M, K) :- N == M, !, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).
実際に:
?- [bet].
% bet compiled 0.00 sec, 416 bytes
true.
?- between(1,5,K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5.
?- [bet].
% bet compiled 0.00 sec, 240 bytes
true.
?- bet(1,5,K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5.
あなたが本当に求めているのは、選択ポイントを作成する方法です。統合が成功すると、解決策が得られます。@seanmcl の最初の述語では次のようになります。
bet(N, M, K) :- N =< M, K = N.
選択ポイントを得るには、代替案が必要です。Prolog で代替を取得する方法は 2 つしかありません: 明示的な "or":;を使用するか、別のルールを提供することです。@seanmcl のコードは、この状況で慣用的な別のルールを提供します。
別の例を挙げるとmember/2、リスト内のすべての項目に対してソリューションを生成しますが、必要な魔法の C 関数はなく、2 つのルールだけです。
member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).
ここで で何が起こるか見てみましょうmember(X, [1,2])。まず、最初の規則が使用され、 、 、 、 、と[X|_]統一されます。これで統合が成功したため、ソリューションが生成されます。これが失敗した場合 (コンソールで を押すなど)、バックトラックが開始されます。次の選択ポイントは 2 つのルールの間にあるため、次のルールが入力されます。[1,2] と統合し、バインディングを生成してから呼び出されます。再エントリ時に、同じ決定を再度行うことができるため、最初のルールが適用され、バインディングが生成されます。これは解決策です。再びバックトラックすると、どちらの規則も と統一されないため、無害な失敗が発生します。[1,2]X=1_=[2];[_|Xs]Xs=[2]member(X, [2])member(X, [X|_])X=2[]
これが状況を少し理解するのに役立つことを願っています。