§5   代入とバックトラック

 BASIC などのプログラミング言語では x = x + 1 といった 計算がよく用いられます。 このような言語では、変数を単なる「数値を記憶する場所」としてあつかっています。 従って変数の値をかえる操作(再代入)が許され、 それを繰り返すことで、複雑な計算を実行します。

 Prolog のような論理の世界では、 一度確定した変数の値を変更することは``不可''です。 初めて Prolog に接したとき、どうして値を変更できないの、 と多くの人は戸惑うでしょう。 実はこのことが、残念なことですが、Prolog プログラミングへの 高い敷居となっているようです。

 Prolog では変数への再代入はできませんが、 その代わりとして、 バックトラック機能(これは強力なメカニズムです)が用意されています。

 2次方程式 式 を解くこと考えてみます。 解と係数の関係を用いれば、a b = 6, a + b = 5 となる 2整数を求める問題となります。 Prolog への質問と実行結果は次のようになります。

    ?- mul(A,B,[0,6]),add(A,B,[0,5]).
    A=2
    B=3 ;
    A=3 
    B=2 ;
    no

 このように Prolog では、複数の述語をコンマで区切って並べる形の質問ができます。 意味は「a b = 6 かつ a + b = 5 となる a, b を求めよ」です。

 この質問はどのように実行されるのでしょうか。

(b) のように「変数の値を御破算とし、後戻りし、別解を探す」メカニズムを バックトラックといいます。 バックトラックにより、述語 mul(A,B,[0,6]) と述語 add(A,B,[0,5]) との間を 行ったり来たりして、試行錯誤をくり返し、 2つの述語を同時に満たす解を探します。

 2次方程式 式 の解を求めるときの次のような場面もバックトラックです。 因数分解により (x - 2)(x - 3) = 0。 (i) x - 2=0 のとき x = 2。 (ii) x - 3=0 のとき x = 3。 従って解の集合は {2,3}。 場合分けが2つあり、最初に (i) を計算し次に (ii) を計算するという手順ですが、 その (i) から (ii) に移るときにバックトラックが行われています。

 筆算による割り算にもバックトラックが使われています。 252 ÷ 36 を計算するとき、25 ÷ 3 から商 8 と見当をつける。 36× 8 = 288、 大きすぎた。 消しゴムで 8 と 288 を消す(値を御破算にする)。 商が大きすぎたので、商を順に 1つずつ小さくしてこの計算をやり直す(後戻り)。

 バックトラックと BASIC の IF-THEN-ELSE 文とは全く異なるものです。 バックトラックは必要ならば 2つの可能性の両方を試します。 一方の IF-THEN-ELSE 文は二者択一です。

 学校教育にコンピュータが導入され、子供達もそれを操作することが多くなります。 IF-THEN-ELSE 方式の「流れ図(フローチャート)」も学習するでしょう。 数学の計算手順を流れ図で説明しようとする試みも行われるでしょう。 でも、数学は Prolog と同様に論理を基礎にして作り上げられています。 BASIC 仕込みの IF-THEN-ELSE で計算手順を記述するよりは、 数学らしくストレートに、パターン・マッチングやバックトラックなる概念を 使って説明を試みてはいかがでしょうか。


follow link follow link