Prolog 課題 解答例


再帰的プログラミング

問題1
1! + 2! + … + N! を求める述語 factsum を定義しなさい.
(解答例)
fact と同様に次のように再帰的に定義できます.

     factsum(N) = 0                  (N=0のとき)
                = N! + factsum(N-1)  (N>0のとき)
     
これを単純に Prolog に直して見ると,

     factsum(0, 0).
     factsum(N, S) :-
         N > 0, N1 is N-1,
         factsum(N1, S1),
         S is N!+S1.
     
のようになりますが, N! を計算できないので,このプログラムでは 動きません. N! を fact を使って,変数 F に求めればうまくいきます.

     factsum(0, 0).
     factsum(N, S) :-
         N > 0, N1 is N-1,
         factsum(N1, S1),
         fact(N, F),
         S is F+S1.
     
問題2
正整数 A と B の最大公約数Gを求める述語 gcd(A,B,G) を定義しなさい. A と B の最大公約数は,ユークリッドの互除法により, 次のように再帰的に定義できます.

     gcd(A, B) = B                (A=0のとき)
               = gcd(B mod A, A)  (A=0でないとき)
     
A が 0 でないことの判定は A =\= 0 で行えます. B を A で割った余り R は R is B mod A で求められます.
(解答例)
この Prolog のプログラムは次のようになります.

     gcd(0, B, B).
     gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
     
上のプログラムは正整数だけを対象にしていますが, 実は,整数すべてに対して最大公約数は定義できます (0と0の最大公約数は0とする). プログラムを次のようにすれば OK です.

     gcd(0, B, G) :- G is abs(B).
     gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).
     

記号処理

問題3
数式微分のプログラムで, Y-Z, Y*Z, sin(Y), cos(Y) に 対する規則を付け足しなさい.
(解答例)
数学の教科書をみて,そのまま規則を付け加えれば OK です.

     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(Y-Z, DY-DZ) :- d(Y, DY), d(Z, DZ).
     d(Y*Z, DY*Z+Y*DZ) :- d(Y, DY), d(Z, DZ).
     d(sin(Y), cos(Y)*DY) :- d(Y, DY).
     d(cos(Y), -sin(Y)*DY) :- d(Y, DY).
     
実に自然ですね.

結果の数式を簡単化したくなりますが, これを行うのは結構面倒です.

問題4
命題論理式の充足可能性のプログラムに (A -> B) に対する規則を付け足しなさい. なお A -> B にはカッコを付ける必要があるので注意してください.

     canbe_t((A -> B)) :- ??? ここに何を書いたら良いか ???
     canbe_f((A -> B)) :- ??? ここに何を書いたら良いか ???
     
(解答例)
論理式 (A -> B) は ((-A) \/ B) と同値です. したがって,単純に次のようにすれば OK です.

     canbe_t((A -> B)) :- canbe_t((-A) \/ B).
     canbe_f((A -> B)) :- canbe_f((-A) \/ B).
     
もちろん真理値表から考えることもできます. (A -> B) が t になるのは A が f または B が t の時であり, (A -> B) が f になるのは A が t かつ B が f の時ですから, 次のようにプログラムできます.

     canbe_t((A -> B)) :- canbe_f(A); canbe_t(B).
     canbe_f((A -> B)) :- canbe_t(A), canbe_f(B).
     

リスト処理

問題5
与えられたリスト L の要素の合計 S を求める述語 sum_list(L,S) を定義しなさい.
(解答例)
まず,再帰的に定義してみます.

     sum_list(L) = 0                 (L=[]のとき)
                 = X + sum_list(L1)  (L=[X|L1]のとき)
     
これを Prolog でプログラムしてみると次のようになります.

     sum_list([], 0).
     sum_list([X|L1], S) :-
         sum_list(L1, S1), S is X+S1.
     
どうでしょう.うまく思い付いたでしょうか? Prolog では,うまく考えれば考えるほど プログラムが短くなっていきます.
問題6
与えられたリスト L 中で N 以上の要素だけを集めた リスト M を求める述語 ge_list(L,N,M) を定義しなさい. たとえば ?- ge_list([3,1,4,1,5,9],4,M). の結果は M = [4,5,9] です.
(解答例)
これも,再帰的に定義してみましょう.

     ge_list(L,N) = []                     (L=[]のとき)
                  = [ X | ge_list(L1,N) ]  (L=[X|L1], X>=Nのとき)
                  = ge_list(L1,N)          (L=[X|L1], X<Nのとき)
     
Prolog でプログラムしてみると次のようになります.

     ge_list([], N, []).
     ge_list([X|L1], N, [X|M]) :-
         X >= N,
         ge_list(L1, N, M).
     ge_list([X|L1], N, M) :-
         X < N,
         ge_list(L1, N, M).
     
すべての場合がつくされているのがわかると思います.

コメント

Prolog のプログラミング,特に再帰的プログラミングは 慣れないとわかりにくいものです. 特に,ループ (繰り返し) によるプログラミングに慣れてしまっている 場合にはなおさらです.

しかし実は,再帰的プログラミングのほうが,むしろ繰り返しよりも 自然だともいえるのです. 再帰によるプログラムのほうが正しさを確信しやすいのです.

再帰的プログラミングのコツをまとめておきます.

再帰呼び出しのときには,必ず何かが減っているようにする.
たとえば,数が減る,あるいはリストが短くなる. こうなっていることを確かめておけば, プログラムが停止することが確信できます (プログラムの停止性).
再帰呼び出しの結果は正しく求められるものと仮定して考える.
たとえば, N-1 に対しての結果は正しく求められているとして, そこから N に対しての結果を求める. 一つ短いリスト L に対しての結果は正しいとして, リスト [X|L] に対しての結果を求める. これに注意しておけば, 正しい結果が得られることが確信できます (プログラムの正当性).
再帰の「種」のところに注意する.
たとえば, 0 に対しての答を何にすれば良いか注意する. 空リスト [] に対しての答を何にすれば良いか注意する.
Prolog は面白い言語です. 私自身はずっと Prolog に関連した研究を行っています.
Prolog 処理系(インタープリタ)の開発 (修士課程のとき)
並列 Prolog 処理系の開発 (博士課程のとき)
Prolog マシンの開発 (博士課程のとき)
Prolog 処理系(コンパイラ)の開発 (IBMのとき)
Prolog 言語の拡張 (IBMのとき)
Prolog の自然言語処理への応用 (神戸大学)
ファジィ論理に基づいた Prolog の開発 (神戸大学)
線形論理に基づいた Prolog の開発 (神戸大学)