| Edit this page | Report an issue |
中身の説明に入る前に，ソース言語を再確認しよう．ソース言語はMiniML4のうち，関数定義はトップレベルのみで行うことに制限した言語である．先にも述べた通り，このサブセットを MiniML4- と呼ぶ．（この制限は関数閉包を作らなくともプログラムを実行できるために講義の時間の都合上設けている制限である．実行時に関数閉包が作られうるようなプログラムをアセンブリ言語に落とすには，クロージャ変換 (closure conversion) と呼ばれるプログラム変換を途中で行うなどして，関数がトップレベルで定義される形にプログラムを変換する必要がある．この変換を講義中で扱う時間がないので，ソース言語の方を制限しちゃうのである．興味のある者はMinCaml コンパイラを参照のこと．）構文は以下のように定義される．
\[\begin{array}{rcl} P &::=& (\{d_1,\dots,d_n\},e)\\ d &::=& \mathbf{let}\ \mathbf{rec}\ f\ =\ \mathbf{fun}\ x \rightarrow e\\ e &::=& x \mid n \mid \mathbf{true} \mid \mathbf{false} \mid e_1\ \mathit{op}\ e_2 \mid \mathbf{if}\ e\ \mathbf{then}\ e_1\ \mathbf{else}\ e_2 \mid \mathbf{let}\ x = e_1\ \mathbf{in}\ e_2 \mid e_1 \; e_2\\ \mathit{op} &::=& {+} \mid {*} \mid {<}\\ \end{array}\]ここで，$P$，$d$, $e$，$\mathit{op}$はそれぞれプログラム，再帰関数定義，式，二項演算子を表すメタ変数とする．また，$x,y,f,g$ を変数を表すメタ変数とする．以前も述べたが，メタ変数とは，言語のある要素を表すものとしてあらかじめ定められた記号である．例えば上記のBNFでは$P$は「プログラム」を表すメタ変数として，$e$は「式」を表すメタ変数として定めておくわけである．このようにすると，いちいち「$e_1$と$e_2$はそれぞれ式であり．．．」と断ることなく，単に式$e_1+e_2$と書いただけである形の式を表すことができるわけである．
この制限された言語では，プログラム（$P$）は関数定義の集合（${d_1,\dots,d_n}$）とプログラム開始時に評価されるメインの式（$e$）とからなる．各関数定義は，相互再帰が可能であるものとする．また，各関数定義の中で定義されている関数の名前は他のどの場所でも現れない名前であるものとする．式の構文からは$\mathbf{let}\ \mathbf{rec}$式と$\mathbf{fun}$式が除かれていることに注意されたい．
これからソースプログラムをいくつかの中間言語を経由してMIPSアセンブリまで変換する．ソース言語とMIPSアセンブリの大きな差異の一つは，ソース言語においては，式を評価したときにどのような順序でどのような計算が起こるかが必ずしも明示されていない，すなわち式の評価でどのような 制御 (control) が行われるかが明示されていないということがある．例えば，式((x + 1) * 2) + (3 + 1)を考えよう．この式を評価する際には
xの値を取り出し，1を加え，2を乗じ，その値を覚えておき，3 + 1を評価して4を得て，4を覚えておいた値に加える
という計算が起こるはずである．（なお，この説明では$e_1 + e_2$や$e_1 * e_2$という式の評価が「$e_1$が初めに評価され，$e_2$が続いて評価され，最後にそれぞれの評価結果を用いて足し算や掛け算が行われる」と定義されていることを仮定している．式の評価をどのように定義するか（あるいは定義しないか）は言語による．）ターゲット言語であるMIPSアセンブリでは，このような計算順序に関する情報（もう少し正確に言えば，各計算ステップで得られた値が次にどのような計算で用いられるのかに関する情報）を逐一指定しなければならない．したがって，ソース言語をMIPSアセンブリに変換する過程では，計算順序に関する情報を明示化する必要がある．元の式が仮に以下のように書いてあれば，計算順序が明示化されている感じがしないだろうか．let t1 = x + 1 in
let t2 = t1 * 2 in
let t3 = 3 + 1 in
let t4 = t2 + t3 in
t4
このプログラムでは，元のプログラム中のすべての部分式の評価結果にletで何らかの変数が束縛されており，かつ各部分式の評価結果がその後どのような計算でどのように用いられるかが明示されている．
言語$\mathcal{C}$は，すべての部分式の評価結果に何らかの変数が束縛されることを強制した関数型言語である．文法は以下の通りである． \(\begin{array}{rcl} P &::=& (\{d_1,\dots,d_n\},e)\\ d &::=& \mathbf{let}\ \mathbf{rec}\ f = \mathbf{fun}\ x \rightarrow e\\ v &::=& x \mid n \mid \mathbf{true} \mid \mathbf{false}\\ e &::=& x \mid n \mid \mathbf{true} \mid \mathbf{false} \mid v_1\ \mathit{op}\ v_2 \mid \mathbf{if}\ v\ \mathbf{then}\ e_1\ \mathbf{else}\ e_2 \mid \mathbf{let}\ x = e_1\ \mathbf{in}\ e_2 \mid x_1 \; x_2\\ \mathit{op} &::=& {+} \mid {*} \mid {<}\\ \end{array}\)
メタ変数$v$は変数，整数定数，真偽定数を表すメタ変数である．式$e$の文法がソース言語のそれと少し変わっており，二項演算子の引数，$\mathbf{if}$式の条件部分，関数適用式の関数部分と引数部分には（式ではなく）変数か値しか取れないようになっている．これにより，先に挙げた式((x + 1) * 2) + (3 + 1)のような，引数部分に変数でも値でもない式3+1を取ることはできないようになっており，すべての部分式に名前をつけ，評価順序を明示することを強制している．