講義テキスト5章のML言語にはfun
式がないため,(fun x -> x + 1) 2
のような式を書くことはできないが,代わりに,トップレベルのlet rec
式によって同じ関数を定義する次の等価な式:
let rec f = fun x -> x + 1 in
f 2
を書くことができる.
講義テキストのML言語(のサブセット)が,このようにトップレベルでしか関数を定義できないよう制限されている理由は,同じくfun
式やその評価結果であるところの関数値のような高級な機能を備えていないアセンブリ言語への変換が,明らかに簡単なためである.
一方,この実験では,講義で学んだ知識を基に,より現実的な関数型言語のためのコンパイル手法を身につけることも目的としているため,MiniML言語はfun
式やトップレベル以外のlet rec
式を含んでいる.
fun
式は存在しない. しかし,変換先のアセンブリ言語の機能は(MIPSとARMの些細な違いを除き)同じであるため,我々のコンパイラにおいても一連の変換のどこかの段階で「トップレベルのlet rec
式だけで関数を定義する表現」へと帰着させる必要がある.
上の簡単な例だけ考える限りでは,すべての関数定義をトップレベルのlet rec
式で行うようにプログラムを変換することはそれほど難しくなさそうである.
しかし,関数本体が自由変数を含んでいる場合,このように単純に書き換えることはできない.たとえば:
(fun x -> fun y -> x + y) 2 3
には2つのfun
式が含まれているが,先程と同様にしてトップレベルのlet rec
式に書き換えてみると:
let rec g = fun y -> x + y in
let rec f = fun x -> g in
f 2 3
となる.しかしながら,この変換後のコードでは,関数g
の本体中にスコープ外からの関数f
のパラメータx
への参照,つまり未定義変数の参照が含まれており正しくない.
変数束縛の入れ子構造に起因するこのような難しさを解決し,プログラム中の関数定義の位置を自由に動かせるようにするための変換が,この章で扱うクロージャ変換である.実際にすべての関数定義をトップレベルのlet rec
式へと置き換える作業については,後ろの平滑化で扱う.