3-2. 変数と letの処理の続き

前節で学習した環境を用いて、変数と letの処理を実装する。まず、ミニOCaml言語の式の構文に、これらを追加する。

(* 式の型 *)
type exp =
    ...
  | Var of string        
  | Let of string * exp * exp

変数 x は、Var "x" という形のデータとして表現する。また、let x = e1 in e2 という式は、Let("x",e1,e2)という形のデータとして表現する。なお、今回は、値(計算結果となる式)の種類は増えていないので、value型には変更はない。

次に、インタープリタに環境を導入する。改訂版を eval3と呼ぶと、eval3は exp型の式だけでなく、環境も引数として受けとり、value型の値を返す関数である。つまり、eval3 の型は、

  eval3 : exp -> (string * value) list -> value

となる。ここで、環境の型が (string * value) list である。

さて、eval3 を書いてみよう。 eval3 の引数に環境を表す env が加わるので、 eval3 の中でeval3自身を再帰的に呼び出すところもすべて env を引数に追加する。

(* eval3 : exp -> (string * value) list -> value *)
(* let と変数、環境の導入 *)
let rec eval3 e env =           (* env を引数に追加 *)
  let binop f e1 e2 env =       (* binop の中でも eval3 を呼ぶので env を追加 *)
    match (eval3 e1 env, eval3 e2 env) with
    | (IntVal(n1),IntVal(n2)) -> IntVal(f n1 n2)
    | _ -> failwith "integer value expected"
  in 
  match e with
  | Var(x)       -> 変数の処理は後で追加する
  | IntLit(n)    -> IntVal(n)
  | Plus(e1,e2)  -> binop (+) e1 e2 env     (* env を追加 *)
  | Times(e1,e2) -> binop ( * ) e1 e2 env   (* env を追加 *)
  | Eq(e1,e2)    -> ...
  | If(e1,e2,e3) ->
    begin
      match (eval3 e1 env) with          (* env を追加 *)
      | BoolVal(true)  -> eval3 e2 env   (* env を追加 *)
      | BoolVal(false) -> eval3 e3 env   (* env を追加 *)
      | _ -> failwith "wrong value"
    end
  | Let(x,e1,e2) -> Let式の処理はこれから追加する
  | _ -> failwith "unknown expression"

変更は、eval3 を呼びだす部分に、env という引数を追加しただけである。さて、いよいよ Var と Letの処理を記述する。

let rec eval3 e env =           
  ...
  match e with
  | Var(x)       -> lookup x env 
  | ...
  | Let(x,e1,e2) ->
      let env1 = ext env x (eval3 e1 env) 
      in eval3 e2 env1
  | _ -> failwith "unknown expression"

まず、変数 x の処理だが、環境 env の中の x に対応する値を取ってくればよい。このために lookup関数を使う。env の中に x が含まれないときは、 x に値が束縛されていないという意味であるのでエラーとなる。

Let式の処理は少し複雑だが、以下の手順で行われる。

e1 を現在の環境 env のもとで計算する．(eval3 e1 env)
その計算結果を v とすると、x=v を環境 env に追加し、拡張された環境 env1 を得る．
e2 を環境 env1 のもとで評価し、それが Let式の評価の最終結果となる。

課題 3-2.

上記のeval3に種々の例題を与えてテストしなさい。

(* テスト *)
let var_x  = Var("x") ;;   (* 空環境で評価するとエラーになるはず *)
let var_y  = Var("y") ;;   (* 空環境で評価するとエラーになるはず *)
let ex32_1 = Let("x",IntLit(3),Plus(var_x,IntLit(5))) ;;
let ex32_2 = Let("x",ex32_1,Times(ex32_1,var_x)) ;;
let ex32_3 = Let("x",ex32_1,Let("y",IntLit(5),Times(var_x,Var("y")))) ;;
let ex32_4 = Let("x",ex32_1,If(Eq(IntLit 2,var_x),Times(var_x,var_x),IntLit(5))) ;;

let x= 1 in let x = 2 in x のように、同じ変数に関する let式をネストした場合(入れ子にした場合)、 OCaml では、内側の let が優先される。上記の処理系 eval3 に、ネストした let 式を表現する適当な式を与えて、 eval3 が OCaml と同じ処理をするか試しなさい。

(* テスト *)
let ex32_5 = Let("x",IntLit(3),Let("x",IntLit(5),var_x)) ;;
let ex32_6 = Let("x",IntLit(3),Let("x",BoolLit(true),var_x)) ;;
let ex32_7 = Let("x",IntLit(3),Let("x",IntLit(5),Let("x",IntLit(7),var_x))) ;;
let ex32_8 = Let("x",IntLit(3),Let("y",Plus(var_x,IntLit(1)),Times(var_x,var_y))) ;;
let ex32_9 = Let("x",IntLit(3),Let("x",Plus(var_x,IntLit(1)),Times(var_x,IntLit(2)))) ;;

OCaml では、let x= 1 in let y = x+1 in x+y のように、外側の letで定義された変数を、内側の let式の中で使うことができる。このような処理が eval3で実現されているかどうか確かめなさい。
```
(* テスト *)
let ex32_10 = Let("x",IntLit(3),Let("y",IntLit(5),Plus(var_x,var_y))) ;;
```
また、let x= 1 in let y = x+1 in x+y のような式を eval3 で評価して、処理の過程で環境がどのように変化していくか考えなさい。 (eval3 の処理の過程で、環境がどうなっているかを見るためには、「環境を印刷する」関数を用意して、環境の中身が変更されるごとにその関数を呼びだせばよい。)
let x= 1 in (let x = 2 in x+3) + (x * 4) のような式の評価では、最後の x の値は(内側の let式の外にあるので) 1である。すなわち、最後の (x * 2) の式を評価しているときは、内側の let式で追加した x=2 という束縛を解除しなければならない。上記の eval3 のプログラムは、「環境から、束縛を除去する」という操作は一切使っていないのに、どうして、この「解除」の操作が実現できているのだろうか。その理由を考えなさい。
```
(* テスト *)
let ex32_20 =
Let("x",IntLit(1),Plus(Let("x",IntLit(2),Plus(var_x,IntLit(3))),Times(var_x,IntLit(4)))) ;;
```

注. 今回の処理系では、環境は単なるリストであり、 lookup関数は、先頭から順番に1つずつ見ていくので、非常に効率が悪い。たとえば、もし、let文が 100回ネストしていたら、環境は長さ 100のリストとなり、最悪の場合リストの要素を100回検査する必要がある。この効率を改善するためには、どのような方法があるか答えなさい。 (この問題は、方法を答えればよく実装まではしなくてよい。しかし、時間的余裕がある人は，それを実装すれば、加点要素とする。なお、本実験の最後の方で扱うコンパイラでは、この問題に1つの解を与えている。)

トップ, 前へ, 次へ.

亀山幸義