8-3. ミニOCamlからASEC機械へのコンパイル

Dowek & Levy の教科書に掲載されているコンパイル方式では、補助関数として以下のものを使っているので、まず、それを実装する。関数 position は、変数名xと、変数名のリスト venv が与えられたとき、 x が venv の何番目の要素であるかを計算する関数である。ここで、1番目に現れるとき 0 を返し、一般に venvの N番目の要素であったとき、N-1を返すものとする。 x が venv に現れない時はエラーとし、 x が venv に2回以上出現するときは、最初の出現についての値を返す。

たとえば (position "a" ["b"; "a"; "c"; "a"]) は、1を返す。

position の具体的な実装は以下の通りである。

  let rec position (x : string) (venv : string list) : int =
    match venv with
      | [] -> failwith "no matching variable in environment"
      | y::venv2 -> if x=y then 0 else (position x venv2) + 1

いよいよコンパイラの本体である。まず、Dowek & Levy の教科書のコンパイル方式を引用する。

48ページ (下の方に、変換の定義あり)
49ページ (上の方に、変換の定義の続きあり)
いずれも、 Dowek & Levy, "Introduction to the Theory of Programming Languages", 2011 の4章から引用

これから上記の変換(Compilation of PCF)の定義を解読しよう。

全体として、|M|_e の形に対する定義である。ここで、Mは式 (実装上は、exp 型のデータとして表されるもの)である。また、右下にある e は変数の列(実装上は、変数名のリスト)である。 |M|_e の定義の右辺は、ASEC機械の命令列である。結局、M というミニOCamlプログラムを、ASEC機械の命令列にどう変換(コンパイル)するかを定義したものである。 (e の初期値は空リストであり、定義の途中で補助的に使う。)
最初は、e を無視して、|M| の定義だと思って読んでみよう。 eを無視しても、変数の取扱いを除いてはだいたいは理解できるのではないだろうか。
たとえば、6行目の |t+u|_e は、 (1) u の計算に対応する命令列, (2) その結果をスタックに積む Push命令, (3) t の計算に対応する命令列、 (4)　その結果とスタックトップの値を足す Add命令、の4つから構成されている。
2行目は |t u| という形の式、つまり、関数適用の形の式をどう変換するかである。右辺の全体は、 Pushenv ... Popenv の形になっている。これは、関数適用の式を処理するためには、現在の環境をスタックに保存し、関数適用の処理が終わったら、再びスタックから取り戻すことを意味する。なぜ「取り戻す」操作がいるかといえば、関数適用の最中に let式の処理などのために、環境が変化する可能性があるためである。 Pushenv と Popenv の間の命令列は、(1) まず引数 u の計算に対応する命令例 |u|_e 、 (2) 次に引数u の計算結果(この瞬間は Accumulator にある)をスタックに積む Push命令、 (3) 関数部分の t の計算に対応する命令列 |t|_e、 (4) 最後に、Accumulator にある値(関数部分t の計算結果)を、スタックトップにある値(引数uの計算結果)に適用する Apply命令、という4つの部分から構成されている。
次に、e の役割を考える。これは、具体例で考えるとよい。たとえば、let x=1 in let y=2 in x+y という式を変換してみると、 (計算を始めるとき、e は空リストとする)
```
  |let x=1 in let y=2 in x+y|_空
= Pushenv, |1|_空, Extend, |let y=2 in x+y|_x, Popenv
= Pushenv, Ldi 1, Extend, Pushenv, |2|_x, Extend, |x+y|_(x,y), Popenv, Popenv
```
となる。ここで、x+y という式の変換のときの e が (x,y) になっていることに注目してほしい。(ここで (x,y) と書いたが、かっこはグルーピングの目的のためにつけた記号であり、無意味である。) これは、x+y という式を変換するとき、束縛変数(実行時の環境に格納される変数たち)は、 x と y であること、また、x が1番目で、y が2番目であることを表している。そこで、x+y の中の x を変換するときは、Search 0 に変換され、 y を変換するときは、Search 1 となる。(1番目が0, 2番目が1である。) よって、
```
  |let x=1 in let y=2 in x+y|_空
= Pushenv, Ldi 1, Extend, Pushenv, Ldi 2, Extend, Search 0, Push, Search 1, Add, Popenv, Popenv
```
となる。このように、変数が(実行時の)環境の中の何番目に格納されているかを調べる目的のため、|M|_e の e を使ったのである。
let式以外でも、fun と fixfun において、変数が束縛されるので、e の部分が増加している。ただし、fixfun は、ミニOCaml言語にはないが、再帰関数を導入する構文であり、以下の等式を満たす。
```
    (letrec f x = e1 in e2)  === (let f = (fixfun f x -> e1) in e2)
```
fun の場合は、変数列 e の途中に _ (underscore)という謎の変数名が出てきている。これは、「決して使われることのない変数名」を意味する。こんなことをする理由は以下の通り。 ASEC機械では、「再帰しない関数のクロージャ」というデータ構造は持たず、「再帰関数のクロージャ」1つで両方を兼用している。そこで、再帰しない無名関数の場合も、「再帰関数の名前」に相当する部分に、何か変数名を置く必要がある。これは、実際には fun で構成される無名関数なので、この「変数名」は決して使われることはないので、ダミーの _ という変数名としている。なお、このダミーの変数をいれないと、計算が狂ってしまうので必ずいれること。
最後に、式M を変換(コンパイル)したいときは e を空リストとして |M|_e の計算を行なう。 (eの初期値は空リストである。)

