ブートストラップ問題

ブートストラップ問題とは

ブートストラップ問題（Bootstrap problem）は、コンピュータ科学、特にプログラミング言語の処理系開発において発生する、「鶏と卵」にも例えられる再帰的な依存関係の問題を指します。最も典型的なのは、コンパイラを、そのコンパイラ自身が処理対象とするプログラミング言語で記述した場合に直面する困難です。

例えば、新しいプログラミング言語Xを開発し、その言語Xで書かれたコンパイラを作成したとします。この言語Xのコンパイラを実行するためには、当然ながら言語Xのコンパイラが必要です。しかし、そのコンパイラ自体が言語Xで書かれているため、最初にそのソースコードを機械が理解できる形式に変換する（コンパイルする）には、別の言語Xのコンパイラが必要になる、という状況に陥ります。

このような、自身で自身を処理する環境（セルフホスティング環境）の最初の起動や構築に関する問題を、ブートストラップ問題と呼びます。そして、この困難を乗り越え、何とかして最初の完全に機能する環境、特に最初のコンパイラやインタプリタを構築するプロセス全体を「ブートストラッピング」と呼びます。

名称については、靴紐（bootstraps）を持って自身を持ち上げるという、物理的には不可能な行為に由来するとされており、自力で環境を立ち上げる困難さを比喩的に表現しています。

ブートストラッピングの主な手法

自身で自身をコンパイルする必要があるようなブートストラップ問題を解決するために、いくつかの確立された手法が存在します。以下にその主なものを挙げます。

別の言語で最初の処理系を作成する:
目的とする言語Xのコンパイラやインタプリタのごく基本的なバージョンを、既に利用可能な別の言語（例えば、FORTRAN、C、アセンブリ言語など）で記述します。ニクラウス・ヴィルトが最初のPascalコンパイラをFORTRANで書いたのはこの手法の典型例です。この最初の処理系を用いて、言語Xで書かれた本格的なコンパイラのソースコードをコンパイルします。

既存の処理系を利用する:
目的とする言語Xのインタプリタやコンパイラが、たとえ別の言語で書かれたものであっても、既にどこかに存在する場合は、それを利用して言語Xで書かれたコンパイラ自身をコンパイルできます。これはSchemeなどの言語処理系でしばしば用いられるアプローチです。

言語のサブセットを利用する:
まずは、目的の言語Xの機能の小さな部分（サブセット）のみを扱えるコンパイラを作成します。このサブセットコンパイラは、既存の別の言語で書くか、ハンドコンパイルなどの手法で作成します。次に、このサブセットコンパイラを使って、言語X全体の機能を備えたコンパイラ自身を、言語Xのサブセットの範囲で記述・コンパイルしていきます。例えば、Javaの拡張言語や初期のFree Pascal、一部のHaskellコンパイラなどで採用された方法です。

クロスコンパイルを利用する:
言語Xのコンパイラが既に利用可能な環境（ホスト環境）で、開発対象の異なる環境（ターゲット環境）向けの実行コードを生成する言語Xのコンパイラ、すなわちクロスコンパイラを構築します。ホスト環境でこのクロスコンパイラをコンパイルし、次にこのクロスコンパイラを用いて、ターゲット環境で動作する言語Xのコンパイラ自身のソースコードをコンパイルします。これにより、ターゲット環境用のコンパイラが得られます。新しいアーキテクチャにC言語コンパイラを移植する際によく用いられる手法です。

インタプリタ上でコンパイルを実行する:
目的とする言語Xのソースコードを直接実行できるインタプリタが存在する場合、そのインタプリタ上で、言語Xで書かれたコンパイラのソースコードを実行し、コンパイル処理を行わせることができます。UCSD PascalのP-Codeベースのシステムにおけるトランクコンパイラ（特定の機能がコメント化されている基本的なコンパイラ）を、インタプリタ上で動作させて利用するケースなどがこれに該当します。

ハンドコンパイル:
極めて原始的な方法ですが、言語Xで書かれたコンパイラのソースコードを、開発者自身が手作業で解釈し、ターゲットとなる機械語や中間コードに変換していく手法です。ドナルド・クヌースが文芸的プログラミングシステムWEBの開発初期に用いたことで知られています。

* 移植用バイナリの提供:
コンパイラをソースコードとして配布する際に、移植が比較的容易な中間形式（バイトコードなど）で表現されたコンパイラ自身の実行可能形式を同時に配布する方法です。これにより、利用者はまずこの中間形式のコンパイラを実行し、その上で本格的なネイティブコードコンパイラを自身の手元の環境でビルドできます。OCamlなどがこの方式を採用しています（OCamlはネイティブコードコンパイラのソースとバイトコード版を配布しています）。

歴史と現代

ブートストラッピングが行われた最初の著名な実装の一つは、ALGOLの方言であるNELIACでした。商用ソフトウェアとしては、初期のPL/I|PL_Iの実装がブートストラップ手法を用いた例として挙げられます。

現代の言語処理系、特にC言語のように低レベルなシステム記述に適した言語では、処理系自体がその言語自身で書かれていることが一般的です。そのため、全く新しい環境でゼロから開発を行う際には、ブートストラッピングが必要になる場合があります。しかし、多くの場合、既にあるプラットフォームのバイナリディストリビューションを利用したり、より開発が進んだ環境でクロスコンパイルを行ったりすることで、ブートストラップの複雑なプロセスを回避することが可能です。

現代の有名な例としては、前述のOCamlや、Haskellで書かれているGlasgow Haskell Compiler (GHC) があります。GHCは、ブートストラッピングのために、中間言語としてC言語コードを生成するオプションを利用し、既存のCコンパイラでコンパイル可能なブートストラップ用コードを提供しています。

言語処理系の開発に関連して、パーサジェネレータのように、プログラムを生成するプログラム自体を開発する場合にも、似たような再帰的な依存関係の問題が生じることがあります。

もう一度検索