第4回: Incremental Computation — 変わったところだけ計算し直す
シリーズ「構文エラーのない世界へ」 — 目次に戻る / 前回
問題の確認
前回、Gradual Structure Editing のアーキテクチャを見た。テキスト入力 → AST操作 → 型チェック → 画面表示というパイプラインが、キーを押すたびに走る。
プログラムが100行なら一瞬で終わる。しかし1万行、10万行なら？ 文字を一つ打つたびにAST全体を型チェックし直していたら、使い物にならない。
この問題を正面から定式化したのが Yanhong A. Liu の “Incremental Computation: What Is the Essence?”（Foundations and Trends in Programming Languages, 2025）だ。
基本的なアイデア
インクリメンタル計算の核心は驚くほどシンプルだ。
前回の計算結果がある。入力が少し変わった。全部やり直す代わりに、前回の結果を使って効率的に新しい結果を出す。
式で書くとこうなる:
f(x) = r ← 前回の計算
f(x ⊕ y) = ? ← 入力が x から x⊕y に変わった。結果は？
f'(x, y, r) = f(x ⊕ y) ← f' が f のインクリメンタル版。r を再利用する。
f は何らかの計算。x は入力。r は前回の結果。⊕ は入力の変更操作。y は変更の内容。f' は前回の結果 r を使って新しい結果を効率的に求める関数。
身近な例で理解する
例1: 合計
1 から n までの合計を求める関数:
sum(100) = 5050 ← 計算済み
n が 100 から 101 に変わった（⊕ は +1）。全部足し直す？
sum(101) = 1 + 2 + 3 + ... + 101 ← O(n) かかる
いや、前回の結果を使えばいい:
sum'(100, +1, 5050) = 5050 + 101 = 5151 ← O(1) で済む
sum'(n, y, r) = r + (n + 1) がインクリメンタル版。やっていることは当たり前だが、これを体系的にあらゆる関数に適用する方法が重要になる。
例2: ソート済みリスト
ソート済みリストに新しい要素を追加する:
sorted = [1, 3, 5, 7, 9] ← ソート済み
sorted ⊕ insert(4) = ? ← 4 を追加
全部ソートし直す？ O(n log n) かかる。しかしリストが既にソート済みと知っていれば:
sorted' = [1, 3, 4, 5, 7, 9] ← 正しい位置に挿入するだけ。O(n)、あるいは適切なデータ構造で O(log n)。
例3: スプレッドシート
実はスプレッドシートこそ、日常で最も身近なインクリメンタル計算だ。
セル A1 を変更すると、A1 を参照しているセル B1 が再計算され、B1 を参照しているセル C1 も再計算される。しかし A1 と無関係なセル D1 は再計算されない。
これが「変わったところだけ計算し直す」の実例だ。
Liu の定式化: 離散領域の微分
Liu はインクリメンタル化を微分の離散版と位置づけている。
連続関数の微分は「入力の微小な変化に対する出力の変化率」を求める。f(x) = x² なら f’(x) = 2x。これを知っていれば、x が少し変化したとき f(x + Δx) ≈ f(x) + 2x·Δx と近似できる。
インクリメンタル化は同じことを離散領域でやる。ただし、離散では変化が「微小」ではないので、近似ではなく正確な値を求める必要がある。
連続: f(x) = x², f'(x) = 2x （近似: f(x+ε) ≈ f(x) + 2xε）
離散: f(x) = x², f'(x, r) = r + 2x + 1 （正確: f(x+1) = f(x) + 2x + 1）
離散版に +1 が余分につくのは、変化が無限小でないからだ。この差が、インクリメンタル化を微分より難しくしている。
P1-P3: インクリメンタル化の3つのテクニック
Liu は f のインクリメンタル版 f’ を導出する方法を、3つの段階に分けて整理している。
P1: 前回の結果を利用する
最も基本。f(x) の結果 r がそのまま f(x ⊕ y) の計算に使える部分を見つけ、r で置き換える。
先ほどの sum の例がこれにあたる。sum(101) = sum(100) + 101 で、sum(100) の部分を前回の結果 5050 に置き換えた。
P2: 中間結果をキャッシュする
f(x) の最終結果だけでなく、計算途中の中間結果も保存しておく。
例えば、配列の平均を計算する関数:
average(arr) = sum(arr) / length(arr)
要素を一つ追加したとき、sum と length を別々にキャッシュしていれば:
average'(arr, add(v), cached_sum, cached_len) =
(cached_sum + v) / (cached_len + 1)
最終結果の average だけをキャッシュしていたら、ここまで効率的にはできない。
P3: 補助情報を発見する
f(x) の計算では全く使わないが、f’ の効率化に役立つ「補助情報」を見つけ出す。
例えば、グラフの連結成分を求める関数。辺を一つ追加したとき、「元々の連結成分」の情報があればすぐに更新できる。しかし連結成分の情報は、元の関数の出力そのものではなく、元の関数を変形して追加で維持する補助情報だ。
P3 は最も難しく、かつ最も強力なテクニックだ。
III メソッド: 体系的なインクリメンタル化
Liu は、P1-P3 をプログラム設計全体に適用する方法として III (Iterate-Incrementalize-Implement) メソッドを提案している。
I1. Iterate（反復化）
計算を「最小の増分を繰り返し適用する形」に書き換える。
I2. Incrementalize（インクリメンタル化）
各反復ステップの高コスト操作を、P1-P3 でインクリメンタルにする。
I3. Implement（データ構造設計）
キャッシュや補助情報を効率的に格納・アクセスするデータ構造を選ぶ。
重要な洞察がある。プログラムが使う抽象のレベルによって、必要なステップが違う。
| プログラムの特徴 | 例 | 必要なステップ |
|---|---|---|
| ループと配列 | 配列の集計計算 | I2 のみ |
| 集合式 | データベースクエリ | I2 + I3 |
| 再帰関数 | 木の走査 | I1 + I2 |
| 論理規則 | 型推論規則 | I1 + I2 + I3 |
ループと配列なら、反復方法（I1）もデータ構造（I3）も既に決まっているので、I2（各ステップのインクリメンタル化）だけ考えればよい。
一方、再帰関数は「最小の増分」が自明でない。木構造の再帰関数で、入力の木にノードが一つ追加されたとき、どの部分を再帰的に再計算すべきか？ これを決めるのが I1 だ。
そして Liu が繰り返し強調するのが: 高レベルの抽象を使うほど、インクリメンタル化は容易かつ強力になる。 集合演算や論理規則のような高レベルの表現でプログラムを書いていれば、そのインクリメンタル化は機械的に導出できる場合が多い。低レベルのループや配列操作で同じことを手作業でやるのは、はるかに困難だ。
微分による積分: 最も深い洞察
Liu の論文で最も驚くべき発見は、インクリメンタル化が最適化に使えるということだ。
フィボナッチ数列を考えよう:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
素朴な再帰実装は指数時間 O(2ⁿ) かかる。
ここで、fib のインクリメンタル版を導出する。「n が n+1 に変わったとき、fib(n) と fib(n-1) を知っていれば fib(n+1) = fib(n) + fib(n-1)」。
このインクリメンタル版の外側にループを巻く:
result = fib(0)
for i in 1..n:
result = fib'(i, result, prev) // インクリメンタル版を繰り返し適用
得られるのは O(n) のフィボナッチ計算。動的プログラミングの有名な最適化と同じ結果が、インクリメンタル化を機械的に適用するだけで得られる。
Liu はこれを「微分による積分」と呼んでいる。微分（インクリメンタル版の導出）をしてから積分（ループを巻く）ことで、元の計算を最適化する。
次回への橋渡し
ここまでで、二つの大きなアイデアが揃った:
- Projectional Editing + Gradual Structure Editing: 構造を直接編集しつつ、テキスト入力の自然さを維持する
- Incremental Computation: 変更箇所だけ計算し直す体系的な方法
次回、最終回では、この二つを具体的に統合する。エディタ内部のパイプラインの各段階（AST操作、型チェック、画面表示）をどうインクリメンタル化するのか。Liu の III メソッドがエディタの各コンポーネントにどう対応するのか。そして、パイプライン全体を連鎖律（chain rule）で繋ぐ話。