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

前節と同じプログラムについて考える。

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

OCaml は静的束縛の言語であるので、このプログラムの実行における let f = ... という部分で、「f に束縛される値は (fun y -> x + y) という式である」と考えることはできない。なぜなら、そう考えると、上記の式は、

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

という式と同じになってしまうが、これは、OCaml で実行すると 7 になってしまい、上記のプログラムを OCamlで実行したときの値 6 と異なってしまうからである。

上記のプログラムを正しく実行するためには、「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)

前回に比べて、FunVal の引数の型に (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"

まず、Fun(x,e1)の形の式のときは、上記の解説通り、現在の環境 env を関数クロージャに取りこんで返す。ここで、関数定義の本体である e1 は全く計算せず、そのまま取りこむことに注意せよ。

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

まず、関数部分である式 e1 を評価する (eval4 e1 env)。通常は e1 の位置には、関数が書いてあるのだが、 OCaml では、((if x=0 then f else g) 3) というように、関数が書かれるべき部分に式を書き、その式の計算結果が関数になる、という場合もあるので、まずは e1 を評価する必要がある。
e1の評価結果をパターンマッチして、FunVal(...) の形かどうかを確認する。もし、この形にならなかったら、 "function value expected" というエラーを発生させる。
次に e2 の評価を行う。これは (eval4 e2 env) とするだけである。その結果を argという変数に格納する。
関数の仮引数を x とすると、 x=arg という束縛を環境 env1 に追加する。これは、(ext env1 x arg) とすることにより得られる。ここで、非常に非常に大事なポイントは、追加される環境は env (この関数適用を実行している時点での環境)ではなく、 env1 (この関数が作られた時の環境)である点である。このために、関数クロージャを作ったのだ! このおかげで、静的束縛を実現できている。
上記の準備をした後で、関数の本体(中身) body を実行して、その結果を返す。

ここは、本実験では一番難しいところであるので、すぐには理解できないかもしれないが、静的束縛された関数の計算方法の理解は、 C言語など他の言語でも必要なことなので、時間がかかってもよいので、頑張って理解してほしい。

課題 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 を定義できるか，考察せよ．

実は、eval4 における関数適用の計算の順序は、 OCaml処理系の評価順序とは一致していない。このことを知るために、以下のプログラムを OCamlで実行してみよ。

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

このプログラムは、プリント文をのぞけば 10 + 20 を計算しているだけであるが、問題は、2つのプリント文のどちらが先に計算されるか、である。 OCaml 処理系では、"1" と "2" のどちらが先に印刷されるかを確かめよ。

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

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

を実行してみよ。

課題 5-2. 後半

この実験で与えた eval4 が (e1+e2) や (e1 e2) という式の計算を、どういう順序で行うか答えなさい。また、OCaml と食い違っている順序になっている部分は、OCaml と一致させるようにeval4 を変更しなさい。 (ただし、ここまでで作成したミニOCaml言語には、プリント文など副作用を持つ式が含まれていないので、OCamlとの評価順序の食い違いは表面化しない。将来、プリント文や例外処理を導入したときに表面化する。)

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

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

これでは、第1引数が eval4 に渡される前に、 print_string "1" と print_string "2" が実行されてしまうので、 eval4 の評価順序を調べることにならず、OCamlの評価順序を調べていることになる。従って、上記のプログラムについては、OCaml と eval4 の結果は一致してしまう。

トップ, 前へ, 次へ.

亀山幸義