実験ノート：Claude Code on the webで、静的型付き関数型プログラミング言語をvibe coding(2)
前の記事では、静的型付き関数型プログラミング言語TreePの言語処理系と、トランスディユーサーをvibe codingした。最後に macro tree transducerを作ってもらった。
Macro Tree Transducer
Macro Tree Trasduderとは、
In principle, macro tree transducers consist of rules, each of them meaning to transform a node of the input tree depending on the node's label. Subsequent functions are called for the children of the transformed node. This means, a macro tree transducer can be considered as a recursive first-order functional program generating trees, where the choice of functions is triggered by top-down pattern matching an input tree. During a computation, macro tree transducers may accumulate intermediate results in additional parameters, and thus have access to context information. Compared to the top-down tree transducer, the ability of carrying context information to further processing steps makes the macro tree transducer the more expressive model.
自分の20年弱前の社会人ドクターのサブテーマ論文、「MDAフレームワークのEDA分野への適用」によると、
Tree Transducerは 、 入 力 木 の ノ ー ドの パ タ ー ン に 対 し て 、 出 力 木 を 生 成 す る 関 数 を 呼 ぶ ル ール の 集 合 で 構 成 さ れ る 。 特 にMacroTreeTransducer(以 下MTTと 略 す)と 呼 ば れ るク ラ ス は 、 入 力 パ タ ー ン に 引 数 を と る こ と が で き る こ と が 特 徴 で 、 木 を 生 成 す る 再 帰 的な1階 関 数 プ ロ グ ラ ム と み な す こ と が で き る 。
Transduderの実行例(Family Tree)に対応してもらう。
例えば、以下の木構造があるとする、lastNameを先頭に、father、mother、doughterとm-listというノードを起点に木構造が深くなっていく。
こちらが、MTTの例、
ソ ー ス ノ ー ドがmlistで あ る と き に は 二 分 木 で 展 開 さ れ 子 ノ ー ドがmlistで あ る 場 合は 再 帰 的 に ル ー ル が 呼 ば れ る 。 ま たIastNameはFamilyノ ー ドのrank=1の 子 ノ ー ドに格 納 さ れ て い る の で こ れ を 引 数(y)と し て 他 の ル ー ル を 呼 び 、 最 後 に リ ー フ ノ ー ドで 、lastNameを タ ー ゲ ッ ト枝 に 展 開 し て い る 。
このMTTの出力が以下の木である、男女別に、姓名が枝となった木構造になっている。
どうも、複数状態をもつMTTが必要だったようで、これが実装された
状態は、q0,q,qidの３つがあり、ルールは以下のように展開される。
実行
mtt_transducer.tsから、
Example1:Copy Transducer (No Parameters)
最初は木のコピー
そして入力木が、
このような出力を得る、当然入力と同じ。
Output tree (should be identical):
{
"kind": "a",
"children": [
{
"kind": "b",
"children": [
{
"kind": "e"
},
{
"kind": "e"
}
]
},
{
"kind": "e"
}
]
}
Trees are equal: true同じである。
Example2: Flatten Leaves with Accumulator Parameter
ルールは以下の通り、
入力木が
これをflat化すると、step-by stepではこのように変換され、
Step-by-step execution:
q(a(b(e(), e()), e()), nil)
→ q(b(e(), e()), q(e(), nil))
→ q(b(e(), e()), cons(e(), nil))
→ q(e(), q(e(), cons(e(), nil)))
→ q(e(), cons(e(), cons(e(), nil)))
→ cons(e(), cons(e(), cons(e(), nil)))出力木は、右よせのリストになる。
Output (right-associated cons list):
{
"kind": "cons",
"children": [
{
"kind": "e"
},
{
"kind": "cons",
"children": [
{
"kind": "e"
},
{
"kind": "cons",
"children": [
{
"kind": "e"
},
{
"kind": "nil"
}
]
}
]
}
]
}Example 3: Depth Calculator with Accumulator
そして、ついにパラータ付きのMTT、深さｄがパラメータ
入力に対して、
出力は、各ノードに深さが付与されている(depth_x)。
Output (annotated with depths):
{
"kind": "a",
"name": "depth_0",
"children": [
{
"kind": "b",
"name": "depth_1",
"children": [
{
"kind": "e",
"name": "depth_2"
},
{
"kind": "e",
"name": "depth_2"
}
]
},
{
"kind": "e",
"name": "depth_1"
}
]
}Example 4: Path Accumulator - Build path from root
今度は、ノードに対して、そこまでのパス情報を付与、pathが引数として引き回される。
入力に対し、
出力は、nameにどちらの枝を通ったか履歴が付与される。
Output (annotated with paths):
{
"kind": "a",
"name": "root",
"children": [
{
"kind": "b",
"name": "L",
"children": [
{
"kind": "e",
"name": "LL"
},
{
"kind": "e",
"name": "LR"
}
]
},
{
"kind": "e",
"name": "R"
}
]
}Example 5: Using MTT with TreeP EAST
これは、TreePのプログラムの木EASTを変換できるという例。
入力ｈ、x+yの関数定義である。
出力は、depthを追加したものが出る。
Output (transformed with depth annotations):
{
"kind": "function",
"name": "add",
"attrs": [
{
"key": "nesting_depth",
"value": "0"
}
],
"children": [
{
"kind": "param",
"name": "x",
"attrs": [
{
"key": "depth",
"value": "1"
}
]
},
{
"kind": "param",
"name": "y",
"attrs": [
{
"key": "depth",
"value": "1"
}
]
},
{
"kind": "block",
"attrs": [
{
"key": "depth",
"value": "1"
}
],
"children": [
{
"kind": "return",
"attrs": [
{
"key": "depth",
"value": "1"
}
],
"children": [
{
"kind": "call",
"name": "+",
"attrs": [
{
"key": "depth",
"value": "1"
}
],
"children": [
{
"kind": "var",
"name": "x"
},
{
"kind": "var",
"name": "y"
}
]
}
]
}
]
}
]
}Example 6: Family Tree Transformation with Multiple States
そして最後が、Famly Treeの例である。
ルールは、
入力は、
わかりやい木構造記述で表現すると、
Input (Family Tree):
Family(
lastName(March),
m-list(
father(Jim),
m-list(
mother(Cindy),
m-list(
daughter(Brenda),
e
)
)
)
)出力は、
Output (Gender-tagged member list with inherited lastName):
{
"kind": "o",
"children": [
{
"kind": "Male",
"children": [
{
"kind": "identifier",
"name": "March"
},
{
"kind": "identifier",
"name": "Jim"
}
]
},
{
"kind": "o",
"children": [
{
"kind": "Female",
"children": [
{
"kind": "identifier",
"name": "March"
},
{
"kind": "identifier",
"name": "Cindy"
}
]
},
{
"kind": "o",
"children": [
{
"kind": "Female",
"children": [
{
"kind": "identifier",
"name": "March"
},
{
"kind": "identifier",
"name": "Brenda"
}
]
},
{
"kind": "e"
}
]
}
]
}
]
}
こちらもわかりやすい構造にすると、
Expected structure:
o(
Male(March, Jim),
o(
Female(March, Cindy),
o(
Female(March, Brenda),
e
)
)
)このように、Macro Tree Transducerが実装された。
MTTの応用例
構文器の属性計算
コード生成とXML/HTM変換
感想
TreePの言語処理系をつくったが、ついでにTree Transducerも作った、Macro Tree Transducerに拡張してもらったおかげで、高い変換性能をもつようになり、プログラム変換なんかも可能になった。例題としてTreeP言語のASTの変換例も示してくれた。
木を変換するのはTransducerでこれはルールで記述でき、そして、それは木オートマトンと関連する。ルールからTransducerができてうれしい。
追記：Macro Tree Transducerに糖衣構文(syntax sugar)を追加してもらった
寝起きに、ハッと思い付き、スマホから指示。。
MTTに対する、syntax sugarを設計して、木の構造と、ルールと両方
目が覚めると完成していた。
そして、MTTのルールは
文法定義はこちら、
むう、寝てる間に作ってくれるって、素晴らしい。
複数のTransducerの合成？
MTT_SYNTAX_SUGAR.mdにこんなことが描いてある。
まあ、木変換をパイプラインでつなげるという話だな。。これが実装されているのか？？ つづく、、
成果物をここに供養する、
