実行効率の良いクロージャ(関数値の実行時データ表現)を生成できるだけの能力を与えるため,まず,クロージャ変換の出力形式である中間表現(以降,閉じた正規形(closed normal form)と呼ぶ)に対し,MiniML言語にはない以下の2つの機能を追加する.
(1) 任意サイズの組
MiniML言語やここまでの中間表現では,2つ組しか書くことができなかった.効率良いクロージャ表現には,3つ以上の要素を含む組が必要となるため,組に関する構文に対し任意個の要素を含むことのできるよう自然な拡張を行う.言語仕様の節にあった2つ組を入れ子にした例は,この拡張によって次のように簡潔になる(あくまで中間表現に対する拡張であるため,ユーザプログラム中にこのように書く手段は用意されていないが,minimlc
コマンドの-v
オプションはこの記法で任意サイズの組を表示する):
let grades' = (0, 1, 2, 3, 4) in
let good' = grades'.3 (* good' is bound to 3 *)
2つ組の要素への参照が1と2だったのに対し,任意サイズの組では第1要素のインデックスは0,第2要素のインデックスは1,…となることに注意して欲しい.
MiniMLコンパイラのクロージャ表現を含め,ある種のデータ構造を構築するのに任意サイズの組を用いる方が効率が良い理由を正確に理解するには,コード生成フェーズまで読み進めてハードウェア上での具体的な表現をイメージする必要があるが,とりあえずは以下のように大雑把に理解しておけば十分である.
- 空間使用量
- 組のデータ表現には,すべての要素を表現するのに必要なメモリ量1ワード分のメモリが必要となる.整数値のデータ表現に1ワードが必要とすると,言語仕様の節にあった2つ組を入れ子にした例の
grades
には9ワードが必要なのに対し,上のgrades'
は6ワードで済む. - 時間使用量
- 組から要素を取り出すには1回のメモリアクセスを要する.そのため,言語仕様の節にあった2つ組を入れ子にした例の
good
に束縛される値を取り出すには計4回のメモリアクセスが必要だが,上のgood'
なら1回で済む.
(2) 多引数関数
OCaml,MiniMLを含むML系言語には多引数関数の概念はない.その代わりに,高階関数によるカリー化や,組を使って複数の引数をひとまとめにして渡すことにより,多引数関数を間接的に表現できる.
一方で,Java,Python,Lisp等々,その他多くの言語は多引数関数を備えており,また,コンパイラにとってさらに重要なことには,多くのハードウェアも多引数関数を効率良く実行するための何らかの仕組みを備えている.そこで,この実験のMiniMLコンパイラでは,ハードウェア上の仕組みと直接対応する関数呼出しを表現できるよう,閉じた正規形以降のすべての中間表現に多引数関数を含めることにする.
簡単な多引数関数の例を,minimlc -v
の表示形式を用いて以下に示す.
let rec add (x, y) = x + y in
add (1, 2)
関数定義のパラメータリストはともかく,関数適用式の実引数リストが組(を生成する式)とまったく同じ表現であるのは一見紛らわしく思われるかも知れないが,実際には正規形への変換以降では関数適用の実引数は「値」しかありえないため,混乱が生じることはない.
上記2つの機能追加を除き,閉じた正規形は前章の正規形とまったく同じである.対応するOCamlデータ型を以下に示す(正規形のデータ型との差分のみ抜粋.配布コードのclosure.ml
中ですでに定義されている):
type cexp =
...
| AppExp of value * value list (* NEW *)
| TupleExp of value list (* NEW *)
| ...
and exp =
...
| LetRecExp of id * id list * exp * exp (* NEW *)
| ...
なお,後の章を読むと分かるように,MiniMLコンパイラが実際に扱う関数の引数の数は0個あるいは2個しかあり得ないのだが,ここで任意個に一般化したとしても実装の複雑さはほとんど同じである.