名前付けと名前参照によるサイクルとシェアリングの表現
「letマップ付きグラフ」で、letマップ付きグラフは、結局はサイクルとシェアリングを持つグラフの表現だ、と述べた。逆に、サイクル/シェアリングを持つグラフから出発して、letマップ付きグラフを作ってみる。これにより、ふだん我々が使っている名前機構(名前空間、名前空間のエントリー、名前による参照)の構造と使い方が明確になる。
まず、例題のグラフ。ここで出てくるラベル、A, B, ... は、ノードの「名前」ではなくて、説明用の識別ラベルである。名前に関係するノードは(後で)ピンクで示す。
任意の連結グラフにスパニングツリーが存在する。スパニングツリーを選んで、スパニングツリー以外の辺を赤点線で示す。
赤点線の辺を、名前付け(naming)と名前参照(reference)に置き換える。ピンク四角が名前付けノード、ピンク楕円が名前参照ノードである。
名前付けノードをデータツリーの一部に埋め込んでしまうのがインラインネーミング方式で、fetchで使われている@=構文がコレ。
名前付けノードをデータツリーとは別な場所において、データツリーには名前参照ノードだけにするとletマップ方式となる。letマップ=名前空間なので、通常の名前空間を使う方式はコレになる。
テキスト構文として直接表現できる構造がツリーに限られるので、名前付けと名前参照を使ってサイクリックシェアリンググラフを表すことになる。名前の使用は原理的に避けられない手段ではあるが、間接的で冗長になるし、リンク用に導入する名前は恣意的となる。恣意的だからアルファ変換が可能だが、アルファ変換(系統的リネーム)の手間はバカにならない。
絵のソース。
/* cyclic-graph-1 */ [ gv:node A, gv:node B, gv:node C, gv:node X, gv:node Y, gv:edge --label=p A X, gv:edge --label=q A B, gv:edge --label=r X C, gv:edge --label=s B C, gv:edge --label=t C B, gv:edge --label=u C Y, gv:edge --label=v Y A, ] | gv:graph cyclic-graph-1
/* cyclic-graph-1a */ [ gv:node A, gv:node B, gv:node C, gv:node X, gv:node Y, gv:edge --label=p A X, gv:edge --label=q A B, gv:edge --color=red --style=dashed --label=r X C, gv:edge --label=s B C, gv:edge --color=red --style=dashed --label=t C B, gv:edge --label=u C Y, gv:edge --color=red --style=dashed --label=v Y A, ] | gv:graph cyclic-graph-1
/* -*- coding: utf-8 -*- */ /* cyclic-graph-2 */ [ gv:node A, gv:node B, gv:node C, gv:node X, gv:node Y, gv:node --style=filled --fillcolor=pink --shape=box a, gv:node --style=filled --fillcolor=pink --shape=box b, gv:node --style=filled --fillcolor=pink --shape=box c, gv:edge --arrowhead=onormal --color="black:white:black" a A, gv:edge --arrowhead=onormal --color="black:white:black" b B, gv:edge --arrowhead=onormal --color="black:white:black" c C, gv:node --style=filled --fillcolor=pink --label="a" A_, gv:node --style=filled --fillcolor=pink --label="b" B_, gv:node --style=filled --fillcolor=pink --label="c" C_, gv:edge --label=p A X, gv:edge --label=q A B, gv:edge --label=r X C_, gv:edge --label=s B C, gv:edge --label=t C B_, gv:edge --label=u C Y, gv:edge --label=v Y A_, ] | gv:graph cyclic-graph-2
/* -*- coding: utf-8 -*- */ /* cyclic-graph-3 */ [ gv:node A, gv:node B, gv:node C, gv:node X, gv:node Y, gv:node --style=filled --fillcolor=pink --shape=box a, gv:node --style=filled --fillcolor=pink --shape=box b, gv:node --style=filled --fillcolor=pink --shape=box c, gv:edge --arrowhead=onormal --color="black:white:black" a A, gv:edge --arrowhead=onormal --color="black:white:black" b B, gv:edge --arrowhead=onormal --color="black:white:black" c C, gv:node --style=filled --fillcolor=pink --label="a" A_, gv:node --style=filled --fillcolor=pink --label="b" B_, gv:node --style=filled --fillcolor=pink --label="c" C_, gv:edge --label=p A X, gv:edge --label=q A b, gv:edge --label=r X C_, gv:edge --label=s B c, gv:edge --label=t C B_, gv:edge --label=u C Y, gv:edge --label=v Y A_, ] | gv:graph cyclic-graph-3
/* -*- coding: utf-8 -*- */ /* cyclic-graph-4 */ [ gv:node A, gv:node B, gv:node C, gv:node X, gv:node Y, [ gv:node --style=filled --fillcolor=pink --shape=box a, gv:node --style=filled --fillcolor=pink --shape=box b, gv:node --style=filled --fillcolor=pink --shape=box c, ] | gv:cluster --label="let map" letmap, gv:edge --arrowhead=onormal --color="black:white:black" a A, gv:edge --arrowhead=onormal --color="black:white:black" b B, gv:edge --arrowhead=onormal --color="black:white:black" c C, gv:node --style=filled --fillcolor=pink --label="a" A_, gv:node --style=filled --fillcolor=pink --label="b" B_, gv:node --style=filled --fillcolor=pink --label="c" C_, gv:node --style=filled --fillcolor=pink --label="b" B2_, gv:node --style=filled --fillcolor=pink --label="c" C2_, gv:edge --label=p A X, gv:edge --label=q A B2_, gv:edge --label=r X C_, gv:edge --label=s B C2_, gv:edge --label=t C B_, gv:edge --label=u C Y, gv:edge --label=v Y A_, ] | gv:graph cyclic-graph-4