Arantium Maestum

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

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.mlisrc/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> ff : 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.mlisrc/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と関数findextendが定義されている。.mliではtype tとしか定義されていないのでEnvモジュールの外では(string * Val.t) listVal.t型として扱うことはできない(型の実装が隠蔽されている)。

評価器

LET言語の評価器はsrc/eval.mlisrc/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))

それ以外

ついでにsrcbinの上のディレクトリに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

成功。