16

SICPを読んでいるときに、論理プログラミングの第4.4章に出くわしました。それから私はPrologプログラミング言語を調べ始め、Prologのいくつかの簡単な割り当てを理解しようとしました。Prologは数値計算に問題があるようだとわかりました。

標準のPrologでの階乗の計算は次のとおりです。

f(0, 1).
f(A, B) :- A > 0, C is A-1, f(C, D), B is A*D.

私が見つけた問題は、2つの補助変数（CおよびD）、新しい構文（is）を導入する必要があること、および問題が元に戻せないことです（つまり、f(5,X)期待どおりに機能しますが、f(X,120)機能しません）。

素朴に、私は少なくともC is A-1, f(C, D)上記がに置き換えられるかもしれないと期待していますf(A-1,D)が、それでも機能しません。

私の質問は、数値計算ではこの余分な「作業」を行う必要があるのに、他のクエリでは行う必要がないのはなぜですか。

私は、一般的に「何をすべきか」に関する情報は「それをどのように行うか」という質問に答えるには不十分であることを理解しています（そしてSICPはそれについて非常に明確です）。したがって、（少なくともいくつかの）数学の問題に関する宣言的知識は、これらの問題を実際に解決するには不十分です。しかし、それは次の疑問を投げかけます：Prologのこの余分な「もの」は、「何をすべきか」が「それをどのように行うか」に答えるのに十分である問題だけに定式化を制限するのにどのように役立ちますか？

4

4 に答える 4

9

is/2非常に低レベルで制限されています。正しく観察しているように、すべての方向で使用できるわけではないため、真の関係ではありません。

可逆演算の場合は、Prologシステムの制約ソルバーを使用します。

たとえば、SWI-PrologのCLP（FD）マニュアルには、次の定義が含まれていますn_factorial/2。

:- use_module(library(clpfd)).

n_factorial(0, 1).
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).

次のクエリ例は、すべての方向で使用できることを示しています。

?- n_factorial(47, F).
F = 258623241511168180642964355153611979969197632389120000000000 ;
false.

?- n_factorial(N, 1).
N = 0 ;
N = 1 ;
false.

?- n_factorial(N, 3).
false.

もちろん、この定義は依然として統一に依存しているため、任意の整数式をプラグインすることはできません。2-2（接頭辞表記である）のような用語は、。-(2,2)と一致しません0。ただし、これを次のように書き直すと、簡単に許可できます。

:- use_module(library(clpfd)).

n_factorial(N, F) :- N #= 0, F #= 1.
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).

クエリの例とその結果：

?- n_factorial(2-2, -4+5).
true .
于 2010-05-26T00:51:40.070 に答える
5

変数を忘れて、and-は、その句 に到達可能にするために配置できる値の名前にすぎないAと考えてください。数式を表すデータ構造について考えてみてください。あなたがプロローグに目標を達成するように頼むならば、それは「成功」に統一されるそのようなアトムまたはルールを見つけようとします。最初の引数を式として解釈した結果と最初の引数を統合しようとします。の変形として考えてください：B(X :- Y).X = (2 + (3 * 4))f(A-1, B)f(A-1,B).(f(A-1,B) :- Z), Z.
is/2eval/2is/2

eval(0, 1-1). eval(0, 2-2). eval(1,2-1).
eval(Y, X-0):- eval(Y, X).
eval(Y, A+B):- eval(ValA, A), eval(ValB, B), eval(Y, ValA + ValB).
eval(4, 2*2).
eval(0, 0*_). eval(0, _*0).
eval(Y, X*1):- eval(Y, X).
eval(Y, 1*X):- eval(Y, X).
eval(Y, A*B):- eval(ValA, A), eval(ValB, B), eval(Y, ValA * ValB).

f(X,120)単純に機能しない理由は>/2、引数がバインドされている場合にのみ機能します（つまり、まだ定義されていないものを他のものと比較することはできませXん）。これを修正するには、そのルールを次のように分割する必要があります。

f(A,B) :- nonvar(A), A > 0, C is A-1, f(C, D), B is A*D.
f(A,B) :- nonvar(B), f_rev(A, B, 1, 1).

% f_rev/4 - only first argument is unbound.
f_rev(A, B, A, B). % solution 
f_rev(A, B, N, C):- C < B, NextN is (N+1), NextC is (C*NextN), f_rev(A, B, NextN, NextC).

