前節で述べた言語と正規形の文法上の違いは，同じMiniMLプログラムから得られるそれそれの表現の間の構造の違いとして明確に現れる．簡単な算術式の例を使って見てみよう．

まず，講義テキストの変換によって，式(x + 1) * 2 + (3 + 1)を言語へ変換すると次の表現が得られる：

let _v1 = let _v3 = let _v7 = x in
                    let _v8 = 1 in
                    _v7 + _v8 in
          let _v4 = 2 in
          _v3 * _v4 in
let _v2 = let _v5 = 3 in
          let _v6 = 1 in
          _v5 + _v6 in
_v1 + _v2

これはletの右辺式としてlet式を含んでいるため正規形ではない．正規形であるためには：

let _v7 = x in
let _v8 = 1 in
let _v3 = _v7 + _v8 in
let _v4 = 2 in
let _v1 = _v3 * _v4 in
let _v5 = 3 in
let _v6 = 1 in
let _v2 = _v5 + _v6 in
_v1 + _v2

となっていなければいけない．let式の入れ子構造がなく，どの順にプリミティブな演算を実行するかが上から順に読めば分かるという点で，後者の方がハードウェア上で実行される低水準な計算により近い表現という印象である．

ここでは，言語の式を正規形の式へ変換する方法について説明する．つまり，変換全体は：

  • 講義テキストの変換による抽象構文木（Syntax.exp）から言語への変換

  • この節で説明する方法による言語から正規形（Normal.exp）への変換

の2パスの処理となる．実際にOCamlでコーディングする際には，言語の式を表現するOCamlのデータ型をあらたに定義せず，Syntax.expをそのまま用いると良い．

以下では簡単のため，letの右辺式がlet式である場合に限定して説明する．let rec式やloop式の場合にも同様に考えれば良い．

まず，式に対する通常の代入操作「中に現れるすべての自由変数にを代入する」をと書くことにする．たとえば：

は，(fun x -> x + 1) (2*3)となる．

次に，let式を特別に扱う特殊な代入操作を次のように定義する．

任意の式，について，式と式が（少なくとも副作用のないMiniML言語においては）同じ値に評価されることに注意して欲しい．

この特殊な代入操作を上手く用いることで，let式の入れ子構造を取り除く処理を実現できる．まず，簡単な例を考えてみよう．たとえば：

let _v0 = let _v1 = 1 in
          _v1 + 2 in
_v0 * 3

のような入れ子のlet式は，内側のlet式全体を表わす適当なフレッシュ変数を用意し，通常の代入操作：

の結果と見なすことができる．この代入式を等価な特殊代入式：

に置き換え，さらにその代入を行うと，望みどおりの式：

let _v1 = 1 in
let _v0 = _v1 + 2 in
_v0 * 3

が得られる．

2パス目の変換をで表わすことにすると，一般的なlet式に対しては：

のように変換すれば良い．

最後に，抽象構文木中のfun式は，let rec式のシンタックス・シュガーと見なすことで簡単に扱うことができる．たとえば，式fun x -> x + 1は，まず適当なフレッシュな名前の関数をlet rec式で定義し，すぐさまその名前を参照する式：

let rec _f0 = fun x -> x + 1 in _f0

のシンタックス・シュガーに過ぎない．このシンタックス・シュガーを展開する変換処理は非常に単純なため，先程の2つの変換のどちらかで同時に行うと良い．

ここまでの説明に従って素直に実装するのであれば，正規形への変換は2パスの処理となるのが普通であるが，実際には，実装方法を工夫することにより1パスでの変換が可能である．

課題5(必須) 正規形への変換
言語への変換と，正規形への変換を同時に行う，nomal.ml中のnorm_exp関数を完成させよ．関数は次に示す形で実装すること．引数fを適切に用いれば各場合分けで数行書くだけで完成する．
let rec norm_exp (e: Syntax.exp) (f: cexp -> exp) = match e with
  | Syntax.Var i -> ...
  ...
  | Syntax.ProjExp (e, n) -> ...

and normalize e = norm_exp e (fun ce -> CompExp ce)

課題5で必要となる工夫のヒント

「抽象構文木中の全ての名前にプレフィックス"_"をつける」という単純な変換をOCamlでコーディングすることを考えてみる．通常なら：

let rec trans e = match e with
    Var id -> Var ("_" ^ id)
  | RecurExp e' -> RecurExp (trans e')
  | ...

と書くところだが，それ以外に：

let rec trans' e k = match e with
    Var id -> k (Var ("_" ^ id))
  | RecurExp e' -> trans' e' (fun x -> k (RecurExp x))
  | ...

let trans e = trans' e (fun x -> x)

と書くこともできる．