翻訳するプログラムと実行するプログラム

一言でいうと

コンパイラーは、プログラムを実行せずに別の言語のプログラムに移すプログラムで、インタプリターは、プログラムを読みながらすぐに実行するプログラムです。2つは同じ前段(文字をトークンに、トークンを木に、木の意味を検査)を共有し、最後の「今計算するのか、あとで計算するコードを残すのか」で分かれます。

なぜ必要なのか

CPUはx = (a + 1) * 2を読めません。読めるのは、add、imulのような命令とレジスター番号だけです。人が書きやすい文章と、機械が実行できる命令の間の距離を、誰かが埋める必要がありますが、埋める時点が2つあります。

実行する前に一度(コンパイラー)。翻訳に時間はかかりますが、翻訳した結果は何度でも速く動きます。エラーのかなりの部分(存在しない変数、合わない型、括弧の対応)を、ユーザーがプログラムを実行する前に見つけられます。
実行しながら毎回(インタプリター)。翻訳を待たずにすぐ動きますが、同じ行を100万回実行すれば100万回解釈します。その代わり、実装が単純で、実行中の状態をのぞきやすくなります。

実務では、この2つは混ざっています。Pythonは、ソースをバイトコードにコンパイルしてから(__pycache__の.pyc)、そのバイトコードをインタプリットします。Javaは、javacがバイトコードを作り、JVMが最初はインタプリットして、よく動くメソッドだけを機械語にコンパイルします(JIT)。そのため、「この言語はコンパイル言語か」より「どの段階をいつ行うのか」のほうが、正確な問いです。

どう動くのか

コンパイラーは1つの塊ではなく、段階の列です。前の段階の出力が次の段階の入力になり、このコースのモジュールも、その列をそのままたどります。

소스 글자 ──렉서──▶ 토큰 ──파서──▶ 트리(AST) ──의미 분석──▶ 검사된 트리
   (2모듈)            (3모듈)              (4모듈)
                                              │
            ┌─────────────────────────────────┼──────────────────────────┐
            ▼                                 ▼                          ▼
     트리를 걸으며 실행               바이트코드 + 스택 VM        중간 표현 → 최적화 → x86-64
        (5모듈)                            (6모듈)                  (7·8·9모듈)

gccも、同じ列をいくつかのプログラムに分けて実行します。普段はgcc hello.cの1行に隠れて見えませんが、オプションで段階ごとに止められます。

止めるオプション	行ったこと	出力
`-E`	プリプロセス: `#include`を展開し、`#define`を置き換えます	`.i`(まだC)
`-S`	コンパイル: Cをアセンブリにします	`.s`(テキスト)
`-c`	アセンブル: アセンブリを機械語にします	`.o`(再配置可能オブジェクトファイル)
(なし)	リンク: オブジェクトファイルとライブラリをつなぎ合わせます	実行ファイル

オブジェクトファイルには、まだアドレスが決まっていない名前が残ります。hello.oが呼ぶprintfはlibcにあるので、nm hello.oはその名前の前にU(undefined)を出力します。リンカーがその空欄を埋めます。リンク段階でだけ出るエラー(「undefined reference to …」)が別にある理由が、これです。コンパイルはファイル1つだけを見て、リンクはすべてを見ます。

インタプリターとコンパイラーが同じ意味を守っているかも、別に確認する必要があります。このラボの計算機は、除算をCのように0の方向へ切り捨てます(-7 / 2は-3)。Pythonの//は下へ切り下げるので(-4)、インタプリターをPythonで書きながら//を使うと、同じプログラムが、インタプリターとコンパイルした実行ファイルで違う答えを出します。2つの実装の意味が同じかどうかは、自然には守られず、実行して突き合わせてはじめてわかります。このコースの採点ツールが、ほとんどのステップで、基準実装とランダムな入力で突き合わせる理由も同じです。

現場での姿

ビルドは通るのにリンクできません。ヘッダー(#include)は宣言しか与えないので、コンパイルは通り、定義が入ったライブラリをリンク行に入れ忘れると、undefined referenceが出ます。上の表のどの段階で出たかがわかれば、直す場所(ソースか、ビルド設定か)がすぐに分かれます。
「Pythonはインタプリター言語なので遅い」。遅い理由は、コンパイルをしていないからではなく、バイトコードの命令1つ1つが、型を実行中に確認するからです。PyPyやJVMのように、実行中によく動く箇所を再コンパイル(JIT)すると、同じソースが数十倍速くなることもあります。
CIのビルドキャッシュでは、コンパイルがファイル単位で終わり、リンクが別にあるので、変更されたファイルだけを再コンパイルして、リンクだけをやり直す増分ビルドが可能です。

このコースを通して作る言語は「ミニ」です。64ビット整数と真偽値、let・print・if・while・fn・return、そして優先順位のある演算子20個ほどがすべてです。小さいですが、レキサーからx86-64コードまで1本につなげて見るには十分で、すべての段階を、採点ツールが実際に実行して確かめられます。

次のラボですること

/opt/fixtures/mini/c/hello.cをgccで段階ごとに止めて4つの出力ファイルを作り、nmでオブジェクトファイルの空欄を見ます。そのあと、RPN計算機をrpn.py1つに、2通りで作ります。トークンに切って、スタックですぐに計算するインタプリター、実行せずにスタックの深さだけをたどるチェッカー、同じ計算をするCを書いてgccで焼くコンパイラーです。最後に、2つの道が同じ答えを出すかを、ランダムなプログラムで突き合わせ、どちらがいつ速いかを測ります。