グラフ書き換えとAGG
GWに学んだログを残す。
読者の魂が私のように震えることを期待しているので、執筆にAIを利用していない。
きっとC言語のポインタでいくつもの構造体がつながった複雑なシステムを設計したり理解したいエンジニアに刺さると思う。
私はグラフ書き換えの専門家ではない。
読んだ本
Fundamentals of Algebraic Graph Transformation
以下のようなイントロから始まる本であった。
1960年代後半から1970年代前半にかけて、グラフ変換とグラフ文法の概念が、画
像処理および計算機科学の分野で注目を集め始めた。その主な目的は、文字列や木
構造において確立されていた既知の書き換え技法をグラフに一般化することで、こ
れによりグラフ変換とグラフ文法が誕生したのである。特に、代数的グラフ変換の
概念は初期段階で重要な位置を占め、過去10年間でさらに重要性を増してきた。
今日では、代数的グラフ変換技術は理論計算機科学の中核をなすだけでなく、ソフ
トウェア工学、並行・分散システム、視覚的モデリング手法、モデル変換など、様
々な応用分野においても中心的な役割を果たしている。
全く理解出来なかった。内容が難しい。私は圏論を理解していない。
Chapter 15に書いてあったAGGの紹介を読んだ。これが唯一役に立った情報だった。
AGGによって、我々は実践的にグラフ書き換えを学ぶことができる。圏論を知らずとも。
AGG
環境構築はdownload のリンクをCodex/ClaudeCodeに渡して指示をすれば良い。
例: N!を計算する
Actorを試す。
グラフ文法を以下からダウンロードしてくる。
AGGを起動し、このファイルを開く。
UIは古いがそれは些細な問題である。
文法は以下の要素で構成されている。
- Calculator: グラフの初期状態
- AskForValue, Delegate, Multiply, EndDelegate: ルール
- AC x>2: ルールの適用条件
- NAC OnlyOne, Last: この条件が満たされる場合、ルールを適用しない
それぞれ見ていく。
- Calculator
何もない。
- AskForValue
ユーザに値を求め、その値を属性に持つノードを作成する。
そのノードには自己参照する辺がついている。
ただ、なにか一つでもノードがあった場合、このルールは適用されない。
ルールは、「グラフの一部がLHS（ルールの左側）にマッチしていた場合、その部分をRHS（右側）に変換する」ことで記述される。
このNACが定義されていないと無限にこのルールが適用されてしまう。
- Delegate
自己参照する辺がついているノードにおいて、x>2であるかぎり、ノードと辺を増やしていく。
- Multiply
ノードと辺を削除しながら乗算していく。NACによって乗算の順序が決まる（木構造の葉の方向から順にマッチする）。言い換えると最初に自己参照する辺をもつノードが消える。
- EndDelegate
AskForValueで2を入力したとき一度もMultiplyされない。そのときに限って自己参照する辺が残ってしまう。そのためこのルールが必要である。
実行方法
Transform->Start を実行する。
Javaから実行する方法もある。詳しくはCodex/ClaudeCodeに聞くと良い。
試したこと
私はPOSIX（正確にはそのサブセット。ファイル・ディレクトリの操作）のモデル化に関心があった。
自分でGUIで操作すると日が暮れるのでCodexにggxファイルを直接編集してもらい、テストを回してもらった。
その結果の一部を示す。47000行のXMLが出来上がった。
型グラフ
LinuxのVFSの構造体をなるべくそのままモデル化した。
ルール
終わりに
グラフ書き換えを頭の中で設計するのは非常に困難であるが、AGGを使えば理解が深まり、さらには検証も可能だ。
Discussion