K正規化(kNormal.ml)

 

「コンパイルとは高水準言語と低水準言語のギャップを埋めることである」と述べましたが、そのようなギャップの一つに「ネストした式」がありました。たとえばMLや大概の言語ではa + b + c - dのような式の値を一発で計算することができますが、普通のアセンブリにそのような命令はありません。

 

このギャップを埋めるために、計算の途中結果もすべて変数として定義するのがK正規化という変換です(ちなみにK正規化という名前は、ML Kitというコンパイラに由来します)。たとえば、さっきの例は

 

let tmp1 = a + b in
let tmp2 = tmp1 + c in
tmp2 - d

 

という風に変換できます。

 

MinCamlでは、KNormal.gK正規化の実装本体、KNormal.tK正規化した後の式を表すデータ型です。KNormal.gは変数の型環境envK正規化前の式とを受け取り、K正規化後の式と、その型とを組にして返します(型環境を受け取ったり型を返したりするのは、letで変数を定義するときに型も付加する必要があるためで、あまりK正規化の本質とは関係がありません)。

 

たとえばe1 + e2という式だったら、まずg env e1のようにe1K正規化し、その結果をletにより変数xとして定義します。それからg env e2のようにe2K正規化し、その結果をletにより変数yとして定義し、x + yという式を(その型intとともに)返します。

 

このようなletを挿入するために、insert_letという補助関数を使用しています。insert_letは、式eを受け取り、新しい変数xを作って、let x = e in ...という式を返します(ただしeが最初から変数のときは、それをxとして利用し、letは挿入しません)。inの中を作るための関数kも引数として受け取り、kxに適用した結果を...の部分として利用します。

 

なお、KNormal.gでは、K正規化のついでに、論理値true, falseを整数1, 0に変換する処理もやっています。また、比較や条件分岐も、e1 <= e2if e then e1 else e2ではなく、if e1 <= e2 then e3 else e4のように比較と分岐が一体となった特殊な形に直します。通常のアセンブリでは比較と分岐が一体となっているので、そのギャップを早めに埋めてしまうためです。そのために、もし条件eが比較になっていなかったら、if e <> 0 then e1 else e2のように、条件の部分を比較に変換します。また、if (not e) then e1 else e2if e then e2 else e1のように変換していくことにより、最後は

if e1 = e2 then e3 else e4

あるいは

if e1 <= e2 then e3 else e4

という二つの形に帰着できます。これらはK正規化とは無関係ですが、もし別々のモジュールにしてしまうと途中のデータ型を定義せねばならず面倒なので、あくまで「ついで」としてKNormal.gで一緒に実装されています。

 

また、外部変数の使用は、外部関数の呼び出し(KNormal.ExtFunApp)か、外部配列の参照(KNormal.ExtArray)のどちらかに限ることとします。大抵のアプリケーションでは、この2つで必要十分だからです。これもK正規化のついでに実現されています。

 

次へ進む