2008年5月9日(金)
この資料では第2回の資料の再帰の深さの制御についてもう少し 別の例を示す。
解答例ex7.plで示した 述語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).
なお、この再帰の深さを制御する方法は、パズルを解かせる場合に 手数(手順)の上限を設けるために利用することができる。