Prolog (1)

Prologの強みはなんと言ってもパターンマッチングとバックトラックです。それを利用することによって、「どうやって(how)?」ではなく「どんな(what)?」でプログラミングを行うことが可能となります。またPrologは型の無い動的な言語なので、自分がどういった仕様を欲しているのか、スケッチするように考えながら作ることが出来ます。例えば簡単な電卓を作るプロセスを紹介します。

まずは四則演算がどういったものなのか、思いついたまま書き下してみました。

% calc_op/4
calc_op(X, +, Y, Z) :- Z is X + Y.
calc_op(X, -, Y, Z) :- Z is X - Y.
calc_op(X, *, Y, Z) :- Z is X * Y.
calc_op(X, /, Y, Z) :- Z is X / Y.

引数の部分がこれで良いのかどうか、現時点では分かりません。なので他のアイデアとして、こんな事も考えてみました。

calc_op([X, +, Y | R], Ans) :-
    calc_op(R1, Ans),
    append([Z], R, R1),
    Z is X + Y.

ですが、この方法だと演算子の優先度を解決するために、演算子の組み合わせの数だけパターンを用意してやらなければならない事が分かります。だって、+Yの後に*が来たら、Zはまだ計算しちゃいけませんからね。もちろん、後者の方法でも場合分けのパターンを網羅してやれば（MECE... MECE... MECE...）、誤った選択はバックトラックによって解の候補から消えていくので間違った実装では無いでしょう。でも組み合わせの数は簡単に膨れ上がることは察してやる必要があります。

ここではとりあえず、演算子が増える事を想定して、演算操作と操作の組み合わせは別の論理として表現する道を選びました。それでは、前者の個別に表現された演算の論理を制御する部分を考えます。

% calc/2
calc([], []).
calc([X], [X]).
calc([X, Y, Z | R], Ans) :-
    calc_op(X, Y, Z, A1),
    append([A1], R, E),
    calc(E, Ans).

一歩づつ、とにかく実行させて行くことが重要です。クロッキー片手に製図のような線を引くことはないですよね？とりあえず数式をリストで渡してやれば、頭から演算を適用して答えを返すところまで来ました。当然、数式によっては間違います。

ここまではほとんど何も考えずに来るわけですが、ここで少し考えます。さて演算子の優先順位をどうやって解決してやろうか？と。僕も含め、恐らく多くの人はまず入力されたリストをパースしてRPNのような構造に変換しようと考えると思います。今回はそれだと普通過ぎるなと思ったのでわざと違うことをしてみました。実際に目の前に式を提示されたらどうやって順番決めて解いていくかしら？というアプローチです。

ここは極端な話、人によりけりですし、問題によって解き易いように分解したりファクタリングしたりすると思います。ですが単調な方法で行けば、まず一番優先度の高いところを解決して項を書き換えて、新しい式に次の優先度の書換えを施して、という手順です。

1+2*3-4/2 => 1+6-4/2 => 1+6-2 => 7-2 => 5

左から右、乗除から加算。つまり数式に対してステージングを行っているわけですね。そこで2つのステージに分けてみます。

% calc/2
calc(Exp, Ans) :- calc1(Exp, Tmp), calc2(Tmp, Ans).

% calc1/2
calc1([], []).
calc1([X], [X]).
calc1([X, Y, Z | R], Buf) :-
    calc1op(X, Y, Z, A1, B1),
    append(A1, R, E),
    calc1(E, A2),
    append(B1, A2, Buf).

% calc2/2
calc2([], []).
calc2([X], [X]).
calc2([X, Y, Z | R], A2) :-
    calc2op(X, Y, Z, A1),
    append(A1, R, E),
    calc2(E, A2).

どちらのステージでもリストの先頭から順にマッチングしたものを演算論理に渡します（ちなみにこれって、C/C++で言うディスパッチャみたいな処理ですね。パターンマッチのおかげで多重ディスパッチも簡単です）。演算論理の結果と先頭を挿げ替えて、再帰的に、ただしステージごとに分離した形で、マッチングを行っていきます。

1つめのステージ(calc1)では乗除算だけが実行されて、項が書き換わった式を生成します。2つめのステージ(calc2)では渡された加減算のみの式に演算を適用して答えを求めます。ステージ別に演算に要求される仕様が変わりましたから、このままでは動きません。最初の演算ルールを修正しましょう。

% calc1op/5
calc1op(X, *, Y, [Z], []) :- Z is X * Y.
calc1op(X, /, Y, [Z], []) :- Z is X / Y.
calc1op(X, +, Y, [Y], [X, +]).
calc1op(X, -, Y, [Y], [X, -]).

% calc2op/4
calc2op(X, +, Y, [Z]) :- Z is X + Y.
calc2op(X, -, Y, [Z]) :- Z is X - Y.

1つめのステージでは+,-演算を書き換えず、またバックトラックを起こさないために若干不恰好な論理を加えています。これで一先ずは四則演算が行えるようになりました。

?- calc([2,*,4,-,3,*,1], Ans).
Ans = 5 ;
No

正しい答えがただ1つ見つかりました。