プログラム解析を分類する

プログラム解析には二種類あって，「グローバルなもの」と「モジュラーなもの」がある．「グローバルなもの」というのはプログラム全体を見て処理する，ということ．フロー解析の類いは，グローバルだと思って良い．「モジュラーなもの」というのはプログラムの一部分だけを見て，答えが(部分的に)出てくるもの．例えば型推論とか．

グローバルとモジュラーの違いっていうのは，つまり無限をどういうふうに扱うか，ということだと思う．型推論の話で言えば，プログラム全体が入力としてあるならば，多相型というのは問題じゃなくなる．多相型を持つべき関数がどういう風に使われているかを全て検出できるなら，関数をコピーしてやるだけで，多相型が扱えることになる．逆に，型推論みたいなモジュラーな解析の場合は，多相型を「任意の型に対して，ほにゃららの動作をする関数」という風に，明示的に無限を表現しなくてはならなくなる．

そして，無限というのは，どういう問題に対しても難しいものなので，型推論アルゴリズムには実はいろいろな制限がある．

じゃあ，型推論なんて制約がきつい方法は捨てて，グローバルに解析すれば良いじゃん，と思うんだけど，グローバルに解析する場合は，計算量がえらいことになりやすい．グローバルに解析する，と言っても，いろいろあって，例えば関数呼び出しひとつ取っても

同じ関数の呼び出しは区別しない
全てじゃなくてコールスタックをいくつか見て区別する
全ての関数呼び出しを区別する

などの方法がある．1→2→3の順で必要な計算量は増大し，精度は向上する．しかもグローバルなもんだから，プログラムをちょっと一箇所直しただけで，全ての解析がやりなおしになる．えらい問題だ．

ちなみに，今時のフロー解析の研究というのは，

そもそも誰も思い付かなかったような解析をやる
膨大な計算量をなんとかする解析方法を考える
計算量と精度のうまいトレードオフを見つける

などに分類できるんじゃないかと思う．んで，型推論みたいなことをフロー解析でやろう，と思った場合には，確実に計算量の問題があって，しかも解析のテーマとしては古典的なものなわけで，そうすると2か3のうちのどちらかを選んで勝負することになる．ここから先は説明しない．