4-3. 再帰関数の処理

再帰呼び出し(recursive call)を行う関数の処理をインタープリタに追加する。 OCaml では、たとえば、階乗を計算するプログラムは以下のように定義できる。

let rec factorial x =
   if x = 0 then 1 else x * (factorial (x - 1))
in factorial 5

ここで let factorial ではなく let rec factorial というように、再帰を表す rec というキーワードが追加されている。

再帰関数を実装するには、いくつかの方法がある。

再帰しない関数(前回までに実装したもの)とは別に、再帰関数を表すデータ構造を導入し、再帰関数のための処理を別途記述する。
この方法は実装が簡単であるため、ここで採用する。詳細は後述する。
再帰しない関数の処理をそのまま使えるように、環境の表現においてループ構造を導入する。
ここでいうループ構造というのは、たとえば、
```
x = [1; 2; x; 3; 4]
```
を満たす x のことである。これは、リストの絵を描くと、環状にぐるっとまわっている構造である。 OCamlにおける「普通」の機能だけを使っていると、このようなループ構造をもつデータは定義することができないが、参照型 (ref型)を使うと定義することができる。再帰関数は、「factorial という関数の中で、factorial を使う」というように、概念的にループ構造をもっているので、このような構造を使って環境を表すと表現することができる。
本実験では、参照型などの「汚ない」機能は使わないことにしているので、この方法は採用しない。ただし、1つ目の方法より効率よく実装できることが多い。
処理系では対応せず、再帰しない関数だけを使って再帰関数を表現する、というテクニックをユーザに使ってもらう。
ラムダ計算の授業などを受講している人は、「ラムダ式だけを使って再帰関数を定義する方法」として習ったことがあるだろう。ただし、この方法は、ユーザに負担をかける(ユーザがラムダ計算の理論をよく知っていなければいけない)。

ここでは、第1の方法に基づいて、再帰関数の実装を行う。そのためには、再帰しない関数のほかに、再帰関数というデータが必要になるので、値の型を拡張する。

type value = 
  | IntVal  of int        
  | BoolVal of bool       
  | ListVal of value list 
  | FunVal  of string * exp * ((string * value) list)
  | RecFunVal  of string * string * exp * ((string * value) list)

ここで RecFunValが追加部分であり、 let rec f x = e1 in e2 という形の式で、再帰関数 f が導入されると、その値を RecFunVal("f", "x", e1, env) という形で保持する。ここで env は FunVal のときと同様、この let rec式を評価するときの環境である。

次に、let rec の処理をeval4 に追加する。新しいインタープリタを eval6 と呼ぶ。

let rec eval6 e env =
  ...
  match e with
  ...
  | LetRec(f,x,e1,e2) ->
      let env1 = ext env f (RecFunVal (f, x, e1, env))
      in eval6 e2 env1
  ...

この定義は、それほど難しくないだろう。let rec f x = e1 in e2 という式に対して、RecFunVal(f,x,e1,env) という再帰関数値を生成し、 f=RecFunVal(f,x,e1,env) という束縛を現在の環境 envに追加して、 e2を評価する、というものである。

次に、再帰関数を使って計算する部分を実装する。これは、関数適用であるので、App(e1,e2) に対する処理を変更する。

  ...
  | App(e1,e2) ->
      (let funpart = (eval6 e1 env) in
      let arg = (eval6 e2 env) in
      match funpart with
	FunVal(x,body,env1) ->
	  let env2 = (ext env1 x arg) in
	  eval6 body env2
      | RecFunVal(f,x,body,env1) ->
	  let env2 = (ext (ext env1 x arg) f funpart) in
	  eval6 body env2
      | _ -> failwith "wrong value")

ここで RecFunVal の部分を追加した。App(e1,e2) の計算においては、 e1 を評価した結果を funpartとするとき、funpart が再帰しない関数 FunVal であるか、再帰関数 RecFunVal かで場合分けしている。前者と後者の処理は非常に似ているが、違いが一点だけあり、後者では、f=funpartという束縛を環境に追加しているのである。これは何故かといえば、再帰関数の本体 body を評価するときは、 f への再帰呼び出しが含まれているかもしれないので、f=funpart という束縛を環境の中にいれなければいけないのである。一方、前者では、再帰しない関数であるので、bodyを計算する最中には f=funpartという束縛はあってはいけない。(body の中で fを呼びだしているところがあれば、その f はもっと外側で束縛されているはずである。)

このように、再帰関数の処理は(言葉で書くと長いが)処理の上では非常に単純に記述できた。

課題 9.

再帰関数の動きを見るため、以下のテストプログラムを評価し、その実行過程を考えてみよ。

let ee = emptyenv () 
let _ = eval6 (LetRec ("f", "x", Var "x", IntLit 0)) ee
let _ = eval6 (LetRec ("f", "x", Var "x", App(Var "f", IntLit 0))) ee
let _ = eval6 (LetRec ("f", "x", If(Eq(Var "x", IntLit 0), IntLit 1,
                                   Plus(IntLit 2, 
                                        App(Var "f", Plus(IntLit (-1),
                                                          Var "x")))),
                        App(Var "f", IntLit 0))) ee
let _ = eval6 (LetRec ("f", "x", If(Eq(Var "x", IntLit 0), IntLit 1,
                                    Times(Var "x",
                                          App(Var "f", Plus(IntLit (-1),
                                                            Var "x")))),
                       App(Var "f", IntLit 3))) ee
let _ = eval6 (LetRec ("f", "x", If(Eq(Var "x", IntLit 0), IntLit 1,
                                    Times(Var "x",
                                          App(Var "f", Plus(IntLit (-1),
                                                            Var "x")))),
                       App(Var "f", IntLit 5))) ee

上記の階乗の計算を、OCaml で直接実行したときと、本インタープリタを通して実行したときに、どの程度の速度差が生じているか、考察せよ。これは、どういう原因によるものか？
上記以外の再帰関数を定義し、eval6 を使って実行せよ。 (たとえば、課題1 で作成した fibや gcd を定義してみよ。)
[発展課題; オプショナル] 上記の実装では、再帰呼び出しが起こるごとに、環境の拡張 (ext関数の呼びだし)を行っており、効率がやや悪い。これを改善することは可能だろうか？

トップ, 前へ, 次へ.

亀山幸義