わかるUNIXの歴史第 4 回 ／ 中間コードという発明

Linux の産室・MINIX。その MINIX 自身は、何がコンパイルしたのか

MINIXとACK ── 中間コードという発明 第2回で Linux の産室だった MINIX。それを作ったのは、Tanenbaum 製の ACK というコンパイラでした。gcc とは違う思想 ── EM という中間コードを真ん中に挟む。この一手が、移植とブートストラップを一変させます。

必要な道具：第1回（再実装の木）・第3回（gcc） 種明かし：真ん中を挟めば、M×N が M+N になる

第2回で、Linux は MINIX という産室で生まれたと見ました。では ── その MINIX 自身は、何がコンパイルしたのか。答えは ACK（Amsterdam Compiler Kit）。Tanenbaum らが作った、gcc とはまた別の系統のコンパイラです。今回はさかのぼりを少し休めて、ACK が体現する「中間コードを挟む」という大発明を味わいます。これは移植を劇的に楽にし、しかも第6回の BCPL の O-code、さらには現代の LLVM IR や WebAssembly まで貫く、コンパイラ史の背骨のひとつです。

01MINIX ── 教科書の付録として生まれたUnix

MINIX は1987年、Tanenbaum が教科書『Operating Systems: Design and Implementation』の付録として作った、教育用のUnix風OSです。カーネル・メモリ管理・ファイルシステムで約12,000行。学生が丸ごと読める大きさに抑え、設計はマイクロカーネル（第1回の論争の主役）。第1回の言葉でいえば、再実装の木の一枚 ── AT&T のコードは1行も使わず、Unixらしさだけを白紙から書いたものでした。

02MINIXを作ったのは、ACK

その MINIX を実際にコンパイルしていたのが ACK。Tanenbaum と Ceriel Jacobs が作った、1980年代初頭としては先進的なretargetable（機種を差し替えられる）コンパイラ群です。ACK の特徴は、扱える言語が一つではないこと ── C・Pascal・Modula-2・Occam・BASIC のフロントエンドを持っていました。

ACK の中身（三段構え）

フロントエンド（言語ごと）→ EM（中間バイトコード）→ 汎用オプティマイザ → バックエンド（機種ごと）→ 機械語。

肝は真ん中の EM。どの言語のフロントエンドも、いったん EM という共通の中間コードに落とす。あとはそれを機種ごとのバックエンドが機械語へ翻訳する。gcc の内部中間表現と似ていますが、EM は「ハードウェアでも実装できる実在の抽象機械の言語」として設計された点が個性です。

03なぜ真ん中を挟むのか ── M×N 問題

中間コードのありがたみは、数を数えるといっぺんに分かります。M 個の言語を N 種類の機種で動かしたい。素朴にやると、言語と機種の全組み合わせぶんのコンパイラが要る ── M×N 個。ところが真ん中に共通の中間コードを置けば、必要なのはM 個のフロントエンド ＋ N 個のバックエンド ＝ M+N 個で済む。下の図で、M と N を増やして、線の数がどれだけ違うか見てください。

図1：M×N 問題。上＝素朴（言語×機種で M×N 個のコンパイラ）。下＝中間コードを挟む（M+N 個で済む）。M・N を増やすほど差が開く
今回の急所 ── 「1回だけ翻訳、あとは使い回す」

中間コードは、第0回の「1回だけ着火」の言語版です。言語の知識はフロントエンドに1回だけ、機種の知識はバックエンドに1回だけ書けばいい。両者は EM を介してだけ会話するので、互いを知らなくてよい。関心事を真ん中で切り離すことで、掛け算だった手間が足し算になる。

◇ ◇ ◇

04種明かし ── 中間コードは、移植とブートストラップの逃げ道

M+N のありがたみが最大化するのは、新しい機種に移すときです。中間コードが無ければ、新機種のために M 個のコンパイラを全部書き直す。中間コードがあれば ── バックエンド（あるいは EM を動かす小さな核）を1つ書くだけで、既存の全言語がその機種で動きだす。下の図で、新機種を1台足してみてください。

図2：新機種への移植。EM の核（バックエンド／インタプリタ）を1つ用意するだけで、既存の全フロントエンドの資産が一気にその機種で使えるようになる
新機種（灰）にはまだ何も動かない。「EM の核」を1つ移植すると、C・Pascal・Modula-2… 全部が一気に動きだす。
ブートストラップに効く理由

まっさらな新機種を立ち上げるとき（第3回の宿題）、素朴には「コンパイラをどう持ち込むか」で詰まります。中間コードなら、EM を動かす小さな核を1つ移植すれば、EM で配られたコンパイラ資産がまるごと動く。大きな塔を、小さな土台1つで支える。第0回「輪は外から一度だけ持ち上げる」の、持ち上げ方をうんと軽くする工夫です。

05中間コードという一族 ── O-code から WASM まで

「真ん中に共通の中間コードを置く」という発想は、ACK の専売ではありません。むしろコンパイラ史を貫く大河です。次回以降でさかのぼる BCPL の O-code（第6回）は、この考えのずっと古い先祖。そして現代の LLVM IR（clang の中間表現）、JVM バイトコード、WebAssembly は、みな同じ血を引く子孫です。ACK の EM は、その大河の途中にある、美しく分かりやすい一里塚でした。

