壊れたパーサから始める関数型設計と構成的なパーサ

構文解析器を題材に、ナイーブな実装を分解し、構成的なパーサへと組み替える過程を示します。

ナイーブな実装では、入力状態の管理、エラー処理、処理の合成といった関心が同じ制御フローに入り込み、分岐が増殖します。その結果、処理の再利用や合成が難しくなります。本セッションでは、このような実装を出発点に、コードとともに段階的に分解します。

分解の過程では、状態・失敗・合成という異なる性質として捉え直します。状態は逐次的な変化、失敗は分岐の可能性、合成は構造の組み合わせとして切り分け、それぞれを独立に記述します。

分離した構造を再び組み合わせる段階では、モナドやApplicativeといった抽象が、合成を記述するための枠組みとして現れます。この流れから、状態・失敗・合成を分離するための手順を整理します。

崩れた設計を整えていく過程の中で、抽象がどのように立ち上がるかを追います。この視点は構文解析に限らず、関心の分離と合成を扱う設計全般に応用できます。

Transcript

1. 壊れたパーサから始める 関数型設計と構成的なパーサ 関数型まつり 2026 ライガー 1 / 46
2. 「関数型◦◦」って、かっこいい！ 2 / 46
3. けど、何から始める？ 3 / 46
4. そもそも関数型って どうすればいいの？ 4 / 46
5. 実際にやってみた 5 / 46
6. 自己紹介 • ライガー • 学生 (名古屋工業大学) • Rust / PHP ※ この発表内容は個人の見解であり、所属団体の公式見解と異なる場合があります ※ 来月院試でまずい 6 / 46
7. 今日のあらすじ • 雑な設計でバグもあった LR(0) パーサを • 関数型の視点でリファクタした話 • 使用言語: Rust 7 / 46
8. 題材: LR(0) パーサの再設計 • 目標 •「関数型っぽさ」とは何か、再設計をやって確かめる • 聞いたことがある Applicative や Monad をなんとなく理解する • LR(0) パーサのコードを見通しやすく・変更しやすくする 8 / 46
9. パーサはどんな計算をするのか • 構文解析をするもの • raw な文字列やデータを、計算で扱いやすい構造にかえる • 抽象構文木など 入力 → 構文解析器 → 出力 9 / 46
10. パーサはどんな計算をするのか • 実際に動いている様子 10 / 46
11. LR(0) パーサについて • 生成規則(文法)と与えられた文字列から、文字列の構造を解析する • 出力は木構造で、抽象構文木(AST)と呼ばれる • 生成規則からプッシュダウンオートマトン / 構文解析表をつくり、入力された文 字列を消費して構文木を生成する • 左(L)から入力を読んで最右導出(R)をするので LR • 解析中の文字から先を n 字読むと LR(n) 11 / 46
12. LR(0) パーサについて • 詳しくは以下の記事で取り扱っています 12 / 46
13. 関数型パラダイム • (ざっくりとした解説)プログラミングを「関数の集まり」で捉える • 関数を軸にプログラムを考える • How to do(どうするか)ではなく What to do(何をするか) • 宣言的パラダイムの具象の一つとして解釈できる 13 / 46
14. 「壊れたパーサ」は何が壊れていたのか？ • 背景: コンパイラの授業を受けたときにプロトタイプとして作ったもの • Parser 構造体に必要な部品を詰め込んだファットな実装 • 副作用もどこで起きているかわかりづらい • 同じ生成規則でも、構文解析表のシンボルの順序が実行のたびに変わってしまう (単純に実装のバグ) • エラー文が整備されておらず、実行に失敗したときの原因を追跡しづらい 14 / 46
15. ひとつにすべてを詰め込むファットな実装 parser@19be3a4 pub(crate) struct Parser { table: ... reducer: ... stack: ... state: ... ast_stack: ... } impl Parser { pub fn new(...) ... pub fn parse(...) ... ... } • Parser 構造体に全部詰め る実装 • 関数の分解が手続きを軸 に決定されているなど • のちのスライドで詳細に 話します 15 / 46
16. 失敗の原因が追跡しづらい parser@19be3a4 L301-L332 match action { Shift(id) => { stack.push(id); ast_stack.push(...); state = id; } Reduce(id) => { ast_stack.drain(...); state = *stack.last().unwrap(); } _ => return vec![], } • 失敗が vec![] と unwrap に 吸われて理由が残らない • 状態遷移・AST 構築・失 敗処理が同じ match に 同居 16 / 46
17. 実際に改善してみよう 17 / 46
18. What to do が明確になるまで分解する 境界を型に明示する 18 / 46
19. What to do が明確になる、とは ☐ 同じ入力に対して同じ出力になるか ☐ I/O や外部状態への作用が関数のシグネチャに表現されているか ☐ 状態遷移が明示されているか≒共有状態への暗黙な変換がないか ☐ 不正な状態や意味の混同が型で表現できなくなっているか ☐ 引数と戻り値だけでテスト・合成ができるか すべてに Yes と言えるまで分解する 19 / 46
20. What to do を明確にする #1 壊れたパーサでチェックしてみる 20 / 46
21. 同じ入力に対して同じ出力になるか parser.rs@f91c5e0 pub fn from_reducer(path: &str) -> Vec<(char, String)> { let content = read_to_string(path).unwrap(); // ... } • 同じパスを渡しても、 ファイルの中身が書き換 わると結果が変わる 21 / 46
22. I/O や外部状態への作用が関数のシグネチャに表 現されているか parser.rs@f91c5e0 pub fn parse(&mut self, input: String) -> Vec<AstNode> { ... println!("case: {}", input.clone()); println!( "head: {} || state: {} || action{:?} || stack : {:?}", // ... ); } • 解析中の状態を標準出力 に流している • 計算中に I/O を暗黙で実 行 22 / 46
23. 状態遷移が明示されているか parser.rs@f91c5e0 pub(crate) struct Parser { stack: Vec<usize>, state: usize, table: (Vec<char>, Vec<Vec<Action>>), reducer: Vec<(char, String)>, ast_stack: Vec<AstNode>, } // parse 冒頭 self.stack.clear(); self.stack.push(0); self.state = 0; self.ast_stack.clear(); • 異なる寿命のデータが同 じ構造体に集まっている • 合わせるために実装 で初期化しないとい けない • 可変にしたいデータに合 わせて、すべてが可変に なりうる型の表現になっ ている • Rust なので他が mutable にはなりえ ないが… 23 / 46
24. 不正な状態や意味の混同が型で表現できなくなっ ているか parser.rs@f91c5e0 enum Action { Shift(usize), // 終端記号の列のみ Reduce(usize),// 終端記号の列のみ Accept, // EOLのみ Goto(usize), // 非終端記号の列のみ Error, } • 構文解析表では、GOTO 表と ACTION 表が結合さ れて書かれる • それをまとめて同じ Enum で表現 • 終端記号の列に Goto、非 終端記号の列に Shift/ Reduce が実装できてし まう 24 / 46
25. 引数と戻り値だけでテスト・合成できるか parser.rs@f91c5e0#L61 parser.rs@f91c5e0#L274 pub fn new(reducer_path: &str) -> Self pub fn parse( &mut self, input: String, ) -> Vec<AstNode> • テストするために外部 ファイルを作成して、そ のパスを固定する必要が ある • 正常に初期化された Parser を用意する必要が ある • 失敗時の型が分からない ので、テストで表現でき ない・しづらい 25 / 46
26. 引数と戻り値だけでテスト・合成できるか parser.rs@f91c5e0#L61 fn action(&self, input: char) -> Action { let idx = self.state; let (symbols, table) = self.table.clone(); // ... } • 入力は char のみだが、 実際の実装として出力結 果を決めるのは、input/ state/table に依存 26 / 46
27. 設計段階からやり直す • 現実的には、今ある実装から少しづつ手を入れることが多い • 今回は、関数型設計を始めるためなので、実装の手前からスタートする 27 / 46
28. そもそも • プロトタイプ実装だったので設計をまともにしていなかった • なので構文解析のフローをそのままコードに起こすことに • 手続き型っぽい書き方になった • プロトタイプでやらかすことは本番でやらかす可能性もある 28 / 46
29. チェックリストおさらい • 同じ入力に対して同じ出力になるか • I/O や外部状態への作用が関数のシグネチャに表現されているか • 状態遷移が明示されているか≒共有状態への暗黙な変換がないか • 不正な状態や意味の混同が型で表現できなくなっているか • 引数と戻り値だけでテスト・合成ができるか 29 / 46
30. フェーズで分割してみる ほしい結果からデータの依存を追ってみる • 最終的にほしいのは AST • AST に必要なのは構文解析表と字句列 • 構文解析表に必要なのは生成規則 • 字句列に必要なのは入力文字列 • 依存からライフサイクルやデータでデザインすべき寿命を観察する 30 / 46
31. What to do を明確にする #2 • ファイルから生成規則・終端記号・非終端記号の集合 = 文法を返す: parse_grammar_text • 文法から構文解析表・解析器を返す: compile_parser • 解釈したい文字列を解析器用に変換する: parse_input_text • 解析器と変換済みの入力を受け取り、AST を返す: run_parser • プッシュダウンオートマトンを操作するので、もう少し細分化したい • ← ここで「状態を保持しながら動かす計算」が必要になる ⇒ 副作用 一つの構造体・関数に処理が混在せず、それぞれが責務をこなせる状態になった 31 / 46
32. What to do を明確にする #3 • 状態を保持する必要がある計算: run_parser • 状態を更新する関数を中に作る: 今回は step • step は内部に状態更新を持つのではなく、古い状態を受け取り、新しい状態 を返す関数とおく • 失敗する可能性のある計算: 今回の場合は全部 • 失敗の種類も、各計算に合わせてきちんと分ける 32 / 46
33. What to do を明確にする #4 • 説明から、関数のシグネチャ(引数と返り値)を書く • 失敗する可能性のあるものは、それぞれのエラーと一緒に Result でラップする grammar@87feb25 lr@87feb25 runtime@87feb25 parse_grammar_text: &str -> Result<Grammar, GrammarError> compile_parser: &Grammar -> Result<CompiledParser, ParserError> parse_input_text: &str -> Result<Vec<Symbol>, RuntimeError> run_parser: (&CompiledParser, &[Symbol]) -> Result<AstNode, RuntimeError> step: (&CompiledParser, ParserState) -> Result<StepResult, RuntimeError> • Grammar: 開始記号と生成規則の集合 / CompiledParser: 解析表と付随情報 • Symbol: 終端・非終端記号の enum / StepResult: Continue(次の状態) か Accept(結果) 33 / 46
34. 副作用のある計算を型で表現する Result 成功か失敗かの直和 Result<T, E> = Ok(T) | Err(E) • 失敗が返り値に現れる ステートマシン 前の状態 × 入力 → 出力 × 今の状態 (State, Input) -> (Output, State') • 状態が引数と返り値に現れる 34 / 46
35. 不正な状態を型で表現できなくする • 構文解析表にある動作を一つの Enum から、表を分割 pub struct CompiledParser { productions: Vec<Production>, action_table: BTreeMap<(InternalState, Terminal), Action>, goto_table: BTreeMap<(InternalState, NonTerminal), InternalState>, start_state: InternalState, state_count: usize, state_infos: Vec<StateInfo>, } 35 / 46
36. 分離できた計算同士の合成 分解した計算を、どう組み直すか 36 / 46
37. 直列の合成: Result と `?` • 失敗すると後続の計算ができない場合は、すぐに Err(e) を返す runtime@87feb25 L121-L133 loop { match step(machine, state)? { // 失敗したらここで停止 Continue(next) => state = next, Accept(result) => return Ok(result), } } • run が step をつなぎ、? が失敗を伝播する • 前段の成功結果で、次の計算が決まる 37 / 46
38. 独立の合成: Validation::map2 • 失敗が個別に起きる場合は、どちらのエラーも拾えるように合成する • 構文解析表の生成と、入力された文字列の字句解析は独立している validation@37c603a L34-L48 match (self, other) { (Valid(t), Valid(u)) => Valid(f(t, u)), (Invalid(e), Valid(_)) => Invalid(e), (Valid(_), Invalid(e)) => Invalid(e), (Invalid(mut e1), Invalid(mut e2)) => { e1.append(&mut e2); // ← 両方のエラーを結合 Invalid(e1) } } • 両方失敗なら、両方のエラーが一度にユーザーへ届く 38 / 46
39. 失敗の回収と追跡性の向上 Before • unwrap / _ => return vec![] • 失敗が「空」や panic に化ける • どの段階で何が起きたか分からな い After • GrammarError / ParserError / RuntimeError • 失敗が返り値に乗って戻ってくる • どの段階の・どんな失敗かが型で 分かる 失敗をなくすのではなく、見える場所へ移す 39 / 46
40. 構成的なパーサ parse_grammar_text 文法を作る → compile_parser 解析器を作る → parse_input_text 入力を変換 (map2 で合流) → run_parser step を回して AST | Error 小さな関数が、型を合わせて合成だけで組み上がっている — 「構成的なパーサ」 40 / 46
41. Before / After • before 入力 生成規則 解釈する文 字列 → Parser 構文解析器の生成 字 句解析 AST の生成 → 出力 AST 失敗は空配列 41 / 46
42. Before / After Grammar CompiledParser Vec parse_grammar_text compile run parse_input_text AST GrammarError ParserError GrammarError RuntimeError 42 / 46
43. 関数型視点の再設計で得られたもの • 独立な合成や、副作用を型で明示する行為からは、関数型プログラミングで扱わ れる Applicative や Monad に近いものが得られる • 実装する言語によっては厳密な Applicative / Monad にならないので注意 • Rust は現在 HKT をサポートしていないため、厳密な Monad は実現できな い (実装しようという動きは存在する) • What to do を明確にするだけで、変更容易性や可読性を高めることができる • 素朴な手順のみで高い効果を得やすい • パーサに限らず、変更容易性や可読性が求められる設計全般に適用できる • パーサの再設計は、関数型設計を学ぶのにいいかも • 最適なモデルがすでに存在しており、枯れている •「要求」が介在しないので、純粋な設計のみに専念しやすい 43 / 46
44. 次のステップは？ •「要求」 「要件」ありの設計を、関数型でしてみる •『関数型ドメインモデリング』(Scott Wlaschin) • 商品の発注システムを題材に、F# による関数型設計を学べる • 今日やった「状態を型に」 「失敗を型に」 「Result」 「Validation」が、業務ド メインで展開されている 44 / 46
45. まとめ • 関数型設計は素朴なアプローチで効果を得やすい • 関数型でよく聞く構造(Monad / Applicative)は、目指すものではなく、このアプ ローチの先に自然と現れる成果物 • パーサはきちんと段階を分け、計算境界を明確にすることで、可読性や変更容易 性が向上する = 構成的なパーサ 45 / 46
46. Thank you! 46 / 46