M.Hiroi's Home Page

Prolog Programming

お気楽 Prolog プログラミング入門

[ PrevPage | Prolog | NextPage ]

データ型と型述語

●データ型

Prolog で使用するデータ型について、まとめておきましょう。Prolog では、すべてのデータをまとめて「項 (term)」と呼びます。項を細かく分類すると次の種類があります。

表 : 項の分類
名前種類
アトム英大文字以外から始まる文字列
シングルクオート (') で囲まれた文字列
数値整数, 有理数, 浮動小数点数
変数英大文字かアンダーライン (_) で始まる文字列
複合項項を組み合わせてできる構造体

変数は英大文字から始まる文字列だけではなく、アンダーライン (_) から始まる文字列も変数となります。特に、アンダーラインだけの変数を「無名変数 (anonymous variable)」と呼び、プログラム上でその変数の値が不用のときに使われます。たとえば、リストから要素を取り出す述語 retrieve を見てください。 

リスト : 参照

retrieve(N, [Y | Ls], X) :-
    N > 1, N1 is N - 1, retrieve(N1, Ls, X).
retrieve(1,  [X | Ls], X).

最後の事実で、変数 Ls は 1 か所しか使われていませんね。そして、最初の規則の変数 Y もそうです。Prolog 処理系からすれば、これらの変数に名前を付ける必要はありません。このような場合、無名変数を使うことができます。 

リスト : 参照 (無名変数を使う場合)

retrieve(N, [_ | Ls], X) :-
    N > 1, N1 is N - 1, retrieve(N1, Ls, X).
retrieve(1,  [X | _], X).

このように無名変数を使うと、SWI-Prolog で Warning が出なくなります。

次に、複合項について簡単に説明しておきましょう。複合項の基本的な形式は、次のようになります。 

func(arg1, arg2, ... argN)

func を「ファンクタ (functor, 関数子)」といいます。複合項は、ファンクタと引数の個数 (arity, アリティ) で定められます。述語と同じ形式になっているところが、ちょっとややこしいところです。述語は物事の関係を表し、複合項はデータ構造を表していることに注意してください。

複合項の例として、二分木を考えてみましょう。二分木の節 (node) を複合項で表すと、次のようになります。 

node(Item, Left, Rigth)

Item にデータが入り、Left には左側の子、Right には右側の子が入ります。空の木は void で表せばいいでしょう。簡単な二分木とその複合項を図に示します。

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 == Term2Term1 と Term2 が等しければ成功します
Term1 \== Term2Term1 と Term2 が等しくなければ成功します

== は 2 つのデータが等しいことを調べる重要な述語です。== はデータ型によって次のように判断します。

簡単な例を示しましょう。 

?- 10 == 10.
true.

?- 10 == 10.0.
false.

?- abc == abc.
true.

?- [a, b, c] == [a, b, c].
true.

?- [[a, b], [10, 20]] == [[a, b], [10, 20]].
true.

?- [[a, b], [10, 20]] == [[a, b], [10, 20.0]].
false.

?-

リストが入れ子になっている場合は、その中の要素も比較します。それから、== はパターンマッチングを行わないことに注意してください。 

?- X == 10.
false.

?- X is 10, X == 10.
X = 10.

?-

変数 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] ;
false.

?- my_flatten([[a, b], [], [c, d]], X).
X = [a, b, c, d] ;
false.

?-

きちんと動作していますね。もうひとつ、簡単な例題を示しましょう。リストの中から整数を取り出して、それをリストにまとめます。プログラムは次のようになります。 

リスト : 整数を取り出す

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, 2] ;
X = [1] ;
X = [1] ;
X = [1] ;
X = [1] ;
X = [1] ;
X = [2] ;
X = [2] ;
X = [] ;
X = [] ;
X = [] ;
X = [] ;
X = [] ;
X = [].

?-

再試行の動作が不満ですね。これは、1, 2 番目の規則が再試行すると、無条件に 3 番目の規則が成功してしまうからです。この問題を解決するには、「カット (cut)」というバックトラックを制御する述語を使います。カットを使えば、あらゆる制御構造を実現することができます。カットはまだ説明していないので、この問題はカットのところで再度取り上げることにします。

