突発簡単チュートリアル３：プリミティブとしての再帰関数

λ計算で再帰関数を表すには不動点演算子を使うのが「教科書的」ですが、現実的な言語処理系やプログラム解析の研究などでは、効率や精度・単純さなどの問題などから、再帰関数をプリミティブにするほうが普通です。

で、Scheme（というかSICP?）の影響かどうかわかりませんが、たまに「再帰関数をプリミティブとして実装するには、Schemeのset!やMLのreferenceのような、破壊的代入が必要である」という誤解があります（追記：これはわりとよくある誤解で、演習のレポートなどでも散見されるので、特定の人間のことを言っているわけではありません。念のため…）。もちろん、そういう実装も可能ですが、そうでない実装も可能です。たとえば、f(x)=Mなる再帰関数fをfix(f,x,M)と書くことにして、前回のbig-step semanticsを

M ::= x | fix(f,x,M) | M1 M2
V ::= Closure(f,x,M,ε)

ε├ x ⇒ ε(x)

ε├ fix(f,x,M) ⇒ Closure(f,x,M,ε)

ε├ M1 ⇒ Closure(f,x,M,ε')かつε├ M2 ⇒ Wかつε'∪{(f,Closure(f,x,M,ε'))}∪{(x,W)}├ M ⇒ Vならば、ε├ M1 M2 ⇒ V

と変更すれば済みます。要するに、再帰関数fの本体Mを評価するときに、環境ε'に引数xだけでなくf自身の値も追加すれば良い、ということです。ちなみに、fがMに現れなければ、fix(f,x,M)はふつーのλx.Mと同じになります。

（わかりやすい例を書くために）整数と条件分岐も追加して、OCamlで実装すると↓のようになります。

type var = string
type exp =
  | Var of var
  | Fix of var * var * exp
  | App of exp * exp
  | Int of int
  | Sub of exp * exp
  | IfPos of exp * exp * exp
type env = (string * value) list
and value =
  | Closure of var * var * exp * env
  | Integer of int
    
let rec eval e = function
  | Var x -> List.assoc x e
  | Fix(f, x, m) -> Closure(f, x, m, e)
  | App(m1, m2) ->
      let Closure(f, x, m, e') as v = eval e m1 in
      let w = eval e m2 in
      eval ((x, w) :: (f, v) :: e') m
  | Int i -> Integer i
  | Sub(m1, m2) ->
      let Integer i1 = eval e m1 in
      let Integer i2 = eval e m2 in
      Integer(i1 - i2)
  | IfPos(m1, m2, m3) ->
      let Integer i = eval e m1 in
      eval e (if i > 0 then m2 else m3)

# let fib =
    Fix("fib", "n",
        IfPos(Sub(Int 2, Var "n"),
              Int 1,
              Sub(App(Var "fib", Sub(Var "n", Int 1)),
                  Sub(Int 0,
                      App(Var "fib", Sub(Var "n", Int 2)))))) ;;
val fib : exp =
  Fix ("fib", "n",
   IfPos (Sub (Int 2, Var "n"), Int 1,
    Sub (App (Var "fib", Sub (Var "n", Int 1)),
     Sub (Int 0, App (Var "fib", Sub (Var "n", Int 2))))))
# eval [] (App(fib, Int 10)) ;;
- : value = Integer 89