ツリーの参照グラフと、変換コピー接ぎ木の手順

ツリーをいちいちリアルに描くとめんどくさいから、三角形で略記。

◎の「ツリー全体を表すノード」は、DOMの文書ノード（ルート要素ノードとは別）のようなもの。ルートノードとは別にあったほうが便利。参照ノードはリーフの位置にあるが、意味的には他の場所まで伸びる辺（グラフのedge）。参照先（ターゲット）は、ツリーの番号とか名前で示す。メモリ内ならほんとの参照（メモリアドレス）でもいい。

1つ以上のツリーがあると、それらのあいだの参照関係は有向グラフになる。

上のほうは割とリアル（つっても三角形で略記）に描いたヤツ。1つのツリーを◎で表現してしまい、参照を辺として描くと、サイクルや多重辺を持つ有向グラフとなる。参照辺には、パラメータリストが記号的代入として付着しているが、それは絵に描いてない（でも使う！）。

さー、次は色付きで説明。

2つのツリーが相互参照している状況。1番のツリーに注目して、自分（1番）から参照されているツリーたちをコピーして接ぎ木する。コピーとは言っても、完全に同じならコピーする必要はない。パラメータリストが代入を定義し、代入は一種のツリー変換となる。このツリー変換で変更を受ける場合に、もととちょっと違ったツリーをコピーする。単なるクローンじゃなくて、変換を施したコピー。

2番の変換コピーが2'、それを1に接ぎ木する。2'から1への参照は残るから、1の変換コピー1'を作って接ぎ木。1'から2'への参照をさらに変換コピー接ぎ木をする、と続く。その状況と手順を簡略に示したのが上の図の下側の螺旋階段風の絵。

下の写真はほんとの螺旋階段。

ほんとの螺旋階段じゃない絵で、赤と青の矢印は変換コピー操作、黒の矢印は接ぎ木操作を表す。例えば、1→2' の矢印は、ツリー1の下にツリー2'を接ぎ木することを意味する。

変換コピーがどんどん出来ると、螺旋階段は無限に上に昇ることになる。これは、接ぎ木も無限に行うことを意味して、永久に終わらない。それじゃ困る。そこで、いずれは新しい変換コピーが不要となる状況を考える。言い換えると、変換コピーをどんどん作ると、オリジナルと同じものができるような場合； オリジナルと同じならコピーする必要はないので、コピーの無限連鎖は避けられる。

変換コピー（赤）と接ぎ木（黒）が有限回で終わる例：

この絵のような話を整理するために、僕はモノドロミー（monodromy）という言葉を使ったのだった。モノドロミーの説明は別エントリーで中途半端になっているから、後で書き足す。[追記]書いたよ[/追記]