●問題

次の術語を定義してください。

  1. リスト Xs の中から X と等しい要素の位置 N を求める position(X, Xs, N)
  2. リスト Xs から X と等しい要素の個数 N を求める count(X, Xs, N)
  3. 引数 X と等しいリスト Xs の要素を Y に置き換える substitute(X, Y, Xs, Zs)
  4. リスト Xs を「木 (tree)」とみなして、要素 (葉, leaf) を数える count_leaf(Xs, N)
  5. リスト Xs を木とみなして、X と等しい要素を Y に置換する述語 subst(X, Y, Xs, Zs)










●解答１

?- [user].
|: position(X, [X | _], I, I).
|: position(X, [Y | Xs], I, N) :- X \== Y, I1 is I + 1, position(X, Xs, I1, N).
|: position(X, Xs, N) :- position(X, Xs, 1, N).
|: ^D
true.

?- position(a, [a,b,c,d,e], N).
N = 1 ;
false.

?- position(c, [a,b,c,d,e], N).
N = 3 ;
false.

?- position(e, [a,b,c,d,e], N).
N = 5 ;
false.

?- position(z, [a,b,c,d,e], N).
false.

position は nth0, nth1 のような使い方 (要素 X の位置を求めること) もできます。 

?- position(X, [a,b,c,d,e], 1).
X = a ;
false.

?- position(X, [a,b,c,d,e], 2).
X = b ;
false.

?- position(X, [a,b,c,d,e], 3).
X = c ;
false.

?- position(X, [a,b,c,d,e], 4).
X = d ;
false.

?- position(X, [a,b,c,d,e], 5).
X = e ;
false.

?- position(X, [a,b,c,d,e], 6).
false.

?- position(X, [a,b,c,d,e], N).
X = a,
N = 1 ;
X = b,
N = 2 ;
X = c,
N = 3 ;
X = d,
N = 4 ;
X = e,
N = 5 ;
false.

●解答２

?- [user].
|: count(X, [X | Xs], N) :- count(X, Xs, N1), N is N1 + 1.
|: count(X, [Y | Xs], N) :- X \== Y, count(X, Xs, N).
|: count(_, [], 0).
|: ^D
true.

?- count(1, [1,2,3,4,1,2,3,1,2,1], N).
N = 4 ;
false.

?- count(2, [1,2,3,4,1,2,3,1,2,1], N).
N = 3 ;
false.

?- count(3, [1,2,3,4,1,2,3,1,2,1], N).
N = 2 ;
false.

?- count(4, [1,2,3,4,1,2,3,1,2,1], N).
N = 1 ;
false.

?- count(5, [1,2,3,4,1,2,3,1,2,1], N).
N = 0 ;
false.

●解答３

?- [user].
|: substitute(X, Y, [X | Xs], [Y | Ys]) :- substitute(X, Y, Xs, Ys).
|: substitute(X, Y, [Z | Xs], [Z | Ys]) :- X \== Z, substitute(X, Y, Xs, Ys).
|: substitute(_, _, [], []).
|: ^D
true.

?- substitute(a, z, [a,b,a,b,c,a,b,c,d], Xs).
Xs = [z, b, z, b, c, z, b, c, d] ;
false.

?- substitute(b, z, [a,b,a,b,c,a,b,c,d], Xs).
Xs = [a, z, a, z, c, a, z, c, d] ;
false.

?- substitute(c, z, [a,b,a,b,c,a,b,c,d], Xs).
Xs = [a, b, a, b, z, a, b, z, d] ;
false.

?- substitute(d, z, [a,b,a,b,c,a,b,c,d], Xs).
Xs = [a, b, a, b, c, a, b, c, z] ;
false.

?- substitute(e, z, [a,b,a,b,c,a,b,c,d], Xs).
Xs = [a, b, a, b, c, a, b, c, d] ;
false.

●解答４

