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)
  | [...]
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/4345989
※言及リンクのないトラックバックは受信されません。

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

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

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


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

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