Prologプログラミング: 記号処理


Prolog で取り扱うデータは,項 (term) と呼ばれます. 以下のものは,項の例です. 項は,下のように木表現 (tree representation) で書いてみると 構造が良くわかります.
        f(a) の木表現       g(X,f(a)) の木表現

              f                      g
              |                     / \
              a                    X   f
                                       |
                                       a

前置記法,挿入記法,後置記法

いくつかの関数記号については, 前置記法,挿入記法,後置記法などの簡略的な記法を使うことができます. たとえば a+b は +(a,b) の挿入記法による書き方です (関数記号は +, 1 番目の引数は a, 2 番目の引数は b ).

プログラムやゴール中で上のような記法を使った場合, Prolog 処理系が自動的に標準的な記法に変換します. Prolog 内部では標準的な記法に従って,項を記憶しています. 標準的な記法は, write_canonical という組込述語で表示できます.


    | ?- write_canonical(a+b).
    +(a,b)
    | ?- write_canonical(1+2+3*4*5).
    +(+(1,2),*(*(3,4),5))
write 述語などで,項を出力する場合は, 逆に内部表現から前置記法,挿入記法,後置記法の形に変換して表示します. カッコも必要な部分だけに付けられます.

    | ?- write(+(a,b)).
    a+b
    | ?- write((1*2)+(3*4)).
    1*2+3*4
Prolog のパターンマッチ (単一化, unification) の動作を理解するには, 項の内部表現がどうなっているのかを理解しておく必要があります. たとえば 1+2*3 は X+Y とはマッチしますが, X*Y とはマッチしません. また 1+2+3 と X+Y をマッチさせると X は 1+2, Y は 3 となります.

    | ?- 1+2*3 = X+Y.
    X = 1,
    Y = 2*3 ? 
    | ?- 1+2*3 = X*Y.
    no
    | ?- 1+2+3 = X+Y.
    X = 1+2,
    Y = 3 ? 
    | ?- write_canonical(1+2+3).
    +(+(1,2),3)
    | ?- 1+2*3 = 1+(2*3).
    yes
    | ?- 1+2*3 = (1+2)*3.
    no
    | ?- 1+2+3 = (1+2)+3.
    yes
    | ?- 1+2+3 = 1+(2+3).
    no
X+Y, 1+2+3 の木表現を下に示します.
        X+Y の木表現          1+2+3 の木表現

              +                      +
             / \                    / \
            X   Y                  +   3
                                  / \
                                 1   2

数式を日本語に

Prolog の記号処理機能を利用して, 与えられた数式を日本語で読むプログラムを作って見ましょう.

    write_siki(X) :-
        atomic(X), write(X).
    write_siki(X+Y) :-
        write(X), write(' と '),
        write(Y), write(' との和').
1つ目の規則は,与えられた式 X が数またはアトム(すなわち atomic )ならば, X をそのまま表示せよ,という意味です. 2つ目の規則は,与えられた式が X+Y という形ならば, 「X と Y との和」と表示せよ,という意味です.

このプログラムを実行すると下のように数式を日本語で表示します.


    | ?- write_siki(1+2).
    1 と 2 との和
しかし数式の部分にまた数式が含まれている場合には, 部分の式はそのまま表示されてしまいます.

    | ?- write_siki(1+2+3).
    1+2 と 3 との和
1+2 の部分も日本語で表示するためには, 以下のように再帰的にプログラミングする必要があります. また X*Y の場合についても規則を付け加えています.

    write_siki(X) :-
        atomic(X), write(X).
    write_siki(X+Y) :-
        write_siki(X), write(' と '),
        write_siki(Y), write(' との和').
    write_siki(X*Y) :-
        write_siki(X), write(' と '),
        write_siki(Y), write(' との積').
実行して見ると,次のような結果になります.

    | ?- write_siki(1+2+3).
    1 と 2 との和 と 3 との和
    | ?- write_siki(1*2+3*4).
    1 と 2 との積 と 3 と 4 との積 との和

数式微分

上のプログラムと同様にして, 数式を変数 x で微分するプログラムを作って見ましょう.

    d(x, 1).
    d(Y, 0) :- atomic(Y), Y \== x.
    d(Y+Z, DY+DZ) :- d(Y, DY), d(Z, DZ).
    d(Y^N, N*Y^N1*DY) :- integer(N), N1 is N-1, d(Y, DY).
それぞれ以下のような規則を表します. 実行例は以下の通りです.

    | ?- d(x^3+x+a, DY).
    DY = 3*x^2*1+1+0 ? 
上のプログラムの 3 行目の規則は, 次のように書いたほうが最初はわかりやすいかもしれません.

    d(Y+Z, W) :-    /* Y+Z の微分 W を求めるには */
        d(Y, DY),   /* Y の微分 DY を求めて */
        d(Z, DZ),   /* Z の微分 DZ を求めて */
        W = DY+DZ.  /* W を DY+DZ とすればよい */
ところが Prolog では,等式は両辺の項が等しいという関係を表しています. したがって,上の例では W = DY+DZ とあるので, W を単純に DY+DZ で 置き換えてかまいません. 置き換えた結果が最初のプログラムなわけです.

