mini Scheme1 インタプリタ --- プリミティブ演算と環境を使った変数参照

mini Scheme¹ インタプリタ --- プリミティブ演算と環境を使った変数参照

まず，非常に単純な言語として，整数，変数参照と加減乗演算のみ(新しい変数の宣言すらできない!)を持つ言語 mini Scheme¹ から始める．

最初に，mini Scheme¹ の(具象)文法を以下のように与える．

<プログラム>	::=	<式>
<式>	::=	<(0以上の)整数>
	\|	<識別子>
	\|	(<プリミティブ> <式₁> … <式_n>)
<プリミティブ>	::=	+ \| - \| * \| add1 \| sub1

プログラムは，ひとつの式からなり，式は，(0以上の)整数，識別子による変数参照，またはプリミティブ適用式のいずれかである．識別子は，英小文字で始まり，数字・英小文字・「'(アポストロフィ)」を並べた文字列である．例えば，以下の文字列はいずれもmini Scheme¹ プログラムである．


3
x
(+ 3 x')
(add1 (+ 3 x1))

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

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

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

(* abstract syntax *)
type id = string

type prim = Plus | Minus | Mul | Add1 | Sub1

type exp = 
    ILit of int
  | Var of id
  | Prim of prim * exp list

type program = Prog of exp

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

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

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

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
%token PLUS MINUS MUL ADD1 SUB1

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

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

toplevel :
    Exp { Prog $1 }

Exp :
    INTV { ILit $1 }
  | ID { Var $1 }
  | LPAREN PrimOp Arglist RPAREN { Prim ($2, $3) }

PrimOp :
    PLUS { Plus }
  | MINUS { Minus }
  | MUL { Mul }
  | ADD1 { Add1 }
  | SUB1 { Sub1 }

Arglist :
 /* empty */ { [] }
  | Exp Arglist { $1 :: $2 }

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

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

ヘッダにある open 宣言は，文法規則宣言部で syntax.ml 中で宣言されているコンストラクタ・型の名前をモジュール名無しで使えるようにしている．(これがないと，Syntax.Varなどの長い名前で参照しなくてはならない．)
%token <トークン名> ... は，属性を持たないトークンの宣言である．ここでは括弧 ``('' と ``)'' に対応するトークン LPAREN, RPARENと，プリミティブ (+, -, *, add1, sub1)に対応するトークン PLUS, MINUS, MUL, ADD1, SUB1 が宣言されている．
%token <<型>> <トークン名> ... は，属性つきのトークン宣言である．数値のためのトークン INTV (属性はその数値情報なので int 型) と変数のための ID (属性は変数名を表すSyntax.id 型²)を宣言している．このふたつの宣言で宣言されたトークン名はocamlyacc の出力する 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 型の値(つまり mini Scheme¹ の式の抽象構文木)を属性として持ち，各アクションでは，その生成規則に対応する抽象構文木を生成するような式が書かれている．

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

{ <ヘッダ> }

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

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

という構成になっている．ヘッダ・トレイラ部には，Objective Caml の宣言を書くことができ，ocamllex が生成する lexer.ml ファイルの先頭・末尾に埋め込まれる．次の宣言部はよく使う正則表現に名前をつけるための部分で， 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 *)
  ("+", Parser.PLUS);
  ("-", Parser.MINUS);
  ("*", Parser.MUL);
  ("add1", Parser.ADD1);
  ("sub1", Parser.SUB1);
] 
}

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 }

