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型には変更はない。

次に、インタープリタ eval2 に環境を導入する。改訂版を 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) ->
    (match (eval3 e1 env) with         (* env を追加 *)
      BoolVal(true)  -> eval3 e2 env   (* env を追加 *)
    | BoolVal(false) -> eval3 e3 env   (* env を追加 *)
    | _ -> raise Wrong_Value)
  | Let(x,e1,e2) -> Let式の処理はこれから追加する
  | _ -> failwith "unknown expression"

変更は、eval2 を呼びだす部分に、 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関数を使う．(x が含まれないときは，x に値がまだはいっていないため，エラーとする．)

Let式の処理は，少し複雑だが，まず，e1 を現在の環境 env のもとで計算する．これが (eval3 e1 env)の部分である．そして，x が，その計算結果の値を持つように環境を拡張し，env1 という新しい環境を得る． e2 を，新しい環境 env1 のもとで評価すると，最終的な結果となる．

課題 7.

上記のeval3に種々の例題を与えてテストしなさい。
let x= 1 in let x = 2 in x のように、同じ変数に関する let式をネストした場合、OCaml では、内側の let が優先される。上記の処理系 eval3 に、ネストした let 式を表現する適当なexp型の式を与えて、 eval3 が OCaml と同じ処理をするか試しなさい。
OCaml では、let x= 1 in let y = x+1 in x+y のように、外側の letで定義された変数を、内側の let式の中で使うことができる。このような処理が eval3で実現されているかどうか確かめなさい。また、let x= 1 in let y = x+1 in x+y のような式を eval3 で評価して、処理の過程で環境がどのように変化していくか考えなさい。 (なお、実際に eval3 の処理の過程で、環境がどうなっているかを見るためには、「環境を印刷する」関数を用意して、環境の中身が変更されるごとにその関数を呼びだせばよい。)
let x= 1 in (let x = 2 in x+1) + (x * 2) のような式の評価では、最後の x の値は(内側の let式の外にあるので) 1である。すなわち、最後の (x * 2) の式を評価しているときは、内側の let式で追加した x=2 という束縛を解除しなければならない。上記の eval3 のプログラムは、「環境から、束縛を除去する」という操作は一切使っていないのに、どうして、この「解除」の操作が実現できているのだろうか。その理由を考えなさい。
今回の処理系では，環境は単なるリストであり，lookup関数は，先頭から順番に1つずつ見ていくので，非常に効率が悪い． (let文が 100回ネストしていたら，環境は長さ 100のリストとなり，変数に値があるかどうか判定するために，最大100回の検査が必要になる．) この効率を改善するためには，どのような方法があるか答えなさい。 (この問題は、方法を答えればよく実装まではしなくてよい。しかし、時間的余裕がある人は，それを実装すれば、加点要素とする。)

トップ, 前へ, 次へ.

亀山幸義