3

私は一日中これについて考えてきました。最後に認めますが、私は Prolog を思ったほどよく理解していません。

一日の初めに、2 つの s-Number を乗算する後継演算の実装に問題がありました。その構造は次のとおりです。

nat(0).
nat(s(X)):-nat(X).

私の最初の試みはこれでした：

 mul(0,_,0).
 mul(s(F1),F2,P):-mul(F1,F2,Tmp),add(F2,Tmp,P)

これは機能しましたが、クエリmul(X,Y,s(0)) は無限ループで終了しました。なんで？次の投稿を読みました: Prolog successor notation yields incomplete result and infinite loop

そこからわかったこと: add を呼び出す前に mul を呼び出し、両方の mul/3 呼び出しで使用されていない変数が mul/3 述語にある場合、Prolog はバインドされなかった変数の新しい可能性を見つけようとします。したがって、無限ループに陥ります。

この問題を解決するために、最初に add を呼び出しました。

mul(0,_,0).
mul(s(F1),F2,P):-add(F2,Tmp,P),mul(F2,F1,Tmp).

それでできました。それからべき乗関数を実装しようとしましたが、「まあ、今は簡単です。最初に試すのは次のようになります。

pow(_,0,s(0)).
pow(B,s(E),R):-pow(B,E,Tmp), mul(Tmp,B,R).

しかし、R と Tmp の左再帰を防ぐために、最初に mul を配置する必要があります。

簡単!」 男の子、私はとても間違っていました. mul を前に置いたとしても、無限ループに陥らずに実装する方法がわかりません.

どんなアドバイスでも大歓迎です。あなたは私の土曜日の仕事の労力を節約し、私の自尊心を高めることができます! 前もって感謝します。

編集:不足している合計述語を追加しました:

add(0, Y, Y).
add(s(S1), S2, s(Sum)):-  add(S1,S2,Sum).
4

1 に答える 1

4

次の終了条件が保持されることを望みます。

pow(B, E, P) terminates_if b(B), b(E).
pow(B, E, P) terminates_if b(P).

または簡単に

pow(B, E, P) terminates_if b(B), b(E) ; b(P).

それ以上を要求することはできません。それ以上はb(B)一人かb(E)一人で。しかし、そのような場合、非終了を意味する無数の答えが必要になります。もちろん、次のように、常に終了し、すべてのテスト ケースで成功する定義を使用することもできます。

pow(_B、_E、_P)。

残念ながら、その定義は、必要のない他のケースでも成功します。したがって、成功するかどうかだけをテストする場合を除き、より複雑な定義を行う必要があります。

非終了を回避する別の方法は、自然数の別の定義に頼ることです。使用library(clpz)(SWIlibrary(clpfd)はより弱い前駆体です)

pow(B, E, P) :-
   B #>= 0,
   E #>= 0,
   P #= B^E.

しかし、現在は後継算術に固執しています。CapelliC は、 で終了する定義を既に提供していますb(B), b(E)。それでは改善していきましょう！P1 つの方法は、推論の数を有限数に制限するために何らかの方法で使用することです。これを行う方法は、引数間の関係を考慮することです。

の引数間に興味深い関係はありますpow/3か? 私は本当にそれを望みます:

b e ≥ e、b e ≥ b for e、b ≥ 0

それはほぼ真実です。実際には b ≥ 2 を加えることで成立します。

私が完全に間違っていないことを確認するために、これを試してみます1 :

?- M #= 10^150, [B,E,P]ins 0..M, P #= B^E, B #>= 2, P #< E.
false.

証明ではありませんが、これを証明と見なします。

次に定義です。アイデアは、再帰の数を制限するために追加の引数を追加することにより、一般的なケースを処理することです。の 1 つの制限LPと の1 つのpow制限。これらの引数は、追加された場所を明確にするために余分なスペースで区切られています。LMmult

pow(_, 0, s(0)).
pow(0, s(_), 0).
pow(s(B), s(0), s(B)).
pow(s(0), s(s(_)), s(0)).
pow(B, E, P) :-
   B = s(s(_)), E = s(s(_)), P = s(s(s(s(_)))), 
   powx(B, E, P,     P, P).
%                    ^^^^^ added arguments to limit pow and mult

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

mul(0,_,0,_).
mul(s(F1),F2,P,    s(LM)) :-
   mul(F1,F2,Tmp,    LM),
   sum(Tmp, F2, P).   % note: arguments exchanged!

powx(_,0,s(0),    _, _).
powx(B,s(E),R,    s(LP), LM) :-
   powx(B,E,Tmp,     LP, LM),
   mul(Tmp,B,R,      LM).

単純なケースpow(b,b,f)では、オーバーヘッドは最小限に抑える必要があります。新しいケースでpow(f,f,b)は、何らかの方法で制限を下げることでオーバーヘッドが削減される可能性があります。

脚注

1 10 150で試しただけです。一般的な証明はありません。うまくいきますように。何らかの理由で、値を大きくすると、stackoverflow™ が生成されます。P #< Eこれは、多くの再計算を誘発する最後の目標です。それ以外の場合は、10 10 7まで機能します。

于 2016-10-16T18:02:37.340 に答える