2005年06月14日

MinCaml読解ノート: α変換

プログラム中の束縛変数の名前を付け替えて一意な名前にする。

Alpha.findが付け替えた変数名の変換を行う関数である。envに登録されていなければ外部変数として変換せずにそのまま返す。

let find x env = try M.find x env with Not_found -> x

本体はAlpha.gで、この関数は環境(付け替え前と後の変数名の対応表)と式を受け取る。基本的には変数名をfind x envで置き換えるだけである。

letでは新しい変数名を生成して置き換え、元の変数名との対応を環境に追加して残りの式を変換する。let recの場合も同様である。let recではそれぞれの関数の引数名も変換し、関数の式をα変換するときに引数の変換も加えた環境を渡す。

let rec g env = function
  | Add(x, y) -> Add(find x env, find y env)
  | Sub(x, y) -> Sub(find x env, find y env)
  | [...]
  | IfEq(x, y, e1, e2) -> IfEq(find x env, find y env, g env e1, g env e2)
  | IfLE(x, y, e1, e2) -> IfLE(find x env, find y env, g env e1, g env e2)
  | Let((x, t), e1, e2) ->
      let x' = Id.genid x in
      Let((x', t), g env e1, g (M.add x x' env) e2)
  | [...]

広告


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

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

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


×

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