?- [user].
|: count_leaf([X | Xs], N) :- count_leaf(X, A), count_leaf(Xs, B), N is A + B.
|: count_leaf(X, 1) :- X \== [], atomic(X).
|: count_leaf([], 0).
|: ^D
true.

?- count_leaf([1,2,3], N).
N = 3 ;
false.

?- count_leaf([[1,2,3],[4,5],[6]], N).
N = 6 ;
false.

?- count_leaf([1,[2,[3],4],5], N).
N = 5 ;
false.

●解答５

?- [user].
|: subst(X, Y, X, Y).
|: subst(X, Y, [L1 | R1], [L2 | R2]) :- X \== [L1 | R1], subst(X, Y, L1, L2), subst(X, Y, R1, R2).
|: subst(X, _, Z, Z) :- X \== Z, atomic(Z).
|: ^D% user://1 compiled 0.03 sec, 3 clauses
true.

?- subst(a, z, [a,b,c,a,b,c], A).
A = [z, b, c, z, b, c] ;
false.

?- subst(a, z, [[a,b],[a,c],[a,d]], A).
A = [[z, b], [z, c], [z, d]] ;
false.

?- subst(a, z, [a,[b,[c,[a],d],a],e], A).
A = [z, [b, [c, [z], d], z], e] ;
false.

?- subst([a,b], z, [[a,b],[a,c],[a,d]], A).
A = [z, [a, c], [a, d]] ;
false.
初版 2000 年 11 月 14 日
改訂 2023 年 4 月 22 日

カットと否定

●カット

「カット (cut)」は Prolog のバックトラックを制御する唯一の述語です。カットは、最初の実行では無条件に成功しますが、再試行するときには失敗するとともに、それ以前に実行されたゴールの再試行と、次の規則の探索を禁止します。次の図を見てください。

カットは ! で表します。規則の中でカットが使用された場合、カットより右側にあるゴール 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].

?-

これで望ましい動作となりました。

●条件分岐

それでは、ほかのプログラミング言語ではお馴染みの条件分岐 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 を実行します。

セミコロンは条件分岐と組み合わせるだけでなく、規則の中でも使用することができます。この場合、最初の規則が失敗してから、次の規則が試されることに注意してください。次の例を見てください。 

?- [user].
|: foo(a).
|: foo(b).
|: bar(c).
|: bar(d).
|: ^D
true.

?- foo(X) ; bar(X).
X = a ;
X = b ;
X = c ;
X = d.

?-

まず foo(X) が実行さるため X の値は a, b となります。そして、foo(X) が失敗してから bar(X) が実行されるので、X の値は c, d となります。

●否定

プログラムによっては、実行結果を逆にしたい場合があります。たとえば、integer はデータが整数値か調べますが、整数値以外のデータか調べたい場合もありるでしょう。このような場合、not という述語を使うと結果を逆にすることができます。 

?- not(integer(10)).
false.

?- not(integer(a)).
true.

?-

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 は失敗となるからです。次の例を見てください。 

?- [user].
|: foo(a).
|: foo(b).
|: bar(b).
|: bar(c).
|: ^D
true.

?- foo(X), not(bar(X)).
X = a ;
false.

?- not(bar(X)), foo(X).
false.

?-

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 \= a.
false.

?- a \= b.
true.

?- X \= a.
false.

?-

最後の例のように、自由変数とのパターンマッチングは成功しますが、\= の結果は false となります。これで、X と Y が等しくないときにだけ、最後の規則を実行することができます。

もし、X \= Y を省略すると、remove を再試行したときに誤動作します。2 番目の規則を実行したあと、最後の規則を再試行する必要はありませんね。X \= Y を省略すると、再試行で最後の規則が無条件に実行されるため、間違った別解を求めてしまうのです。

それでは実行してみましょう。 

?- remove(b, [a, b, c, d], X).
X = [a, c, d] ;
false.

?- remove(b, [a, b, c, b, c, d], X).
X = [a, c, c, d] ;
false.

?- remove(b, [1, 2, 3, 4, 5], X).
X = [1, 2, 3, 4, 5] ;
false.

