ブートストラップ問題

ブートストラップ問題 (Bootstrap problem) は、コンパイラをコンパイル対象のプログラミング言語で作成した際に、そのコンパイラの最初のコンパイルをどうするかといった場合を典型的な例とする、いわゆる「鶏と卵」の形をしたセルフホスティング環境の問題を指す。これを解決するための方式をブートストラップ方式といい、この問題を何とかして最初の完備した環境を作ることをブートストラッピングという。

名前についてはブートストラップの記事を参照。

種類

言語 X のコンパイラを言語 X で書く場合、次のような対処法がある。

• 言語 X のインタプリタかコンパイラを言語 Y で実装する。ニクラウス・ヴィルトは、最初のPascalコンパイラをFORTRANで書いたとされている。
• X の別のインタプリタかコンパイラが言語 Y で既に書かれて存在している。これはSchemeでしばしば用いられる手法である。
• X のサブセットのコンパイラをまず用意し、その X のサブセットで X のコンパイラを書く。Javaを拡張した言語のコンパイラの幾つかやHaskellコンパイラの幾つか、最初のFree Pascalコンパイラはこの方式で作成されている。
• X のコンパイラが既に存在するプラットフォーム上で、別のプラットフォームのオブジェクトコードを生成する X のコンパイラをコンパイルし、クロスコンパイラとする。そのクロスコンパイラでコンパイラをコンパイルすれば、ターゲットのプラットフォーム上で動作するコンパイラが得られる。C言語コンパイラを別のプラットフォームに移植する際にこの方式が採用される。
• X のインタプリタが実装されている場合に、そのインタプリタ上で X のコンパイラを実行し、 X のコンパイラ自身をコンパイルする。UCSD PascalのP-Codeで書かれたトランクコンパイラの場合がこれに相当する。トランクコンパイラは、オブジェクトコード生成部がコメントとなっている場合があり、その場合にはコンパイル前にターゲットマシンに合わせたものに書き換える必要がある。
• X で書かれたコンパイラのソースの最初のコンパイルは、人手により「ハンドコンパイル」する。ドナルド・クヌースは、文芸的プログラミングシステム WEB でこの方式を採用した。

コンパイラをソースコード形式で配布する場合、同時に移植の容易なバイトコード版のコンパイラを提供し、コンパイラ自身のコンパイルができるようにする（一例）。

経緯

ブートストラップがおこなわれた最初の実装はNELIAC（ALGOLの一種）であった。商用の実装ではPL/Iの実装が最初である。

今日の言語処理系では、C言語のようなシステム記述に向いた基本的な言語処理系の実装などは、その言語自身で書かれることが多いため、全く手掛かりのない環境ではブートストラッピングが必要になることがある（大抵の環境では、バイナリディストリビューションやクロスコンパイルを利用して回避できるので、難しいプロセスは回避できる）。以下に幾つかの実装が行っているブートストラッピングの方法を示す。

• OCaml: OCamlで書かれているネイティブコードコンパイラは、ソースだけでなくバイトコードも配布している
• Glasgow Haskell Compiler: Haskellで書かれているので、中間言語としてC言語を使うオプションを利用した、Cコンパイラでコンパイルできるコードを、ブートストラッピング用に配布している

また、パーサジェネレータなど、言語処理系の実装に際して、プログラムを生成するプログラムを使っている場合も、似たような再帰的依存関係の問題がある。