GraphViz を用いた Prolog 項可視化

## 目的

Prolog の項を GraphViz を使って可視化します。

## 項のノードへの変換

与えられた項の要素すべてを再帰的に辿っていって GraphViz のノードに対応づけます。
出現順に番号を割り振っていって、GraphViz 上では node_番号 というノードだということにします。割り振った番号、割り振られた項そのものの情報を表現するために

node(番号, 項情報)

という形で管理することにします。項が子を持つ場合には子の情報も項情報に含みます。リストとかだと

node(番号, [ node(carの子番号,... ) | node(cdrの子番号,... ) ])

のような形で再帰的に続くことになります。

```prolog
%
% new_node(+作成前のノードリスト -> -作成後のノードリスト, +対象の項, -作成されたノード)
%
% ここで、ノードリストの初期値は [] (空リスト)

% 与えられた項が変数の場合
new_node(Nodes -> Nodes2, Var, Node) :-
    var(Var), !,
    Node = node(_,  Var),
    allocate_node(Nodes -> Nodes2, Node), !.
% 与えられた項がノードならなにもしない
new_node(Nodes -> Nodes, Node, Node) :- Node = node(ID, _), number(ID), !.
% 与えられた項がリストの場合
new_node(Nodes -> Nodes4, [ A | B ], Node) :-
    new_node(Nodes -> Nodes2, A, Anode),
    new_node(Nodes2 -> Nodes3, B, Bnode),
    Node = node(_,  [ Anode | Bnode ]),
    allocate_node(Nodes3 -> Nodes4, Node), !.
% 与えられた項がファンクタ（引数が一つ以上）の場合
new_node(Nodes -> Nodes3, Func, Node) :-
    Func =.. [Pred | Args ], \+ Args == [],
    new_node_for_all(Nodes -> Nodes2, Args, Anodes),
    Node = node(_,  func(Pred, Anodes)),
    allocate_node(Nodes2 -> Nodes3, Node), !.
% 与えられた項が上記以外（アトムなど）の場合
new_node(Nodes -> Nodes2, X, Node) :-
    Node = node(_,  X),
    allocate_node(Nodes -> Nodes2, Node), !.
% ファンクタ引数すべてについてノードに変換する
new_node_for_all(Nodes -> Nodes, [], []).
new_node_for_all(Nodes -> Nodes3, [A | As], [Anode | Anodes]) :-
    new_node(Nodes -> Nodes2, A, Anode),
    new_node_for_all(Nodes2 -> Nodes3, As, Anodes).
% 出現順に 0 から番号を払い出す述語
allocate_node([] -> [Node], Node) :- Node = node(0, _).
allocate_node(Nodes -> [Node | Nodes], Node) :-
    Nodes = [node(LastNodeID, _) | _],
    NewNodeID is LastNodeID + 1,
    Node = node(NewNodeID, _).
```
## ノードリストを元にした dot ファイルの作成

new_node/3 で作ったノードのリストを元に dot ファイルを作成できます。

node(番号, 子node)

という要素を持つリストからすべての番号部分を拾ってくると

 node_番号

という GraphViz 上でのノード名すべてを得ることができます。各ノードには子ノードがあるので、同様にノードリストから GraphViz 上でのエッジすべてを得ることができます。

```prolog
write_dot(Nodes, Stream) :-
    write(Stream, 'digraph nodes {'), nl(Stream),
    write_dot_nodes(Nodes, Stream),
    write_dot_edges(Nodes, Stream),
    write(Stream, '}'), nl(Stream), !.
% ノードすべてを dot ファイルに書き出す
write_dot_nodes([], _) :- !.
write_dot_nodes([node(ID, Var) | Nodes], Stream) :-
    var(Var), !,
    write(Stream, 'node_'), write(Stream, ID), write(Stream, ' [label="var"];'), nl(Stream), !,
    write_dot_nodes(Nodes, Stream).
write_dot_nodes([node(ID, [_ | _]) | Nodes], Stream) :-
    write(Stream, 'node_'), write(Stream, ID), write(Stream, ' [label="[_|_]"];'), nl(Stream), !,
    write_dot_nodes(Nodes, Stream).
write_dot_nodes([node(ID, func(Pred, Args)) | Nodes], Stream) :-
    write(Stream, 'node_'), write(Stream, ID),
    length(Args, Arity),
    write(Stream, ' [label="'), write(Stream, Pred),
    write(Stream, '/'), write(Stream, Arity), write(Stream, '"];'), nl(Stream),
    write_dot_nodes(Nodes, Stream).
write_dot_nodes([node(ID, X) | Nodes], Stream) :-
    write(Stream, 'node_'), write(Stream, ID),
    write(Stream, ' [label="'), write(Stream, X), write(Stream, '"];'), nl(Stream),
    write_dot_nodes(Nodes, Stream).
% エッジすべてを dot ファイルに書き出す
write_dot_edges([], _) :- !.
write_dot_edges([node(ID, [node(IDcar, _) | node(IDcdr, _)]) | Nodes], Stream) :-
    number(IDcar), number(IDcdr),
    write(Stream, 'node_'), write(Stream, ID),
    write(Stream, ' -> node_'), write(Stream, IDcar),
    write(Stream, ' [label="car"]'), nl(Stream),
    write(Stream, 'node_'), write(Stream, ID),
    write(Stream, ' -> node_'), write(Stream, IDcdr),
    write(Stream, ' [label="cdr"]'), nl(Stream),
    write_dot_edges(Nodes, Stream).
write_dot_edges([node(ID, func(_, Args)) | Nodes], Stream) :-
    write_dot_edge_foreach(ID, Args, 1, Stream), !,
    write_dot_edges(Nodes, Stream).
write_dot_edges([_ | Nodes], Stream) :- write_dot_edges(Nodes, Stream).
write_dot_edge_foreach(_, [], _, _) :- !.
write_dot_edge_foreach(ID, [node(Aid, _) | As], N, Stream) :-
    write(Stream, 'node_'), write(Stream, ID),
    write(Stream, ' -> node_'), write(Stream, Aid),
    write(Stream, ' [label="arg'), write(Stream, N), write(Stream, '"];'), nl(Stream), !,
    N1 is N + 1,
    write_dot_edge_foreach(ID, As, N1, Stream).
```