?-

正常に動作していますね。ちなみに、SWI-Prolog には remove と同じ働きをする述語 delete が定義されています。

-- note --------
[*1] 最近の SWI-Prolog では not のかわりに \+ を使っています。

●問題

次に示す述語をカットを使って定義してください。

  1. FizzBuzz 問題
  2. リスト Xs から重複要素を取り除く remove_dup(Xs, Ys)
  3. リスト Xs, Ys の和集合を求める set_union(Xs, Ys, Zs)
  4. リスト Xs, Ys の積集合を求める set_intersect(Xs, Ys, Zs)
  5. リスト Xs, Ys の差集合を求める set_difference(Xs, Ys, Zs)










●解答１

リスト : FizzBuzz 問題 (カット版)

change(N, fizzbuzz) :- N mod 15 =:= 0, !.
change(N, fizz) :- N mod 3 =:= 0, !.
change(N, buzz) :- N mod 5 =:= 0, !.
change(N, N).

fizzbuzz(N) :-
    N =< 100, change(N, S), write(S), write(' '), N1 is N + 1, fizzbuzz(N1).
fizzbuzz(N) :- N > 100, nl.

?- fizzbuzz(1).
1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17 fizz 19 buzz fizz 22 23 fizz buzz 
26 fizz 28 29 fizzbuzz 31 32 fizz 34 buzz fizz 37 38 fizz buzz 41 fizz 43 44 fizzbuzz 46 47 fizz 49 buzz
fizz 52 53 fizz buzz 56 fizz 58 59 fizzbuzz 61 62 fizz 64 buzz fizz 67 68 fizz buzz 71 fizz 73 74 fizzbuzz
76 77 fizz 79 buzz fizz 82 83 fizz buzz 86 fizz 88 89 fizzbuzz 91 92 fizz 94 buzz fizz 97 98 fizz buzz
true ;
false.

●解答２

?- [user].
|: remove_dup([X | Xs], Ys) :- remove_dup(Xs, Ys), member(X, Ys), !.
|: remove_dup([X | Xs], [X | Ys]) :- remove_dup(Xs, Ys).
|: remove_dup([], []).
|: ^D
true.

?- remove_dup([1,2,3,2,1], A).
A = [3, 2, 1].

?- remove_dup([1,1,1], A).
A = [1].

?- remove_dup([1,2,2,3,3,1,1], A).
A = [2, 3, 1].

●解答３

?- [user].
|: set_union([X | Xs], Ys, Zs) :- member(X, Ys), !, set_union(Xs, Ys, Zs).
|: set_union([X | Xs], Ys, [X | Zs]) :- set_union(Xs, Ys, Zs).
|: set_union([], Ys, Ys).
|: ^D
true.

?- set_union([1,2,3,4],[3,4,5,6], Zs).
Zs = [1, 2, 3, 4, 5, 6].

?- set_union([1,2,3,4],[5,6,7,8], Zs).
Zs = [1, 2, 3, 4, 5, 6, 7, 8].

?- set_union([1,2,3,4],[1,2,3,4], Zs).
Zs = [1, 2, 3, 4].

●解答４

?- [user].
|: set_intersect([X | Xs], Ys, [X | Zs]) :- member(X, Ys), !, set_intersect(Xs, Ys, Zs).
|: set_intersect([_ | Xs], Ys, Zs) :- set_intersect(Xs, Ys, Zs).
|: set_intersect([], _, []).
|: ^D
true.

?- set_intersect([1,2,3,4],[3,4,5,6], Zs).
Zs = [3, 4].

?- set_intersect([1,2,3,4],[5,6,7,8], Zs).
Zs = [].

?- set_intersect([1,2,3,4],[1,2,3,4], Zs).
Zs = [1, 2, 3, 4].

●解答５

?- [user].
|: set_difference([X | Xs], Ys, Zs) :- member(X, Ys), !, set_difference(Xs, Ys, Zs).
|: set_difference([X | Xs], Ys, [X | Zs]) :- set_difference(Xs, Ys, Zs).
|: set_difference([], _, []).
|: ^D
true.

