2-4. 真理値とif の処理

前節の処理系 eval1 は、 整数型の数式の処理という極めて単純な対象言語に対するインタープリタであった。 これから、構文を徐々に追加して、ミニOCaml言語に近付けていく。

まず、if を追加する。これは、原理的には簡単であるが、処理系の上では 少し準備がいる。 なぜなら、if をいれるためには、true や falseもいれなければいけないが、 そうすると、式を評価した結果が、整数値とは限らず、 真理値(Boolean)かもしれないからである。 OCaml は型つきの言語なので、 「整数も真理値も表す変数」というものは単純には表せない。

これで困ったように思えるが、OCaml では、 「整数型と真理値型の両方を合わせた型」を定義することが できる。(集合の言葉でいえば、「直和」である。) そこで、このような型を定義して使うことにする。 なお、式を評価した結果、返ってくる式のことを、 値(あたい, value) と呼ぶので、ここでは value という名前の新しい型を定義する。

(* 式の型 *)
type exp =
  |  IntLit of int
  |  Plus of exp * exp 
  |  Times of exp * exp
  |  BoolLit of bool        (* 追加分; 真理値リテラル, つまり trueや false  *)
  |  If of exp * exp * exp  (* 追加分; if-then-else式 *)
  |  Eq of exp * exp        (* 追加分; e1 = e2 *)
  |  ...

(* 値の型 *)
type value =
  | IntVal  of int          (* 整数の値 *)
  | BoolVal of bool         (* 真理値の値 *)
前節のインタープリタでは、eval1 e の結果は、1 や 3といった整数値となるように設計していたが、 今回作成するインタープリタでは、 (IntVal 1) や (BoolVal true) といった value型の値を返すようにする。 ここで IntVal や BoolVal というのは どういう型の値かを示す「タグ」の役割を果たしている。 ポイントは、(繰返しになるが)、value というのは1つの型であるため、 「eval e の返す型は value である」と言えるようになることである。

また、今回から、(1+true) のように、式としてはあり得るが、計算としては 誤っているもの(計算しようがないもの)が与えられる可能性がでてくる。 その場合はエラーとすべきであるので、例外を発生させて、処理をその段階で終えるようにする (実際の処理は後述の通り、failwith という関数を使う)。

さて、このように、インタープリタが返す値が、 value型になると eval1 も変更する必要がある。 変更後の新しいインタープリタは eval2という名前とする。

(* eval2 : exp -> value *)
let rec eval2 e =
  match e with
  | IntLit(n)  -> IntVal(n)
  | Plus(e1,e2) ->   
      begin
        match (eval2 e1, eval2 e2) with
	| (IntVal(n1),IntVal(n2)) -> IntVal(n1+n2)
        | _ -> failwith "integer values expected"
      end
  | Times(e1,e2) ->
      begin
        match (eval2 e1, eval2 e2) with
	| (IntVal(n1),IntVal(n2)) -> IntVal(n1*n2)
        | _ -> failwith "integer values expected"
      end
  | _ -> failwith "unknown expression e"
  (* eval2 はまだ終わりではなく、後で追加する。 *)
なんだか、急に難しくなったように感じるかもしれないので細かく見よう。

プログラムの全体構造は eval1と同じであり、式eについての パターンマッチで場合分けしている。

eval1では、足し算の場合、(eval1 e1) + (eval1 e2) を返していた だけだが、今度は、もう一度 match文を使って、複雑な処理をしている。これ はなんだろうか?

課題 (提出不要; ただし、今後必要になる知識なので必ず自分でやること。試した上でわからなければ、TAに質問してよい)


さて、ここまで来るのはやや大変だったが、if などの処理は比較的やさし いので、一気に書いてしまうことにする。
(* eval2 : exp -> value *)
let rec eval2 e =
  match e with
  | IntLit(n)  -> ...
  | Plus(e1,e2) ->  ...
  | Times(e1,e2) -> ...
  | Eq(e1,e2) ->
      begin
	match (eval2 e1, eval2 e2) with
	  | (IntVal(n1),IntVal(n2)) -> BoolVal(n1=n2)
	  | (BoolVal(b1),BoolVal(b2)) -> BoolVal(b1=b2)
	  | _ -> failwith "wrong value"
      end
  | BoolLit(b) -> BoolVal(b)
  | If(e1,e2,e3) ->
      begin
	match (eval2 e1) with
	  | BoolVal(true) -> eval2 e2
	  | BoolVal(false) -> eval2 e3
	  | _ -> failwith "wrong value"
      end
  | _ -> failwith "unknown expression"

(* テスト *)
let _ = eval2 (IntLit 1)
let _ = eval2 (IntLit 11)
let _ = eval2 (Plus (IntLit 1, Plus (IntLit 2, IntLit 11)))
let _ = eval2 (Times (IntLit 1, Plus (IntLit 2, IntLit 11)))
let _ = eval2 (If (Eq(IntLit 2, IntLit 11),
                   Times(IntLit 1, IntLit 2),
                   Times(IntLit 1, Plus(IntLit 2,IntLit 3))))
let _ = eval2 (Eq (IntLit 1, IntLit 1))
let _ = eval2 (Eq (IntLit 1, IntLit 2))
let _ = eval2 (Eq (BoolLit true, BoolLit true))
let _ = eval2 (Eq (BoolLit true, BoolLit false))

課題 2-4


トップ, 前へ, 次へ.

亀山 幸義