IoPLMaterials

Edit this page Report an issue

各モジュールの機能 (1)

実装するインタプリタは6つのモジュール注から構成される．本節ではそれぞれのモジュールについて簡単に説明する．

モジュールについて: OCamlを含め多くのプログラミング言語には， モジュールシステム (module system) と呼ばれる，プログラムを部分的な機能（モジュール (module)）ごとに分割するための機構が備わっている．この機構は，プログラムが大規模化している現代的なプログラミングにおいて不可欠な機構であるが，その解説は本書の範囲を超える．OCaml入門の該当する章を参照されたい．さしあたって理解しておくべきことは，

の二点である．

Syntaxモジュール：抽象構文のためのデータ型の定義

Syntaxモジュールはファイルsyntax.mlに定義されており，抽象構文木を表すデータ型を定義している．具体的には，このモジュールでは上の BNF に対応する抽象構文木を表す以下の型が定義されている．型定義が含まれている．以下にsyntax.mlの中身を示す．

(* 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

type tyvar = int
type ty =
    TyInt
  | TyBool
  | TyVar of tyvar
  | TyFun of ty * ty
  | TyList of ty

以下ではSyntaxモジュールで定義されている型は変数を説明する．実際にsyntax.mlと前出のBNFを見ながら読んでみてほしい．

式の抽象構文木を表す値（すなわち，exp型の値）は，プログラムを表す文字列から，字句解析 と 構文解析 と呼ばれる処理によって生成される．これらの処理については後述するが，

EnvironmentモジュールとEvalモジュール：環境と解釈部

式の表す値

Evalモジュールはインタプリタの動作のメイン部分であり，字句解析と構文解析によって生成された構文木を解釈する．（したがって，この部分をインタプリタの 解釈部 と呼ぶ．）解釈部の動作によって，言語処理系は定義される言語のセマンティクスを定めている．以下にEvalモジュールの中身を示す．

open Syntax

type exval =
    IntV of int
  | BoolV of bool
and dnval = exval

exception Error of string

let err s = raise (Error s)

(* pretty printing *)
let rec string_of_exval = function
    IntV i -> string_of_int i
  | BoolV b -> string_of_bool b

let pp_val v = print_string (string_of_exval v)

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)

プログラミング言語のセマンティクスを定めるに当たって重要なことの一つは，どんな類いの 値 (value) を（定義される言語の）プログラムが操作できるかを定義することである．例えば，C言語であれば整数値，浮動小数値，ポインタなどが値として扱えるし，OCaml であれば整数値，浮動小数値，レコード，ヴァリアントなどが値として扱える．

言語によっては，このとき 式の値 (expressed value) の集合と 変数が指示する値 (denoted value) を区別する必要がある．前者は式を評価した結果得られる値であり，後者は変数が指しうる値である．この2つの区別は，普段あまり意識することはないかもしれないし，実際に今回のインタプリタの範囲では，このふたつは一致する（式の値の集合 = 変数が指示する値の集合）．しかし，この2つが異なる言語も珍しくない．例えば，C 言語では，変数は，値そのものにけられた名前ではなく，値が格納された箱につけられた名前と考えられる．そのため，denoted value は expressed value への 参照 と考えるのが自然になる．

MiniML1 の場合，式の値 expressed value の集合は${\dots, -2, -1, 0, 1, 2, 3, \ldots} \oplus \mbox{真偽値の集合}$であり，denoted value の集合は expressed value の集合に等しい．ここで，$\oplus$ は直和を示している．

eval.mlには値を表す OCaml の型であるexvalとdnvalが定義されている．インタプリタ内では，MiniML の値をこれらの形の（OCamlの）値として表すことになる．型宣言は，初めは以下の通りになっている．

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

exvalがexpressed valueの型，dnvalがdenoted valueの型である．

環境

解釈部を構成する上では，式を評価する際に，各変数の値が何であるかを管理することが重要である．そのためにもっとも簡単な解釈部の構成法のひとつは，抽象構文木と 環境 (environment) と呼ばれるデータ構造を受け取り，抽象構文木が表す式の評価結果を計算する 環境渡しインタプリタ (environment passing interpreter) という方法である．

言語処理系の文脈における 環境 (environment) とは，変数から denoted value への関数（もしくはこの関数を表現するデータ構造）のことである．環境は変数の denoted value への 束縛 (binding) 1を表現する．束縛とは各変数を何らかのデータ（ここでは denoted value）に結びつけることである．プログラムにおいて，各変数が何に束縛されているか（= 各変数の値が何であるか）を，環境で表現するのである．例えば，${x \mapsto 1, y \mapsto 3}$という写像は環境である．この環境は変数$x$を$1$に，$y$を$3$に写像しており，変数xの値が1であり，変数yの値が3であることを表している．

1: 一般に変数$x$が何らかの情報$v$に結び付けられていることを $x$が$v$に束縛されている ($x$ is bound to $v$) と言う．値$v$が変数$x$に束縛されている とはいわない ので注意すること．

OCaml で MiniML の言語処理系を実装する上では，環境をどのような型の値として表現するかが重要である．環境を実装する上では，変数と denoted value の束縛を表現できれば充分なのだが，あとで用いる型推論においても，変数に割当てられた型を表現するために同様の構造を用いるので，汎用性を考えて，環境の型を多相型'a tとする．ここで'aは変数に関連付けられる情報（ここでは denoted value）の型である．こうすることで，同じデータ構造を変数のdenoted valueへの束縛としても，変数の別の情報への束縛としても使用することができるようになる．

