LoginSignup
0
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@tadashi9e

GraphViz を用いた Prolog 項可視化

Last updated at Posted at 2019-06-22

目的

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

項のノードへの変換

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

node(番号, 項情報)

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

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

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

%
% 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 上でのエッジすべてを得ることができます。

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 コマンドのウィンドウを閉じてください）。

% 与えられたノードリストを、
% 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 項を画像に変換する例は以下です。

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
生成される 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 プログラムのデバッグなどに使えそうです。

0
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?