第3回: Gradual Structure Editing — テキストの自然さと構造の安全を両立する
シリーズ「構文エラーのない世界へ」 — 目次に戻る / 前回
Pure Projectional の壁
前回、Projectional Editing の難点を見た。構造を直接編集するので構文エラーは消えるが、テキスト入力の自然さが失われる。この壁を越えなければ、Projectional Editing は理論上の美しさにとどまったまま実用に至らない。
ミシガン大学の Hazel プロジェクトは、この問題に対する答えとして Gradual Structure Editing（段階的構造編集）を提案している（Moon, Blinn, Omar, VL/HCC 2023）。
核心的なアイデアは一言で言える。
テキスト入力は許す。しかし、ASTが壊れることは許さない。
パーサーの役割が変わる
Gradual Structure Editing では、パーサーは消えない。しかし、その役割が根本から変わる。
【従来のパーサー】
テキスト（プログラム全体）→ AST
失敗したら: 構文エラー。何も動かない。
【Text Input Adapter】
テキスト入力の断片 → AST操作の列
失敗したら: 穴を挿入。ASTは常に整合。
パーサーは「プログラム全体をテキストからASTに翻訳する心臓部」から、「テキスト入力をAST操作に変換するアダプタ」へと降格する。心臓が止まったらすべてが止まる心臓部ではなく、止まっても穴で代替できる周辺部品になる。
テキストを打つ、しかしASTは壊れない
具体的にどう動くのか。let x = 1 + 2 を入力する場面を追ってみよう。
最初の状態は、一つの穴だけがあるAST:
AST: [穴] 画面: _
ここにテキストを打ち始める:
入力: "l"
AST: [穴("l")] 画面: l|
まだ式として解釈できない。穴の中にテキスト断片が入った状態。
ASTは壊れていない。穴は正規のノードだから。
入力: "le"
AST: [穴("le")] 画面: le|
まだ。穴の中のテキストが伸びただけ。
入力: "let"
AST: [穴("let")] 画面: let|
"let" と認識できた。しかしまだ完全な式ではない。
（ここで自動変換するか、空白を待つかはUIの設計次第）
入力: "let " (空白で確定)
AST: let 画面: let _ = _ in _
/ | \
_ _ _
変換が起きた！ "let" がキーワードとして認識され、
AST上に let ノードが挿入された。
名前・値・本体の3つの穴が自動的に生成される。
入力: "x" (名前の穴に)
AST: let 画面: let x = _ in _
/ | \
x _ _
入力: "1 + 2" (値の穴に)
途中経過:
"1" → [Lit(1)] AST整合 ✓
"1 +" → [穴("1 +")] AST整合 ✓（穴の中にテキスト）
"1 + 2" → [Add(Lit(1), Lit(2))] AST整合 ✓
どの瞬間でもASTは木構造として整合している。テキストが途中状態のときは穴の中に「未解決のテキスト断片」として保持される。完全な式として認識可能になった瞬間、自動的にASTノードに昇格する。
Marking: 穴にも型がつく
Hazel のもう一つの重要な特徴が Marking だ（POPL 2024）。
プログラムの中に型が合わない部分があっても、ASTを壊さない。代わりに、問題のあるノードに印（mark）をつける。
let x : Int = "hello" in x + 1
^^^^^^^
ここに mark がつく:
"String が来たが Int が期待されている"
この mark はASTの一部として保持される。型エラーがあっても、プログラムの残りの部分は正常に型チェックされ、入力補完やリファクタリングが機能し続ける。
Marking には二つの重要な性質がある:
Totality（全域性）: どんなに壊れたプログラムでも、必ず Marking が完了する。「型チェックが無限ループに陥る」「途中で止まる」ということがない。
Localization（局所性）: 型エラーの影響は、そのエラーの近くに局所化される。一箇所の間違いが遠くのノードに大量のエラーを波及させない。
Grove: 複数人が同時に編集する
ここまでは一人のプログラマーの話だった。しかし現代のソフトウェア開発はチームで行われる。Google Docs のように、複数人が同じコードを同時に編集できたらどうか？
Grove（Adams et al., POPL 2025）は、Projectional Editing を複数人同時編集に拡張する。
技術的には CmRDT（可換CRDT: Commutative Conflict-free Replicated Data Type） を使う。詳しい仕組みは省くが、重要な性質は:
操作の順序に依存しない: Aさんが行った変更とBさんが行った変更を、どの順番で適用しても同じ結果になる。ネットワーク遅延があっても、最終的に全員のエディタが同じ状態に収束する。
異なる射影でも同時編集可能: Aさんがテキスト表示で編集し、Bさんがブロック表示で編集しても、両方の変更がASTに正しく反映される。射影が違っても「本体」のASTは一つだから。
オフラインでも動く: ネットワーク接続がなくても編集でき、再接続時に自動的に同期される。
衝突にも壊れない: 二人が同じ穴に異なる式を入力した場合、「衝突穴（conflict hole）」として両方を保持する。プログラムが壊れるのではなく、「ここに衝突がありますよ」とASTの中で表現される。
全体像
ここまでの要素を組み合わせると、一つのアーキテクチャが見えてくる:
テキスト入力
↓
Text Input Adapter (パーサーの進化形)
↓
Grove CmRDT (AST + 穴 + 衝突穴) ← 複数人が同時に操作
↓
Marking (型チェック、エラーの局所化)
↓
┌───────────┐
│ 射影を選択 │
├───────────┤
│ テキスト表示 │ ← プログラマー向け
│ ブロック表示 │ ← 初学者向け
│ 数式表示 │ ← 科学計算向け
└───────────┘
テキストを自然に入力できる。ASTは常に整合する。型情報は途切れない。複数人で同時に編集できる。異なる見た目を自由に選べる。
理想的に見える。しかし、一つ大きな問題が残っている。
計算コストの問題
文字を一つ打つたびに、このパイプライン全体を走らせる必要がある。
Text Input Adapter がテキスト断片をAST操作に変換する。そのAST操作が Grove のグラフを更新する。グラフの更新がASTを変える。ASTの変更に対して Marking（型チェック）が走る。Marking の結果に基づいて画面表示が更新される。
プログラムが小さいうちは問題ない。しかし、1万行、10万行のプログラムで、文字を打つたびにAST全体を型チェックし直すのか？ 画面全体を再描画するのか？
エディタの応答性はミリ秒単位で問われる。16ミリ秒（60fps）以内に応答できなければ、ユーザーは「遅い」と感じる。
この問題を解決する原理が、次回紹介する Incremental Computation だ。「変わったところだけ計算し直す」という、一見当たり前だが体系化するのが難しいアイデア。