ブートストラップ（コンパイラ）

コンピュータサイエンスにおいて、ブートストラップとは、自己コンパイルコンパイラ、つまりコンパイル対象となるソースプログラミング言語で書かれたコンパイラ（またはアセンブラ）を作成するための手法である。コンパイラの初期コアバージョン（ブートストラップコンパイラ）は別の言語（アセンブリ言語の場合もある）で生成され、その後、この言語の最小限のサブセットを用いてコンパイラの拡張バージョンが開発される。自己コンパイルコンパイラのコンパイル問題は、コンパイラ設計における「鶏が先か卵が先か問題」と呼ばれており、ブートストラップはこの問題の解決策の一つである。[ 1 ] [ 2 ]

ブートストラップは、プログラミング言語を作成する際によく用いられる手法です。ALGOL 、BASIC、C、Common Lisp、D、Eiffel、Elixir、Factor、Go、Haskell、Java、Modula-2、Nim、Oberon、OCaml、Pascal、PL/I、Python、Rust、Scala、Scheme、TypeScript、Vala、Zigなど、多くのプログラミング言語のコンパイラがブートストラップされています。

プロセス

典型的なブートストラッププロセスは3つまたは4つの段階で機能します。[ 3 ] [ 4 ] [ 5 ]

  • ステージ0：ブートストラップコンパイラが動作するための環境を準備します。ここでは、ブートストラップコンパイラのソース言語と出力言語を選択します。「ベアマシン」（どの言語のコンパイラも存在しないマシン）の場合、ソースと出力はバイナリマシンコードとして記述されるか、ターゲットマシン以外のマシンでクロスコンパイルすることによって作成されます。それ以外の場合、ブートストラップコンパイラはターゲットマシン上に存在するプログラミング言語のいずれかで記述され、そのコンパイラはターゲットマシンで実行可能なもの（高級プログラミング言語、アセンブリ言語、オブジェクトファイル、さらにはマシンコードなど）を生成します。
  • ステージ1：ブートストラップコンパイラが生成されます。このコンパイラは、自身のソースコードをターゲットマシンで実行可能なプログラムに変換できる程度に強力です。この時点で、以降の開発はすべてブートストラップコンパイラで定義された言語を用いて行われ、ステージ2が始まります。
  • ステージ2：ブートストラップコンパイラによって完全なコンパイラが生成されます。これは通常、必要に応じて段階的に行われます。例えば、言語のバージョンX用のコンパイラはバージョンX+1の機能をコンパイルできますが、実際にはそれらの機能を使用しません。このコンパイラがテストされ、自身でコンパイルできるようになると、バージョンX+1の機能はコンパイラの以降のリリースで使用できるようになります。
  • ステージ3：ステージ2のフルコンパイラによって完全なコンパイラが生成されます。さらに機能を追加する必要がある場合は、ステージ2から作業を再開し、現在のステージ3のフルコンパイラがブートストラップコンパイラに置き換えられます。

2つのステージの出力を比較するため、フルコンパイラは2回ビルドされます。出力結果が異なる場合、ブートストラップコンパイラまたはフルコンパイラのいずれかにバグが含まれています。[ 3 ]

方法

言語Xで書かれた言語X用のコンパイラをコンパイルする必要がある場合、最初のコンパイラをどのようにコンパイルするかという問題があります。実際には、以下のような様々な方法が用いられています。

コンパイラをソースコードで配布する方法の一つとして、コンパイラの移植可能なバイトコード版を提供することがあります。これは、コンパイラ自身をコンパイルするプロセスをブートストラップするものです。Tダイアグラムは、このようなコンパイラのブートストラップ手法を説明するために使用される記法です。[ 7 ]場合によっては、ソフトウェアがほとんどまたは全くインストールされていないシステム上で複雑なコンパイラを実行する最も便利な方法は、ますます洗練されたアセンブラとコンパイラを連続して使用することです。[ 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 ]が含まれます。

参照

参考文献

  1. ^ Reynolds, John H. (2003年12月). 「マシンXからマシンYへの自己コンパイルコンパイラのブートストラップ」 . CCSC: Eastern Conference. Journal of Computing Sciences in Colleges . 19 (2): 175– 181.コンパイルする言語で書かれたコンパイラというアイデアは、古くからある「鶏が先か卵が先か」という難問を想起させます。最初のものはどこから来るのでしょうか？
  2. ^ Glück, Robert (2012). 「部分評価器からのコンパイラ生成器のブートストラッピング」. Clarke, Edmund, Virbitskaite, Irina, Voronkov, Andrei (編).システム情報学の展望：第8回国際アンドレイ・エルショフ記念会議 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. 「はじめに」では、コンパイラ構築でおなじみの「鶏が先か卵が先か」という問題が提示されます。コンパイラをブートストラップするにはコンパイラが必要であり、コンパイラ ジェネレータのブートストラップも例外ではありません。
  3. ^ a b「GCCのインストール：ビルド」。GNUプロジェクト - フリーソフトウェア財団（FSF）。
  4. ^ "rust-lang/rust: bootstrap" . GitHub .
  5. ^ 「高度なビルド構成 — LLVM 10 ドキュメント」 . llvm.org .
  6. ^ Wirth, Niklaus (2021-02-22). 「Pascalの50周年」. Communications of the ACM . 64 (3). Association for Computing Machinery (ACM): 39– 41. doi : 10.1145/3447525 . ISSN 0001-0782 . S2CID 231991096 .  
  7. ^ Patrick D. Terry (1997). 「3. コンパイラの構築とブートストラップ」 .コンパイラとコンパイラジェネレータ：C++入門. International Thomson Computer Press. ISBN 1-85032-298-82009年11月23日時点のオリジナルよりアーカイブ。
  8. ^ Edmund Grimley-Evans (2003-04-23). 「シンプルなコンパイラをゼロからブートストラップする」 . homepage.ntlworld.com . 2010年3月3日時点のオリジナルよりアーカイブ。
  9. ^ a b Tim HartとMike Levin. 「AI Memo 39-The new compiler」（PDF） . 2017年7月6日時点のオリジナル（PDF）からアーカイブ。 2008年5月23日閲覧。
  10. ^ 「ブートストラップ可能なビルド」。bootstrappable.org 。
  11. ^ 「再現可能なビルド — ソースからバイナリコードまでの独立検証可能なパスを作成する一連のソフトウェア開発プラクティス」。reproducible - builds.org 。
「 https://en.wikipedia.org/w/index.php?title=ブートストラップ(コンパイラ)&oldid =1323208297」より取得