?- set_difference([1,2,3,4],[3,4,5,6],Zs).
Zs = [1, 2].

?- set_difference([1,2,3,4],[5,6,7,8],Zs).
Zs = [1, 2, 3, 4].

?- set_difference([1,2,3,4],[1,2,3,4],Zs).
Zs = [].
初版 2000 年 11 月 21 日
改訂 2023 年 4 月 22 日

繰り返し

●失敗駆動ループ

Prolog の場合、強制的にバックトラックを発生させて、繰り返し処理を行う方法がよく使われます。これを「失敗駆動ループ (failure-driven loop)」と呼びます。たとえば、セミコロン ( ; ) を入力せずにすべての解を表示したい場合は、次のように行います。 

?- [user].
|: foo(a).
|: foo(b).
|: foo(c).
|: ^D
true.

?- foo(X), write(X), nl, fail.
a
b
c
false.

?-

まず 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
|: ^Dtrue.

?-

|: は入力を表すプロンプトです。read は Prolog の構文規則に従ってデータをリードするので、最後は必ずピリオド (.) を入力してください。echo を終了するときは CTRL-D を入力してください。Windows で実行する場合、^Z を入力するとファイルの終了と判断されるので、echo を終了することができます。

echo を単体で使う場合は、echo の最後にあるカットは必要ありません。ところが、ほかの規則と一緒に使う場合には問題があるのです。バックトラックが発生すると、repeat がバックトラックをすべて跳ね返してしまうので、それ以前の規則に戻らなくなってしまうのです。カットが実行されていれば、echo は再試行時に失敗しますので、バックトラックすることができます。repeat を使う場合はカットを忘れないように注意してください。

今度は yes か no を入力するプログラムを作ってみましょう。yes または no 以外のデータが入力された場合は、再度入力を促します。これも repeat を使うと簡単に実現できます。 

リスト : yes または no を入力

yes_or_no(X) :- 
    repeat, read(X), (X == yes ; X == no), !.

read(X) でデータを読み込みます。そして、X が yes か no であれば成功します。それ以外は失敗しバックトラックします。そして repeat によって再び実行が始まります。それでは実行してみましょう。 

?- yes_or_no(X).
|: n.
|: y.
|: yes.

X = yes.

?-

最後のカットがない場合は、再試行によって再び yes または no の入力が始まります。カットが実行されているので、再試行が失敗してトップレベルに戻ります。

●整数値の繰り返し

このほかに、便利な繰り返し述語 between(L, H, V) があります。これは、整数 V が L から H の範囲内 (L =< V =< H) であれば真となる述語です。between は次のように定義されます。 

リスト : bewteen の定義

my_between(L, H, L) :- L =< H.
my_between(L, H, V) :- L < H, L1 is L + 1, my_between(L1, H, V).

SWI-Prolog には between が定義されているので、名前を my_between にしました。たとえば、my_between(1, 5, X) を実行します。まず、最初の規則が選択されて X = 1 となります。再試行すると次の規則が選択され、L の値を +1 して再帰するので、my_between(2, 5, X) が実行されます。したがって、X = 2 になります。このように、L の値を +1 しながら再帰していき、L の値が H より大きくなったならば、再帰が停止して実行終了となります。

それでは実際に使ってみましょう。 

?- my_between(1, 5, X), write(X), nl, fail.
1
2
3
4
5
false.

?-

my_bewteen は失敗駆動ループと組み合わせて利用することができます。たとえば、a を 10 回出力してみましょう。 

?- my_between(1, 10, _), write(a), fail.
aaaaaaaaaa
false.

?-

FizzBuzz 問題 も簡単に解くことができます。 

リスト : FizzBuzz 問題 (between 版)

change(N, fizzbuzz) :- N mod 15 =:= 0, !.
change(N, fizz) :- N mod 3 =:= 0, !.
change(N, buzz) :- N mod 5 =:= 0, !.
change(N, N).