つなぐ声 ── こずえで葉を交換する（第1回の続き） ACK は長く MINIX 純正のコンパイラでしたが、後年 MINIX 3 は、ユーザーランドを血統の木側の NetBSD から取り込み、システムコンパイラを clang に切り替えました。第1回で予告した「再実装の木が、こずえで血統の木から葉を借りる」実例です。ACK 自身も2003年に BSD ライセンスでオープンソース化され、いまも読める古典になっています。
正直な線 ── 中間コードは“楽にする”が“無くしはしない”

(1) ACK 自身もプログラムであり、動かすにはコンパイラが要ります ── 中間コードは鶏と卵を消しません。移植や再利用を劇的に楽にするだけで、「最初の種」はやはりどこかから持ち込む必要がある（第3回の宿題は生きたまま）。(2) 「M+N」は概念上の数え方で、実際には汎用オプティマイザや実行時ライブラリなど別の部品もあります。線の本数は理想化した目安です。

(3) MINIX と ACK の関係も、バージョンや配布物で細部が異なります（初期は限定的なCコンパイラ、後年は他のコンパイラも移植・利用可能に）。ここでは「純正の中核ツールチェーンが ACK だった」という骨格を語っています。(4) 「EM はハードウェアで実装できる」は設計思想の主張で、実際に広く実装されたという意味ではありません。

練習問題（今回の話だけで解けます）
  1. 言語5種・機種4種を素朴に全部作ると何個のコンパイラが要るか。中間コードを挟むと何個か。
    答えを見る
    素朴：5×4＝20個。中間コードあり：5＋4＝9個（フロントエンド5＋バックエンド4）。
  2. 中間コード方式で、新しい機種を1台増やすと、追加で作るものは何か。
    答えを見る
    その機種向けのバックエンド（EM を動かす核）を1つだけ。既存の全フロントエンド＝全言語が、それだけで新機種に対応する。
  3. 中間コードは「鶏と卵」を解決するか。
    答えを見る
    しない。移植・再利用を大幅に楽にするだけで、最初にコンパイラ（種）をどこかから持ち込む必要は残る。第3回の着火の問題は消えない。
  4. ACK の EM と血のつながる“子孫”を1つ挙げよ。
    答えを見る
    例：BCPL の O-code（先祖）、LLVM IR、JVM バイトコード、WebAssembly。いずれも「真ん中に共通の中間コードを置く」同じ発想。

まとめ真ん中を挟めば、掛け算が足し算になる

Linux の産室・MINIX（1987, Tanenbaum, 約12,000行, マイクロカーネル, 再実装の木の一枚）をコンパイルしていたのは ACK。C・Pascal・Modula-2… を扱う retargetable なコンパイラで、肝は真ん中の中間コード EM。フロントエンド（言語ごと）→ EM → バックエンド（機種ごと）と三段に切り離すことで、素朴なら M×N 個要るコンパイラが M+N 個で済む。

真価は移植で出る。新機種には EM の核を1つ足すだけで全言語が動く ── 大きな塔を小さな土台で支える、ブートストラップの軽量化だ。ただし中間コードは鶏と卵を楽にするだけで消しはしない（種はやはり持ち込む）。この「真ん中に中間コードを置く」発想は、第6回の O-code を先祖に、LLVM IR や WebAssembly まで続く大河だった。── さて寄り道はここまで。次回はいよいよ、着火装置 cc の祖先、最初の C コンパイラの誕生へ降ります。

この文書は「わかるUNIXの歴史」シリーズ第4回です。史実：MINIX は Andrew S. Tanenbaum（Albert S. Woodhull の協力）が教科書『Operating Systems: Design and Implementation』（Prentice Hall, 1987）のために作った教育用の Unix 風OSで、カーネル・メモリ管理・ファイルシステムの要約された約12,000行のCソースが書籍に収録された。マイクロカーネル設計で、AT&T UNIX のコードを継承しない独立実装。ACK（Amsterdam Compiler Kit）は Andrew Tanenbaum と Ceriel Jacobs による retargetable なコンパイラ群で、C・Pascal・Modula-2・Occam・BASIC のフロントエンドを持ち、EM と呼ばれる中間バイトコードを介してフロントエンド／バックエンドを分離する。1980年代初頭に複数言語・複数機種を狙った初期の移植性コンパイル系として知られる。MINIX 3（3.2.0）でユーザーランドが NetBSD 由来のものに置き換わり、システムコンパイラが Clang になった。ACK は2003年に BSD ライセンスでオープンソース化された。中間コードを介する設計は BCPL の O-code（第6回）、LLVM IR、JVM バイトコード、WebAssembly などにも通じる。「M+N」の数え方は理想化した概念上のもので、実際には最適化器や実行時部品など追加の要素がある。 ── 印刷する場合はブラウザの「印刷」から「PDF に保存」を（印刷版では図の操作と解答は静止／非表示になります）。

印刷 / PDF 化：⌘+P（Windows は Ctrl+P）。画面では図1のスライダーで M×N と M+N の差を、図2のボタンで新機種への移植を試せます。「答えを見る」で解答が開きます。