Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼 〜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.tVal.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)
  • 整数を表す式はそのまま整数を表す値に
  • 変数を表す式は変数環境でその変数に対応する値に
  • 関数適用の式はまず関数部分を評価し、その後引数をすべて評価してから関数適用した結果の値に(関数部分が関数でなかった場合はエラー)

となる。継続渡しなども使わない、非常に簡単な再帰スタイルの式評価である。(関数適用の部分が末尾再帰になっていない)

次回は言語機能はこのままで、式評価を継続渡しスタイルに変換する。