ML1 インタプリタ — プリミティブ演算，条件分岐と環境を使った変数参照

3.3��ML¹ インタプリタ — プリミティブ演算，条件分岐と環境を使った変数参照

まず，非常に単純な言語として，整数，真偽値，条件分岐，加算乗算と変数の参照のみ(新しい変数の宣言すらできない!)を持つ言語 ML¹ から始める．

最初に，ML¹ の文法を以下のように与える．

��<プログラム>	::=	<式>�;;
��<式>	::=	<識別子>�
	\|	<整数リテラル>�
	\|	<真偽値リテラル>�
	\|	<式₁>�<二項演算子>�<式_n>
	\|	if�<式₁>�then�<式₂>�else�<式₃>�
	\|	(<式>)�
��<二項演算子>	::=	��+�\|�*�\|�<

プログラムは，;;で終わるひとつの式である．式は，識別子による変数参照，整数リテラル，真偽値リテラル(trueとfalse)，条件分岐のためのif式，または二項演算子式，括弧で囲まれた式のいずれかである．識別子は，英小文字で始まり，数字・英小文字・「'(アポストロフィ)」を並べた，予約語ではない文字列である．この段階では予約語は if, then, else, true, false の5つである．例えば，以下の文字列はいずれもML¹ プログラムである．


3;;
true;;
x;;
3 + x';;
(3 + x1) * false;;

また，+, * は左結合，結合の強さは，強い方から，*, +, <, if式とする．

それでは，構文に関する部分から順に，6つのファイルを見ていく．

3.3.1��`syntax.ml`: 抽象構文のためのデータ型

上の文法に対する，抽象構文木のためのデータ型は図1のように宣言される．

(* ML interpreter / type reconstruction *)
type id = string

type binOp = Plus | Mult | Lt

type exp =
    Var of id
  | ILit of int
  | BLit of bool
  | BinOp of binOp * exp * exp
  | IfExp of exp * exp * exp

type program = 
    Exp of exp

Figure 1: ML¹インタプリタ: syntax.ml

id は変数の識別情報を示すための型で，ここでは変数の名前を表す文字列としている．(より現実的なインタプリタ・コンパイラでは，変数の型などの情報も加わることが多い．) binOp，exp，program 型に関しては上の文法構造を(括弧式を除いて)そのまま写した形の宣言になっていることがわかるだろう．

3.3.2��`parser.mly`, `lexer.mll`: 字句解析と構文解析

ocamlyacc は，yacc と同様に，LALR(1) の文法を定義したファイルから構文解析プログラムを生成するツールである．ここでは，LALR(1) 文法や構文解析アルゴリズムなどに関しての説明などは割愛し(コンパイラの教科書などを参照のこと)，文法定義ファイルの説明を parser.mly を具体例として行う．

文法定義ファイルは一般に，以下のように4つの部分から構成される．

%{
  <ヘッダ>
%}
  <宣言>
%%
  <文法規則>
%%
  <トレイラ>

<ヘッダ>, <トレイラ> は Objective Caml のプログラムを書く部分で，ocamlyacc が生成する parser.ml の，それぞれ先頭・末尾にそのまま埋め込まれる．<宣言>はトークン(終端記号)や，開始記号，優先度などの宣言を行う．parser.mly では演習を通して，開始記号とトークンの宣言のみを使用する．<文法規則>には文法記述と還元時のアクションを記述する．ヘッダ・トレイラでは，コメントは Objective Caml と同様 (* ... *) であり，宣言・文法規則部分では C 言語と同様な記法 /* ... */ で記述する．

それでは parser.mly を見てみよう(図2)．

%{
open Syntax
%}
%token LPAREN RPAREN SEMISEMI 
%token PLUS MULT LT EQ COLONCOLON 
%token IF THEN ELSE TRUE FALSE

%token <int> INTV
%token <Syntax.id> ID

%start toplevel
%type <Syntax.program> toplevel
%%

toplevel :
    Expr SEMISEMI { Exp $1 }

Expr :
    IfExpr { $1 }
  | LTExpr { $1 }

LTExpr : 
    PExpr LT PExpr { BinOp (Lt, $1, $3) }
  | PExpr { $1 }

