2005年06月17日

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

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

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

  • 使われていないか? ……e2xが出現していなければ使われていない。
  • 副作用がないか? ……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で定義される型で、標準ライブラリのSetId.tを要素に特殊化したものである。
S.add item set
setitemを加えた新しい集合を返す。
S.remove item set
setからitemを除いた新しい集合を返す。
S.union set1 set2
和集合を作る。
S.singleton item
要素を一つだけ含む集合を作る。
S.mem item set
集合に要素に含まれていれば真を返す。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/4413507
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。