## GraphViz の呼び出しと画像表示 (ImageMagick)

ノードリストを元に

1. dot ファイルを作成する
2. dot ファイルを GraphViz を用いて png 画像ファイルに変換する
3. png 画像ファイルを ImageMagick の display コマンドで表示する

までをまとめると以下のような述語を作ることができます（display コマンドが終了するまでブロックするので、見終わったら display コマンドのウィンドウを閉じてください）。

```prolog
% 与えられたノードリストを、
% OutputBasePath + '.dot' の dot ファイル および
% OutputBasePath + '.png' の png ファイルに 変換する
do_graphviz(Nodes, OutputBasePath) :-
    format(string(DotPath), '~s.dot', [OutputBasePath]),
    format(string(PngPath), '~s.png', [OutputBasePath]),
    generate_dot_file(Nodes, DotPath),
    generate_png_file(DotPath, PngPath).
% ノードリストを dot ファイルに変換する
generate_dot_file(Nodes, DotPath) :-
    open(DotPath, write, Stream),
    write_dot(Nodes, Stream),
    close(Stream).
% dot ファイルを png 画像ファイルに変換する
generate_png_file(DotPath, PngPath) :-
    format(atom(DotCommand), 'dot -Tpng -o~s ~s', [PngPath, DotPath]),
    write('shell: '), write(DotCommand), nl,
    shell(DotCommand).
```
## 動作確認

実際にこれを使って Prolog 項を画像に変換する例は以下です。

```prolog
test1 :-
    % 適当な項をノードリストに変換する
    write('generating node list...'), nl,
    string_chars("テストプログラム", Cs),
    new_node([] -> Nodes, ["テストプログラム"| Cs], _),
    new_node(Nodes -> Nodes2, f(a, b, g(c, [d, e])), _),
    write('generated.'), nl,
    % GraphViz を使って画像に変換する
    OutputBasePath = "/tmp/test",
    do_graphviz(Nodes2, OutputBasePath),
    % ImageMagick の display コマンドを使って画像を表示
    format(atom(DisplayCommand), 'display ~s.png', [OutputBasePath]),
    write('shell: '), write(DisplayCommand), nl,
    shell(DisplayCommand).
```
![term_to_dot.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/0112c851-e27e-4cfb-a1f9-069430952ad1.png)
生成される dot ファイルはこんな感じです：
```dot
digraph nodes {
node_28 [label="f/3"];
node_27 [label="g/2"];
node_26 [label="[_|_]"];
node_25 [label="[_|_]"];
node_24 [label="[]"];
node_23 [label="e"];
node_22 [label="d"];
node_21 [label="c"];
node_20 [label="b"];
node_19 [label="a"];
node_18 [label="[_|_]"];
node_17 [label="[_|_]"];
node_16 [label="[_|_]"];
node_15 [label="[_|_]"];
node_14 [label="[_|_]"];
node_13 [label="[_|_]"];
node_12 [label="[_|_]"];
node_11 [label="[_|_]"];
node_10 [label="[_|_]"];
node_9 [label="[]"];
node_8 [label="ム"];
node_7 [label="ラ"];
node_6 [label="グ"];
node_5 [label="ロ"];
node_4 [label="プ"];
node_3 [label="ト"];
node_2 [label="ス"];
node_1 [label="テ"];
node_0 [label="テストプログラム"];
node_28 -> node_19 [label="arg1"];
node_28 -> node_20 [label="arg2"];
node_28 -> node_27 [label="arg3"];
node_27 -> node_21 [label="arg1"];
node_27 -> node_26 [label="arg2"];
node_26 -> node_22 [label="car"]
node_26 -> node_25 [label="cdr"]
node_25 -> node_23 [label="car"]
node_25 -> node_24 [label="cdr"]
node_18 -> node_0 [label="car"]
node_18 -> node_17 [label="cdr"]
node_17 -> node_1 [label="car"]
node_17 -> node_16 [label="cdr"]
node_16 -> node_2 [label="car"]
node_16 -> node_15 [label="cdr"]
node_15 -> node_3 [label="car"]
node_15 -> node_14 [label="cdr"]
node_14 -> node_4 [label="car"]
node_14 -> node_13 [label="cdr"]
node_13 -> node_5 [label="car"]
node_13 -> node_12 [label="cdr"]
node_12 -> node_6 [label="car"]
node_12 -> node_11 [label="cdr"]
node_11 -> node_7 [label="car"]
node_11 -> node_10 [label="cdr"]
node_10 -> node_8 [label="car"]
node_10 -> node_9 [label="cdr"]
}
```

## まとめ

Prolog 項を GraphViz を使って可視化できました。
簡単な Prolog プログラムのデバッグなどに使えそうです。