fizzbuzz :- between(1, 100, N), change(N, S), write(S), write(' '), fail.

?- fizzbuzz.
1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17 fizz 19 buzz fizz 22 23 fizz buzz 
26 fizz 28 29 fizzbuzz 31 32 fizz 34 buzz fizz 37 38 fizz buzz 41 fizz 43 44 fizzbuzz 46 47 fizz 49 buzz 
fizz 52 53 fizz buzz 56 fizz 58 59 fizzbuzz 61 62 fizz 64 buzz fizz 67 68 fizz buzz 71 fizz 73 74 fizzbuzz 
76 77 fizz 79 buzz fizz 82 83 fizz buzz 86 fizz 88 89 fizzbuzz 91 92 fizz 94 buzz fizz 97 98 fizz buzz
false.

●末尾再帰による繰り返し

このように、Prolog でも繰り返しを利用することができますが、手続き型言語のようにプログラムできるわけではありません。というのも、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(X, Sum) :-
    X > 0, X1 is X - 1, fact(X1, Sum1), Sum is X * Sum1. 
fact(0, 1).

このプログラムは 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 はいちばん最後に呼び出されるため、末尾再帰最適化により繰り返しに変換されます。

もう一つ簡単な例題としてフィボナッチ関数を示しましょう。フィボナッチ関数は階乗と同様に再帰的に定義される関数です。

\(\begin{array}{l} fibo(0) = 0 \\ fibo(1) = 1 \\ fibo(n) = fibo(n - 1) + fibo(n - 2) \quad if \ n \geq 2 \end{array}\)

0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列

図 : フィボナッチ関数の定義

まず最初に、フィボナッチ関数を単純にプログラムします。 

リスト : フィボナッチ関数 (二重再帰)

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).

fibo は階乗の計算を行う fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo は同じ値を何回も求めているため、実行時間はとても遅くなります。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。

プログラムは次のようになります。 

リスト : フィボナッチ数列 (末尾再帰)

fibo1(N, F) :- fibo1(N, 0, 1, F).
fibo1(N, A1, A2, F) :-
    N > 0, N1 is N - 1, A3 is A1 + A2, fibo1(N1, A2, A3, F).
fibo1(0, A1, _, A1).

累算変数 A1 と A2 の使い方がポイントです。現在のフィボナッチ数を変数 A1 に、一つ先の値を変数 A2 に格納しておきます。あとは A1 と A2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo1/4 は末尾再帰になっているので、最初のプログラムより高速に実行できます。

それでは実際に試してみましょう。 

?- between(0, 10, X), fibo(X, A), write(A), nl, fail.
0
1
1
2
3
5
8
13
21
34
55
false.

?- between(0, 10, X), fibo1(X, A), write(A), nl, fail.
0
1
1
2
3
5
8
13
21
34
55
false.

?- time(fibo(35, X)).
% 74,651,758 inferences, 6.867 CPU in 6.868 seconds (100% CPU, 10870325 Lips)
X = 9227465.

?- time(fibo1(35, X)).
% 109 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 5647668 Lips)
X = 9227465.

?-

time は実行時間を計測する SWI-Prolog の述語です。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].

?-

正常に動作していますね。

再帰定義と比べると、繰り返しは実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しでプログラムするとめちゃくちゃ複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり繰り返し (末尾再帰) へ変換する必要はないと思います。わかりやすいプログラムが一番です。

●問題

次に示す述語を末尾再帰で定義してください。

  1. 整数 1 から X までの合計値を求める sum(X, A)
  2. リスト Xs の要素の合計値を求める sumlist(Xs, A)
  3. リスト Xs の中から最大値を求める maxlist(Xs, A)
  4. リスト Xs の中から最小値を求める minlist(Xs, A)
  5. 九九表を出力する ninetynine
  6. リストの長さを求める my_length(Xs, N)










●解答１

?- [user].
|: sum(X, N, A) :- X > 0, X1 is X - 1, N1 is N + X, sum(X1, N1, A).
|: sum(0, A, A).
|: sum(X, A) :- sum(X, 0, A).
|: ^D
true.