| ['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: mini Scheme¹ インタプリタ: lexer.mll

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

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

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

3.3.3 core.ml: 解釈部

Expressed value と Denoted value

さて，本節冒頭でも述べたように，解釈部は，定義される言語のセマンティクスを定めている．プログラミング言語のセマンティクスを定めるに当たって重要なことは，どんな類いの値をプログラムが操作できるかを定義することである．この時，式の値(expressed value)の集合と変数が指示する値(denoted value)の集合を区別する．mini Scheme¹ では，このふたつは一致するが，これらが異なる言語も珍しくない．実際， mini Scheme⁶ で，言語に変数への代入を導入することで一致しなくなる．

Expressed Value	=	整数 (…, -2, -1, 0, 1, 2, 3, …)
Denoted Value	=	整数

であるとする．

このための型宣言を以下に示す．

(* Expressed values *)
type exval = 
    IntV of int

(* Denoted values *)
and dnval = exval

exval 型はコンストラクタがひとつのヴァリアント型で表現しているが，これは，将来，式の値の集合に整数以外のものが入ってきたときの，コードの変更を容易にするためである．

環境

もっとも簡単な解釈部の構成法のひとつは，抽象構文木と，変数・Denoted Value 間の束縛状態の組から，実行結果を計算する方式である．この，変数の束縛状態を表現するデータ構造を環境(environment) という．

まずは，環境の型を env として，環境を操作する関数の型と例外を示す．

exception UnboundVar of string
val empty_env : unit -> env
val extend_env : Syntax.id list -> dnval list -> env -> env
val apply_env : Syntax.id -> env -> dnval

最初の関数 empty_env は，empty_env () とすると，何の変数も束縛されていない，空の環境を生成する．次の extend_env は，環境に新しい束縛をいくつか同時に付け加えるための関数で，extend_env ids dnvals env で，環境 env に対して，変数名のリストids のi番目の要素である変数を， denoted value のリスト dnvalsの i 番目の要素に束縛したような新しい環境を表す．最後の apply_env 関数は，環境から変数が束縛された値を取り出すもので，apply_env id env で，環境 env の中を，新しく加わった束縛から順に変数 id を探し，束縛されている値を返す．変数が環境中に無い場合は，例外 UnboundVar が発行される．

この関数群を実装したものが図4である．環境のデータ表現は，ヴァリアント型を使っており，コンストラクタ EmptyEnv が空の環境を，ExtendEnv (ids, varray, env) が，環境 env に，変数名のリスト ids と値の配列 varray で表現される束縛を付け加えたような環境を表現している．apply_env での，補助関数 list_pos と，例外の使用法に注意されたい．

type env = 
    EmptyEnv
  | ExtendEnv of id list * dnval array * env

exception UnboundVar of string

let empty_env () = EmptyEnv

let extend_env ids dnvals env = 
  (* assumes List.length syms = List.length dnvals *)
  ExtendEnv (ids, Array.of_list dnvals, env)

let rec list_pos n = function
    [] -> raise Not_found
  | m :: rest -> if n = m then 0 else succ (list_pos n rest)

let rec apply_env id = function
    EmptyEnv -> raise (UnboundVar id)
  | ExtendEnv (ids, dnvals, rest) -> 
      (try dnvals.(list_pos id ids) with Not_found -> apply_env id rest)

Figure 4: mini Scheme¹ インタプリタ: 環境の実装 (core.ml)

また，プログラム実行開始時の環境(大域環境)を i，v，x がそれぞれ 1，5，10 に束縛されたような環境として

let global_env = 
  extend_env 
    ["i"; "v"; "x"] 
    (List.map (fun i -> IntV i) [1; 5; 10]) 
    (empty_env())

と定義する．

解釈部の主要部分

以上の準備をすると，残りは，プリミティブ適用式を実行する部分と式を評価する部分である．前者を apply_prim, 後者を eval_exp という関数として図5のように定義する． eval_exp では，リテラル数値(ILit)はそのまま値に，変数は apply_env を使って値を取りだし，プリミティブ適用式は，引数となる式をそれぞれ評価し(eval_rands)，apply_prim を呼んでいる．apply_prim は与えられたプリミティブにしたがって，対応する Objective Caml の演算をしている．引数の数のチェックはパターンマッチで行っている．

let apply_prim p args =
  match p, args with
  | (Plus, [IntV i; IntV j]) -> IntV (i + j)
  | (Plus, _) -> failwith "Arity mismatch: +"
  | (Minus, [IntV i; IntV j]) -> IntV (i - j)
  | (Minus, _) -> failwith "Arity mismatch: -"
  | (Mul, [IntV i; IntV j]) -> IntV (i * j)
  | (Mul, _) -> failwith "Arity mismatch: *"
  | (Add1, [IntV i]) -> IntV (i + 1)
  | (Add1, _) -> failwith "Arity mismatch: add1"
  | (Sub1, [IntV i]) -> IntV (i - 1)
  | (Sub1, _) -> failwith "Arity mismatch: sub1"

let rec eval_exp env = function
    ILit i -> IntV i
  | Var sym -> apply_env sym env
  | Prim (p, es) -> 
      let args = eval_rands env es in
      apply_prim p args

and eval_rands env = function
    [] -> []
  | e :: rest -> eval_exp env e :: eval_rands env rest

let eval_program (Prog e) = eval_exp global_env e

Figure 5: mini Scheme¹ インタプリタ: 評価部の実装(core.ml)

3.3.4 main.ml

メインプログラム main.ml を図6に示す．この部分は，今後の拡張に影響しない．関数 run で，字句解析・構文解析・解釈部の結合を行っている．関数 read_eval_print では，まず，プロンプトを出力し， run の呼び出しによるプログラムの入力と評価を行い，その結果を core.ml に定義された pp という関数を使って出力し，自分自身にループしている．最後の宣言(let _ = ...)で，read_eval_print を呼出し，インタプリタの実行を開始する．

let run () =
  Core.eval_program 
    (Parser.toplevel Lexer.main (Lexing.from_channel stdin))

let rec read_eval_print () =
  print_string "=> ";
  flush stdout;
  Core.pp (run ()); 
  print_newline ();
  read_eval_print ()

let _ = read_eval_print ()

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

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

(- (sub1 (* iii (+ ii v))) iv)

などを試してみよ．

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