更新:(修正済みf_rev/4）
有限領域ソルバーに興味があるかもしれません。そのようなものを使うことについて質問がありました。を使用することで、いくつかの式#>/2と#=/2制限を記述し、それらを解決できます。しかし、これらの述語は、名前をいくつかの属性に関連付けることを可能にするいくつかのプロローグシステムの特別な機能を使用します。これは、制限の交差によって可能な値のセットを絞り込むのに役立つ場合があります。他のいくつかのシステム（通常は同じ）では、処理目標のシーケンスを並べ替えることができます（「一時停止」）。
またmember(X,[1,2,3,4,5,6,7]), f(X, 120)、おそらくあなたの「他のクエリ」が行うのと同じことをしています。

一般的な論理言語に興味がある場合は、カレー言語も参照してください（純粋でない関数はすべて、未定義の値が統一されるまで「一時停止」されます）。

于 2010-05-24T15:11:03.990 に答える
5

この回答では、前の回答と同じようにを使用します。

:- use_module(library(clpfd)).

（後で）簡単に直接比較できるように、ここに示す述語を呼び出しますn_fac/2。

n_fac(N_expr,F_expr) :-
   N #= N_expr,                 % eval arith expr
   F #= F_expr,                 % eval arith expr
   n_facAux(N,F).

この前の答えのようn_fac/2に、算術式の使用を認めます。

n_facAux(0,1).                  % 0! = 1
n_facAux(1,1).                  % 1! = 1
n_facAux(2,2).                  % 2! = 2
n_facAux(N,F) :- 
   N #> 2,
   F #> N,                      % redundant constraint
                                %   to help `n_fac(N,N)` terminate
   n0_n_fac0_fac(3,N,6,F).      % general case starts with "3! = 6"

ヘルパー述語n_facAux/2は、「実際の」作業を次のように委任しますn0_n_fac0_fac/4。

n0_n_fac0_fac(N ,N,F ,F).
n0_n_fac0_fac(N0,N,F0,F) :-
   N0 #< N,
   N1 #= N0+1,                  % count "up", not "down"
   F1 #= F0*N1,                 % calc `1*2*...*N`, not `N*(N-1)*...*2*1`
   F1 #=< F,                    % enforce redundant constraint
   n0_n_fac0_fac(N1,N,F1,F).

n_fac/2比較してみましょうn_factorial/2！

?- n_factorial(47,F).
  F = 258623241511168180642964355153611979969197632389120000000000
; false.
?- n_fac(47,F).
  F = 258623241511168180642964355153611979969197632389120000000000
; false.

?- n_factorial(N,1).
  N = 0
; N = 1
; false.
?- n_fac(N,1).
  N = 0
; N = 1
; false.

?- member(F,[3,1_000_000]), ( n_factorial(N,F) ; n_fac(N,F) ).
false.                          % both predicates agree

わかった！これまでのところ同じです...少しブルートフォーステストをしてみませんか？

？-time（（F1＃\ = F2、n_factorial（N、F1）、n_fac（N、F2）））。
％57,739,784推論、7.112秒で6.415 CPU（90％CPU、9001245リップ）
％実行が中止されました
？-time（（F1＃\ = F2、n_fac（N、F2）、n_factorial（N、F1）））。
％52,815,182推論、6.631秒で5.942 CPU（90％CPU、8888423リップ）
％実行が中止されました

？-time（（N1＃> 1、N2＃> 1、N1＃\ = N2、n_fac（N1、F）、n_factorial（N2、F）））。
％99,463,654推論、16.575秒で15.767 CPU（95％CPU、6308401リップ）
％実行が中止されました
？-time（（N1＃> 1、N2＃> 1、N1＃\ = N2、n_factorial（N2、F）、n_fac（N1、F）））。
％187,621,733推論、18.232秒で17.192 CPU（94％CPU、10913552リップ）
％実行が中止されました

最初の数百の値に違いはありませんN in 2..sup...良いです！

次に進む：次はどうですか（この回答へのコメントで提案されています）？

?- n_factorial(N,N), false.
false.
?- n_fac(N,N), false.
false.

元気にやっています！同一の終了動作...もっと？

?- N #< 5, n_factorial(N,_), false.
false.
?- N #< 5, n_fac(N,_), false.
false.

?- F in 10..100, n_factorial(_,F), false.
false.
?- F in 10..100, n_fac(_,F), false.
false.

大丈夫！まだ同じ終了プロパティ！もう少し深く掘り下げましょう！次はどうですか？

？-inf..10のF、n_factorial（_、F）、false。
...％Execution Aborted％はユニバーサルに終了しません
？-inf..10のF、n_fac（_、F）、false。
false。％はユニバーサルに終了します

D'oh！最初のクエリは終了せず、2番目のクエリは終了します。なんてスピードアップ！:)

経験的な実行時測定を行いましょう！

？-member（Exp、[6,7,8,9]）、F＃= 10 ^ Exp、time（n_factorial（N、F））; 本当。
％328,700推論、0.043秒で0.043 CPU（100％CPU、7660054リップ）
％1,027,296推論、0.153秒で0.153 CPU（100％CPU、6735634リップ）
％5,759,864推論、1.967秒で1.967 CPU（100％CPU、2927658リップ）
％22,795,694推論、23.908秒で23.911 CPU（100％CPU、953351リップ）
本当。

？-member（Exp、[6,7,8,9]）、F＃= 10 ^ Exp、time（n_fac（N、F））; 本当。
％1,340推論、0.000秒で0.000 CPU（99％CPU、3793262リップ）
％1,479推論、0.000秒で0.000 CPU（100％CPU、6253673リップ）
％1,618推論、0.000秒で0.000 CPU（100％CPU、5129994リップ）
％1,757推論、0.000秒で0.000 CPU（100％CPU、5044792リップ）
本当。

わお！もう少し？

？-member（U、[10,100,1000]）、time（（N in 1..U、n_factorial（N、_）、false））; 本当。
％34,511推論、0.004秒で0.004 CPU（100％CPU、9591041リップ）
％3,091,271推論、0.322秒で0.322 CPU（100％CPU、9589264リップ）
％305,413,871推論、90.721秒で90.732 CPU（100％CPU、3366116リップ）
本当。

？-member（U、[10,100,1000]）、time（（N in 1..U、n_fac（N、_）、false））; 本当。
％3,729推論、0.001秒で0.001 CPU（100％CPU、2973653リップ）
％36,369推論、0.004秒で0.004 CPU（100％CPU、10309784リップ）
％362,471推論、0.036秒で0.036 CPU（100％CPU、9997610リップ）
本当。

結論は？

  • この回答で提示されているコードは、必要なだけ低レベルです：忘れてくださいis/2！
  • 冗長な制約は報われる可能性があり、実際に報われます。
  • 算術演算の順序（「上」と「下」を数える）もかなりの違いを生む可能性があります。
  • 「大きい」の階乗を計算する場合は、別のアプローチNを使用することを検討してください。
  • を使用してください！
于 2015-09-04T08:42:02.437 に答える
3

Prologを見るときに覚えておかなければならないことがいくつかあります：

  • 述部を呼び出す場合、暗黙の戻り値はありません。f/2呼び出しから値を取得する場合は、述語の2番目の引数である値を「返す」ために使用できる引数を追加する必要があります。より冗長である一方で、多くの値を簡単に返すことができるという利点があります。

  • これは、呼び出しで引数を自動的に「評価」することは、返す値がなく、実行されないため、実際にはまったく意味がないことを意味します。したがって、ネストされた呼び出しはありません。この点で、Prologはフラットです。したがってf(A-1, D)、最初の引数を呼び出すときf/2は構造体 A-1、または実際-(A, 1)に-は中置演算子です。したがって、呼び出しから呼び出しに値を取得する場合は、foo次のbarように変数を明示的に使用する必要があります。

    foo(..., X), bar(X, ...),

  • したがって、算術評価を強制する特別な述語が必要ですis/2。2番目の引数は、結果を解釈、評価し、変数または数値のいずれかである最初の引数と統合する算術式を表す構造です。

  • 原則として、実行できないほとんどのことを逆方向に実行できます。通常、それは可能である構造に作用する単純な述語だけですが、それが可能であるいくつかの非常に有用なケースがあります。is/2逆方向には機能しません。逆方向に機能した場合は例外的です。

これが、追加の変数が必要であり、CでD置き換えることができない理由C is A-1, f(C, D)ですf(A-1,D)。

（はい、あなたがPrologで電話をかけないことは知っていますが、目標を評価しますが、ここでは機能的な観点から始めました）

于 2010-05-26T00:57:17.307 に答える