prolog - 再帰を使用しない階乗計算

Question

プロローグの遡及のみを使用して、再帰を使用せずに階乗計算 (n!) のソリューションを実装しようとしています。例えば：

factorial(0, 1).
factorial(1, 1).
factorial(2, 2).

retroaction(X, Y) :-
factorial(K, Y),
not(K = X),
fail.

retroaction(K, Y) :- factorial(K, Y).   

固定事実factorialを使用して、たとえば、2 の階乗を発見するために述語retroactionを呼び出すと、正しい答えが得られます。

?- retroaction(2, X).
X = 2.

私が実装しようとしている解決策は次のとおりです。

factorial_ret(Number, _) :-
    retractall(factorial(_, _)),
    assertz(factorial(0,1)),
    factorial(X, Y),
    not(X = Number),
    NewNumber is X + 1,
    Factorial is Y * NewNumber,
    retractall(factorial(_, _)),
    assertz(factorial(NewNumber, Factorial)),
    fail.

factorial_ret(Number, Y) :- 
    factorial(Number, Y).

1 より大きい数値の階乗を取得しようとすると、機能しません。誰かが理由を知っていますか？

Answer 1

@lurkerが指摘したように、「ストレージ述語」と「定義述語」を混同しています。factorial/2 の定義が必要なので、 の意味はほとんどありませんretractall(factorial(_,_))。

以下ではretract(mem(N, F))、一時的な値を取得し、最終的な更新のために DB を準備するために使用します。常に mem/2 のインスタンスのみが存在する必要があります。

% replace recursion with a failure driven loop
:- dynamic mem/2.
factorial(X, Y) :-
    assert(mem(0, 1)),
    repeat,
    retract(mem(N, F)),
    (  X == N % done ?
    -> Y = F, % yes, succeed
       !      % but be sure to avoid 'external' backtracking...
    ;  N1 is N + 1,
       F1 is N1 * F,
       assert(mem(N1, F1)),
       fail   % loop: 'goto repeat'
    ).

間の分岐にあるすべてのビルトインはrepeat,...,failバックトラックできないことに注意してください (retract/1 を除く)。

また、そのようなコードは再帰的な定義よりもはるかに遅くなることに注意してください (また、マルチスレッドの SWI-Prolog では機能しません)。

アサート/リトラクトは、グローバル変数として機能するのではなく、「知識ベース」を処理するために必要なため、Prolog プログラマーが早期に利用できるようになったと思います。いくつかのプロローグは、グローバル変数の正当な使用法があるため、グローバル変数用に特化したライブラリ述語を持っています: たとえば、memoizationを参照してください。

PS: 「レトロアクティブ」は、線形システムの安定性理論で使用される用語です。プログラミングについて使用されているのを見たことがありません。

編集@repeat によって報告されたバグがどのように解決されるかを確認することは有益かもしれません: 統合とカットを交換するだけです。X が正の整数であることのテストも必要です。誠に申し訳ありませんが、これは当面の質問とは実際には関係がないと思います。

...
    (  X == N % done ?
    -> !,     % yes, be sure to avoid further backtracking
       Y = F  % unify with the computed factorial
    ;  N1 is N + 1,
...

Answer 2

句に小文字kがあります。not