前回親子関係や兄弟、祖先を求める述語を定義しているが、ある解が 求められた際に、それ以外の別解が必要であれば、 バックトラックするという方式であった。 プログラムで特に記述しなくてもバックトラックによって別解が求められるのが Prolog の大きな特徴であるが、実際的なプログラミングの際にはこの バックトラックではやや都合が悪い場合がある。
バックトラックでは、別解を求めるために、後戻りした分だけ変数の値も 無効になる。つまり、別解を求める際には、その前に求めた解に関する記憶を 後戻りする分だけ失うのである。このことは例えば、兄弟関係を求める際に 以前求めた組み合わせを覚えていないので、以前と同じ解を求めてしまったこと がわからずにそのまま解として示してしまうことにつながる。 また、可能な解全てを一括して求めることもできない。
実際のプログラミングを行う際には、このようなバックトラックを越えて 値を覚えておきたい場合というのが生じることも多い。 バックトラックを越えて値を覚える プログラムはどのようにすればできるだろうか。一つの手としては ファイル入出力機能を使う手が考えられる。writelnで考えれば わかるように Prolog 自身はバックトラックしても、画面やファイルに出力を したということ自体はキャンセルされないことを利用するのである。 しかしながら、性能などの観点でファイル入出力をその目的に使うことは 稀である。(ちなみに、古典的なProlog処理系ではファイル入出力では write, nl, tell, told, read, see, seenなどの述語を 用いる。)
そのようなバックトラックをしても値を覚えておくことや、プログラム実行中に プログラムを問題に対応して書換えるようなプログラミング手法 のために、Prologでは節定義を追加したり削除するための特別な述語を 準備している。「assert(節)」は節を追加する述語であり、 「retract(節)」はマッチする節を(1つ)削除する述語である。 なお、マッチする節をすべて削除する場合はretractallを 用いる。なお、Prolog では節定義の順序が重要な意味を持つので節を 追加する時に先頭に追加するassertaと最後に追加する assertz を使い分けることもできる(assertとassertzは同じである)。 なお、SWI-Prologではassertやretractで節を動的に 変更する場合にはその述語をdynamicによって事前に宣言しておく 必要がある。
このような副作用を持つ述語の応用例として、 ある述語が定義されている際に、それで求められる解を一括してリストに する組み込み述語bagofがある。例えば、前回の最後の課題の1を 解くために定義した述語をsum10とすると全ての解をリストに入れる際は、
bagof([A, B, C, D], sum10(A, B, C, D), L).
のようになる。bagof の第1引数は一種の一時変数の宣言に相当し、 目的の述語の各解が入るべき変数名(複数の場合はそのリスト)を書く。 第2引数は解を求めたい述語の式である。そして、第3引数に指定した変数に 全ての解を要素としたリストが入る。別の例としては、1, 2, 3 と sum10 の 関係にある数のリストを求めるのであれば、
bagof(D, sum10(1, 2, 3, D), L).
とすることもできる。トリッキーな例としては、
bagof(A, member(A, [a, b, c]), L).
とすると、L には元のリストと等しいリスト、つまり[a, b, c]が入る。 なお、bagofは解を全て（求められた順に）リストに納めるが、 解をソートし、重複を取り除いた結果をリストにするsetofも 組み込み述語として準備されている。
assert, retract, dynamicを使ってbagofとほぼ同じ ことができるmy_bagofを定義すると次のようになる。
my_bagof(V, P, _) :-
(dynamic my_bagof_buffer/1),
retractall(my_bagof_buffer(_)),
assert(my_bagof_buffer([])),
P,
my_bagof_buffer(M),
retract(my_bagof_buffer(M)),
assert(my_bagof_buffer([V| M])),
fail.
my_bagof(_, _, L) :-
my_bagof_buffer(M),
retract(my_bagof_buffer(M)),
reverse(M, L).
ここで、バックトラックしても途中の結果を覚えておくために、 述語my_bagof_bufferを用いる。 なお、リストは前に値を付け加えるのが簡単なので、結果として 逆順になっているのを組み込み述語reverseで順序をひっくり返す。 1つ目の節では、まずdynamicで引数1個の述語 my_bagof_buffer について、追加削除を行うことを示し、まず前回までの定義が残っていると 誤動作の元なので、すべて削除しておく。そして、最初は結果がないので、 引数を空リストとして節を1つ追加しておく。 あとは第2引数で指定された式(P)を確かめ、成立すれば、 my_bagof_bufferで引数のリストを取り出して、節を削除、 リストに値を追加して節を追加し、最後にfailでバックトラックさせる。 最後までバックトラックすると2番目の節定義に移り、リストを取り出して、 追加した節定義を削除しておいて、リストの順序を反転させるという流れになる。
このassert/retractを用いた状態の記録はパズルなどを解かせる 場合には、同じ状態に戻って堂々巡りすることがないように使うことも多い。 ただし、節定義の 追加・削除とバックトラックとの関係を良く理解して使う必要があり、 バックトラックと共に忘れても良いようなら引数にそれまでのパズルの状態を リストにして渡すという方が簡単なこともある。
ハノイの塔は、Prolog の入門書にも例題としてよく扱われる パズルである。3本の棒が立っていて、そのうちの一つに64枚の直径が 少しずつ異なる円盤が刺さっておりそれを一枚ずつ移動させて64枚すべてを 別の棒に移動させるというのが元々の問題である。なお、円盤の積み方は常に 必ず大きいものが下になっていなくてはならない。
このハノイの塔を解くアルゴリズムは良く知られており、棒がa, b, c とすると、n枚の円盤を棒aから棒cに動かす手順は以下のようになる。
この手順の2番目は1枚をそのまま空いている場所に動かすだけで、 1番目と3番目はこの手順全体の枚数や棒を対応させれば、同じ手順を 再帰的に繰り返せば良いことがわかる。なお、この手順でわかるように n枚の円盤を動かすためには2のn乗から1を引いた回数だけ円盤1枚分の移動の 操作をする必要がある。 (上の手順は単純な再帰手続きなので、Prologでなくても簡単にプログラム にすることができる。)
さて、上の手順をプログラムにしてみよう。 まず簡単な2番目の手順である、1枚(n枚目)の円盤をaからcに 動かすということを「move(n, a, c)」と表現し、動かすことが 可能であれば真であるととらえることにする。すると、上のアルゴリズムに 従えば必ず移動可能なので、これは無条件に真として良い。そして、 上ではn, a, c としているのは実際にはどんどん変わるので変数となる。 つまり、
move(N, A, C).
が手順の2番目を記述したものになる。
さて、ではこの手順全体がうまくできる 時に真になる述語を考える。それはつまり、手順の1、3番目で使われるもの でもある。既にmoveというのを使ってしまっているので、この述語には 「hanoi」と名付ける。さて、上の手順に書いてあるものを 見ると「n枚の円盤を棒aから棒cに動かす」とあるので、このまま 「hanoi(n, a, c)」と表現したいところであるが、そうすると手順の 中に出てくるbがどこで指定されるのかがわからなくなる。例えば、棒そのものは 世界に数え切れないくらいあるけど、そのどれを使うかは問題として3本と 指定されているから、実際にはこの手順は「n枚の円盤を棒aから棒cに、棒bを 使って動かす」ということである。 日本語など自然言語の表現ではこのように自明なことが略されているので、 プログラムにする際はそれを明示しなければならない。とすると、述語の 表現としては、「hanoi(n, a, c, b)」となる。で、これが成立する 条件としては上の3つの手順が可能な場合ということになり、それぞれを変数 とすれば、
hanoi(N, A, C, B) :-
N1 is N - 1,
hanoi(N1, A, B, C),
move(N, A, C),
hanoi(N1, B, C, A).
となる。あとは、nが1だった場合のことを考えるだけである。上の手順では n-1枚というのを考えているので、nが1の場合は1、3番目の手順では0枚を動かす、 つまり何もしなくて良いことになる。よって、nが1の場合は2番目の手順だけで 良いので、
hanoi(1, A, C, B) :- move(1, A, C).
となる。あとはhanoiの2つの節の順序を決めるだけだが、通常 より特殊解の方、つまりより状況が限定されている方を先にすれば良いので、 nが1の場合の節を先にすれば良い。以上で、アルゴリズムにしたがったハノイの塔 を解くプログラムは基本的に完成である。では実際に実行するには、 例えば10枚をaからbに移動させたい時は、 質問式として「hanoi(10, a, b, c).」を入力すれば良い。
しかしながら、これだけだと最後に「true」と返ってくるだけなので、 本当に解いているのかどうかがわからない。そこで、実際に円盤を動かす手順を 画面に表示させてみる。実際に1枚1枚の円盤を動かすことを表しているのは 述語moveである。そこで、moveのところで画面表示を させることで円盤の動かし方を示す。その場合moveの節定義を次のように する。
move(N, A, C) :- writeln(move(N, from, A, to, C)).
こうすると例えば、3枚目をaからcに動かす時は画面に
move(3, from, a, to, c)
のように表示される。これで完成である。なお、表示形式は一例なので、 もっと変えても良い。あと、各節で1箇所にしか出てこない変数がある場合は、 それは「_」(無名変数)に変えても良い。
hanoiの引数を一つ増やして、そこに何回動かすかという回数の 意味を持たせ、上の手順中での回数を加算するようにすれば良い。 move は1回になり、再帰のhanoiについてはそれぞれの引数に回数が返ってくる ことになるので、それらを合計すると良い。
ハノイの塔はアルゴリズムが良く知られているので、それを用いるのが 最も効率が良いが、ここでは後のパズルを解く前哨戦として、試行錯誤法を 試してみる。
試行錯誤法といっても様々に考え得るが、ここではある場面から可能な 手を表す規則を定義し、それに基づいてあらゆる可能な手を試して、正解に たどり着いたら終了とすることにする。この方法を用いる際は、 その場面(状態)を何らかの形で表現しなくてはならない。ここではハノイの塔 なので、3本の棒とそれに刺さっている円盤を状態として表すことになる。
ハノイの塔のルールによると円盤の大きさによって積み上げる順序に制限が ある。そこで、円盤の大きさを比較し易くするために、円盤は整数で表し、 数値がすなわち大きさであることにする。これにより大きさが比較 可能になる。
次にその整数で表された円盤が3本の棒のどれに刺さっているかを表す ために、リストを用いることにする。まず1本の棒に円盤1, 2, 3が刺さっている のを「[1, 2, 3]」と表す。リストの先頭に一番上にある円盤が来る ようにしているのは、必ず上の円盤から動かす(取り除く)ことになるので、 リストの操作がし易くなるからである。
次にどの棒に刺さっているのかを表すことになるが、その棒に刺さった 全体の状態を一つの述語で表すことにする。述語名はなんでも良いがここでは 仮にpole(1番目の棒, 2番目の棒, 3番目の棒)と表すことにする。例えば、 今、4枚の円盤があって小さいものが2枚、大きいものが2枚 刺さっているのを表すと、
pole([1, 2], [3, 4], [])
のようになる。
以下では考え方を順を追って説明するために「Step」としているが、 各Step毎にプログラムが完成するとは限らない。一通り全Stepに 目を通してから徐々に手をつけてみること。なお、節定義の順序にも依存するが、 最後のStepの考え方を取り入れるまでは2枚以上の円盤がある場合を 解けない可能性もあることに注意せよ。
まず、3番目が空リストの時は無条件に1番目の先頭の要素(=一番上の円盤)を 入れることができる。従って、最も簡単には
pole([A| AL], B, []) :- pole(AL, B, [A]).
のようにすれば、結論部と条件部で、移動前の状態と 移動後の状態が表されることになる。(条件部と結論部のどちらを 移動前とするかは解釈の仕方次第である。)
これにならって、3番目の棒に円盤が1枚以上刺さっている場合の節を 定義してみよ。なお、リストで先頭二つの要素と残りに分ける(あるいはつなぐ) 時は、「[A, B| L]」 のように書くことができる。
最後にたどり着くべき状態をゴールとして事実節を定義する。 例えば、3番目の棒にすべての円盤が刺さっている状態をゴールと するのであれば、
pole([], [], [_| _]).
と書けば、何枚の場合でも最後のリストのみ空リストではないことを 示すので、対応できる。
Step 1, 2 を済ませると残り1枚を1番目から3番目に動かせば良い状態から 最後の状態に移ることができるかどうかを確かめることができる。 例えば、「pole([1], [], [2, 3, 4]).」が成立するはずである。
ここまででは成立するかどうかはわかるが移動の様子は画面に出ない。 そこで、Step 1で定義した節に手を加えて、画面に表示させる。その節が 成立したら、成立した条件を画面に出せば良いので、上の例を修正したものを 示すと
pole([A| AL], B, []) :- pole(AL, B, [A]), writeln(pole(AL, B, [A])).
のようにすれば良い。 ただし、writelnをこのように後ろにつけた場合は、最後まで 解を得られた後に画面に表示される。例えば、堂々巡りしてしまっている ような場合にはなかなか表示されないということが起きる。 その場合は、条件部の先頭にwritelnを入れれば、堂々巡りしている 様子も見ることができる(ただし、正解にたどり着かなかった場合の移動も 画面に表示されるので、最終的には条件部の最後に記述するべきである)。
Step 1では一通りの移動のみであるが、これを3本の棒それぞれの 間を動かす場合のものを追加する。3つのうちの2つの順列を書くことになるので、 6通りになる。
ここで、一度3枚程度の場合で実行してみるとどうなるか確かめる。 例えば、「pole([1, 2, 3], [], []).」を入力してみる。多くの場合 止まらないか、スタック溢れでエラーとなるはずなので(止まらない場合は途中で ^Cで 強制的に止めて)、「g」と入力してどんな動きになっているか 画面に表示されたものを見てみると堂々巡りになっていることが解かる。
延々と止まらないのはおかしいので、ある程度の手数だけ進めて ゴールにたどり着けないなら強制的に失敗させ、別の手を試させるようにする。 実際には、手数が指定よりも大きくなったら単にその先に進ませない ようにするだけで別の節を試すようになるので、再帰の深さを制限する方法を 試す。例えば、再帰によって同じデータを繰り返して表示する述語を単純に 定義すると以下のようになるが、これでは止まらない。
repeat_writeln(X) :- writeln(X), repeat_writeln(X).
これをもう一つ引数を増やして繰り返す回数、すなわち再帰する深さを 指定すると、次のようになる。
repeat_writeln(X, N) :- N > 0, writeln(X), N1 is N - 1, repeat_writeln(X, N1).
この例を参考にして、再帰の深さを制限するようにせよ。 その際引数が増えるので修正の見落としが ないようにすること。
一応ここまでである程度円盤を「正しく」動かすものができるはずであるので、 確認する。なお、3枚程度の時に深さ(手数の最大)を100ぐらいにするとどうなるか も試してみよ。
最大の手数を増やすと堂々巡りする局面が出てくる。これは無駄な手数なので、 これを抑止する方法を考えて組み込んでみる。要するにそこまでに辿った途中の 状態と同じ状態に入らないようにすれば良い。 引数を増やして、そこにこれまで辿った途中の状態をリストで持たせ、 それに含まれる状態に入らないように条件を書く方法が無難である。 手数の上限を設けるやり方は、手数の目安がわかっていれば良いが、 そうでない場合に困ることがあるので、こちらの実装も重要である。
練習8の述語gennumの定義に関しては、そのままではバックトラック をさせると、0以上の整数は無限にあるので、 延々とその別解が求められる。その結果、例えば 0〜9といった決まった範囲の数値を生成することができなかった。
そのため、第1回の最後の4つの数字を組み合わせる課題に単純に使用すると、 最初の値が求まったとしても、バックトラックさせるとなかなか終了せず、 エラーになるなど期待通りに動作しない。
これでは使い勝手が悪いので、決まった範囲の整数を生成するように 修正を試みる。
gennum(0).
gennum(N) :- gennum(N1), N is N1 + 1.
問題点は再帰の順序にある。階乗など再帰によって値を求める場合などは、 通常再帰を止めるための条件を書くが、このgennumの場合は、 再帰を止めるのは1番目の節である。そこで一旦再帰が止まっても、 バックトラックした場合には2番目の節を用いる。 これが無条件で再帰に突入するので、 止まらなくなる(条件部の一つ目の述語が再帰になっている)。
階乗の場合は、これをカット(!)を付与したり、条件部の再帰の前に 値の条件を指定し、再帰を止めることができるが、このgennumの場合 にはそのような方法を使うことはできない。
このような場合には、カットと OR (;)、failを使って 無理矢理次のように定義することができる。
gennum1(0).
gennum1(N) :- gennum1(N1), N is N1 + 1, ((N > 9, !, fail); true).
このgennum1は0〜9までの整数を生成することができる。 しかしながら、これは少しトリッキーな方法でもあるので、 もっと素直な方法について考える。
問題は、バックトラックを繰り返すと再帰が無限に深くなって しまうことにある。そこで、この再帰の深さに制限を持たせることができれば良い。 再帰の深さを数える引数を追加して、再帰する度にそれに1ずつたせばどのくらい の深さになったかがわかる。まず深さを数えるようにしたものが次の定義である。
gennum2(0, D) :- writeln(D).
gennum2(N, D) :- D1 is D + 1, gennum2(N1, D1), N is N1 + 1.
2番目の引数で深さを数え、最後には必ず1つ目の節で止まるので、 そこで確認のために画面に表示する。このgennum2を使う際には 「gennum2(X, 0).」のように第2引数に0を指定する。なお、 NとDで同じ数を数えているように見えるが、深さを数える方は再帰の前に 加算することに注意せよ。一方生成する方は先に加算することはできず、 再帰で、1つ目の節にマッチした時点で初めて値が決まっていく ことになる。あとは、これに再帰する前に次のように条件を指定すれば良い。
gennum3(0, _).
gennum3(N, D) :- D < 9, D1 is D + 1, gennum3(N1, D1), N is N1 + 1.
これで一応の完成となる。これを使う際は「gennum3(X, 0).」の ようになる。 しかし、これでは生成したい数の範囲が変わると その度に節を定義し直さなければならない。そこで、深さを加算するのではなく、 最初に深さの上限を与え、そこから再帰の度に減算し、0になれば再帰を 止めるということにすれば、最初に深さの上限を与えることで数の範囲を 変えることができる。
gennum4(0, _).
gennum4(N, D) :- D > 0, D1 is D - 1, gennum4(N1, D1), N is N1 + 1.
このように定義すると、「gennum4(X, 上限).」と指定すれば、 指定した上限までの整数を生成することに使える。前回の練習問題用に 引数を1つだけにしたければ、以下のような定義を追加すれば良い (注: Prologでは述語名が同一でも引数の数が異なると、別の述語として 扱われる)。
gennum4(N) :- gennum4(N, 9).
なお、この再帰の深さを制御する方法は、パズルを解かせる場合に 手数(手順)の上限を設けるために利用することができる。
by Tetsuo Sakaguchi
更新日時 $Date: 2013/01/22 03:49:07 $ (UTC)