上記教科書49ページの上から5行目以降に、具体的な変換結果が記載されている。

実装にあたっての補足

上記の変換を実装するためには、教科書に記載の数学的な表記を、 OCamlのプログラムとして表現しなければいけない。このためには、ある程度の作業が必要である。以下に注意点を述べる。

束縛変数の列 x,y などは OCaml のリストで表すが、そこで大事な注意が1つある。 ASEC機械の説明で述べたように、 let x = 1 in let y = 2 in x + y という式の x+y の部分の実行時の環境は、 [("y",2); ("x", 1)] というように、内側で束縛される変数がリストの先頭に来る。そこで、コンパイラにおける変数列も、 ["y"; "x"] というリスト(Dowekらの教科書の表記とは逆の順番) で表現すべきである。たとえば、49ページ1行目の |let x=t in u|_e の定義の右辺において、 |u|_e,x と書いてあるが、この e,x は実装上は x::e とする(リストe の先頭に x を追加する)のが良い。同様に、fixfun の定義の右辺で |t|_e,f,x とある部分も、x::(f::e) というように逆順にすべきである。
命令列も、命令のリストという形で実現するが、これは教科書通りの順番とする。つまり、先に実行すべき命令が先頭にあるリストである。また、本実験では、個々の命令名の頭に I_ をつけた。たとえば、let x=1 in let y=2 in x+y という式をコンパイルすると、
```
 [I_Pushenv; I_Ldi 1; I_Extend; I_Pushenv; I_Ldi 2; I_Extend; I_Search 0; I_Push; 
  I_Search 1; I_Add; I_Popenv; I_Popenv]
```
となる。
上記教科書では、対象言語がPCFであり、ミニOCamlに似ているが少し違う。たとえば、真理値定数(true, false)がない、 if-then-else式のかわりに、ifz-then-else式がはいっているなど。なお、ifz n then e1 else e2 は、 if z=0 then e1 else e2の意味である。また、上記教科書のコンパイラのターゲット言語の Test は、本実験の I_Test と少し違う。 Test は「Accumulator にある値が 0 か 0でない整数値かを判定して分岐する」命令だが、 I_Test は「Accumulator にある値が true か false かを判定して分岐する」命令である。
letrec の処理は教科書には書いていないので自分で考えないといけないが、 let と fixfun の組合せで表現できる(表現方法は上記で述べた)ことを使えばよい。

課題 8-3.

上記の説明を参考にして、ミニOCaml言語から ASEC機械の機械語へのコンパイラを実装しなさい。
コンパイラが正しく変換できていることを示す例を与えて実行しなさい。
また、変換されたコードを、ASEC機械の実装にかけて実行し、正しい答えが返ってくるかを試しなさい。

発展課題 [2012/10/19追加]

上記コンパイラは、「ミニOCaml言語からASEC機械への変換」はきちんとやってくれるが、素朴なものであるので、「インタープリタより高速に実行されるコードへの変換」については、不満足なものである。そこで、様々な工夫について考察し、実装に取り組んでもらいたい。

定数の伝搬: let x = 10 in x+x+x といった式を let x = 10 in 10+10+10 といった式に変換するものである。なお、同じようでも、xの値が定数でないときは変換しない。たとえば、 let x = (f 10) in x+x+x といった式を let x = 10 in (f 10)+(f 10)+(f 10) といった式には変換しない。これは、 (1)　そもそも (f 10) の計算に時間がかかるようなら、上記の変換は実行速度を低下させる、 (2) ミニOCaml に「純粋でない」機構を加えたら、この変換がプログラムの意味を変えしてしまうことがある(危険である)、という理由による。
関数のインライン化 (inlining): インライン化とは、 let f x = e1 in e2 の形で、e2 の中で (f e3) の形で呼び出されているとき、この式を e1[e3/x] という式に置き換えることである。ただし、e3 は定数や関数など、いわゆる「値」を表す式とする。 (e3 が「計算」を表す式であるときは、上記の定数伝搬のときに書いたことと同じ事情により、インライン化をしない。)
ここで e1[e3/x] は、式e1の中の x (の自由な出現)に、式e3を代入して得られる式のことであり、以下の例を参照されたい。
```
インライン化前
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    g 10
gのインライン化後
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    (f 10) * 10
fのインライン化後
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    (10 + y) * 10
```
なお、f を先にインライン化するときには、注意しなければならい。つまり、単純に、
```
fのインライン化後(誤り)
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (x + y) * y in
    g 10
```
とやってしまうと誤りになるからで、この場合は、y の変数名を変更して、
```
fのインライン化後(誤り)
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y1 -> (x + y) * y1 in
    g 10
```
としなければならない。
インライン化のもう1つの注意として、(当然だが)再帰関数は、インライン化しても消えないので、単純にやると無限にインライン化してしまうことになる、ということがある。(従って、通常、再帰関数はインライン化しない。)
その他の効率化: コンパイラでおこなわれる効率化には様々なものがあるので、各自、工夫してもらいたい。(コンパイラの教科書を見て、それを実装してみるのは面白くない。自分で苦労して高速化のための工夫を試行錯誤せよ。)

トップ, 前へ

亀山幸義