?- sum(10, A).
A = 55.

?- sum(1000, A).
A = 500500.

?- sum(100000, A).
A = 5000050000.

●解答２

?- [user].
|: sumlist([X | Xs], N, A) :- N1 is N + X, sumlist(Xs, N1, A).
|: sumlist([], A, A).
|: sumlist(Xs, A) :- sumlist(Xs, 0, A).
|: ^D
true.

?- sumlist([1,2,3,4,5], A).
A = 15.

?- sumlist([1,3,5,7,9], A).
A = 25.

●解答３

?- [user].
|: maxlist([X | Xs], N, A) :- X > N, !, maxlist(Xs, X, A).
|: maxlist([_ | Xs], N, A) :- maxlist(Xs, N, A).
|: maxlist([], A, A).
|: maxlist([X | Xs], A) :- maxlist(Xs, X, A).
|: ^D
true.

?- maxlist([1,2,3,4,5], A).
A = 5.

?- maxlist([1,2,5,4,3], A).
A = 5.

?- maxlist([5,4,3,2,1], A).
A = 5.

?- maxlist([5], A).
A = 5.

?- maxlist([], A).
false.

●解答４

?- [user].
|: minlist([X | Xs], N, A) :- X < N, !, minlist(Xs, X, A).
|: minlist([_ | Xs], N, A) :- minlist(Xs, N, A).
|: minlist([], A, A).
|: minlist([X | Xs], A) :- minlist(Xs, X, A).
|: ^D
true.

?- minlist([1,2,3,4,5], A).
A = 1.

?- minlist([3,2,1,4,5], A).
A = 1.

?- minlist([5,4,3,2,1], A).
A = 1.

?- minlist([1], A).
A = 1.

?- minlist([], A).
false.

●解答５

リスト : 九九表

write_num(N) :- N >= 10, write(' '), write(N).
write_num(N) :- N < 10, write('  '), write(N).

nn_sub(M, N) :-
    N < 10, A is M * N, write_num(A), N1 is N + 1, nn_sub(M, N1).
nn_sub(_, 10) :- nl.

nn(N) :- N < 10, nn_sub(N, 1), N1 is N + 1, nn(N1).
nn(10) :- nl.

ninetynine :- nn(1).

?- ninetynine.
  1  2  3  4  5  6  7  8  9
  2  4  6  8 10 12 14 16 18
  3  6  9 12 15 18 21 24 27
  4  8 12 16 20 24 28 32 36
  5 10 15 20 25 30 35 40 45
  6 12 18 24 30 36 42 48 54
  7 14 21 28 35 42 49 56 63
  8 16 24 32 40 48 56 64 72
  9 18 27 36 45 54 63 72 81

true ;
false.

●解答６

?- [user].
|: my_length([], A, A).
|: my_length([_ | Xs], A, N) :- A1 is A + 1, my_length(Xs, A1, N).
|: my_length(Xs, N) :- my_length(Xs, 0, N).
|: ^D
true.

?- my_length([], N).
N = 0.

?- my_length([a,b,c,d,e], N).
N = 5.

?- my_length(Xs, 5).
Xs = [_, _, _, _, _] ;
=> エラー

length のようにリストを生成することもできますが、再試行するとエラー (スタックオーバーフロー) になります。次のように、最初の規則にカットを追加すると正常に動作します。 

リスト : リストの長さを求める

my_length([], A, A) :- !.
my_length([_ | Xs], A, N) :- A1 is A + 1, my_length(Xs, A1, N).

my_length(Xs, N) :- my_length(Xs, 0, N).

?- my_length([], N).
N = 0.

?- my_length([a,b,c,d,e], N).
N = 5.

?- my_length(Xs, 0).
Xs = [].

?- my_length(Xs, 5).
Xs = [_, _, _, _, _].
初版 2000 年 11 月 28 日
改訂 2023 年 4 月 22 日
Copyright (C) 2000-2023 Makoto Hiroi
All rights reserved.
[ PrevPage | Prolog | NextPage ]