PExpr :
    PExpr PLUS MExpr { BinOp (Plus, $1, $3) }
  | MExpr { $1 }

MExpr : 
    MExpr MULT AExpr { BinOp (Mult, $1, $3) }
  | AExpr { $1 }

AExpr :
    INTV { ILit $1 }
  | TRUE { BLit true }
  | FALSE { BLit false }
  | ID { Var $1 }
  | LPAREN Expr RPAREN { $2 }

IfExpr :
    IF Expr THEN Expr ELSE Expr { IfExp ($2, $4, $6) }

Figure 2: ML¹ インタプリタ: parser.mly

この文法定義ファイルではトレイラは空になっていて，その前の%% は省略されている．

ヘッダにある open 宣言は，文法規則宣言部で syntax.ml 中で宣言されているコンストラクタ・型の名前をモジュール名無しで使えるようにしている．(これがないと，いちいち Syntax.Varなどの長い名前で参照しなくてはならない．)
%token <トークン名> ... は，属性を持たないトークンの宣言である．ここでは括弧 “(”， “)” と，入力の終了を示す “;;” に対応するトークン LPAREN, RPAREN，SEMISEMIと，プリミティブ (+, *, <)に対応するトークン PLUS, MULT, LT, 予約語 if, then, else, true, false に対応するトークンが宣言されている．(図1に現れる構文木のコンストラクタ Plus などとの区別に注意すること．トークン名は全て英大文字としている．) この宣言で宣言されたトークン名はocamlyaccの出力する parser.ml 中で，token 型の(引数なし)コンストラクタになる．字句解析プログラムは文字列を読み込んで，この型の値(の列)を出力することになる．
%token <<型>> <トークン名> ... は，属性つきのトークン宣言である．数値のためのトークン INTV (属性はその数値情報なので int 型) と変数のための ID (属性は変数名を表すSyntax.id 型³)を宣言している．この宣言で宣言されたトークン名は parser.ml 中で，<型> を引数とする token 型のコンストラクタになる．
%start <開始記号名> ... で(一つ以上の) 開始記号の名前を指定する．ocamlyacc が生成する， parser.ml ファイルでは，同名の関数が構文解析関数として宣言される．ここでは toplevel という名前を宣言しているので，後述する main.ml では Parser.toplevel という関数を使用して構文解析をしている．開始記号の名前は，次の %type 宣言でも宣言されていなくてはならない．
%type <<型>> <名前> ... 名前の属性を指定する宣言である，toplevel はひとつのプログラムの抽象構文木を表すので属性はSyntax.program 型となっている．
文法規則は，
```
<非終端記号名> : 
   <記号名₁₁> ... <記号名_1n₁> { <還元時アクション₁> }
 | <記号名₂₁> ... <記号名_2n₂> { <還元時アクション₂> }
 ...
```
のように記述する．<還元時アクション>には Objective Caml の式を記述する． $i で，i番目の記号の属性を参照することができる．式全体の評価結果がこの非終端記号の属性となるので，式の型は全て一致している必要がある．例えば Exp は Syntax.exp 型の値(つまり ML¹ の式の抽象構文木)を属性として持ち，各アクションでは，その生成規則に対応する抽象構文木を生成するような式が書かれている．

図2の文法規則が，上で述べた結合の強さ，左結合などを実現していることを確かめてもらいたい．

さて，この構文解析器への入力となるトークン列を生成するのが字句解析器である．ocamllex は lex と同様に正則表現を使った文字列パターンを記述したファイルから字句解析プログラムを生成する．.mll ファイルは，

{ <ヘッダ> }

let <名前> = <正則表現>
...

rule <エントリポイント名> =
  parse <正則表現> { <アクション> }
    |   <正則表現> { <アクション> }
    |   ...
and <エントリポイント名> =
  parse ...
and ...
{ <トレイラ> }

