5-2. 関数の処理とクロージャ

   let x = 1 in
     let f = fun y -> x + y in
       let x = 2 in
         f (x + 3)

   let x = 1 in
       let x = 2 in
         (fun y -> x + y) (x + 3)

上記のプログラムを正しく実行するためには、 「f に束縛される値は (fun y -> x + y) という式であるが、 そこでの x の値が 1 である」という風に、x の値の情報を持っておく必要がある。 なるほど! このように、計算結果として関数が返るときは(上記の let f = ... jの ....において、fun y->x+y という式は、計算されて、関数を返している)、 関数そのものだけでなく、その時点での環境をセットにして保存する必要がある。

この考えに基づき、値の型の定義を以下のように改善する。

(* 値の型 *)
type value = 
  | IntVal  of int        
  | BoolVal of bool       
  | FunVal  of string * exp * ((string * value) list)

冒頭のプログラムについて考えると、(fun y -> x + y) という式を計算した結果としての値は、 FunVal ("x", Plus(...)) ではなく、 FunVal ("x", Plus(...), [("x",IntVal(1))]) となる。 ここで [("x",IntVal(1))] は、(fun y -> x + y) を計算している時の環境であり、 (x=1) という意味を持っている。

関数型プログラム言語の処理系においては、上記のような 「値としての関数(関数の引数、本体に、環境を追加したもの)」を、 「関数クロージャ (function closure、あるいは、単に closure)」と呼ぶ。

値を上のように決めると、関数抽象 (fun x -> e) と関数適用 (e1 e2) の評価方法は比較的容易に実装することができる。 新しいインタープリタを eval4 とする。

(* eval4 : env -> (string * value) list -> value *)
(* ラムダ式の導入 *)

let rec eval4 e env =
  let binop f e1 e2 env =
    ...
  in 
  match e with
  ......
  | Fun(x,e1) -> FunVal(x, e1, env)
  | App(e1,e2) ->
     begin
      match (eval4 e1 env) with
        | FunVal(x,body,env1) ->
            let arg = (eval4 e2 env) 
	    in eval4 body (ext env1 x arg)
        | _ -> failwith "function value expected"
     end
  | _ -> failwith "unknown expression"

次に、App(e1,e2) の形の関数適用の処理である。これが一番面白いところである。 この処理は、以下の手順で行われる。

1. まず、関数部分である式 e1 を評価する (eval4 e1 env)。 通常は e1 の位置には、関数が書いてあるのだが、 OCaml では、((if x=0 then f else g) 3) というように、 関数が書かれるべき部分に式を書き、その式の計算結果が関数になる、 という場合もあるので、まずは e1 を評価する必要がある。

2. e1の評価結果をパターンマッチして、FunVal(...) の形かどうかを確認する。 もし、この形にならなかったら、 "function value expected" というエラーを発生させる。

3. 次に e2 の評価を行う。これは (eval4 e2 env) とするだけである。 その結果を argという変数に格納する。

4. 関数の仮引数を x とすると、 x=arg という束縛を環境 env1 に追加する。これは、(ext env1 x arg) とす ることにより得られる。 ここで、非常に非常に大事なポイントは、 追加される環境は env (この関数適用を実行している時点での環境)ではなく、 env1 (この関数が作られた時の環境)である点である。 このために、関数クロージャを作ったのだ! このおかげで、静的束縛を実現できている。

5. 上記の準備をした後で、関数の本体(中身) body を実行して、その結果を返す。

課題 5-2. 前半

• 以下のプログラムをミニOCaml言語のプログラムとして表現し、 eval4 で計算し、本当に IntVal 6 が返ってくるかどうか、確かめよ。

  let x = 1 in
    let f = fun y -> x + y in
      let x = 2 in
        f (x + 3)
  

• eval4 の APP のケースで、in eval4 body (ext env1 x arg) とあると ころを in eval4 body (ext env x arg) と変更したとする。 (env1 を env に変更した。) このようにしたとき、上記のプログラム例がどう計算されるか確かめよ。 また、これは動的束縛になっているといえるか、検討せよ。
• ここまでに出てきたミニOCaml の構文だけを使って、 階乗を求める関数 factorial を定義できるか，考察せよ．

  (print_string "point-1"; 10) + (print_string "point-2"; 20) 

上記と同様に、関数の適用においても、OCaml は(予想外の)順序で評価を行う。 たとえば、

  (print_string "point-1"; (fun x -> x)) (print_string "point-2"; 20) 

課題 5-2. 後半

[補足] この問題において、上記の OCamlプログラムを真似して、以下のプログラムを eval4 に渡するのは意味がない。

eval4 (App((print_string "1"; Fun("x",Var "x")), 
           (print_string "2"; IntLit 100)))
      (emptyenv ())

亀山 幸義