Previous Up Next

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

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

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

��<プログラム>::=<式>�;;
��<式>::=<識別子>�
 |<整数リテラル>�
 |<真偽値リテラル>�
 |<式1>�<二項演算子>�<式n>
 |if�<式1>�then�<式2>�else�<式3>�
 |(<式>)�
��<二項演算子>::=����+�|�*�|�<

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


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: ML1インタプリタ: 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: ML1 インタプリタ: parser.mly

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

図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 という名前で使えるが，通常は 以下の使用法でしか使われない．

それでは，具体例 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: ML1 インタプリタ: 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)の集合を区別する4．今回の実験を行う範囲で実装する機能の範 囲では，このふたつは一致するが，これらが異なる言語も珍しくない．例え ば，C 言語では，変数は，値そのものにつけられた名前ではなく，値が格納さ れた箱につけられた名前と考えられるため， denoted value は expressed value への参照と考えるのが自然になる．ML1 の場合，式の表しうる 集合 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: ML1 インタプリタ: 環境の実装 (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 は ML1の範囲では単に式の値を返すだけのものでよいの だが，後に，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: ML1 インタプリタ: 評価部の実装(eval.ml)の抜粋

3.3.4��main.ml

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

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

処理を繰返している．まず，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 Scheme1 インタプリタ: main.ml
Exercise�1��[必修課題] ML1 インタプリタのプログラムをコンパイル・実行し， インタプリタの動作を確かめよ．大域環境として 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)と関連する
Previous Up Next