Prolog で使用するデータ型について、まとめておきましょう。Prolog では、すべてのデータをまとめて 項 (term) と呼びます。項を細かく分類すると次の種類があります。
| 名前 | 種類 |
|---|---|
| アトム | 英大文字以外から始まる文字列 シングルクオート (') で囲まれた文字列 |
| 数値 | 整数と浮動小数点数 |
| 変数 | 英大文字かアンダーライン (_) で始まる文字列 |
| 複合項 | 項を組み合わせてできる構造体 |
変数は英大文字から始まる文字列だけではなく、アンダーライン (_) から始まる文字列も変数となります。とくに、アンダーラインだけの変数を 無名変数 (anonymous variable) と呼び、プログラム上でその変数の値が不用のときに使われます。たとえば、リストから要素を取り出す述語 retrieve を見てください。
リスト：参照
retrieve(1, [X | Ls], X).
retrieve(N, [Y | Ls], X) :-
N > 1, N1 is N - 1, retrieve(N1, Ls, X).
最初の規則で、変数 Ls は 1 か所しか使われていませんね。そして、次の規則の変数 Y もそうです。Prolog 処理系からすれば、これらの変数に名前を付ける必要はありません。このような場合、無名変数を使うことができます。
リスト：参照 (無名変数を使う場合)
retrieve(1, [X | _], X).
retrieve(N, [_ | Ls], X) :-
N > 1, N1 is N - 1, retrieve(N1, Ls, X).
このように無名変数を使うと、SWI-Prolog で Warning が出なくなります。
次に、複合項について簡単に説明しておきましょう。複合項の基本的な形式は、次のようになります。
func(arg1, arg2, ... argN)
func をファンクタ (functor, 関数子) といいます。複合項は、ファンクタと引数の個数 (arity, アリティ) で定められます。述語と同じ形式になっているところが、ちょっとややこしいところです。述語は物事の関係を表し、複合項はデータ構造を表していることに注意してください。
複合項の例として、二分木を考えてみましょう。二分木の節 (node) を複合項で表すと、次のようになります。
node(Item, Left, Rigth)
Item にデータが入り、Left には左側の子、Right には右側の子が入ります。空の木は void で表せばいいでしょう。簡単な二分木とその複合項を図に示します。
12
／ ＼ => node(12, node(11, void, void), node(13, void, void))
11 13
図：二分木
Prolog による二分木の操作は、そのうちに取り上げてみたいと思っています。
実をいうと、Prolog ではリストも複合項なのです。
[a, b] => .(a, .(b, [ ])).
このように、リストはファンクタ ' . ' を使って表すことができます。これは Lisp のドット表記と同じです。もうひとつ、"abc" のようにダブルクオートで囲まれた文字列を 文字列リスト といいます。これは、その文字を表すアスキーコード (ASCII CODE) のリストと同じです。
"abc" => [97, 98, 99]
Prolog にはデータ型を判断する述語が用意されています。よく使用される述語を説明します。
| 述語名 | 機能 |
|---|---|
| atom(Term) | Term がアトムならば成功します |
| integer(Term) | Term が整数ならば成功します |
| float(Term) | Term が浮動小数点数ならば成功します |
| atomic(Term) | Term がアトム、整数、浮動小数点数ならば成功します |
| compound(Term) | Term が複合項ならば成功します |
| var(Term) | Term が自由変数ならば成功します |
| nonvar(Term) | Term が自由変数でなければ成功します |
atom や atomic で空リスト [ ] を調べると成功します。ご注意くださいませ。
型述語ではありませんが、データが等しいか判断する述語を説明します。
| 述語名 | 機能 |
|---|---|
| Term1 == Term2 | Term1 と Term2 が等しければ成功します |
| Term1 \== Term2 | Term1 と Term2 が等しくなければ成功します |
== は 2 つのデータが等しいことを調べる重要な述語です。== はデータ型によって次のように判断します。
簡単な例を示しましょう。
?- 10 == 10. YES ?- 10 == 10.0. NO ?- abc == abc. YES ?- [a, b, c] == [a, b, c]. YES ?- [[a, b], [10, 20]] == [[a, b], [10, 20]]. YES ?- [[a, b], [10, 20]] == [[a, b], [10, 20.0]]. NO
リストが入れ子になっている場合は、その中の要素も比較します。それから、== はパターンマッチングを行わないことに注意してください。
?- X == 10. NO ?- X is 10, X == 10. X = 10 ; NO
変数 X は自由変数ですが、X == 10 の比較は失敗します。X に 10 をセットしてから比較すると成功します。
それでは、型述語を使って簡単なプログラムを作ってみましょう。入れ子になっているリストの中から要素を取り出して、それをリストにまとめます。これをリストの平坦化といいます。簡単な動作例を示します。
?- flatten([a, [b, [c], d], [e, f]], X). X = [a, b, c, d, e, f]
リストの平坦化は、二重再帰を使うと簡単にプログラムできます。
リスト：リストの平坦化
my_flatten([X | Xs], Ys) :-
my_flatten(X, Ys1), my_flatten(Xs, Ys2), append(Ys1, Ys2, Ys).
my_flatten(X, [X]) :- atomic(X), X \== [].
my_flatten([], []).
flatten は SWI-Prolog に定義されているので、名前を my_flatten としました。最初の規則で、my_flatten を 2 回使っていますね。このように、自分自身を 2 回使っている再帰定義を二重再帰といいます。第 1 引数がリストの場合、この規則が選択されてリストが分解されます。そして、リストの先頭の要素 X を平坦化し、残りのリスト Xs を平坦化して、その結果を append で結合します。
次の規則は、第 1 引数がリスト以外の場合に選択されます。データ型の判定に atomic を使いますが、これだけでは不十分です。空リストを除外するため、X \== [] が必要になります。体部が成功したら、頭部の第 2 引数で X をリストに格納します。最後の規則は、空リストを平坦化すると空リストになることを表しています。
それでは実行してみましょう。
?- my_flatten([a, [b, [c], d], [e, f]], X). X = [a, b, c, d, e, f] ; NO ?- my_flatten([[a, b], [], [c, d]], X). X = [a, b, c, d] ; NO
きちんと動作していますね。もうひとつ、簡単な例題を示しましょう。リストの中から整数を取り出して、それをリストにまとめます。プログラムは次のようになります。
リスト：整数を取り出す
take_integer([X | Xs], Ys) :-
take_integer(X, Ys1), take_integer(Xs, Ys2), append(Ys1, Ys2, Ys).
take_integer(X, [X]) :- integer(X).
take_integer(X, []).
最初の規則で、リストを先頭の要素と残りのリストに分解します。そして、先頭の要素から整数値を取り出し、残りの要素から整数値を取り出して、それを append で連結すればいいわけです。この処理は flatten と同じですね。
次の規則は、第 1 引数が整数であれば成功します。この場合、第 2 引数で X をリストに格納します。最後の規則が選択される場合、第 1 引数はリストと数値以外のデータのはずです。この場合は無条件に第 2 引数を空リスト [ ] にします。append は空リストを省くので、数値だけのリストになります。
それでは、実行してみましょう。
?- take_integer([1, a, [2, b]], X). X = [1, 2] ; X = [1] YES
再試行の動作が不満ですね。これは、1, 2 番目の規則が再試行すると、無条件に 3 番目の規則が成功してしまうからです。この問題を解決するには、カット (cut) というバックトラックを制御する述語を使います。カットを使えば、あらゆる制御構造を実現することができます。カットはまだ説明していないので、この問題はカットのところで再度取り上げることにします。
カット (cut) は、Prolog のバックトラックを制御する唯一の述語です。カットは、最初の実行では無条件に成功しますが、再試行するときには失敗するとともに、それ以前に実行されたゴールの再試行と、次の規則の探索を禁止します。次の図を見てください。
head :- goalA, ..., goalM, !, goalN, ..., goalZ.
~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~
再試行は行われない 再試行する
───→
一方通行
head1 :- goalA, !, goalB.
head2 :- goalC, goalD. ──┐
│
・・・・・・・・ ├─ カットは goalA の再試行だけではなく
│ 次候補節の選択もカットする
head13 :- goalY, goalZ. ──┘
図：カットの動作
カットは ! で表します。規則の中でカットが使用された場合、カットより右側にあるゴール goalN から goalZ は再試行しますが、カットより左側にある goalA から goalM は再試行されません。また、複数の規則 head1 から head13 がある場合は、goalB の再試行はできますが、カットによって goalA の再試行は禁止され、それ以降の規則 head2 から head13 までの実行も禁止されます。
ただし、実際に次候補の規則がカットされるのは、カット (!) というゲートを通り、そこへ戻ろうとしたときに行われる、ということに注意してください。たとえば、規則 goal1 :- goalA, !, goalB. の goalA が失敗した場合は、まだカットは実行されていないので、それ以降の規則が選択されることになります。
簡単な例題として、年齢によってチケットの金額を決める述語 ticket を作りましょう。ある遊園地のチケットは、13 才未満の子供が 500 円で、大人が 1000 円だとしましょう。述語 ticket(Age, Money) は、年齢 Age と代金 Money の関係を表しています。カットを使わないと、次のようになるでしょう。
リスト：チケット代金の計算 ticket(Age, Money) :- Age < 13, Money is 500. ticket(Age, Money) :- Age >= 13, Money is 1000.
2 番目の規則の Age >= 13 は必要です。これがないと、1 番目の規則が再試行したときに無条件で 2 番目の規則が成功し、大人の料金が表示されてしまいます。この場合、カットを使うと、次のように表すことができます。
リスト：チケット代金の計算(カット版) ticket(Age, Money) :- Age < 13, Money is 500, !. ticket(Age, Money) :- Money is 1000.
1 番目の規則が成功してカットが実行されると、再試行のときに 2 番目の規則は選択されない、つまり、カットされるため、大人の料金が表示されることはありません。
次に、リストから整数を取り出す take_integer を再度考えてみましょう。take_integer は再試行したときに、不要な答えを出しました。これは、1, 2 番目の規則が再試行すると、無条件に 3 番目の節が成功してしまうためでした。そこで、カットを使って再試行を禁止しましょう。
リスト：整数を取り出す(カット版)
take_integer([X | Xs], Ys) :-
take_integer(X, Ys1), take_integer(Xs, Ys2), append(Ys1, Ys2, Ys), !.
take_integer(X, [X]) :- integer(X), !.
take_integer(X, []).
1 番目と 2 番目の規則の最後にカットを追加します。これで、1, 2 番目の規則を再試行すると、他節を選択せずに無条件に失敗します。それでは実行してみましょう。
?- take_integer([1, a, [2, b]], X). X = [1, 2] ; NO
これで望ましい動作となりました。
それでは、ほかのプログラミング言語ではお馴染みの条件分岐 if を、カットを使って実現してみましょう。
リスト：カットによる if の実現 if(Test, Then, _) :- Test, !, Then. if(_ , _ , Else) :- Else.
ここで、変わった表現が出てきました。ゴールが変数になっていますね。規則を定義する場合、ゴールには事実や規則のほかに、変数を使うことができるのです。これを メタ変数機構 (meta-variable facility) といいます。ただし、変数の値は実行するときまでに規則または事実がセットされていないといけません。たとえば、数値であったり自由変数のままでは、実行できないのでエラーとなります。
Test が成功したらカットを通って Then が実行されます。Then の再試行に失敗した場合、カットがないと Test が再試行されてしまいます。そして、Test が失敗したすると、次の節が選択され Else が実行されてしまいます。カットがあるからこそ、if と同じ動作をさせることができるのです。
if を使うと、チケットの代金を求めるプログラムは、次のようになります。
リスト：チケット代金の計算(if) ticket(Age, Money) :- if(Age < 13, Money is 500, Money is 1000).
ほかのプログラミング言語に慣れている方は、こちらのプログラムの方がわかりやすいでしょうね。SWI-Prolog では、条件分岐を表す演算子 -> が用意されています。述語 ticket を -> を使って書き換えると、次のようになります。
リスト：チケット代金の計算(->) ticket(Age, Money) :- Age < 13 -> Money is 500 ; Money is 1000.
セミコロン ( ; ) は 選言 (OR) を表します。今までは、別解を求めるために ; を入力しましたが、実は OR の働きをする述語なのです。また、規則の定義で使っているカンマ ( , ) は 連言 (AND) といい、AND の働きをする述語です。まず、Age < 13 をテストし、真であれば Money is 500 を実行し、そうでなければ Money is 1000 を実行します。
セミコロンは条件分岐と組み合わせるだけでなく、規則の中でも使用することができます。この場合、最初の規則が失敗してから、次の規則が試されることに注意してください。次の例を見てください。
foo(a). foo(b). bar(c). bar(d). ?- foo(X) ; bar(X). X = a ; X = b ; X = c ; X = d ; NO
まず foo(X) が実行さるため X の値は a, b となります。そして、foo(X) が失敗してから bar(X) が実行されるので、X の値は c, d となります。
プログラムによっては、実行結果を逆にしたい場合があります。たとえば、integer はデータが整数値か調べますが、整数値以外のデータか調べたい場合もありるでしょう。このような場合、not という述語を使うと結果を逆にすることができます。
?- not(integer(10)). NO ?- not(integer(a)). YES
not [*1] は引数を規則として実行して、その結果が成功ならば not の実行結果は失敗します。実行した規則が失敗ならば、not の実行結果は成功します。最初の例では、integer(10) が成功するので、not は失敗となります。次の例では、integer(a) が失敗するので、not は成功となります。
Prolog の not はカットを使って表すことができます。次の定義を見てください。
リスト：カットの定義 not(X) :- X, !, fail. not(_).
fail は常に失敗する述語です。逆に、常に成功する述語が true です。最初の規則で、ゴール X が実行されます。これが成功すると、カットを実行して fail で失敗します。つまり、X が成功すると not(X) は失敗するのです。カットを通過しているので、再試行するときに not(_). が選択されることはありません。
次に、ゴール X が失敗すると、まだカットを実行していないので、次の規則 not(_). を選択して成功します。つまり、X が失敗すると not(X) は成功するのです。これが述語 not の働きです。
一般に、not は自由変数を含むない規則に適用した方が安全です。自由変数を含んだ規則の場合、その変数がマッチングに成功すると、not は失敗となるからです。次の例を見てください。
foo(a). foo(b). bar(b). bar(c). ?- foo(X), not(bar(X)). X = a YES ?- not(bar(X)), foo(X). NO
foo に定義されていて、bar に定義されていないアトムを求めます。最初の例で foo(X) を実行すると、X は a とマッチングします。次は not(bar(X)) の実行ですが、bar(a) という事実はないので、bar(X) は失敗し not(bar(X)) は成功します。したがって、X の値は a となります。
次の例で、bar(X) の X は自由変数ですね。この場合、bar(b) とマッチングして成功するので、not(bar(X)) は失敗するのです。このように、自由変数を含んでいる規則を not に与えると、思ってもいなかった動作をすることがあります。十分にご注意くださいませ。
簡単な例題として、削除するデータを指定して、リストから等しい要素をすべて削除する述語 remove を作ります。remove(X, Ls, Zs) はリスト Ls から X と等しいデータをすべて削除します。新しいリストは変数 Zs にセットされます。
基本的な考え方は今までのリスト操作と同じです。リストを分解していって、先頭のデータと指定したデータが一致すれば、そのデータを取り除きます。先頭からデータを削除することは簡単ですし、データの一致を調べることは、Prolog のパターンマッチングそのものですから、これも簡単にできます。そのあと、残りのリストから等しい要素を削除する必要があります。これも再帰定義を使えば簡単です。プログラムは次のようになります。
リスト：要素の削除 remove(X, [], []). remove(X, [X | Xs], Zs) :- remove(X, Xs, Zs). remove(X, [Y | Ys], [Y | Zs]) :- X \= Y, remove(X, Ys, Zs).
最初の規則が再帰の停止条件です。空リストは削除する要素がないので、空リストのままです。次の規則が削除する要素を見つけた場合です。残りのリスト Xs から X と等しい要素を remove で削除します。最後の規則は X とリストの先頭要素 Y が等しくない場合です。残りのリスト Ys から X と等しい要素を remove で削除します。そして、削除したリスト Zs の先頭に Y を追加します。
このとき、X と Y が等しくないことをチェックしてください。\= はパターンマッチングに失敗したときに成功する演算子です。この演算子はパターンマッチングを行う演算子 = の結果に not を適用します。簡単例を示しましょう。
?- a \= b. YES ?- a \= a. NO ?- X \= a. NO
最後の例のように、自由変数とのパターンマッチングは成功しますが、\= の結果は NO となります。これで、X と Y が等しくないときにだけ、最後の規則を実行することができます。
もし、X \= Y を省略すると、remove を再試行したときに誤動作します。2 番目の規則を実行したあと、最後の規則を再試行する必要はありませんね。X \= Y を省略すると、再試行で最後の規則が無条件に実行されるため、間違った別解を求めてしまうのです。
それでは実行してみましょう。
?- remove(b, [a, b, c, d], X). X = [a, c, d] ; NO ?- remove(b, [a, b, c, b, c, d], X). X = [a, c, c, d] ; NO ?- remove(b, [1, 2, 3, 4, 5], X). X = [1, 2, 3, 4, 5] ; NO
正常に動作していますね。ちなみに、SWI-Prolog には remove と同じ働きをする述語 delete が定義されています。
Prolog の場合、強制的にバックトラックを発生させて、繰り返し処理を行う方法がよく使われます。これを失敗駆動ループ (failure-driven loop) と呼びます。たとえば、セミコロン ( ; ) を入力せずにすべての解を表示したい場合は、次のように行います。
foo(a). foo(b). foo(c). ?- foo(X), write(X), nl, fail. a b c NO
まず foo(X) が実行され、X = a となります。次の write は、標準出力にデータを出力する述語です。この述語の働きにより X の値 a が出力されます。その次の nl は標準出力へ改行を出力します。最後の fail は、必ず失敗する述語です。
fail によって失敗するので、バックトラックが起こります。nl, write は再試行時は失敗します。したがって foo(X) まで戻り、次の節とマッチングして X = b となり、同じように b が出力されます。これを foo(X) が失敗するまで繰り返します。
このほかに、繰り返しでよく使われる述語に repeat があります。repeat は再試行時にも成功する述語です。この述語を使うと無限回の繰り返しを行うことができます。
それでは簡単な例題として、入力をエコーバックするプログラム echo を作りましょう。
リスト：エコーバック echo :- repeat, read(X), echo_sub(X), !. echo_sub(X) :- X == end_of_file, !. echo_sub(X) :- write(X), nl, fail.
read は Prolog の構文規則にしたがって、標準入力からデータを読み込む述語です。データは引数とマッチングします。echo_sub は、入力の終了をチェックすることと、入力されたデータをエコーバックすることを行います。read はファイルの終了を検出すると、引数にアトム end_of_file をセットします。そこで、まず最初に X と end_of_file が等しいか == を使ってチェックします。end_of_file であればエコーバックする必要はないので、次の節の実行をカットします。
end_of_file でなければ、次の節が実行されます。この節では入力されたデータを write を使って出力します。最後に fail を実行して強制的にバックトラックさせます。repeat を使って繰り返しを行う場合は、fail のように失敗する述語を使って、ループさせる必要があります。
echo_sub が end_of_file を検出した場合は、その実行は成功しますので、echo の最後のゴール ! を実行して終了します。それでは、実行させてみましょう。
?- echo. |: test. test |: prolog. prolog |: ^Z YES
|: は入力を表すプロンプトです。read は Prolog の構文規則に従ってデータをリードするので、最後は必ずピリオド (.) を入力してください。Windows で実行する場合、^Z を入力するとファイルの終了と判断されるので、echo を終了することができます。
echo を単体で使う場合は、echo の最後にあるカットは必要ありません。ところが、ほかの規則と一緒に使う場合には問題があるのです。バックトラックが発生すると、repeat がバックトラックをすべて跳ね返してしまうので、それ以前の規則に戻らなくなってしまうのです。カットが実行されていれば、echo は再試行時に失敗しますので、バックトラックすることができます。repeat を使う場合はカットを忘れないように注意してください。
今度は yes か no を入力するプログラムを作ってみましょう。yes または no 以外のデータが入力された場合は、再度入力を促します。これも repeat を使うと簡単に実現できます。
リスト：yes または no を入力
yes_or_no(X) :-
repeat, write('yes or no >'), read(X), (X == yes ; X == no), !.
プロンプト yes or no > を出力してから read(X) でデータを読み込みます。そして、X が yes か no であれば成功します。それ以外は失敗しバックトラックします。そして repeat によって再び実行が始まります。それでは実行してみましょう。
?- yes_or_no(X). yes or no >n. yes or no >y. yes or no >yes. X = yes ; NO
最後のカットがない場合は、再試行によって再び yes または no の入力が始まります。カットが実行されているので、再試行が失敗し no が表示されるのです。
このほかに、便利な繰り返し述語 between(L, H, V) があります。これは、整数 V が L から H の範囲内 (L =< V =< H) であれば真となる述語です。between は次のように定義 [*2] されます。
リスト：bewteen の定義 between(L, H, L) :- L =< H. between(L, H, V) :- L < H, L1 is L + 1, between(L1, H, V).
たとえば、between(1, 5, X) を実行します。まず、最初の規則が選択されて X = 1 となります。再試行すると次の規則が選択され、L の値を +1 して再帰するので、between(2, 5, X) が実行されます。したがって、X = 2 になります。このように、L の値を +1 しながら再帰していき、L の値が H より大きくなったならば、再帰が停止して実行終了となります。
それでは実際に使ってみましょう。
?- between(1, 5, X), write(X), nl, fail. 1 2 3 4 5 NO
bewteen は失敗駆動ループと組み合わせて利用することができます。たとえば、a を 10 回出力してみましょう。
? between(1, 10, _), write(a), fail. aaaaaaaaaa NO
このように、Prolog でも繰り返しを利用することができますが、Ｃ言語や Perl のようにプログラムできるわけではありません。というのも、Prolog の変数は自由変数のときにのみ値を代入でき、その値を書き換えることができないからです。たとえばＣ言語の場合、階乗を繰り返しでプログラムすると次のようになります。
リスト：階乗の計算 (Ｃ言語)
int fact(int n)
{
int i;
int value = 1;
for(i = 2; i <= n; i++) value *= i;
return value;
}
Ｃ言語の場合、変数 value の値を書き換えることで階乗を計算します。Prolog の場合、このようなプログラムを書くことはできません。ですが、末尾再帰 (tail recursion) の場合、末尾再帰最適化 (tail recursion optimization) が実装されている処理系では、中間コードにコンパイルするときに繰り返しのコードへ変換されます。
末尾再帰を簡単に説明すると、between のように規則のいちばん最後で自分自身を使っている再帰定義のことです。一般に、繰り返しは再帰定義で記述できますが、逆に、 再帰定義を繰り返しで記述することはできません。ところが末尾再帰だけは、簡単な処理で繰り返しに変換できることが知られています。
Prolog や Lisp の場合、コードの最適化を行うときに末尾再帰を繰り返しに変換する処理系が多いのです。もちろん、SWI-Prolog には末尾再帰最適化が実装されています。
ここでもう一度、階乗のプログラムを示します。
リスト：階乗の計算
fact(0, 1).
fact(X, Sum) :-
X > 0, X1 is X - 1, fact(X1, Sum1), Sum is X * Sum1.
このプログラムは fact がいちばん最後ではないので、このままでは末尾再帰最適化が効きません。そこで、次のように書き換えます。
リスト：階乗の計算 (末尾再帰) fact(X, Sum) :- fact(X, 1, Sum). fact(X, Y, Sum) :- X > 0, Y1 is Y * X, X1 is X - 1, fact(X1, Y1, Sum). fact(0, Sum, Sum).
Prolog の場合、規則の名前が同じでも引数の個数が異なれば別の規則として扱われます。Prolog のリファレンスマニュアルでは、fact/2 や fact/3 のように、名前の後ろに引数の個数を付けて表記しています。fact(10, X) は fact(10, 1 , Sum) を呼び出して、10 から 1 までの掛け算を実行します。このとき、第 2 引数に掛け算の途中経過が記憶されます。
このような変数を 累算変数 とか 累算器 といいます。第 1 引数が 0 になると最後の規則が選択されて、X の階乗が Sum に求まります。この場合、fact はいちばん最後に呼び出されるため、末尾再帰最適化により繰り返しに変換されます。
もうひとつ簡単な例題としてフィボナッチ数列を示しましょう。まず、フィボナッチ数列を単純にプログラムします。
リスト：フィボナッチ数列
fibo(N, F) :-
N > 1,
N1 is N - 1, fibo(N1, F1),
N2 is N - 2, fibo(N2, F2),
F is F1 + F2.
fibo(0, 0).
fibo(1, 1).
このプログラムは二重再帰になっているので、とても時間がかかります。これを末尾再帰に変換します。プログラムは次のようになります。
リスト：フィボナッチ数列(末尾再帰)
fibo1(0, 0).
fibo1(N, F) :- fibo1(N, 1, 0, F).
fibo1(1, A1, _, A1).
fibo1(N, A1, A2, F) :-
N > 1, N1 is N - 1, A3 is A1 + A2, fibo1(N1, A3, A1, F).
累算変数 A1 と A2 の使い方がポイントです。現在のフィボナッチ数を変数 A1 に、ひとつ前の値を変数 A2 に格納しておきます。あとは A1 と A2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo1/4 は末尾再帰になっているので、最初のプログラムより高速に実行できます。fibo(25, X) を実行したところ、結果は次のようになりました。実行環境は M.Hiroi のオンボロマシン (WIndows 95, Pentium 166 MHz) です。
二重再帰： 5.6 [s] 849,746 inferences 末尾再帰： 0.0 [s] 98 inferences
inference は推論という意味です。おおざっぱですが、プログラム (規則) を実行した回数を表している、と考えてください。二重再帰のプログラムとは雲泥の差ですね。
ところで、リストを反転する述語 my_reverse は append を使ってリストを連結しています。
リスト：リストの反転
my_reverse([], []).
my_reverse([X | Xs], Ys) :-
my_reverse(Xs, Zs), append(Zs, [X], Ys).
apeend はリストを連結するとき第 1 引数のリストをコピーしているので、このままでは効率の良いプログラムとはいえません。そこで、my_reverse を末尾再帰に変換してみましょう。プログラムは次のようになります。
リスト：リストの反転 (末尾再帰) my_reverse(Xs, Ys) :- my_reverse(Xs, [], Ys). my_reverse([], Xs, Xs). my_reverse([X | Xs], As, Ys) :- my_reverse(Xs, [X | As], Ys).
my_reverse/2 は my_reverse/3 を使って定義します。my_reverse/3 は第 2 引数の変数に逆順のリストを作ります。第 1 引数の先頭要素を取り出して、第 2 引数の先頭に追加していけば、第 2 引数に逆順のリストを得ることができます。
my_reverse/3 の最初の規則で、第 1 引数の要素がなくなったら、第 2 引数と第 3 引数をマッチングして、結果を第 3 引数に取り出します。これが再帰定義の停止条件となります。次の規則でリストを分解し、リストの先頭要素を第 2 引数のリストに追加します。
それでは実行してみましょう。
?- my_reverse([a, b, c], X). X = [c, b, a] ; NO
正常に動作していますね。
再帰定義と比べると、繰り返しは実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しでプログラムするとめちゃくちゃ複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり繰り返し (末尾再帰) へ変換する必要はないと思います。わかりやすいプログラムがいちばんです。