講義テキストの言語がそうであるように,この実験の正規形も式の評価順序が明確に表現されるように設計されている.そのため,算術式のオペランド式やif式の条件式として任意の式を書くことはできず,変数あるいは整数定数(正規形ではこれらを合わせて (value)と呼ぶ)しか書けないようになっている.

さらに,言語と異なり,正規形では式を二種類に分類し,let式やloop式によって変数に束縛される値となる式(以下,単にletの右辺式と呼ぶ)として書くことの許される式に制限を設ける.具体的には,let式,loop式,let rec式,recur式をletの右辺式とすることはできないようにする.

プログラム全体はである.抽象構文木に含まれていた:

  • bool型のリテラルtruefalse
  • fun

は正規形には含まれていない.前者はそれぞれ整数リテラル10で表現することにする.後 者は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型の値"_"を返すようになっている(はフレッシュとなるよう適当に割り振られる番号).フレッシュな名前を生成する際,関連するソースプログラム中の識別子名をとして指定しておくと,中間表現を読むときにフレッシュな名前がソースプログラム中のどれと対応しているのか分かりやすくなり,デバッグに便利である.正規形に限らず,この後のフェーズすべてで同様の工夫を行うようにすると良い.