Loading article…
コンピュータサイエンスにおいて、ブートストラップとは、コンパイル対象のソースプログラミング言語で書かれたコンパイラ（またはアセンブラ）である自己コンパイルコンパイラを作成するための手法である。コンパイラ（ブートストラップコンパイラ）の最初のコアバージョンは、別の言語（アセンブリ言語の場合もある）で生成され、その後のコンパイラの拡張バージョンは、この言語の最小限のサブセットを使用して開発される。自己コンパイルコンパイラをコンパイルする問題は、コンパイラ設計における鶏が先か卵が先か問題と呼ばれており、ブートストラップはこの問題の解決策である。[1] [2]
ブートストラップは、プログラミング言語を作成するときによく行われる手法です。BASIC、ALGOL、C、C#、D、Pascal、PL / I 、 Haskell 、 Modula - 2 、 Oberon 、 OCaml 、 Common Lisp、Scheme、Go、Java、Elixir、Rust、Python、Scala、Nim、Eiffel、TypeScript、Vala、Zigなどのコンパイラを含め、多くのプログラミング言語のコンパイラがブートストラップされています。
プロセス
典型的なブートストラッププロセスは3段階または4段階で機能します。[3] [4] [5]
- ステージ 0:ブートストラップ コンパイラが動作する環境を準備します。ここでは、ブートストラップ コンパイラのソース言語と出力言語を選択します。"ベア マシン" (どの言語のコンパイラも存在しないマシン) の場合、ソースと出力はバイナリマシン コードとして記述されるか、ターゲット以外のマシンでクロス コンパイルすることによって作成されます。それ以外の場合、ブートストラップ コンパイラは、ターゲット マシンに存在するプログラミング言語の 1 つで記述され、そのコンパイラは、高水準プログラミング言語、アセンブリ言語、オブジェクト ファイル、さらにはマシン コードなど、ターゲットで実行できるものを生成します。
- ステージ 1: ブートストラップ コンパイラが作成されます。このコンパイラは、独自のソースをターゲット マシンで実行できるプログラムに変換するのに十分です。この時点で、以降のすべての開発はブートストラップ コンパイラによって定義された言語を使用して行われ、ステージ 2 が開始されます。
- ステージ 2: ブートストラップ コンパイラによって完全なコンパイラが生成されます。これは通常、必要に応じて段階的に行われます。たとえば、言語のバージョン X のコンパイラはバージョン X+1 の機能をコンパイルできますが、そのコンパイラは実際にはそれらの機能を使用しません。このコンパイラがテストされ、自身をコンパイルできるようになると、バージョン X+1 の機能がコンパイラの以降のリリースで使用できるようになります。
- ステージ 3: ステージ 2 のフル コンパイラによってフル コンパイラが生成されます。さらに機能を追加する場合は、ステージ 2 で作業を再開し、現在のステージ 3 のフル コンパイラがブートストラップ コンパイラに置き換えられます。
フルコンパイラは2回ビルドされ、2つのステージの出力を比較します。出力結果が異なる場合は、ブートストラップまたはフルコンパイラのいずれかにバグが含まれています。[3]
利点
コンパイラのブートストラップには次のような利点がある: [6]
- これはコンパイルされる言語の重要なテストであり、一種のドッグフーディングです。
- コンパイラ開発者とバグ報告者は、コンパイルされる言語のみを知っていればよいのです。
- コンパイラ開発は、コンパイルされる高級言語で実行できます。
- コンパイラのバックエンドの改善により、汎用プログラムだけでなくコンパイラ自体も改善されます。
- 独自のオブジェクト コードを再現できる必要があるため、包括的な一貫性チェックになります。
これらのポイントのいくつかは、言語ランタイムも同じ言語で記述されていることを前提としていることに注意してください。
方法
言語 X で記述された言語 X 用のコンパイラをコンパイルする必要がある場合、最初のコンパイラをどのようにコンパイルするかという問題があります。実際に使用されるさまざまな方法は次のとおりです。
- 言語Xのインタプリタまたはコンパイラを言語Yで実装する。ニクラウス・ヴィルトは、最初のPascalコンパイラをFortranで書いたと報告した。[7]
- X 用の別のインタープリタまたはコンパイラは、すでに別の言語 Y で書かれています。Schemeは多くの場合、このようにしてブートストラップされます。
- 以前のバージョンのコンパイラは、他のコンパイラが存在する X のサブセットで書かれていました。これは、Java、Haskell、および初期のFree Pascalコンパイラのいくつかのスーパーセットがブートストラップされる方法です。
- 非標準の言語拡張機能またはオプションの言語機能をサポートするコンパイラは、それらの拡張機能や機能を使用せずに記述できるため、同じ基本言語をサポートしながらも拡張機能と機能のセットが異なる別のコンパイラでコンパイルできます。C ++コンパイラclangの主要部分は、 g++とMicrosoft Visual C++の両方でコンパイルできる C++ のサブセットで記述されています。高度な機能は、いくつかの GCC 拡張機能を使用して記述されています。
- X 用のコンパイラは、X 用のコンパイラが存在する別のアーキテクチャからクロスコンパイルされます。これは、 C用のコンパイラが他のプラットフォームに移植される一般的な方法です。また、これは、最初のブートストラップ後のFree Pascalで使用される方法です。
- X でコンパイラを作成し、ソースから手動でコンパイルし (おそらく最適化されていない方法で)、それをコード上で実行して最適化されたコンパイラを取得します。Donald Knuth はこれをWEB リテラシー プログラミングシステムに使用しました。
コンパイラをソースコードで配布する方法には、コンパイラのポータブルなバイトコード版を提供することがあり、これによりコンパイラをコンパイルするプロセスを自ら起動することができる。Tダイアグラムは、こうしたコンパイラのブートストラップ手法を説明するために使用される表記法である。 [6]場合によっては、ソフトウェアがほとんどまたはまったくインストールされていないシステム上で複雑なコンパイラを実行する最も便利な方法は、ますます洗練された一連のアセンブラとコンパイラを使用することである。[8]
歴史
アセンブラは、自身をブートストラップする最初の言語ツールでした。
このようなブートストラップを提供する最初の高級言語は、 1958 年のNELIACでした。これを最初に広く使用した言語は、 1961 年のBurroughs B5000 Algol と1962 年の LISPでした。
1962年、ハートとレビンはMITでLISPでLISPコンパイラを書き、既存のLISPインタープリタ内でテストしました。コンパイラが独自のソースコードをコンパイルできるレベルまで改良されると、コンパイラは自己ホスティング可能になりました。[9]
標準コンパイラ テープ上に存在するコンパイラは、コンパイラのS 式定義をインタープリタを介して自身で動作させることによって取得されたマシン言語プログラムです。
— AIメモ39 [9]
この手法は、コンパイルする言語と同じ言語のインタープリタがすでに存在する場合にのみ可能です。これは、プログラムを入力として実行するという概念を直接借用したもので、ライスの定理を使用した停止問題が決定不可能であることの証明のバリエーションなど、理論計算機科学のさまざまな証明でも使用されています。
現在の取り組み
Trusting Trust Attack（コンパイラが悪意を持って改変され、コンパイルするプログラムに隠れたバックドアが仕込まれたり、悪意のある改変がコンパイラ自体の将来のバージョンでさらに複製され、不信の永続的なサイクルが生み出される）やバイナリの信頼性に対するさまざまな攻撃に関するセキュリティ上の懸念から、複数のプロジェクトが、ソースからのブートストラップの労力を軽減するだけでなく、ソースと実行ファイルが対応していることを誰もが検証できるように取り組んでいます。これには、Bootstrappable buildsプロジェクト[10]やReproducible buildsプロジェクト[11]が含まれます。
参照
参考文献
- ^ Reynolds, John H. (2003 年 12 月)。「マシン X からマシン Y への自己コンパイル コンパイラのブートストラップ」。CCSC: 東部カンファレンス。Journal of Computing Sciences in Colleges。19 (2): 175–181。コンパイルする言語で記述されたコンパイラというアイデアは、古くからある「鶏が先か卵が先か」という
難問を思い起こさせます。最初のものはどこから来るのでしょうか。
- ^ Glück, Robert (2012)。「部分評価器からのコンパイラ ジェネレータのブートストラップ」。Clarke, Edmund、Virbitskaite, Irina、Voronkov, Andrei (編)。システム情報学の展望: 第 8 回国際 Andrei Ershov 記念会議、PSI 2011、ロシア、ノボシビルスク、2011 年 6月27 日～7 月 1 日、改訂選書。コンピュータ サイエンスの講義ノート。第 7162 巻。Springer。pp. 125～141。doi :10.1007/978-3-642-29709-0_13。ISBN 978-3-642-29708-3.
始める際には、コンパイラ構築でおなじみの鶏が先か卵が先かという問題が出てきます。コンパイラをブートストラップするにはコンパイラが必要であり、コンパイラ ジェネレーターのブートストラップも例外ではありません。
- ^ ab 「GCC のインストール: ビルド」。GNUプロジェクト - フリーソフトウェア財団 (FSF)。
- ^ 「rust-lang/rust: bootstrap」。GitHub。
- ^ 「高度なビルド構成 — LLVM 10 ドキュメント」。llvm.org。
- ^ ab Patrick D. Terry (1997)。「3. コンパイラの構築とブートストラップ」。コンパイラとコンパイラジェネレータ: C++ 入門。International Thomson Computer Press。ISBN 1-85032-298-82009年11月23日時点のオリジナルよりアーカイブ。
- ^ Wirth, Niklaus (2021-02-22). 「50 years of Pascal」. Communications of the ACM . 64 (3). Association for Computing Machinery (ACM): 39–41. doi :10.1145/3447525. ISSN 0001-0782. S2CID 231991096.
- ^ Edmund Grimley-Evans (2003-04-23). 「シンプルなコンパイラをゼロからブートストラップする」. homepage.ntlworld.com . 2010-03-03 にオリジナルからアーカイブ。
- ^ ab Tim Hart および Mike Levin。「AI Memo 39-The new compilation」(PDF)。2020 年 12 月 13 日時点のオリジナル(PDF)からアーカイブ。2008年 5 月 23 日閲覧。
- ^ 「ブートストラップ可能なビルド」。bootstrappable.org。
- ^ 「再現可能なビルド — ソースからバイナリ コードまでの独立検証可能なパスを作成する一連のソフトウェア開発プラクティス」。reproducible-builds.org。