めざそう言語処理系の沼 〜shift/resetへの旅 〜 その1 四則演算
shift/resetという限定継続を扱うための機構を備えた言語のインタプリタをOCamlで段階的に作っていく。長めのシリーズになりそう。
今回は整数と関連する演算が評価できるインタプリタを作成するまで。EoPLの最初の言語であるLETの二歩くらい手前。
例えば:
(+ (* 1 2 3) 4 (- 5 6 7)) => (+ 6 4 -8) => 2
コードは以下の通り:
GitHub - zehnpaard/kontlang at v0.1
構成:
. ├── README.md ├── dune ├── dune-project ├── main.ml ├── src │ ├── builtins.ml │ ├── dune │ ├── env.ml │ ├── execute.ml │ ├── exp.ml │ ├── lexer.mll │ ├── parser.mly │ └── val.ml └── test ├── dune └── test_nums.ml
心臓部分と言えるのはexecute.ml
の中のこの部分:
let eval_string s = Lexing.from_string s |> Parser.f Lexer.f |> eval (Builtins.load Env.empty) |> Val.to_string
流れとしては
- 文字列を
Lexing.lexbuf
型に変換し - ocamllex/menhirのパーサに渡し
- 返ってきた式(
Exp.t
型)をビルトイン変数だけ追加した変数環境を使って評価し - その結果である
Val.t
型の値を文字列に変換して返す
というものになる。他の記事でも使っているいつものインタプリタ構成である。ついでに言うとS式なのでlexerやparser部分の説明は今回は割愛。
インタプリタの機能が非常に限られているので式や値は非常に簡単なもの。
式を表すExp
モジュール:
type t = | Int of int | Var of string | Call of t * t list let rec to_string = function | Int n -> string_of_int n | Var s -> s | Call (e, []) -> Printf.sprintf "(%s)" @@ to_string e | Call (e, es) -> let fn = to_string e in let args = List.map to_string es |> String.concat " " in Printf.sprintf "(%s %s)" fn args
整数、変数、関数適用のみ。(ちなみに言語内でありえる変数・関数はビルトインのみで、変数を追加したり関数を定義したりはできない)
値を表すVal
モジュール:
type t = | Int of int | Op of string * (t list -> t) let to_string = function | Int n -> string_of_int n | Op (s, _) -> Printf.sprintf "Op(%s)" s
整数と演算子しか存在しない。
変数環境は素直にリストを使うだけ、なEnv
モジュール:
type t = (string * Val.t) list let empty = [] let extend var val_ env = (var, val_)::env let extend_list vvs env = vvs @ env let rec find var = function | [] -> failwith @@ Printf.sprintf "Variable %s not found" var | (var', val')::env' -> if var = var' then val' else find var env'
いわゆるassociation listで、変数を評価するときにO(定義されている変数の総数)
かかるので効率としてはかなり悪い。が、楽なのでとりあえず・・・
変数環境の初期状態として追加されるBuiltins
モジュール:
let num_num_op s op = let g = function | Val.Int n -> n | _ -> failwith @@ "Non-numeric value passed to numeric op " ^ s in let f xs = match List.map g xs with | [] -> failwith @@ Printf.sprintf "Numeric op %s applied to empty list" s | y::ys -> Val.Int (List.fold_left op y ys) in Val.Op (s, f) let builtins = [ "+", num_num_op "+" (+) ; "-", num_num_op "-" (-) ; "*", num_num_op "*" ( * ) ; "/", num_num_op "/" (/) ] let load env = Env.extend_list builtins env
「引数としてVal.Int
のリストを受けとり、fold_left
で畳み込んでVal.Int
を返すVal.Op
」を定義するためのヘルパー関数num_num_op
を使って四則演算を実装している。
Execute
モジュール内で定義されている、Exp.t
をVal.t
に変換するためのeval
関数:
let rec eval env = function | Exp.Int n -> Val.Int n | Exp.Var s -> Env.find s env | Exp.Call (e, es) -> (match eval env e with | Val.Op (_, fn) -> fn @@ List.map (eval env) es | v -> let s = Val.to_string v in failwith @@ Printf.sprintf "Non-function %s in operator position" s)
- 整数を表す式はそのまま整数を表す値に
- 変数を表す式は変数環境でその変数に対応する値に
- 関数適用の式はまず関数部分を評価し、その後引数をすべて評価してから関数適用した結果の値に(関数部分が関数でなかった場合はエラー)
となる。継続渡しなども使わない、非常に簡単な再帰スタイルの式評価である。(関数適用の部分が末尾再帰になっていない)
次回は言語機能はこのままで、式評価を継続渡しスタイルに変換する。