4-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)

正しく実行するためには、 「(fun y -> x + y) 」における x の値が 1 である、という情報を持ってお く必要がある。なるほど! 関数そのものを(引数を与えずに)実行して、(関数としての)値を得るときには、 その時点での環境を保存しておく必要がある。

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

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

なお、関数型プログラム言語の処理系においては、上記のような 「関数を評価した結果」であるところの「値としての関数(関数の引数、本体 に、環境を追加したもの)」を、「関数クロージャ (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) ->
      (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")
  | _ -> failwith "unknown expression"

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

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

2. この評価結果をパターンマッチして、FunVal(...) の形かどうかを確認 する。もし、この形にならなかったら、(関数でないものに対して、 関数適用はできないので) Wrong_Value というエラーを発生させる。

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

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

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

課題 8 中盤

• 以下のプログラムをミニ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 を定義できるか，考察せよ． (factorial の自然な定義は再帰呼び出しを含むことに注意せよ．)

課題 8 後半

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

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

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

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

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

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

亀山 幸義