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

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

最初に,mini Scheme1 の(具象)文法を以下のように与える.
<プログラム> ::= <式>
<式> ::= <(0以上の)整数>
  | <識別子>
  | (<プリミティブ> <式1><式n>)
<プリミティブ> ::= + | - | * | add1 | sub1

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

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             (* Integer LITeral *)
  | Var of id               (* VARiable reference *)
  | Prim of prim * exp list (* PRIMitive application *)

type program = Prog of exp


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


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

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


この文法定義ファイルではトレイラは空になっていて,その前の%% は省略されている. さて,この構文解析器への入力となるトークン列を 生成するのが字句解析器である.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 *)
  ("+", 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 Scheme1 インタプリタ: 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 Scheme1 では,このふたつは一 致するが,これらが異なる言語も珍しくない.実際,mini Scheme6 で,言語に変 数への代入を導入することで,両者に違いが現れる.
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 として,環境を操作する関数の型と例外を示す.
val empty_env : unit -> env
val extend_env : Syntax.id list -> dnval list -> env -> env
val apply_env : Syntax.id -> env -> dnval
exception UnboundVar of string
最初の関数 empty_env は,empty_env () とすると,何の変数も束縛され ていない,空の環境を生成する.次の extend_env は,環境に新しい束縛 をいくつか同時に付け加えるための関数で,extend_env ids dnvals env で,環 境 env に対して,変数名のリストidsi番目の要素である 変数を, denoted value のリスト dnvalsi 番目の要素に束縛した ような新しい環境を表す.最後の apply_env 関数は,環境から変数が束縛 された値を取り出すもので,apply_env id env で,環境 env の中を, 新しく加わった束縛から順に変数 id を探し,束縛されている値を返す. 変数が環境中に無い場合は, 例外 UnboundVar が発行される.

この関数群を実装したものが図4である.環境のデータ 表現は,ヴァリアント型を使っており,コンストラクタ EmptyEnv が空の環 境を,ExtendEnv (ids, varray, env) が,環境 env に,変数名のリスト ids と denoted value の配列 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 Scheme1 インタプリタ: 環境の実装 (core.ml)


また,プログラム実行開始時の環境(大域環境)を ivx が それぞれ 1510 に束縛されたような環境として
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 Scheme1 インタプリタ: 評価部の実装(core.ml)


3.3.4 main.ml

メインプログラム main.ml を図6に示す.関数 run で, 字句解析・構文解析・解釈部の結合を行っている.lexer.mll で宣言された 規則の名前 main が関数 Lexer.main に,parser.mly (の %start)で 宣言された非終端記号の名前 toplevel が 関数 Parser.toplevel に対応している.Parser.toplevel は第一引数と して構文解析器から呼び出す字句解析器を,第二引数として読み込みバッファ を表す Lexing.lexbuf 型の値(ここでは標準入力から Lexing.from_channel を使って作られている)をとっている.関数 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 Scheme1 インタプリタ: main.ml



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

Exercise 2  [難易度 1] 本来の Scheme 言語では +* は以下のように, 任意個の引数を受け取れる.

⇒ (+ 2 3 4)
9
⇒ (* 3 4 5)
60
+* がこのように動作するように変更せよ.

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

Exercise 4  [難易度 1] バッチインタプリタを作成せよ.具体的には scm コマンドの引数として ファイル名をとり,そのファイルの内容を mini Schemeプログラムとして 解釈し,結果をディスプレイに出力するように変更せよ.また,Lisp 系 言語では ; 以降行末まではコメントとして扱われる.この機能を 実装せよ.


Previous Up Next