環境を操作する値や関数の型，これらの環境から送出されか可能性のある例外は，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

この関数群を実装したものが以下のenvironment.mlである．

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)

環境のデータ表現は，変数と，その変数が束縛されているデータのペアのリストである．例えば上に出てきた環境${x \mapsto 1, y \mapsto 3}$はリスト[(x,1); (y,3)]で表現される．ただし environment.mli では型 'a t が定義のない抽象的な型として宣言されているので，環境を使う側からは環境の実体がこのように実装されていることを使うことはできず，環境の操作はEnvironmentモジュール中の関数を介して行う必要がある．（例えば，環境envに対してmatch env with [] -> ... | hd::tl -> ...のようにリストのパターンマッチを適用することはできない．）

環境の作り方の例を見てみよう．以下は後述する cui.ml に記述されている，プログラム実行開始時の環境(大域環境)の定義である．

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

empty と extend を用いて i，v，x が，それぞれ 1，5，10 に束縛されている環境を作成している．cui.mlはEnvironmentモジュールの外側にいるので，emptyとextendを用いる際にはEnvironment.empty, Environment.extendのように用いている．この大域環境は主に変数参照のテスト用で，(空でなければ)何でもよい．

.mlファイルと.mliファイルの関係について（あるいは，「実装の隠蔽」について）

environment.mliとenvironment.mlの関係を理解しておくのはとても重要なので，ここで少し説明しておこう．どちらもEnvironmentモジュールを定義するために用いられるファイルなのだが，environment.mlは Environmentモジュールがどう動作するかを決定する 実装 (implementation) を定義し，environment.mliはこのモジュールがどのように使われてよいかを決定する インターフェイス (interface) を宣言する．2 中身を見てみると，environment.mlにはEnvironmentモジュールがどう動作するかが記述されており，environment.mliは，このモジュールの使われ方が型によって表現されている．

2: 一般にインターフェイスとは，2つ以上のシステムが相互に作用する場所のことを言う．Environmentモジュールの内部動作と外部仕様との相互作用をenvironment.mliが決めているわけである．

これを頭に入れて，environment.mlとenvironment.mliを見返してみよう．environment.mlは型'a tを連想リスト(Syntax.id * 'a) list型として定義し，'a t型の値を操作する関数を定義している．これに対して，environment.mliは (1) なんらかの多相型'a tが 存在する ことのみを宣言しており，この型の実体が何であるかには言及しておらず，(2) 各関数の型を'a tを用いて宣言している．（.mliファイル中の各関数の型宣言は'a tの実体が(Syntax.id * 'a) listであることには言及していないことに注意．）

Environmentモジュール中の定義を使用するモジュール（例えばあとで説明するEvalモジュールなど）は，environment.mliファイルに書かれている定義のみを，書かれている型としてのみ 使うことができる．例えばEnvironmentモジュールのemptyという変数をEnvironmentモジュールの外から使う際にはEnvironment.emptyという名前で参照することになる．Environment.emptyは'a t型なので リストとして使うことはできない． すなわち，environment.ml内で'a tがリストとして実装されていてemptyが[]と実装されているにも関わらず，1 :: Environment.emptyという式は型エラーになる．

なぜこのように実装とインターフェイスを分離する言語機構が提供されているのだろうか．一般によく言われる説明は プログラムを変更に強くするため である．例えば，開発のある時点でEnvironmentモジュールの効率を上げるために，'a t型をリストではなく二分探索木で実装し直したくなったとしよう．今の実装であれば，'a t型が実際はどの型なのかがモジュールの外からは隠蔽されているので，environment.mlを修正するだけでこの変更を実装することができる．このような隠蔽のメカニズムがなかったとしたら，Environmentモジュールを使用する関数において，'a t型がリストであることに依存した記述を行うことが可能となる．そのようなプログラムを書いてしまうと，二分木の実装への変更を行うためには 全プログラム中のEnvironmentモジュールを利用しているすべての箇所の修正が必要になる． この例から分かるように，実装とインターフェイスを分離して，モジュール外には必要最低限の情報のみを公開することで，変更に強いプログラムを作ることができる．

解釈部の主要部分

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

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

Cui モジュール

メインプログラム main.ml は Cuiモジュール中で定義されているread_eval_printという関数を呼び出している．Cui モジュールは以下のようになっている．

open Eval

let rec read_eval_print env =
  print_string "# ";
  flush stdout;
  let decl = Parser.toplevel Lexer.main (Lexing.from_channel stdin) in
  let _ = print_string "parsing done\n"; flush stdout 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))

関数read_eval_printは，

という処理を繰返している．

（以下の説明は，わからなければとりあえず飛ばしてもよい．）まず，let decl = の右辺にある式

Parser.toplevel Lexer.main (Lexing.from_channel stdin)

を見てみよう．この式は，標準入力から入力された文字列を抽象構文木（すなわちSyntax.exp型の値）に変換して返す．

標準ライブラリ

OCamlの標準ライブラリのドキュメントを読むと，標準ライブラリの使い方が分かる．

なお，OCamlの標準ライブラリは必要最低限の関数のみが提供されているため，OCamlでソフトウェアを作る際にはその他のライブラリの力を借りることが多い．様々なライブラリをパッケージマネージャの opam を用いてインストールすることができる．