という構成になっている．ヘッダ・トレイラ部には，Objective Caml のプログラムを書くことができ，ocamllex が生成する lexer.ml ファイルの先頭・末尾に埋め込まれる．次の let を使った定義部は，よく使う正則表現に名前をつけるための部分で，lexer.mll では何も定義されていない．続く部分がエントリポイント，つまり字句解析の規則の定義で，同名の関数が ocamllex によって生成される．規則としては正則表現とそれにマッチした際のアクションを(Objective Caml 式で)記述する．アクションは，基本的には(parser.mly で宣言された)トークン(Parser.token 型)を返すような式を記述する．また，字句解析に使用する文字列バッファが lexbuf という名前で使えるが，通常は以下の使用法でしか使われない．

Lexing.lexeme lexbuf で，正則表現にマッチした文字列を取り出す．
Lexing.lexeme_char lexbuf n で，マッチした文字列の n 番目の文字を取り出す．
Lexing.lexeme_start lexbuf で，マッチした文字列の先頭が入力文字列全体でどこに位置するかを返す．末尾の位置は Lexing.lexeme_end lexbuf で知ることができる．
<エントリポイント> lexbuf で，<エントリポイント>規則を呼び出す．

それでは，具体例 lexer.mll を使って説明を行う．

{
let reservedWords = [
  (* Keywords in the alphabetical order *)
  ("else", Parser.ELSE);
  ("false", Parser.FALSE);
  ("if", Parser.IF);
  ("then", Parser.THEN);
  ("true", Parser.TRUE);
] 
}

rule main = parse
  (* ignore spacing and newline characters *)
  [' ' '\009' '\012' '\n']+     { main lexbuf }

| "-"? ['0'-'9']+
    { Parser.INTV (int_of_string (Lexing.lexeme lexbuf)) }

| "(" { Parser.LPAREN }
| ")" { Parser.RPAREN }
| ";;" { Parser.SEMISEMI }
| "+" { Parser.PLUS }
| "*" { Parser.MULT }
| "<" { Parser.LT }

| ['a'-'z'] ['a'-'z' '0'-'9' '_' '']*
    { let id = Lexing.lexeme lexbuf in
      try 
        List.assoc id reservedWords
      with
      _ -> Parser.ID id
     }
| eof { exit 0 }

Figure 3: ML¹ インタプリタ: lexer.mll

ヘッダ部では，予約語の文字列と，それに対応するトークンの連想リストである，reservedWords を定義している．後でみるように，List.assoc関数を使って，文字列からトークンを取り出すことができる．

エントリポイント定義部分では，main という(唯一の)エントリポイントが定義されている．最初の正則表現は空白やタブなど文字の列にマッチする．これらは MLでは区切り文字として無視するため，トークンは生成せず，後続の文字列から次のトークンを求めるために main lexbuf を呼び出している．次は，数字の並びにマッチし，int_of_string を使ってマッチした文字列をint 型に直して，トークン INTV (属性は int 型)を返す．続いているのは，記号に関する定義である．次は識別子のための正則表現で，英小文字で始まる名前か，演算記号にマッチする．アクション部では，マッチした文字列が予約語に含まれていれば，予約語のトークンを，そうでなければ(例外 Not_found が発生した場合は) ID トークンを返す．最後の eof はファイルの末尾にマッチする特殊なパターンである．ファイルの最後に到達したら exit するようにしている．

なお，この部分は，今後もあまり変更が必要がないので，正則表現を記述するための表現についてはあまり触れていない．興味のあるものは lex を解説した本やObjective Camlマニュアルを参照すること．

3.3.3��`environment.ml`, `eval.ml`: 環境の実現，解釈部

式の表す値

さて，本節冒頭でも述べたように，解釈部は，定義される言語のセマンティクスを定めている．プログラミング言語のセマンティクスを定めるに当たって重要なことは，どんな類いの値を(定義される言語の)プログラムが操作できるかを定義することである．この時，式の値(expressed value)の集合と 変数が指示する値(denoted value)の集合を区別する⁴．今回の実験を行う範囲で実装する機能の範囲では，このふたつは一致するが，これらが異なる言語も珍しくない．例えば，C 言語では，変数は，値そのものにつけられた名前ではなく，値が格納された箱につけられた名前と考えられるため， denoted value は expressed value への参照と考えるのが自然になる．ML¹ の場合，式の表しうる集合 Expressed Value は

