めざそう言語処理系の沼 〜shift/resetへの旅 〜 その4 真偽値

前回までは言語で扱える値は整数値と組み込み関数だけだった。比較とか分岐とかしたいよね、ということで今回は真偽値を追加して、ifで分岐できるようにする。

以下のようなコードが書けるようにする：

(if
  (and (>= 3 1 1)
       (< 0 3)
       false
       (<= 1 2 3 3 5))
  1
  2)

コード差分：

Comparing v0.3...v0.4 · zehnpaard/kontlang · GitHub

Valモジュール：

type t =
| Int of int
| Bool of bool
| Op of string * (t list -> t)

let to_string = function
| Int n -> string_of_int n
| Bool b -> string_of_bool b
| Op (s, _) -> Printf.sprintf "Op(%s)" s

Val.t型にBoolコンストラクタを追加した。

次はBuiltinsモジュールにいろいろ追加していく。

まずはtrue/false：

let builtins =
[ ...
; "true", Val.Bool true
; "false", Val.Bool false
...
]

trueやfalseをパーサに追加するのではなく、Val.Boolの値を持つ組み込み変数として定義している。

次は整数の比較：

let num_bool_op s op =
  let g = function
  | Val.Int n -> n
  | _ -> failwith @@ "Non-numeric value passed to numeric op " ^ s
  in
  let rec h op = function
  | [] | [_] -> Val.Bool true
  | x::y::ys -> if op x y then h op @@ y::ys else Val.Bool false
  in
  let f xs = match List.map g xs with
  | [] -> failwith @@ Printf.sprintf "NumBool op %s applied to empty list" s
  | [_] -> failwith @@ Printf.sprintf "NumBool op %s applied to one arg" s
  | ys -> h op ys
  in
  Val.Op (s, f)

let not_equal_op =
  let g = function
  | Val.Int n -> n
  | _ -> failwith "Non-numeric value passed to numeric op !="
  in
  let rec h = function
  | [] | [_] -> Val.Bool true
  | x::y::ys -> if x != y then h @@ y::ys else Val.Bool false
  in
  let f xs = match List.sort compare @@ List.map g xs with
  | [] -> failwith "NumBool op != applied to empty list"
  | [_] -> failwith "NumBool op != applied to one arg"
  | ys -> h ys
  in
  Val.Op ("!=", f)


let builtins =
[ ...
; "=", num_bool_op "=" (=)
; "!=", not_equal_op
; ">", num_bool_op ">" (>)
; ">=", num_bool_op ">=" (>=)
; "<", num_bool_op "<" (<)
; "<=", num_bool_op "<=" (<=)
...
]

整数のリストを引数に取って真偽値を返す組み込み関数を作るためのヘルパ関数num_bool_opを定義し、それを使って=, >, >=, <, <=を定義している。これらは引数の左端からペアごとに比較していけば全体の結果が出るため。

num_bool_opの内容としては：

• 引数がVal.Intであることを確認しつつOCamlの整数に変換するg関数（Val.Intでないものが含まれている場合はエラー）を定義
• 左端からペアごとにop比較演算子を適用していくh関数を定義
• まず引数であるリストにmap gしてから、要素数が２以上であることを確認してhを適用するf関数を定義
• fをラップしたVal.Opを返す

となっている。今見直すと、hの引数にopいらないな・・・

ポイントの一つとしては、引数がVal.Intじゃなかった場合エラーを返すところ。Lispや他の動的言語だとこういう場合は型変換が起きることもある（例えば偽は0、それ以外は1に変換されるなど）がもしかしたら後々この言語に静的型付けを追加したくなるかもしれないので制約を厳しめにしておく。

!=だけは特別で、専用のnot_equal_opを定義している。何故なら(!= 0 1 0)のような式もfalseになってほしいのでそのままでは「左端からペアごとに比較」が使えない。no_equal_op内では、効率が悪くなるがまずはソートしている。

最後にand、or、not：

let bool_bool_op s op =
  let g = function
  | Val.Bool b -> b
  | _ -> failwith @@ "Non-boolean value passed to bool op " ^ s
  in
  let f xs = Val.Bool (List.fold_left (fun x y -> op x @@ g y) true xs) in
  Val.Op (s, f)

let not_op = function
  | [Val.Bool b] -> Val.Bool (not b)
  | [_] -> failwith "Non-boolean value passed to bool uniop not_op"
  | _ -> failwith "Bool uniop not_op applied to more than one arg"

let builtins =
[ ...
; "and", bool_bool_op "and" (&&)
; "or", bool_bool_op "or" (||)
; "not", Val.Op("not_op", not_op)
]

andやorはVal.Boolのリストをとり、Val.Boolを一つ返す。（andの時にfalseが見つかった時点でその後の評価をやめるようなロジックを実装していないので非効率だが）notもVal.Boolのリストをとり、そのリストの要素数が１ならVal.Boolを、１以外ならエラーを返す。

これで真偽値（と真偽値を返す演算）が言語に追加できた。

今度はこれを有効活用するためにifを追加する。

Expモジュールにif式を追加：

type t =
...
| If of t * t * t

let rec to_string = function
...
| If (e1, e2, e3) ->
    let s1 = (to_string e1) in
    let s2 = (to_string e2) in
    let s3 = (to_string e3) in
    Printf.sprintf "(if %s %s %s)" s1 s2 s3

パーサも拡張：

...
%token IF
...

%start <Exp.t> f

%%

f : e = expr; EOF { e }

expr :
...
| LPAREN; IF; e1 = expr; e2 = expr; e3 = expr; RPAREN { Exp.If (e1, e2, e3) }

if式は「真偽を確かめる式」と「真だった場合に評価する式」と「偽だった場合に評価する式」の三つの式を保持する。

「真偽を確かめる式」を評価してから次の式を選んで評価するので、継続が必要になる。

Contモジュール：

type cont =
...
| If of Exp.t * Exp.t

このCont.If継続に「真だった場合に評価する式」と「偽だった場合に評価する式」を保存しておく。

最後にExecuteモジュール：

let eval env cont = function
...
| Exp.If(e1, e2, e3) -> Eval(env, Cont.If(e2, e3) :: cont, e1)

let apply_cont env cont v = match cont with
...
| Cont.If(e2, e3) :: cont' -> (match v with
  | Val.Bool b -> Eval(env, cont', if b then e2 else e3)
  | _ -> failwith "Non-boolean in condition position of If expression")

evalにExp.Ifのケースを追加、apply_contにCont.Ifのケースを追加している。apply_contの部分で最初に評価した式がVal.Boolではなかった場合、やはり厳しめにエラーにしている。

これで真偽値、比較、分岐が実装できた。

次回はletで変数を定義できるようにする。