目的
Prolog メタインタプリタを作ることで、GraphViz で状態を表示しながらステップ実行できるようにします。
基本的な Prolog メタインタプリタ
メタインタプリタの書き方はいくつかあると思いますが、「制約論理プログラミング」（淵 一博監修・溝口 文雄・古川 康一・J-L.Lassez 編）には以下のような例が載っています：
prolog(true) :- !.
prolog((P, Q)) :- !, prolog(P) , prolog(Q).
prolog((P; Q)) :- !, prolog(P) ; prolog(Q).
prolog(Head) :-
functor(Head, F, N), functor(Copy, F, N),
clause(Copy, Body),
unify(Head, Copy),
prolog(Body).
「制約論理プログラミング」には、このメタインタプリタの拡張によって制約論理言語を実装する手順が詳細に書かれています。
同様な方法で「GraphViz を用いた Prolog 項可視化」で書いたノード形式で表現したデータ構造を持つ Prolog 処理系を実装します。ステップ毎に GraphViz で描画しながら実行することで、Prolog プログラムになにが起こっているのかを見られるようにしたいと思います。
可視化可能な Prolog メタインタプリタの実装
まずは、呼び出し口です。引数に、実行したい項を与えます。与えられた項を GraphViz を用いた Prolog 項可視化 に書いた形式の
node(番号, ...)
からなる木構造に変換して実行を開始します。
% 与えられた項を GraphViz に可視化しながら実行する
node_prolog(P) :-
% 与えられた項をノード形式に変換する
new_node([] -> Nodes, P, Node),
% 実行前の状態を描画
display_nodes(0 -> DispCount, Nodes),
% ステップ実行
node_prolog(DispCount -> DispCount2, Nodes -> Nodes2, Node), !,
% 実行完了後の状態を描画
display_nodes(DispCount2 -> _, Nodes2).
ここで、変換された項は以下の node/2 の木構造です。
- 変数は node(番号, _)
- リスト（ペア）は node(番号, [ carノード | cdrノード ])
- ファンクタは node(番号, func(述語名, 引数リスト))
- アトムは node(番号, アトム)
- 参照は node(番号, 参照先ノード)
といった形です。
ユーティリティ述語として、こんなものを用意します。
% 引数がノード形式で表現された項か調べる
is_node(node(ID, _)) :- number(ID).
% ノード形式で表現された項の内容を取り出す
unbox(Node, Content) :-
(
is_node(Node)
->
Node = node(_, Content1),
( unbox(Content1, Content) ; Content = Content1 )
), !.
% F がファンクタ、あるいはノード形式で用いている func(F, Args) ならば
% Pred, Args に分解して返す。
is_functor(F, Pred, Args) :-
(
\+ var(F),
functor(F, _, N), N > 0
->
F =.. [Pred | Args]
;
\+ var(F),
F = pred(Pred, Args)
->
true
).
メタインタプリタ本体は以下です。node(番号, ...) で表現された項を直接解釈・実行します。
上に引用した「制約論理プログラミング」のそれと見比べていただければ、基本的に同じであることがわかると思います。
node_prolog(DispCount -> DispCount3, Nodes -> Nodes5, Node) :-
( unbox(Node, Content) ; Node = Content ),
(
% true は無条件に成功する
Content = true
->
DispCount = DispCount3, Nodes = Nodes5
;
% 連言の実行
% (P , Q) は node(ID, func(',', [Pnode, Qnode])) に翻訳されている
Content = func(',', [P, Q])
->
subgoal_context(Nodes -> Nodes2, Node, P),
node_prolog(DispCount -> DispCount2, Nodes2 -> Nodes3, P),
subgoal_context(Nodes3 -> Nodes4, Node, Q),
node_prolog(DispCount2 -> DispCount3, Nodes4 -> Nodes5, Q)
;
% 選言の実行。
% (P ; Q) は node(ID, func(';', [Pnode, Qnode])) に翻訳されている
Content = func(';', [P, Q])
->
(
subgoal_context(Nodes -> Nodes2, Node, P),
node_prolog(DispCount -> DispCount3, Nodes2 -> Nodes5, P)
;
subgoal_context(Nodes -> Nodes2, Node, Q),
node_prolog(DispCount -> DispCount3, Nodes2 -> Nodes5, Q)
)
;
% 与えられた項にマッチする述語を実行する。
Content = func(Pred, Args)
->
length(Args, Arity), functor(Copy, Pred, Arity),
clause(Copy, Body),
Head =.. [Pred | Args],
node_unify(Nodes -> Nodes2, Head, Copy),
new_node(Nodes2 -> Nodes3, Body, BodyNode),
subgoal_context(Nodes3 -> Nodes4, Node, BodyNode),
display_nodes(DispCount -> DispCount2, Nodes4),
node_prolog(DispCount2 -> DispCount3, Nodes4 -> Nodes5, BodyNode)
).
% メタインタプリタデバッグ用
node_prolog(DispCount -> DispCount, Nodes -> Nodes, Node) :-
write('fail: '), write(Node), nl, !, fail.
呼び出し親子関係の表示
処理している項と、その項のサブゴールとして呼び出される項との親子関係をグラフ上で見ることができるように、以下の述語でノードリストに 'CONTEXT'/2 として登録しています。
subgoal_context(Nodes -> Nodes2, HeadNode, BodyNode) :-
ContextNode = node(_, func('CONTEXT', [HeadNode, BodyNode])),
allocate_node(Nodes -> Nodes2, ContextNode).
今の状態だと「ないよりはまし」レベルであまり見やすくはありません。
組み込み述語について
とりあえずのお試し実装なので組み込み述語には対応していません。対応させるには clause/2 を使っている部分で組み込み述語を適当な独自実装処理を返す必要があります。
ステップ実行
ここで、display_nodes は与えられたノードリストを元に GraphViz を使って画像を生成し display コマンドで表示するまでを行う述語です。DispCount は実行回数カウンタで、
/tmp/0.png
/tmp/1.png
/tmp/2.png
:
のように画像ファイルを残していきます（連番の画像ファイルを動画で見たいため）。
引数の DispCount->DispCount2 は、DispCount に開始番号を受け取ってその番号を基準に新たな番号を割り振っていき、使った番号の最大値を DispCount2 に返す、という意味で使っています。
% DispCount の使われ方を示すダミーソースコード
何か述語(DispCount -> DispCount5) :-
サブゴール1(DispCount -> DispCount2), % DispCount2 に値を返す
サブゴール2(DispCount2 -> DispCount3), % DispCount3 に値を返す
サブゴール3(DispCount3 -> DispCount4), % DispCount4 に値を返す
サブゴール4(DispCount4 -> DispCount5). % DispCount5 に値を返す
正直いうと、いちいち番号を自分で割り振って書かなければならないのは苦痛なのであまり人様におすすめできる書き方ではありません（Mercury だとマクロで !IO と書くと同じことが簡便に書けます）。
外部コマンド display が起動されるたびにそこでメタインタプリタの実行がストップするため、ステップ実行的な動きになります。
display_nodes(DispCount -> DispCount2, Nodes) :-
format(string(OutputBasePath), '/tmp/~d', DispCount),
do_graphviz(Nodes, OutputBasePath),
format(atom(DisplayCommand), 'display ~s.png', [OutputBasePath]),
write('shell: '), write(DisplayCommand), nl,
shell(DisplayCommand),
NextDispCount is DispCount + 1,
DispCount2 = NextDispCount.
単一化器
メタインタープリタ実装の肝となるのは単一化器の実装です。
生の Prolog 項同士の単一化は処理系がやってくれますが、独自に定義したノード形式同士、あるいは生の Prolog 項と独自に定義したノード形式との単一化は自分で実装する必要があります。
% X、Y 共に変数の場合には、一方をノード形式にラップして他方に代入。
% Y が変数でないなら X と Y をひっくり返して node を作らずに継続できることを期待する
node_unify(Nodes -> Nodes2, X, Y) :-
var(X), !,
(
var(Y)
->
new_node(Nodes -> Nodes2, Y, X)
;
node_unify(Nodes -> Nodes2, Y, X)
).
node_unify(Nodes -> Nodes3, X, Y) :-
( unbox(X, Xc) ; X = Xc), ( unbox(Y, Yc) ; Y = Yc), !,
(
var(Xc)
->
new_node(Nodes -> Nodes3, Y, Xc)
;
var(Yc)
->
new_node(Nodes -> Nodes3, X, Yc)
;
Xc = [], Yc = []
->
Nodes = Nodes3
;
Xc = [X1 | X2], Yc = [Y1 | Y2]
->
node_unify(Nodes -> Nodes2, X1, Y1),
node_unify(Nodes2 -> Nodes3, X2, Y2)
;
is_functor(Xc, Pred, Xargs),
is_functor(Yc, Pred, Yargs)
->
node_unify(Nodes -> Nodes3, Xargs, Yargs)
;
Xc = Yc, Nodes = Nodes3
), !.
% デバッグ時には以下を有効にする
node_unify(Nodes -> Nodes, A, B) :-
write('failed to node_unify: '), nl,
write(' '), write(A), nl,
write(' and '), write(B), nl,
(
A = B, write(' ??? must be success ???'), nl
), fail.
動作確認
append/3 をメタインタプリタで実行してみます。といっても、通常の append/3 は組み込み述語のため、append/3 相当の述語を自分で定義して実行する必要があります。
test_append([], X, X).
test_append([A|As], Bs, [A|Cs]) :-
test_append(As, Bs, Cs).
test1 :-
node_prolog(
(
test_append(['こ', 'れ', 'は'], ['テ', 'ス', 'ト'], A),
test_append(A, ['で', 'す'], B)
)),
write(B), nl.
ffmpeg コマンドを使えば、ステップ実行で生成した /tmp/[通し番号].png をまとめて gif アニメーション化することができます。
$ cd /tmp
$ ffmpeg -r 1 -i %d.png -vf format=gray anim.gif
...アニメーションで見ても少しも分かりやすい感じがしないのが難点です。
まとめ
Prolog プログラムをステップ実行しながら、実行状況をノードグラフとして可視化できます。
しかし、アニメーション化に耐えるほどきれいな表示にはなりません。GraphViz はあくまで与えられたファイルに従って描画するだけのツールであって、時間的な連続性を考慮した滑らかな動きを目的としたツールではないためです。
また、実行中に出現したすべてのノードを記録しているためにあまり実用的でもありません。GraphViz 上に表示するノードを適当に削る処理を追加するとか、種類によってノードやエッジの表示を変えるとかすれば若干見やすくもなるかもしれません。