Expressed Value	=	整数�(…,�−2,�−1,�0,�1,�2,�3,�…)�+�真偽値
Denoted Value	=	Expressed Value

と与えられる．+ は直和を示している．

このことを表現した Objective Caml の型宣言を以下に示す．

(* Expressed values *)
type exval = 
    IntV of int
  | BoolV of bool
and dnval = exval

環境

もっとも簡単な解釈部の構成法のひとつは，抽象構文木と，変数・denoted value の束縛関係の組から，実行結果を計算する方式である．この，変数の束縛を表現するデータ構造を環境(environment)といい，この方式で実装されたインタプリタ(解釈部)を環境渡しインタプリタ(environment passing interpreter)ということがある．

ここでは変数と denoted value の束縛を表現できれば充分なのだが，後半の型推論においても，変数に割当てられた型を表現するために同様の構造を用いるので，汎用性を考えて設計しておく．

環境の型は，変数に関連付けられる情報(ここでは denoted value)の型を 'a として，'a t とする．環境を操作する値や関数の型，例外を示す． (environment.mliの内容である．)

type 'a t
exception Not_bound
val empty : 'a t
val extend : Syntax.id -> 'a -> 'a t -> 'a t
val lookup : Syntax.id -> 'a t -> 'a
val map : ('a -> 'b) -> 'a t -> 'b t
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b

最初の値 empty_env は，何の変数も束縛されていない，空の環境である．次の extend_env は，環境に新しい束縛をひとつ付け加えるための関数で， extend_env id dnval envで，環境 env に対して，変数 id を denoted value dnval に束縛したような新しい環境を表す．関数 lookup は，環境から変数が束縛された値を取り出すもので，lookup id env で，環境 env の中を，新しく加わった束縛から順に変数 id を探し，束縛されている値を返す．変数が環境中に無い場合は，例外 Not_bound が発生する．

また，関数 map は，map f env で，各変数が束縛された値に f を適用したような新しい環境を返す．fold_right は環境中の値を新しいものから順に左から並べたようなリストに対して fold_right を行なう．これらは，後に型推論の実装などで使われる．

この関数群を実装したものが図4である．環境のデータ表現は，単なる連想リストである．ただし，environment.mli では 'a t の定義を示していないので，環境を使う側は，その事実を活用することはできない．

type 'a t = (Syntax.id * 'a) list

exception Not_bound

let empty = []
let extend x v env = (x,v)::env

let rec lookup x env = 
  try List.assoc x env with Not_found -> raise Not_bound

let rec map f = function
    [] -> []
  | (id, v)::rest -> (id, f v) :: map f rest

let rec fold_right f env a = 
  match env with
      [] -> a
    | (_, v)::rest -> f v (fold_right f rest a)

Figure 4: ML¹ インタプリタ: 環境の実装 (environment.ml)

以下は後述する main.ml に記述されている，プログラム実行開始時の環境(大域環境)の定義である．

let initial_env = 
  Environment.extend "i" (IntV 1)
    (Environment.extend "v" (IntV 5) 
       (Environment.extend "x" (IntV 10) Environment.empty))

i，v，x が，それぞれ 1，5，10 に束縛されていることを表している．この大域環境は主に変数参照のテスト用で，(空でなければ)何でもよい．

解釈部の主要部分

以上の準備をすると，残りは，二項演算子によるプリミティブ演算を実行する部分と式を評価する部分である．前者を apply_prim, 後者を eval_exp という関数として図5のように定義する．eval_exp では，整数・真偽値リテラル (ILit, BLit )はそのまま値に，変数は lookup を使って値を取りだし，プリミティブ適用式は，引数となる式(オペランド)をそれぞれ評価し apply_prim を呼んでいる．apply_prim は与えられた二項演算子の種類にしたがって，対応する Objective Caml の演算をしている． if式の場合には，まず条件式のみを評価して，その値によって then節/else節の式を評価している．関数 err は，エラー時に例外を発生させるための関数である(eval.ml 参照のこと)．

eval_decl は ML¹の範囲では単に式の値を返すだけのものでよいのだが，後に，let宣言などを処理する時のことを考えて，新たに宣言された変数名(ここではダミーの"-")と宣言によって拡張された環境を返す設計になっている．