では,最初のプログラムがどのように実行されるかを調べてみましょう. 次のようなゴールを入れたとします.


    | ?- d(x+a, W).
  1. まず Prolog は, d の最初の定義を調べます. ゴール d(x+a, W) は, 最初の定義の頭部 d(x, 1) とはマッチしません.
  2. Prolog は次の定義を調べます. ゴールと次の定義の頭部 d(Y, 0) とマッチします (Y = x+a, W = 0 となります)ので, 本体の実行を行います. まず本体の最初の atomic(Y) を実行します. Y はアトミック(数または記号)ではないので, 本体の実行は失敗します. Y および W への代入は取り消されます(バックトラック).
  3. Prolog は次の定義を調べます. ゴールと次の定義の頭部 d(Y+Z, DY+DZ) とマッチします. Y = x, Z = a, W = DY+DZ となります. ここで注意すべき点は,微分結果 W の値です. W は DY+DZ となっていますが, DY や DZ の値はまだ求まっていません(未定義のままです). あとから求めた DY や DZ の値が自動的に W の値に 反映されるわけです. この点が Prolog の変数の特徴です.
  4. 次に Prolog は本体の実行を行います. まず d(Y, DY),すなわち d(x, DY) を実行することにより DY は 1 となります. 次に d(Z, DZ),すなわち d(a, DZ) を実行することにより DZ は 0 となります. したがって, W は 1+0 となります.
このように, Prolog では後から変数の値を決めることができます. 以下の例で確かめてください.

    | ?- DY=1, DZ=0, W=DY+DZ.
    DY = 1,
    DZ = 0,
    W = 1+0 ?
    | ?- W=DY+DZ, DY=1, DZ=0.
    DY = 1,
    DZ = 0,
    W = 1+0 ?
先に DY=1, DZ=0 としてから W=DY+DZ としても, 先に W=DY+DZ としても全く同じ結果になります. これは Prolog の = は,代入ではなく, 両辺が等しいという関係を表しているということを意味します.

このように Prolog では, 計算過程をプログラミングする (手続き的プログラミング) のではなく, 関係をプログラミング (宣言的プログラミング) すれば良いのです. 関係を満たす解は,処理系が自動的に探してくれます.

ただし Prolog は常に万能ではありません. たとえば is を使った計算ではうまくいきません. これは is の計算に方向性があるからです.


    | ?- DY=1, DZ=0, W is DY+DZ.
    DY = 1,
    DZ = 0,
    W = 1 ?
    | ?- W is DY+DZ, DY=1, DZ=0.
    {INSTANTIATION ERROR: in expression}
数値の計算に対しても宣言的プログラミングを可能にする 処理系も存在しています(制約論理型プログラミング言語).

命題論理式の充足可能性

与えられた命題論理式が充足可能かどうかを 判定するプログラムを書いてみましょう. ただし,論理式は以下のような項で表すことにします. また,命題変数は Prolog の変数で表します.

ある命題論理式が充足可能であるのは, 論理式中の各命題変数に t か f をうまく割り当てると その論理式の真理値を t にできる時です. たとえば A /\ B という論理式は, A に t を, B にも t を割り当てれば t になりますから充足可能です. A /\ (-A) という論理式は, A に t を割り当てても f を割り当てても t になりませんから充足不可能です.

まず, NOT を含まない場合について考えてみましょう. 以下のプログラムは,引数に与えられた論理式が t になる場合を探します.


    canbe_t(t) :- !.
    canbe_t(A /\ B) :- canbe_t(A), canbe_t(B).
    canbe_t(A \/ B) :- canbe_t(A); canbe_t(B).
最初の行は命題変数の場合です. 命題変数が充足可能であるためにはその真理値が t でなければなりません. またカット(!)が実行されるので, 命題変数に対しては他の規則は利用されません (このWeb文書の中には,カットについての説明はまだ含まれていません. 参考書,たとえばBratko著「Prologへの入門」の5章など,を読んでください). 2 行目は A かつ B の場合です. A と B の両方が t になる場合を探します. 3 行目は A または B の場合です. A または B の少なくともどちらか一方が t になる場合を探します. セミコロン ; は,または を表します. 以下のように 2 行に分けてもまったく同じことになります.

    canbe_t(A \/ B) :- canbe_t(A).
    canbe_t(A \/ B) :- canbe_t(B).
NOT が入ってくると真理値が f になる場合を探す必要が出てきます. そのための述語 canbe_f の定義を付け加えます. プログラムの全体は以下のようになります.

    canbe_t(t) :- !.
    canbe_t(A /\ B) :- canbe_t(A), canbe_t(B).
    canbe_t(A \/ B) :- canbe_t(A); canbe_t(B).
    canbe_t(-A) :- canbe_f(A).

    canbe_f(f) :- !.
    canbe_f(A /\ B) :- canbe_f(A); canbe_f(B).
    canbe_f(A \/ B) :- canbe_f(A), canbe_f(B).
    canbe_f(-A) :- canbe_t(A).
以下に利用例を示します. 結果が no となった場合は,充足不可能 (常に f ) ということです. したがってその否定の論理式が恒真 (トートロジー) であることがわかります.

    | ?- canbe_t(A /\ (-B)).
    A = t,
    B = f ? 
    | ?- canbe_t(A /\ (B \/ (-A)) /\ (-B)).
    no

練習問題

問題3
数式微分のプログラムで, Y-Z, Y*Z, sin(Y), cos(Y) に 対する規則を付け足しなさい.
問題4
命題論理式の充足可能性のプログラムに (A -> B) に対する規則を付け足しなさい (A -> B は「AならばB」を表します). なお A -> B にはカッコを付ける必要があるので注意してください.

     canbe_t((A -> B)) :- ??? ここに何を書いたら良いか ???
     canbe_f((A -> B)) :- ??? ここに何を書いたら良いか ???
     

最初に戻る 前へ 次へ