これまでのプログラムでは、既にある規則や事実を使って新しい述語を定義するものでした。今度は、自分自身の定義を使って新しい述語を定義する 再帰定義 (recursive definition) について説明します。再帰定義は、ほかのプログラミング言語でも使われる、とても重要な方法です。
簡単な例として、階乗の計算を考えてみましょう。
階乗の定義 0! = 1 n! = n * (n - 1)!
階乗の定義からわかるように、 n! は (n - 1)! の値がわかれば求めることができます。つまり、階乗自身を使って階乗を定義するという、再帰的な構造になっています。これを Prolog でプログラムしてみましょう。
リスト：階乗の計算
fact(0, 1).
fact(X, Sum) :-
X > 0, X1 is X - 1, fact(X1, Sum1), Sum is X * Sum1.
述語 fact(X, Sum) は X! = Sum という関係を表しています。最初の事実 fact(0, 1). で 0! = 1 を定義し、次の規則 fact(N, Sum) で、n! = n * (n - 1)! を計算しています。この中で注目すべき点は、(n - 1)! を求めるときに述語 fact を再び実行していることです。このように、自分自身を使って規則を定義することを再帰定義といいます。
述語の定義に自分自身を使うことができるなんて、不思議に思われるかもしれません。ところが、再帰定義は特別なことではありません。たとえば、Ｃ言語, Lisp, Perl, Python, Ruby など、ほとんどのプログラミング言語で再帰定義を使うことができます。
とくに Lisp や Prolog では、再帰定義を積極的に活用してプログラミングを行うため、初心者が覚えるべき基礎テクニックのひとつにすぎません。慣れるまで苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
それでは、このプログラムの動作を詳しく説明します。次の図を見てください。
1: fact(3, Z)
2: fact(3, Sum) % X = 3
3: X > 0 % 3 > 0
4: X1 is X - 1 % X1 = 3 - 1 (2)
5: fact(X1, Sum1) % fact(2, Sum1)
6: fact(X, Sum) % X = 2
7: X > 0 % 2 > 0
8: X1 is X - 1 % X1 = 2 - 1 (1)
9: fact(X1, Sum1) % fact(1, Sum1)
10: fact(X, Sum) % X = 1
11: X > 0 % 1 > 0
12: X1 is X - 1 % X1 = 1 - 1 (0)
13: fact(X1, Sum1) % fact(0, Sum1)
14: fact(X, Sum) % X = 0
15: X > 0 % 0 > 0 失敗
16: fact(0, 1) % 成功
% Sum1 = 1
17: Sum is X * Sum1 % Sum = 1 * 1
% Sum1 = 1
18: Sum is X * Sum1 % Sum = 2 * 1
% Sum1 = 2
19: Sum is X * Sum1 % Sum = 3 * 2
20: Z = 6
図：述語 fact の実行
3 の階乗を求めるため、fact(3, Z) を実行します。まず頭部 fact(X, Sum) のマッチングで、X の値が 3 となります (2 行目)。次に体部を実行します。X > 0 は成功しますね。そして、X1 is X - 1 を計算して X1 = 2 となります。
さて、問題の fact(X1, Sum1) ですが、X1 = 2 ですから fact(2, Sum1) を実行します。再帰定義されている規則は特別なものではなく、いままで説明してきた規則と同じように実行されます。すなわち、fact(2, Sum1) と頭部がマッチングする規則を選択して実行します。
規則を選択する場合、規則で使われている変数は自由変数の状態です。fact(2, Sum1) と fact(X, Sum) をマッチングするときも、X や Sum は自由変数です。この場合、3 とマッチングした変数 X を、自由変数に戻すわけではありません。規則を選択する場合、Prolog は規則で使用する変数を新しく用意するのです。ここが再帰定義を理解するポイントのひとつです。
もう一度、fact の実行を見てください。規則の実行を色を変えて表しています。fact(3, Z) とマッチングした規則は黒で表しています。この規則では、X の値は 3 で X1 の値は 2 ですね。次は、fact(2, Sum1) とマッチングした規則 (青) です。新しい変数が用意されてからマッチングが行われるので、今度はこの規則を実行している間、X の値は 2 になるのです。このように、変数名は同じでも、異なる変数として扱われることに注意してください。
あとは同様に、fact(1, Sum1) を実行し、fact(0, Sum1) を実行します。ここで、fact(X, Sum) が選択され X = 0 となります (14 行目)。ところが、体部の X > 0 で失敗します (15 行目)。今度は、fact(0, 1) とのマッチングに成功します。fact(0, 1). は事実ですから、これ以上 fact(X, Sum) を実行することはありません。これを 停止条件 といいます。ここが再帰定義でいちばん大切なポイントです。
再帰定義をプログラムする場合、この停止条件を考慮しないと同じ規則を無限に実行する、つまり無限ループとなるため、プログラムは正常に動作しません。ご注意ください。
fact(0, 1) とマッチングしたので、変数 Sum の値は 1 となります。したがって、fact(0, Sum1) の Sum1 は 1 となります。そのあと、Sum is X * Sum1 を計算します。このとき、X の値は 1 なので Sum の値は 1 となります (17 行目)。あとは同じように fact(1, Sum1) の値が求まり、fact(2, Sum1) の値が求まり、最後に fact(3, Sum) の値が求まって、Z = 6 という答えを求めることができました。
このように、Prolog の変数は規則を実行している間だけ有効です。このような変数を 局所変数 (local variable) といいます。局所変数は Prolog だけではなく、近代的なプログラミング言語では必要不可欠な機能のひとつです。
ところで、次から リスト (list) の話に入ります。リストは複数のデータを格納することができる基本的なデータ構造です。リストといえば Lisp ですが、Prolog でもリストを扱うことができます。とくに、パターンマッチングによるリストの操作はとても便利です。
実は、リストの操作と再帰定義はとても相性が良い、というよりも、Prolog の場合は再帰定義を使わないとリストの操作ができない、といってもいいでしょう。次回から再帰定義をバシバシ使いますので、覚悟してくださいね。
リスト (list) は、複数のデータを一列に並べたデータ構造です。Prolog で扱うリストは、基本的には Lisp のリストと同じです。Prolog では、リストの両側を [ と ] で囲んで表し、データはカンマ ( , ) で区切ります。簡単な例を示しましょう。
[spring, summer, autumn, winter] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [X, Y, Z] [[a, b, c], [d, e, f], [g, h, i]]
リストはデータを入れる容器と考えることができます。リストの中に入っているデータを要素といいます。要素は Prolog で扱うことができるデータであればなんでもかまいません。最初の例では、四季のデータを格納しています。次の例では数値を格納しています。そして、変数を格納することもできますし、リストの中にリストを格納することもできます。
このように、リストに格納する要素に制限はありません。100 個でも 1000 個でも、Prolog システムが許容する範囲内であればいくつでも格納することができます。また、データが入っていないリストというものもあります。これを 空リスト といって [ ] で表します。
リストの長所は、要素の追加や削除が簡単にできるところです。Prolog の場合、パターンマッチングを使って柔軟にリストを操作することができます。
リストはほかのリストとパターンマッチングさせることができます。次の例を見てください。
?- [spring, summer, autumn, winter] = [A, B, C, D]. A = spring B = summer C = autumn D = winter ; NO
= はパターンマッチングを行う演算子です。このように、リスト同士のマッチングは先頭の要素から順番に行います。
パターンマッチングを使って、リストを分解することができます。次の例を見てください。
?- [spring, summer, autumn, winter] = [X | Y]. X = spring Y = [summer, autumn, winter] ; NO
X と Y の間にある "|" に意味があります。| でリストを区切ると、それより後ろの変数は 残りのリストすべて とマッチングします。この場合、X が先頭の要素とマッチングし、spring を取り除いた残りのリストと Y がマッチングします。もう少し例を見てみましょう。
?- [spring, summer, autumn, winter] = [X, Y | Z]. X = spring Y = summer Z = [autumn, winter] ; NO
この例では、X が spring、Y が summer にマッチングし、残りのリストと Z がマッチングします。このように、| の前にはいくつでも変数を置くことができますが、| の後ろには変数をひとつしか置けません。「残りのリストすべて」とマッチングするのですから、複数の変数を書いても意味がありません。また、| を同じリストに複数書くこともできません。次の例はすべてエラーになります。
[X | Y, Z] % | の後ろに変数が複数ある [X | Y | Z] % | が複数ある [ | X] % | の前にデータがない [X | ] % | の後ろにデータがない
Lisp ユーザーであれば、[X | Y] がドットリスト (X . Y) と同じであることに気づかれたことでしょう。Lisp では、関数 car でリストの先頭の要素を、関数 cdr で先頭要素を取り除いた残りのリストを求めることができます。Prolog の場合はパターンマッチングを行うことで、リストを分解することができるのです。
それでは具体的にリスト操作を行う述語を作ってみましょう。先頭の要素を求める述語 first と、先頭の要素を取り除いた残りのリストを求める述語 rest は、リストのパターンマッチングを使えば簡単にプログラムできます。
リスト：first と rest first([X | Ys], X). rest([X | Ys], Ys).
これだけで OK です。では、実行してみましょう。
?- first([a, b, c, d], Z). Z = a ; NO ?- rest([a, b, c, d], Z) Z = [b, c, d] ; NO
first も rest もリストと [X | Ys] をマッチングさせ、必要なデータを取り出します。Ｃ言語や Lisp では、実行結果を関数の返り値として返しますが、Prolog の場合は変数とマッチングさせることで実行結果を受け取ります。この例では、第 1 引数にリストを与え、その結果を第 2 引数の変数で受け取ります。
次に、リストの先頭にデータを追加する述語を作りましょう。
リスト：先頭にデータを追加 add_to_list(X, Ls, [X | Ls]).
これも簡単ですね。実行結果を示します。
?- add_to_list(a, [b, c, d], Z). Z = [a, b, c, d] ; NO
add_to_list(X, Ls, Zs) は、リスト Ls の先頭に X を追加したリストが Zs となります。Lisp では cons という関数がリストの合成を行いますが、Prolog ではパターンマッチングで行うことができます。
今度は、再帰定義を使ってリストを操作する述語を作りましょう。実は、リスト操作と再帰定義は相性がとても良いのです。まず、リストの n 番目の要素を求めるプログラムを作ってみましょう。Lisp ではリストの要素を 0 から数えますが、エジンバラ Prolog [*1] では 1 から数えるようなので、これから作るプログラムもそれに従います。
リストは [X | Ls] とマッチングすると、X には先頭の要素が、Ls には残りのリストがセットされますね。したがって、n 番目の要素を求めるには、Ls とマッチングしたリストに対して n - 1 番目の要素を求めればいいわけです。これは、再帰定義を使えばプログラムすることができます。プログラムは次のようになります。
リスト：参照
retrieve(1, [X | Ls], X).
retrieve(N, [Y | Ls], X) :-
N > 1, N1 is N - 1, retrieve(N1, Ls, X).
述語 retrieve(N, Ls, X) は、リスト Ls の N 番目の要素が X である、という関係を表しています。最初の規則で、N が 1 の場合は先頭の要素を取り出します。これが再帰定義の停止条件となります。
次の規則では、再帰定義を使ってリストを分解しています。第 2 引数に与えられるリストは [Y | Ls] とマッチングするので、変数 Ls には残りのリストがセットされます。あとは、N の範囲をチェックし N1 is N - 1 を計算して、retrieve(N1, Ls, X) を実行すればいいわけです。ここで、リスト Ls の N - 1 番目の要素が求まります。つまり、第 2 引数のリストの N 番目の要素が変数 X にセットされます。それでは実行 [*2] してみましょう。
?- retrieve(3, [a, b, c, d], X). X = c ; NO
正常に動作していますね。なお SWI-Prolog には retrieve と同様の動作を行う述語 nth1 があります。
次は、リストの n 番目にデータを挿入する述語 insert_at を作りましょう。insert_at(N, X, Ls, Zs) は、リスト Ls の N 番目にデータ X を挿入します。新しいリストは変数 Zs にセットされます。基本的な考え方は述語 retrieve と同じです。リストを分解して、N が 1 になったらリストの先頭にデータを挿入します。これは簡単にできますね。あとは、取り除いたデータを再度組み立てていけばよいのです。プログラムは次のようになります。
リスト：挿入
insert_at(1, X, Ls, [X | Ls]).
insert_at(N, X, [Y | Ls], [Y | Zs]) :-
N > 1, N1 is N - 1, insert_at(N1, X, Ls, Zs).
最初がリストの先頭にデータを挿入する規則です。次の規則で、再帰定義を使ってリストを分解していきます。この中で、変数 Zs の使い方がポイントです。
insert_at の 3 番目の引数 [Y | Ls] で、リストは先頭要素 Y と残りのリスト Ls に分解されます。このリスト Ls に対して最後に insert_at を実行していますが、この結果は変数 Zs にセットされます。ここで 2 行目の第 4 引数が [Y | Zs] になっていますね。Zs に先頭要素 Y を追加することで、分解したリストを再び組み立てているのです。
それでは、実行してみましょう。
?- insert_at(3, x, [a, b, c, d], Z). Z = [a, b, x, c, d] ; NO
次は、データを削除する述語 remove_at を作りましょう。remove_at(N, Ls, Zs) はリスト Ls の N 番目の要素を削除します。新しいリストは変数 Zs にセットされます。基本的な考え方は述語 insert_at と同じです。リストを分解して、N が 1 になったらリストの先頭要素を削除するだけです。プログラムは次のようになります。
リスト：削除
remove_at(1, [X | Ls], Ls).
remove_at(N, [X | Ls], [X | Zs]) :-
N > 0, N1 is N - 1, remove_at(N1, Xs, Zs).
N > 0, N1 is N - 1, remove_at(N1, Ls, Zs). /* 修正 (2011/02/25) */
最初の規則は、N が 1 の時にリストの先頭要素を削除することを表しています。先頭要素を取り除いたリスト Ls を第 3 引数に指定します。これは述語 rest と同じですね。次の規則では、insert_at と同様にリストを分解して remove_at を再帰呼び出しします。そして、Zs の先頭に X を追加して、分解したリストを再び組み立てます。
それでは実行してみましょう。
?- remove_at(3, [a, b, c, d], Z). Z = [a, b. d] ; No
今度は、リストの長さを求めるプログラムを作ります。リストの長さとは、リストに格納されている要素の個数のことです。この場合、入れ子になっているリストは、ひとつの要素として数えます。入れ子のリストに格納されている要素は数えません。また、空リスト [ ] は長さ 0 とします。
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => 10個
[ [1, 2], [3, 4], [5, 6], [7, 8] [9, 10] ] => 5 個
~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~ ~~~~~~~
図：リストの長さ
このように、リストは階層構造を作ることができますが、いちばん上の階層を トップレベル といいます。そして、リストの一番上の要素に対して機能することを、トップレベルの要素に対して働く と表現します。
プログラムは簡単です。リスト Y を先頭の要素 X と残りのリスト Xs に分解すると、リスト Y の長さはリスト Xs の長さに 1 を足した値になります。リストを分解していけば必ず空リストになりますから、空リストの長さを 0 と定義すれば、リストの長さを求めることができます。プログラムは次のようになります。
リスト：リストの長さ my_length([], 0). my_length([X | Xs], N) :- my_length(Xs, N1), N is N1 + 1.
SWI-Prolog には、リストの長さを求める述語 length が定義されているので、名前は my_length としました。最初の規則が「空リストの長さは 0 である」を表しています。次の規則でリストを分解します。再帰定義で残りのリスト Xs の長さを N1 に求めます。そして、その値を +1 すれば求めるリストの長さ N になります。
それでは実行してみましょう。
?- my_length([1, 2, 3, 4, 5], X). X = 5 ; NO ?- my_length([[1, 2], [3, 4], [5, 6]], X). X = 3 ; NO
次は、2 つのリストをひとつのリストに結合する述語を作りましょう。
[a, b, c] + [d, e, f] => [a, b, c, d, e, f]
[[a, b], c, d] + [[e, f], g, h] => [[a, b], c, d, [e, f], g, h]
図：リストの結合
リストの結合は、1 番目のリストの後ろに 2 番目のリストの要素を追加する、と考えると難しくなってしまいます。この場合は逆に考えて、1 番目のリストの最後の要素から 2 番目のリストの先頭へ追加していく、と考えた方が簡単に実現できます。
たとえば、[a, b, c] と [d, e, f] であれば、[d, e, f] に c を追加して [c, d, e, f] を作り、そこに b を追加して [b, c, d, e, f] を作り、最後に a を追加して [a, b, c, d, e, f] とするわけです。最後尾のデータを求めるには再帰を使えば簡単です。プログラムは次のようになります。
リスト：リストの結合 my_append([], Xs, Xs). my_append([X | Ls], Ys, [X | Zs]) :- my_append(Ls, Ys, Zs).
SWI-Prolog には、リストを結合する述語 append が定義されているので、名前は my_append としました。最初の規則は「空リストと Xs を結合すると Xs である」ということを表しています。リストを分解していくと、最後は空リストになるので、この規則が再帰定義の停止条件になります。
次の規則で、第 1 引数のリストを分解します。第 1 引数のリストが空リストになると、変数 Zs は第 2 引数のリストとマッチングします。あとは、変数 Zs の先頭に第 1 引数の先頭要素 X を加えていけばいいわけです。
それでは実行してみましょう。
?- my_append([a, b, c], [d, e, f], Z). Z = (a b c d e f) ; NO ?- my_append([[a, b], [c, d]], [[e, f], [g, h]], Z). Z = [[a, b], [c, d], [e, f], [g, h]] ; NO
ところで、append はリストを結合するだけでなく、リストを分解することもできます。
?- my_append(Z, [c, d], [a, b, c, d]). Z = [a, b] ; NO ?- my_append([a, b], Z, [a, b, c, d]). Z = [c, d] ; NO
このほかに、第 1 引数と第 2 引数を変数にすると、2 つのリストに分解できるすべての組み合わせを求めることができます。
?- my_append(X, Y, [a, b, c, d]). X = [] Y = [a, b, c, d] ; X = [a] Y = [b, c, d] ; X = [a, b] Y = [c, d] ; X = [a, b, c] Y = [d] ; X = [a, b, c, d] Y = [] ; NO
このように、ひとつの述語で複数の使い方ができるのが、ほかのプログラミング言語では真似のできない Prolog の面白い特徴です。
次は、リストを反転する述語 my_reverse を作りましょう。SWI-Prolog には、すでに reverse が定義されているので、名前を my_reverse としました。第 1 引数にリストを与え、第 2 引数で逆にしたリストを取り出します。
リスト：リストの反転
my_reverse([], []).
my_reverse([X | Xs], Ys) :-
my_reverse(Xs, Zs), append(Zs, [X], Ys).
プログラムは簡単です。最初の規則は空リストを反転すると空リストになることを表しています。これが再帰定義の停止条件になります。次の規則で、リストの先頭要素 X を取り除いたリスト Xs を my_reverse で反転します。そして、反転したリスト Zs の最後尾に X を追加します。これは append を使えば簡単ですね。そして、Zs と [X] を結合したリスト Ys を頭部の第 2 引数に指定すればいいわけです。
それでは実行してみましょう。
?- my_reverse([a, b, c], X). X = [c, b, a] ; NO
リストは、ある要素の集まりを表しています。つまり、集合 として考えることができます。リストを集合と考えた場合、集合に要素を加えることや削除するといった基本的な操作のほかに、要素が集合に含まれているか、集合 A は集合 B の部分集合か、といった操作を考えることができます。
まずは、要素がリストの中に含まれているかチェックする述語 my_member を作ります。SWI-Prolog には member という述語が定義されているので、名前を my_member としました。my_member(X, Ls) は「X は Ls の要素である」という関係を表します。
リスト：要素がリストに含まれているか my_member(X, [X | Ls]). my_member(X, [Y | Ls]) :- my_member(X, Ls).
述語 my_member は、再帰定義で簡単に作ることができます。まず、X とリストの第 1 要素が等しいのであれば、最初の規則が成功します。そうでなければ、再帰定義を使ってリストの残りの要素と比較します。それでは実行してみましょう。
?- my_member(c, [a, b, c, d]). YES ?- my_member(e, [a, b, c, d]). NO
この 2 つの例は簡単ですね。このほかに my_member は第 1 引数を変数にすると、 要素を順番に取り出すことができます。
?- my_member(X, [a, b, c, d]). X = a ; X = b ; X = c ; X = d ; NO
Prolog の場合、リストの要素を順番に取り出すには、member ではなく select という述語を使うのがふつうです。そこで、リストの要素を取り出す述語 my_select を作りましょう。これも SWI-Prolog に select が定義されているので、名前を my_select としました。第 2 引数にリストを与え、第 1 引数には取り出した要素、第 3 引数には要素を取り出したあとのリストがセットされます。
リスト：リストの要素をひとつ選択する my_select(X, [X | Xs], Xs). my_select(X, [Y | Ys], [Y | Zs]) :- my_select(X, Ys, Zs).
最初の規則で、リストを分解して第 1 要素を取り出しています。my_select を実行すると、まずこの規則が選択されます。再試行が行われると、次の規則で第 1 要素を取り除いたリストから要素を選択します。変数 Zs には残りの要素を格納したリストがセットされるので、ここに取り除いた先頭要素 Y を追加すればいいわけです。再試行するたびに要素が取り出され、要素がなくなると実行は失敗します。
?- my_select(X, [a, b, c], Y). X = a Y = [b, c] ; X = b Y = [a, c] ; X = c Y = [a, b] ; NO ?- my_select(a, [a, b, c], X). X = [b, c] ; NO ?- my_select(d, [a, b, c], X). NO
my_select は、第 1 引数の値を変数ではなくアトムにしても動作します。
最後に、部分集合を判定する述語を作りましょう。述語 selects(X, Y) は、リスト X の要素がリスト Y に含まれているか調べます。
リスト：部分集合の判定 selects([], Ys). selects([X | Xs], Ys) :- select(X, Ys, Ys1), selects(Xs, Ys1).
selects は select を使えば簡単に定義できます。最初の規則は、「空リストは Ys の部分集合である」ということを表しています。これが再帰定義の停止条件となります。次の規則で、リストの先頭要素 X が Ys の要素であることを select で確認し、それから Xs が Ys の部分集合であることを selects で確認すればいいわけです。それでは、実行例を示します。
?- selects([a, b, c], [a, b, c, d, e]). YES ?- selects([a, b, c], [d, e, f, g]). NO ?- selects([a, b, c, d], [a, b, c]). NO
このほかに、selects は第 1 引数を変数にすると、第 2 引数の部分集合をすべて求めることができます。
?- selects(X, [a, b]). X = [] ; X = [a] ; X = [a, b] ; X = [b] ; X = [b, a] ; NO