let rec apply_prim op arg1 arg2 = match op, arg1, arg2 with
    Plus, IntV i1, IntV i2 -> IntV (i1 + i2)
  | Plus, _, _ -> err ("Both arguments must be integer: +")
  | Mult, IntV i1, IntV i2 -> IntV (i1 * i2)
  | Mult, _, _ -> err ("Both arguments must be integer: *")
  | Lt, IntV i1, IntV i2 -> BoolV (i1 < i2)
  | Lt, _, _ -> err ("Both arguments must be integer: <")

let rec eval_exp env = function
    Var x -> 
      (try Environment.lookup x env with 
        Environment.Not_bound -> err ("Variable not bound: " ^ x))
  | ILit i -> IntV i
  | BLit b -> BoolV b
  | BinOp (op, exp1, exp2) -> 
      let arg1 = eval_exp env exp1 in
      let arg2 = eval_exp env exp2 in
      apply_prim op arg1 arg2
  | IfExp (exp1, exp2, exp3) ->
      let test = eval_exp env exp1 in
        (match test with
            BoolV true -> eval_exp env exp2
          | BoolV false -> eval_exp env exp3
          | _ -> err ("Test expression must be boolean: if"))

let eval_decl env = function
    Exp e -> let v = eval_exp env e in ("-", env, v)

Figure 5: ML¹ インタプリタ: 評価部の実装(eval.ml)の抜粋

3.3.4��`main.ml`

メインプログラム main.ml を図6に示す．関数 read_eval_print で，

入力文字列の読み込み・構文解析
解釈
結果の出力

処理を繰返している．まず，let decl = の右辺で字句解析部・構文解析部の結合を行っている．lexer.mll で宣言された規則の名前 main が関数 Lexer.main に，parser.mly (の %start)で宣言された非終端記号の名前 toplevel が関数 Parser.toplevel に対応している．Parser.toplevel は第一引数として構文解析器から呼び出す字句解析器を，第二引数として読み込みバッファを表す Lexing.lexbuf 型の値 (ここでは標準入力から読み込むため Lexing.from_channel を使って作られている)をとっている．pp_val は eval.ml で定義されている，値をディスプレイに出力するための関数である．

open Syntax
open Eval

let rec read_eval_print env =
  print_string "# ";
  flush stdout;
  let decl = Parser.toplevel Lexer.main (Lexing.from_channel stdin) in
  let (id, newenv, v) = eval_decl env decl in
    Printf.printf "val %s = " id;
    pp_val v;
    print_newline();
    read_eval_print newenv

let initial_env = 
  Environment.extend "i" (IntV 1)
    (Environment.extend "v" (IntV 5) 
       (Environment.extend "x" (IntV 10) Environment.empty))

let _ = read_eval_print initial_env

Figure 6: mini Scheme¹ インタプリタ: main.ml

Exercise�1��[必修課題] ML¹ インタプリタのプログラムをコンパイル・実行し，インタプリタの動作を確かめよ．大域環境として i, v, x の値のみが定義されているが，ii が 2，iii が 3，iv が 4 となるようにプログラムを変更して，動作を確かめよ．例えば，

iv + iii * ii

などを試してみよ．

Exercise�2��[難易度 1] このインタプリタは文法にあわない入力を与えたり，束縛されていない変数を参照しようとすると，プログラムの実行が終了してしまう．このような入力を与えた場合，適宜メッセージを出力して，インタプリタプロンプトに戻るように改造せよ．

Exercise�3��[難易度 1] 論理値演算のための二項演算子 &&, || を追加せよ．

3: ヘッダ部のopen宣言はトークン宣言部分では有効ではないので，Syntax. をつけることが必要である．
4: この区別はコンパイラの教科書で見られる左辺値(L-value)，右辺値(R-value)と関連する

3.3��ML1 インタプリタ — プリミティブ演算，条件分岐と環境を使った変数参照

3.3.1��syntax.ml: 抽象構文のためのデータ型

3.3.2��parser.mly, lexer.mll: 字句解析と構文解析

3.3.3��environment.ml, eval.ml: 環境の実現，解釈部