MinCaml読解ノート: 不要定義削除

このフェーズでは使われない変数や関数の定義を削除する。

let x = e1 in e2 という定義を削除するには2つの条件を調べればよい。

• 使われていないか? ……e2にxが出現していなければ使われていない。
• 副作用がないか? ……e1に副作用がなければ削除できる。配列の破壊的変更があれば明らかに副作用がある。他の関数を呼んでいる場合その先はわからないので副作用がないとは言い切れない。

両方の条件を満たせば、Letを取り払ってe2に置換できる。

まずここで使われるKNormal.fvから見てゆく。この関数は式を再帰的に調べて、式に出現する自由変数の集合を返す。つまり式の内部で束縛した変数は含まない(調べる式はα変換済なので束縛変数を含もうが含むまいが影響はないのだが)。

変数の集合はS.tで表す。これは標準ライブラリのSetを要素にId.tをとるよう特殊化したものである。

Elim.fではこの関数を使って、変数が使われるかどうかを調べることになる。

次に副作用をチェックするElim.effectをみる。変数の値を計算する式e1を取り、その中に破壊的変更や関数呼び出しがあれば真を返す。非常に簡単である。

let rec effect = function
  | Let(_, e1, e2) | IfEq(_, _, e1, e2) | IfLE(_, _, e1, e2) -> effect e1 || effect e2
  | LetRec(_, e) | LetTuple(_, _, e) -> effect e
  | App _ | Put _ | ExtFunApp _ -> true
  | _ -> false

内部関数の呼び出しの方は、もう少し頑張ればその先で本当に副作用があるかどうかを調べられる筈である。副作用のある関数の集合を記録し、LetRecで関数を定義する際に副作用があるものは追加すればよい。

不要定義削除の本体はElim.fである。

letの場合、式e1, e2を処理した後、e1に副作用がなく、e2で変数が使われなかった場合はめでたくLetを削除できる。

  | Let((x, t), e1, e2) ->
      let e1' = f e1 in
      let e2' = f e2 in
      let live = fv e2' in
      if effect e1' || S.mem x live then Let((x, t), e1', e2') else
      (Format.eprintf "eliminating variable %s@." x;
       e2')

let recの場合、定義した関数が式e2の中で使われていなければLetRecを削除する。変数と違って値を計算する式はないので副作用は関係せず、使われていなければ削除できる。

OCamlメモ

S.empty

空の集合(S.t)を返す。S.tはs.mlで定義される型で、標準ライブラリのSetをId.tを要素に特殊化したものである。

S.add item set

setにitemを加えた新しい集合を返す。

S.remove item set

setからitemを除いた新しい集合を返す。

S.union set1 set2

和集合を作る。

S.singleton item

要素を一つだけ含む集合を作る。

S.mem item set

集合に要素に含まれていれば真を返す。