マイ・Guarded Horn Clauses の可視化

[マイ・GHC](https://qiita.com/tadashi9e/items/45cef62cda6d38dda0c7) のデータ構造はタグ付きポインタから成り立っています。
レジスタおよびヒープ上にどのようにタグ付きポインタがあるのかをグラフィカルに見てみたいと思いました（自分でもどう動いているのか忘れてしまいかねないし）。

ウェブブラウザ上で見られるようにする、というのが見栄えもよくて便利そうですが、そうそう使うことがない機能の割に実装の手間がかなりのものになりそうです。

お手軽に Graphviz の dot 形式でファイルに書き出すことにします。

# 構想

各アドレスにあるタグ付きポインタは、タグの値に応じて以下のような値を保持します。

- 参照タグ(REF): 参照先アドレスを保持する
- アトムタグ(ATOM): アトム（文字列）を保持する
- 整数タグ(INT): 整数値を保持する
- リストタグ(LIST): CAR/CDR のペアへの参照アドレスを保持する
- ヌル値タグ(NIL): リストの終端を表す
- 構造体タグ(STR): 構造体への参照アドレスを保持する
- 待ち合わせタグ(SUS): 具体化待ちゴールがある未実現変数
- オブジェクトタグ(OBJ): オブジェクトへの参照アドレスを保持する

一つのタグ付きポインタを、Graphviz 上では一つの箱で表すことにして、箱から箱への矢印で参照を表すことにします。
アトムや整数、NIL のように他を参照しない場合には矢印なしで、箱のラベルとしてその値を表示することにします。

箱の表示の出発点（ルート要素）となるのはコンテキストスタックです。コンテキストスタックが当該コンテキストでのレジスタウィンドウ位置を指し示し、レジスタからヒープ上の変数・リスト・構造体・中断ゴールなどを指し示します。

# グループ化

「レジスタ上にある値」のように一連の繋がりがあるものについては、グループ化して、ひとかたまりの連続した箱として表現することにします。

例えば、

- アトム・整数が格納されているアドレスは一つの箱で表現します。格納している値は箱のラベルに表示します。
- 参照タグの付いたポインタの参照先は、一つのアドレスなので一つの箱で表現できます。
- リストタグの付いているタグ付きポインタの参照先は、CAR/CDR をグループとして２つの箱で表現することにします。
- 構造体タグの付いているタグ付きポインタの参照先は、一つの構造体としてグループ化しますが、この場合には構造体のサイズに応じてグループ内の箱の数が変わります。

さらに一般化して複雑な場合を考えると、参照タグの付いたポインタの参照先が実は構造体の要素の一つだった、などという可能性もあります。

このため、以下のようなアルゴリズムでグループを結合して表示することにしました：

1. タグ（例えばリストの場合は固定値２）および参照先（例えば構造体の場合には参照先に書かれたアリティの値）に応じて参照先グループの最低サイズを決定する。
2. 今からグループ化しようとしている参照先アドレスに重複する位置に既存グループがあるか調べる。
2-1. 重複する既存グループがなければ、最低サイズ分の新しいグループを当該アドレスに作る。
2-2. 重複する既存グループがあれば、それらを包含するサイズの新しいグループを作る。新しいグループに重複する既存グループは全て削除する。

一旦、ルート要素から辿って全てのアドレスについて上記の手続きを繰り返し、表示すべき全てのグループを決定します。

決定したグループは、Graphviz 上にレコードとして表示します。

グループを決定する過程でエッジ（矢印）として表示すべき箇所も決定できます。

# 実行例

このようにして可視化した例が以下です。

![primes.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/4d658b80-89d4-ef40-0c1d-62ada99c18e2.png)


ここでは、以下のプログラムによって `primes/2` 実行中に、2 から 5 までの整数のリストを作成した直後の状態を表示しています（画像サイズを抑えるために 5 までにしています）。

```prolog
primes(Max, Ps) :-
    true |
    gen(2, Max, Ns),
    dump_to_dot('dump/primes.dot'),  % ←ここで可視化
    sift(Ns, Ps).
gen(N0, Max, Ns0) :-
    N0 =< Max | N1 := N0 + 1, Ns0 = [N0 | Ns1], gen(N1, Max, Ns1).
gen(N0, Max, Ns0) :-
    N0  > Max | Ns0 = [].
sift([P|Xs1], Zs0) :-
    true | Zs0 = [P | Zs1], filter(P, Xs1, Ys), sift(Ys, Zs1).
sift([], Zs0) :-
    true | Zs0 = [].
filter(P, [X|Xs1], Ys0) :-
    X mod P =\= 0 | Ys0 = [X | Ys1], filter(P, Xs1, Ys1).
filter(P, [X|Xs1], Ys0) :-
    X mod P =:= 0 | filter(P, Xs1, Ys0).
filter(_, [],      Ys0) :-
    true | Ys0 = [].

printstream(Ps) :- outstream(Stream), printstream(Ps, Stream).
printstream([], Stream) :-
    true | Stream = [].
printstream([P|Ps], Stream) :-
    true |
    Stream = [write(P) | Stream2],
    printstream_rest(Ps, Stream2).
printstream_rest([], Stream) :-
    true |
    Stream = [nl].
printstream_rest([P|Ps], Stream) :-
    true |
    Stream = [write(','), write(P) | Stream2],
    printstream_rest(Ps, Stream2).

main([_, A]) :-
    printstream(Primes),
    atom_number(A, N),
    time(primes(N, Primes)).
otherwise.
main([Prog|_]) :-
    outstream([write('usage: '), write(Prog), write(' <max>'), nl]).
```

`active` と書かれた箱が３つあるのがコンテキストスタックです（`active`とあるのはアクティブ・ユニフィケーション状態であることを表します）。各コンテキストから、当該コンテキスト実行時点での入力レジスタ位置への矢印を描いています。

active と書かれた箱から矢印で差されているのがレジスタです。レジスタは実行状況に応じて伸び縮みします。

この例では、最初に起床されたゴールの `time/1` およびその引数が先頭コンテキストにあり、そこから再帰的に `primes/2`、`__dump_to_dot__/1` のゴールが呼び出されています。

dot ファイルへのダンプを行う `dump_to_dot/1` という組み込み述語を作って使っているので、必ず `__dump_to_dot__/1` のゴール呼び出しが最後に現れることになります。

レジスタ先頭の `time/1` およびそれに続く引数が指す値を見ていくと、
`time/1` の引数に `primes(10, Ps)` のような構造体が与えられていて、さらにその構造体引数の変数は中断ゴール `printstream/2` によって具体化待ち合わせが行われていること、さらにその `printstream/2` の引数の具体化を `outstream/1` が待っているのを見て取ることができます。

レジスタ上でゴール `__dump_to_dot__/1` の直前にある変数からリスト `[2,3,4,5]` への参照がありますが、これが `gen/2` が生成した整数リストです。
この値は `dump_to_dot/1` 終了後の `sift/2` によって参照されることになります。

レジスタ上に `<REF>0` とあるのは初期状態のまま使用されなかった部分です。今のコンパイラは変数出現順にレジスタ上の位置を重複しないように割り当てているため、使われないまま残る箇所がちらほら現れます。

# ガベージコレクションに向けて

ガベージコレクションなしでも特に困っていないのでなかなか実装しようという気になれないのですが、dot ファイルを見ているとガベージコレクションもさほど難しくなく実装できそうな気がしています（dot ファイル表示対象部分を新しいヒープにコピーすればよいだけ）。

ただし、dot ファイル生成で行っているグループ化処理はコストが高いため、これをそのままガベージコレクションに流用するのは躊躇われます。多少の重複コピーがあっても目をつぶる形で処理を簡略化する必要がありそうです。