前回の進捗
前回の記事でPrologメタインタプリタを作りました。仕事の合間の気晴らしに書いたのでかなり手抜きでした。前回のバージョンでは再帰が動作しません。今回は再帰について考えなおし、メタインタプリタが動作するようにします。
再帰の簡単な例として階乗計算をとりあげましょう。メタインタプリタは変数をvX,vN のように記述することになっていました。これによれば次のようになります。
fact(0,1).
fact(vN,vX) :-
vN1 is vN-1,
fact(vN1,vX1),
vX is vN*vX1.
α変換
再帰をする場合に考えなくてはならないことに名前の衝突があります。fact/2が再帰した場合には変数の名前を変えてやらないといけません。同じXという変数でも再帰で呼び出された場合には別物です。これをうまくやるのにα変換を行うこととします。再帰の都度変数名を唯一の名前に書き換えてしまうのです。
?- alpha_rename((foo(vX) :- vX1 is vX-1,foo(vX1)),New,0).
New = (foo(vX0):-vX10 is vX0-1,foo(vX10)) .
yes
?-
各変数の名前に共通した数を追加します。これにより変数の衝突を防ぐことができます。resolve/3をresolve/4に変更します。第４引数に０から始まる整数を与えます。alpha_renameはその数をもとに再帰ごとに変数名をユニークに変換します。
変数が変数をUnify
Prologの場合、変数が変数を束縛することが多々あります。XがYとunifyし、YがZにunifyし、Zが３にunifyするということもよくあることです。X＝３なのですがそれをメタインタプリタに理解してもらう必要があります。変数を探し出すfindvar/3に工夫をします。変数Xを探しだす場合、まずは変数Yに束縛していることがわかります。そこでもう一度Yを探します。するとこんどはZに束縛していることがわかります。こんどは変数Zを探します。するとようやく３に束縛していることが判明します。ここでようやく終了です。Zが未束縛の場合にはZを返します。最終的に見つけたものが変数ならばその変数は未束縛だということがわかります。
このことにあわせてunify/3なども書き換えてしまいます。
トレース
メタインタプリタのデバッグプリントのコメントアウトを外して途中経過とその時の変数環境を表示していみます。ゆっくり追いかけられるようにステップ実行できるようにしてあります。
階乗計算を追いかけてみましょう。
?- prolog.
?> fact(3,vX),write(vX).
fact(3,vX)in[]
vN11 is 3-1in[[vX,vX1],[vN1,3]]
fact(2,vX11)in[[vN11,2],[vX,vX1],[vN1,3]]
vN15 is 2-1in[[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
fact(1,vX15)in[[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
vN19 is 1-1in[[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
fact(0,vX19)in[[vN19,0],[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
vX9 is 1*1in[[vX19,1],[vN19,0],[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
vX5 is 2*1in[[vX9,1],[vX19,1],[vN19,0],[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
vX1 is 3*2in[[vX5,2],[vX9,1],[vX19,1],[vN19,0],[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
write(6)in[[vX1,6],[vX5,2],[vX9,1],[vX19,1],[vN19,0],[vX15,vX9],[vN9,1],[vN15,1],[vX11,vX5],[vN5,2],[vN11,2],[vX,vX1],[vN1,3]]
6yes
?>
各ゴールがα変換されているのがわかります。そしてその時の変数環境に注目してください。変数が変数を束縛しています。これを追跡することにより最終的な答えを得ています。メタインタプリタは名前の衝突を避けつつ、各変数の関連をうまく取り扱っているのがわかると思います。
さあ、やってみよう。
どうだったでしょう。Prolog、論理プログラミングは難しいという話をよく聞きます。普通の言語よりずっとややこしいことをしています。その分、人間の考える部分を大幅に簡素化していることがわかってくると思います。仕組みがわかってくるとPrologの理解がぐっと深まると思います。大学でPrologを教わることもあろうかと思います。やっていることがわかると親しみがわいてくることでしょう。
フルコードはgithubにおいてあります。