Iterator/Descriptor/PropertyMap による抽象化は非常に完成度が高く, Boost.Graph に限らず,汎用プログラミングの1つの高度な到達点だと思っていて,これによってとりあえずプログラムが走るようにデータ構造をでっち上げておいてから,後でデータ構造をちょこちょこ変えるということが「ユーザ側のコードの変化を全く伴わずに」可能になるという強烈な利点があり(ただし,この恩恵を得るためにはユーザ側のコードがきちんと Iterator/Descriptor/PropertyMap の Concept のみに基づいて書かれていないといけない),さらに極端なケースとして,データ構造をメモリ上に全く展開することなく,全てを Iterator/Descriptor のインタフェース内部で on-the-fly でデータ構造を現出させているかのような仕様変更にすら「ユーザ側のコードの変化を全く伴わず」耐えることができる.もっともこの例はかなり極端だけれど,より現実的なユースケースとしてはメモリ上に部分的に展開された(巨大な)データ構造,例えばストリーム上に乗っているデータ構造やら,メモリより相対的に遅いストレージに一部が乗っているようなデータ構造に対しても,やっぱり「ユーザ側のコードの変化を全く伴わずに」対応できるキャパシティを潜在的に持っていると思われる.
で,そんな雲をつかむようなワケの分からない話はどちらかとゆ〜とどーでもよくて,上のように強力なデータ構造抽象化能力の一翼を担う PropertyMap についてちょっと個人的なメモ.
前に, PropertyMap のインタフェースは operator[] じゃなくて operator() で提供するべきじゃないのか?っていう話題があってこのブログでもチラッと取り上げたけれど,
http://d.hatena.ne.jp/Cryolite/20050429#p1
http://article.gmane.org/gmane.comp.lib.boost.devel/121406
本当にインタフェースを operator() にすると, PropertyMap って結局関数オブジェクト(一般には PolymorphicFunctionObject) の Refinement になるんちゃうの?ってゆ〜.で PropertyMap は mapping 先のオブジェクトに対する書き込みを許すものもあるので,一見すると関数(mapping)の純粋性を破るような気がするけれど, PropertyMap は mapping 先の値を返す関数と考えているのではなくて, mapping 先そのもの(つまり値が置かれているストレージへの参照それ自体,ただしそれが実際に参照型で表されていない場合も多々ある)が返却値だという捉え方でいけば,純粋な関数となる……のではないか?ってゆー.っていうか, PolymorphicFunctionObject の Refinement で,特にこういう捉え方を要求するものがつまり PropertyMap コンセプトという考え方はダメですかそーですか.
Descriptor/PropertyMap による抽象化
っていうか, PropertyMap についてもうちょっとちゃんと説明しておこうっと.
例えばグラフ構造を考えたとき,グラフの頂点と辺を表現するにあたって,実際に頂点クラスと辺クラスがあって……という抽象化は多分オブジェクト指向なデータ構造の抽象化では(発想としては)一番自然かもしれないけれど,一般には様々なトレードオフなどからこのタイプの抽象化が許容できない場合も多い.例えば,最も代表的なグラフ構造の抽象化の1つである隣接リスト表現を考えても,頂点はプログラム上での明示的なオブジェクトとして表現されていない.
もう一つ重要な点は,グラフを扱う側(ユーザ側)ではグラフ構造がどういう抽象化をされているかなんてぶっちゃけどーでも良くて,(実際に頂点や辺がプログラム上で明示的な頂点オブジェクトあるいは辺オブジェクトとして表現されているかどうかに関係なく)あるグラフ内の「ある頂点を一意に表すナニカ」と「ある辺を一意に表すナニカ」があって(このナニカが具体的に何なのかもグラフ構造のユーザにとってはどーでも良い),「その辺を表すナニカから例えば辺の長さを格納したストレージへの mapping」が取得できさえすれば,例えばダイクストラパスは求められるし,求めたダイクストラパスを頂点の名前で表示したいなら,「頂点を表すナニカと頂点の名前を持ったストレージへの mapping」さえ得られればそれで良い.
ここで書いた「辺を表すナニカ」「頂点を表すナニカ」がつまり Edge Descriptor, Vertex Descriptor であり,「Edge Descriptor から辺の長さを格納したストレージへの mapping」「Vertex Descriptor から頂点の名前を格納したストレージへの mapping」を担うのがすなわち PropertyMap になる.
Descriptor は基本的にポインタ(本当は TrivialIterator(traverse の機能すらない Iterator)と書きたいけれど,なじみのない言葉なのでここではポインタと書く)に近い概念だけれども,決定的に違うのは,ポインタが指す先には本当にある概念に相当するオブジェクトが存在し,ポインタを dereference することによって実際にそのオブジェクトが取得できることが保証されるけれど, Descriptor はそうではない. Descriptor が指し示す概念上のモノが本当にプログラム上の1つのオブジェクトとして表現されているかどうかは分からない(プログラム上で1つのオブジェクトとして表現されていても構わないし,そうでなくても良い)し,そんなことはもはやどーでも良いというのが Descriptor.
さらに,ポインタと Descriptor との相違点として,ポインタはそれ単体で指し示している概念上のモノを一意に決定できる,ポインタオブジェクトさえあれば指している先のオブジェクトを取得できるけれど, Descriptor はそれ単体だけでは指示している概念上のオブジェクトを一意に表すことが保証できない.例えば, Boost.Graph では常に Descriptor はグラフを表すオブジェクトと共に用いないといけない(ただし「保証できない」だけで, Descriptor 単体で辺や頂点を指示するようなグラフ構造の抽象化も許容できる.この場合,グラフオブジェクトは各種インタフェースに対するただのディスパッチタグとしてしか機能しない). Boost.Graph で規定されているインタフェース群(有効式)
// v は Vertex Descriptor // e は Edge Descriptor // g はグラフオブジェクト out_edges( v, g ); // (v,g) で表される頂点から出る辺を列挙 adjacent_vertices( v, g ); // (v,g) で表される頂点に隣接する頂点を列挙 source( e, g ); // (e,g) で表される辺の起点を表す Vertex Descriptor を返す target( e, g ); // (e,g) で表される辺の終点を表す Vertex Descriptor を返す
を見れば分かるように,常に Descriptor はグラフオブジェクトとペアで用いられる.また同時に,上のインタフェースの規定を見れば,ユーザのコードに具体的な「頂点オブジェクト」あるいは「辺オブジェクト」といったものを全く露出させていないことも分かる.これがデータ構造実装の柔軟性の鍵となる.
PropertyMap は Descriptor からプロパティが格納されたストレージへの mapping だと書いたけれど,この抽象化がカバーする範囲は相当広い.例えばグラフの辺が実際にプログラム上の1つ辺オブジェクトとして表現されるデータ構造の場合,例えば辺の長さといったプロパティは辺オブジェクトのメンバとして表現されるかも知れない.この場合,例えば Descriptor は辺オブジェクトへのポインタかも知れなくて,その場合,辺の長さへの PropertyMap は単に辺オブジェクトへのポインタを取ってそのオブジェクト内の長さメンバの値を返す関数として実装できる.あるいは,グラフ内の全ての辺オブジェクトがグラフオブジェクトが保持するランダムアクセスコンテナにあるかもしれない.この場合,例えば Descriptor は辺コンテナの要素インデックスかも知れなくて,この場合,辺の長さへの PropertyMap は要素インデックスとグラフオブジェクトを取って(先に書いたように Boost.Graph では,ある辺を指し示すために必ず Edge Descriptor とグラフオブジェクトをペアで指定する)辺オブジェクトの辺メンバの値を返す関数として実装できる.このように,実際に辺に対応するオブジェクトが存在して,その内部にプロパティが実装されている場合に,そのプロパティを内部プロパティ(internal property)と Boost.Graph では呼んでいたりする.
元々は辺の長さなんてプロパティが必要ないと思ってグラフ構造を作ったけれど,後で辺の長さというプロパティが追加する必要が出てきてしまった,なんてこともあるかも知れない.この場合,例えばグラフオブジェクトと独立して辺の長さを格納するストレージを作って,そのストレージと Edge Descriptor との対応と取れば良い.こういうふうなグラフオブジェクトの外部に作成したプロパティを外部プロパティ(external property)と Boost.Graph では呼んでいる.では,どうやって Edge Descriptor から辺の長さのストレージへ mapping するか?例えば, Edge Descriptor が EquallyComparable ならば, HashMap コンテナを使えば最も簡単に辺の長さプロパティを Edge Descriptor に関連付けられる.もし Edge Descriptor から [0,E) (E は辺の総数)の自然数への PropertyMap がすでに存在するならば,辺の長さをランダムアクセスコンテナに格納して,(要素インデックスとみなした)整数から辺の長さへの PropertyMap を作った上で,先の Edge Descriptor から自然数への PropertyMap と mapping を合成すれば, Edge Descriptor から辺の長さへの PropertyMap が完成する.あるいは,HashMap で先に自然数への PropertyMap pmap1 を作っておけば,辺の長さをランダムアクセスコンテナに載せた PropertyMap pmap2 を pmap1 と合成して辺の長さへの PropertyMap が作れるし,さらに辺の重みプロパティが必要になったときに辺の重みをランダムアクセスコンテナに載せた PropertyMap pmap3 を先に作った pmap1 をさらに使いまわしで合成して辺の重みへの PropertyMap が作れる.
PropertyMap は「あるオブジェクトからあるオブジェクト(を格納するストレージ)への mapping」であり,概念的には関数(写像)そのものになる.なぜわざわざストレージそのものに直接対応したオブジェクト(例えばコンテナ)を直接用いずに,関数(写像)としてストレージへのアクセスを間接化するのか?後者のあり方によって,プロパティが格納されているストレージへアクセスするためにユーザ側で用いるインタフェースが,ストレージの実装詳細に全く関係なく,関数の構文として完全にコードを統一できる.これによって,データ構造の実装詳細の可変性に対する強力な保守性・拡張性を獲得することができる.
以上のような2つ表裏一体での非常に強力で柔軟なデータ構造の抽象化が Descriptr/PropertyMap のすごいところ,という話ですた.すごさが伝えられている気が全然しねぇ.
ちなみに,上で書いてる「PropertyMap のインタフェースは operator() の方が良い」という理由の一つとして,例えば以下のような例が考えられる.例えば Boost.Graph ではほとんどの場合 Descriptor とグラフオブジェクトをペアにしないといけないため, PropertyMap は e を Edge Descriptor, g をグラフオブジェクト, p をプロパティとして,f: (e,g) -> p という2項関数になる.けれど,例えばダイクストラパスを取ることを考えると,グラフオブジェクト自体は完全に不要で,ダイクストラパスアルゴリズムの実装としては単に Edge Descriptor から辺の長さへの PropertyMap f': e -> p のみに関心があり,その PropertyMap さえ与えてくれればよい.これを実現するためには f の項のうちのグラフオブジェクトの項を partial evaluation して PropertyMap f' を作り出し,それをダイクストラパスアルゴリズムに渡してしまえばよい.こういう PropertyMap に対する partial evaluation などの操作は関数(オブジェクト)に対する bind などの実装をそのまま流用したいため, operator[] より operator() の方が圧倒的に良いよね,っていう結論になる.