EoPLのLetlangをocamllex/menhir/duneで実装してみた
前回の記事の構成に従って、簡単な言語のインタプリタを実装してみた。
Essentials of Programming Languagesという本の最初に出てくるLETという言語で、機能としては整数値の引き算、0チェック、if式による分岐、let式による変数束縛。関数定義などはできない。
一例:
let x = 5 in let y = if zero?(x) then 1 else 2 in -(x, y)
これは3に評価される。
ディレクトリ構成は以下の通り:
├── bin │ ├── dune │ └── ex.ml #ライブラリを呼び出して実行するプログラム ├── dune-project └── src #ライブラリ部分 ├── dune ├── env.ml #変数環境の実装 ├── env.mli #変数環境のインタフェース ├── eval.ml #評価器の実装 ├── eval.mli #評価器のインタフェース ├── exp.mli #AST式の型定義 ├── lexer.mll #OCamllexを使ったLexer ├── parser.mly #Menhirを使ったParser ├── val.ml #評価結果である「値」の実装 └── val.mli #「値」のインタフェース
式
LETには文は存在せず、式しかない。のでASTもすべて式だけで表現できる。
その式の型はsrc/exp.mli
に定義されている:
type t = | Const of int #数値リテラル | Diff of t * t #二つの式の評価値の差 | ZeroP of t #式の評価値が0か | If of t * t * t #If式 | Var of string #変数 | Let of string * t * t #letによる変数束縛
Exp
モジュールはこの一つの型のためのみに存在するので、モジュール内で定義される型はOCamlの慣習に則ってtype t
である。Exp
モジュールの外からはExp.t
などとモジュールを指定して使う。
また、Exp
モジュールには型の定義しか存在しないので、インタフェースである.mli
だけが書かれている。
値
式を評価した結果の値を表現する型はsrc/val.mli
とsrc/val.ml
で定義されている。
val.mli
:
type t = | Num of int | Bool of bool val to_str: t -> string
val.ml
:
type t = | Num of int | Bool of bool let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False"
型定義が.ml
と.mli
で重複するのはよくあることらしい。
LET言語では、式を評価した結果は数値か真偽値のみとなる。それを表現する型と、それを文字列に変換する関数。
Parser
src/parser.mly
:
%token <int> INT %token <string> ID %token DIFF %token LPAREN %token RPAREN %token COMMA %token ZERO %token IF %token THEN %token ELSE %token LET %token EQ %token IN %token EOF %start <Exp.t> f %% f : e = expr; EOF { e } expr : | n = INT { Exp.Const n } | DIFF; LPAREN; e1 = expr; COMMA; e2 = expr; RPAREN { Exp.Diff (e1, e2) } | ZERO; LPAREN; e = expr; RPAREN { Exp.ZeroP e } | IF; e1 = expr; THEN; e2 = expr; ELSE; e3 = expr { Exp.If (e1, e2, e3) } | v = ID { Exp.Var v } | LET; v = ID; EQ; e1 = expr; IN; e2 = expr { Exp.Let (v, e1, e2) }
これは普通のOCamlではなく、Menhirというパーサジェネレータに与えるOCamlチックな独自表記である。なのでファイル拡張子もmly
である。まずparser.mly
が普通のOCamlに変換されてから全体がコンパイルされる。(そういったbuild指定はduneファイルで行われる)
Lexerから受け取れるトークンをまず指定し、そのトークンの組み合わせのパターンマッチでExp.t
型の戻り値を返す(パターンマッチは当然再帰的)。
最終的に%start <Exp.t> f
とf : e = expr; EOF { e }
の部分で定義されているf
がパーサ関数となる。
Lexer
LexerはOcamllexを使う。Parserと同じく、OCamlではなく独自表記の.mll
拡張子。
src/lexer.mll
:
{ open Parser } let digit = ['0'-'9'] let number = '-'? digit digit* let whitespace = ['\t' ' ' '\n'] let char = ['a'-'z' 'A'-'Z'] let identifier = char (char|digit)* rule tokenize = parse | whitespace+ { tokenize lexbuf } | number as n { INT (int_of_string n ) } | "-" { DIFF } | "(" { LPAREN } | ")" { RPAREN } | "," { COMMA } | "zero?" { ZERO } | "if" { IF } | "then" { THEN } | "else" { ELSE } | "let" { LET } | "=" { EQ } | "in" { IN } | identifier { ID (Lexing.lexeme lexbuf) } | eof { EOF }
このソースがOcamllexに変換されてOCamlコードになると、rule tokenize = parse ...
のtokenize
がlexer関数名となる。(これもf
でもよかったかも・・・)
変数環境
LETにはlet式による変数束縛があるので、式の中で変数が出てきた場合、なんの値に束縛されているかを評価時に調べなくてはいけない。
そのため、式の評価には式そのものの他に変数環境が必要である。src/env.mli
とsrc/env.ml
に定義されている。
env.mli
:
type t val empty: t val find: t -> string -> Val.t option val extend: t -> string -> Val.t -> t
env.ml
:
type t = (string * Val.t) list let empty = [] let rec find env s = match env with | [] -> None | (s', v)::env' -> if s = s' then Some v else find env' s let extend env s v = (s, v)::env
変数環境の実装は単なる(変数名 * 値)
のタプルのリストで、初期値empty
と関数find
、extend
が定義されている。.mli
ではtype t
としか定義されていないのでEnv
モジュールの外では(string * Val.t) list
をVal.t
型として扱うことはできない(型の実装が隠蔽されている)。
評価器
LET言語の評価器はsrc/eval.mli
とsrc/eval.ml
で定義されている。
eval.mli
:
val f: Exp.t -> Val.t
eval.ml
:
let rec eval' env = function | Exp.Const n -> Val.Num n | Exp.Diff (e1, e2) -> (match eval' env e1, eval' env e2 with | Val.Num n, Val.Num m -> Val.Num (n - m) | _ -> failwith "Diffing non-numeric values") | Exp.ZeroP e -> (match eval' env e with | Val.Num n -> Val.Bool (n = 0) | _ -> failwith "Zero-checking non-numeric value") | Exp.If (e1, e2, e3) -> (match eval' env e1 with | Val.Bool b -> eval' env (if b then e2 else e3) | _ -> failwith "If-condition on non-boolean value") | Exp.Var s -> (match Env.find env s with | Some x -> x | None -> failwith "Variable not in environment") | Exp.Let (s1, e1, e2) -> let v1 = eval' env e1 in let env' = Env.extend env s1 v1 in eval' env' e2 let f = eval' Env.empty
Eval
モジュールは一つの関数f
のみを外部に提供する。内部実装としては、式とともに変数環境を引数にとる再帰関数eval'
をまず定義し、eval'
に空の変数環境を渡したものがf
になる。
Build指示
Buildの指示は前述の通りsrc/dune
に書いてある:
(menhir (modules parser)) (ocamllex lexer) (library (name letlang) (modules_without_implementation exp))
- Parserはmenhirで前処理すること
- Lexerはocamllexで前処理すること
- Expモジュールはインタフェース
.mli
のみであること - ライブラリ全体の名前は
Letlang
であること
が指定されている。
実行プログラム
bin/ex.ml
:
open Letlang let _ = Lexing.from_channel stdin |> Parser.f Lexer.tokenize |> Eval.f |> Val.to_str |> print_endline
stdinをパーサに渡し(パーサはParser.fにLexer.tokenizeを第一引数として渡したもの)、評価し、結果を文字列化して出力する。
これのbuild指示はbin/dune
にある:
(executable (name ex) (libraries letlang))
それ以外
ついでにsrc
とbin
の上のディレクトリにdune-project
というファイルがある:
(lang dune 1.0) (using menhir 1.0)
duneとmenhirのバージョン指定。
実行
実行するにはdune exec
というコマンドを使う。
たとえば
> echo "let x = 5 in -(x, 1)" | dune exec bin/ex.bc 4
あるいは記事冒頭にあるサンプルプログラムのtest.txt
ファイルを作って:
let x = 5 in let y = if zero?(x) then 1 else 2 in -(x, y)
cat
で流し込む:
> cat test.txt | dune exec bin/ex.bc 3
成功。