講義テキストの言語がそうであるように,この実験の正規形も式の評価順序が明確に表現されるように設計されている.そのため,算術式のオペランド式やif
式の条件式として任意の式を書くことはできず,変数あるいは整数定数(正規形ではこれらを合わせて値 (value)と呼ぶ)しか書けないようになっている.
さらに,言語と異なり,正規形では式を二種類に分類し,let
式やloop
式によって変数に束縛される値となる式(以下,単にlet
の右辺式と呼ぶ)として書くことの許される式に制限を設ける.具体的には,let
式,loop
式,let rec
式,recur
式をlet
の右辺式とすることはできないようにする.
プログラム全体はである.抽象構文木に含まれていた:
bool
型のリテラルtrue
,false
fun
式
は正規形には含まれていない.前者はそれぞれ整数リテラル1
,0
で表現することにする.後 者はlet rec
式を使った等価な正規形の式として表現できる.具体的にどのようなlet rec
式に変換するかは次節で説明する.
先述のlet
の右辺式に関する制限は,定義中のlet
式,loop
式の右辺式がではなくであることにより表現されている.一方,定義中のif
式の部分式はではなくである.つまり,let
式やlet rec
式をlet
の直接の右辺式として書くことはできないが,間接的にlet
式やlet rec
式が入れ子になることはあり得る.たとえば:
let x = if i < 10 then
let j = i + 1 in ...
else ...
in ...
は正しい正規形である.
let
の右辺式の種類を上記のように制限し,束縛を伴う式の(直接の)入れ子構造を取り除いておくと,後のフェーズの処理が簡潔になる.詳しくは仮想機械で説明する.
正規形を表現するOCamlのデータ型を以下に示す.BNF記法による文法定義をそのままの形でOCamlの型宣言にしているだけである.配布コードのnormal.ml
にもすでに含まれている.
normal.ml
open Pretty
module S = Syntax
exception Error of string
let err s = raise (Error s)
type id = S.id
type binOp = S.binOp
let fresh_id = Misc.fresh_id_maker "_" (* <= 1 *)
(* ==== 値 ==== *)
type value =
Var of id
| IntV of int
(* ==== 式 ==== *)
type cexp =
ValExp of value
| BinOp of binOp * value * value
| AppExp of value * value
| IfExp of value * exp * exp
| TupleExp of value * value
| ProjExp of value * int
and exp =
CompExp of cexp
| LetExp of id * cexp * exp
| LetRecExp of id * id * exp * exp
| LoopExp of id * cexp * exp
| RecurExp of value
なお,normal.ml
の(* <= 1 *)
行目で定義されているfresh_id
関数は,次節の変換処理中にフレッシュな名前を生成するために用いる.id
型(string
型)の引数"
"
を受け取ると,id
型の値"_
"
を返すようになっている(はフレッシュとなるよう適当に割り振られる番号).フレッシュな名前を生成する際,関連するソースプログラム中の識別子名をとして指定しておくと,中間表現を読むときにフレッシュな名前がソースプログラム中のどれと対応しているのか分かりやすくなり,デバッグに便利である.正規形に限らず,この後のフェーズすべてで同様の工夫を行うようにすると良い.
_
")をフェーズ毎に別にしておくと,どの変換処理中で生成した名前かも一目瞭然である.