プログラム言語論 補足説明

MicroML と OCaml の構文の対応

OCaml                MicroML
 13                  CstI 13
 true                CstI true
 x                   Var "x"
 let x = e1 in e2    Let("x", e1', e2')
 e1 + e2             Prim("+", e1', e2')
 if e1 then e2       If(e1', e2', e3')
       else e3
 let rec f x = e1    Letfun("f","x",e1',e2')
      in e2 
 e1 e2               Call(e1',e2')
 fun x -> e1         Lam("x", e1')

OCaml
  fun x -> x + 10
MicroML
  Lam("x", Prim("+", Var "x", CstI 10))

OCaml
  fun x -> fun y -> x y
MicroML
  Lam("x", Lam("y", Call(Var "x", Var "y")))

OCaml
  let f x = 10 in let g y = 20 in f (g 3)
MicroML
  Letrec("f","x",CstI 10,
  Letrec("g","y",CstI 20,
  Call(Var "f", Call("g", CstI 3))))

MicroML の Lam とは何か？

• ラムダ抽象
• OCaml の fun x -> e と MicroMLの Lam("x",e') は同じ。
• MicroML の内部では、Lam("x",e) と Letfun("dummy","x",e, Var "dummy") は同じ。 つまり、「f(x)=e となる関数f」 のこと。