コンパイラのお仕事 その1

こんにちは、班長の竹井です。先週木曜の台風は大変でしたねぇ。僕の住む千葉では JR 京葉線やら地下鉄東西線まで止まったので、もはや陸の孤島、千葉共和国ってな状態でした。いずれにせよ午前中の授業は休講だったので、特に何もなかったですけど。それで、今日は少し、僕の担当しているコンパイラ係について少し紹介します。ちょっとマジメな記事になる予感。

そもそもコンパイラとは何かというと、人間が書いたコンピュータ プログラムを機械が理解できるデータに直すソフトのことです。たとえば、簡単な例でいえば、フィボナッチ数列の 10 番目を計算するプログラムを考えましょう。まずは C 言語で書いてみると、

x = 0, y = 1;
for (i = 0; i < 10; i++)
    z = x + y, x = y, y = z;

とかすれば、最終的にたぶん x に 10 番目 (11 かも？) のフィボナッチ数が入ります。ただし、このコード、コンピュータの頭脳である CPU では直接こんなものを解釈しているわけではないです。人間が書いているプログラムは高級言語と呼ばれていて、CPU が解釈できるような言語ではないのです。では、CPU が解釈するのはどのような言語かというと、だいたいこんな感じです:

    addu   $v0, $zero, $zero           # x = 0
    addiu  $t0, $zero, 1               # y = 1
    addiu  $t2, $zero, 10              # cnt = 10
fib:
    addu   $t1, $v0, $t0               # z = x + y
    addiu  $v0, $zero, $t0             # x = y
    addiu  $t0, $zero, $t1             # y = z
    addiu  $t2, $t2, -1                # cnt = cnt - 1

(わかる方のために注釈しておくと、今現在のところ班員の圧力でパタヘネをかなり参考にしているので、上のアセンブリは MIPS 準拠です) とりあえず、このような感じで、命令がずらっと並んだのがアセンブリと呼ばれている CPU が解釈できる言語です。このように、よりコンピュータが理解しやすい、裏を返すと人間様が使うような高度な機能がそぎ落とされている言語を低級言語と呼んでます。

それで、要はコンパイラは何をすればよいか大雑把にいうと、高級言語によって書かれたコンピュータ プログラムをもらって、それを CPU が理解できるような低級言語に直す、ただそれだけです。まぁそれだけといっても、だいぶいろんな処理があるんですけど。CPU 実験では、与えられる課題のプログラム コードは事前に配布されているので、そのコードを受け取って、自分たちの班で作る CPU が理解できるような機械語を吐くソフトを作ればいいことになります。

ちなみに、課題のコードは、O'Caml という言語で書かれています。だいたいこんな感じの調子です:

let rec newton x k =
    if abs_float (x *. x -. k) < 0.0001 then x
    else newton ((k /. x +. x) /. 2.) k
let sqrt x = newton 1.0 x

これは、ニュートン法という計算方法で、与えられた数の平方根を導出する関数 sqrt を定義しています。まぁ、こんな感じの O'Caml という言語のコンパイラを作る、っていうのがコンパイラ係の仕事ですね、結局のところ。