- Dozerは、より初期のブートストラップ段階でRustを使えるようにすることを目指す純粋CベースのRustコンパイラで、C++・flex・yacc・Makefileを使わずに書かれている
- 公式コンパイラ rustc はRustで書かれており、以前のバージョンのrustcで新しいバージョンをビルドする。この連鎖は、OCamlで書かれた初期RustコンパイラとGuile・Cの層にまでさかのぼる
- Bootstrappable BuildsのLinuxブートストラップは 512バイトのバイナリシード から始まり、単純なコンパイラ、シェル、Cサブセット、TinyCC、yacc、coreutils、Bash、autotools、GCC、Linuxへと拡張されていく
- 現在Rustは、C++で書かれた mrustc を通じてrustc 1.56をコンパイルする後半の段階で登場するため、C++導入前の段階ではRustを使いにくい
- Dozerは TinyCCでブートストラップ可能なRustコンパイラ を目標としており、その後
libcore、rustcのCraneliftバックエンド、cargo代替ツール、canonical rustc/cargoの再ビルドへとつなげることを目指している
Dozerの目標と制約
- Dozer は 純粋なC で開発中のRustコンパイラ
- C++を使わず、
flex、yacc、Makefileも使用しない
- 中核目標は、Rustを Cからブートストラップ できるコンパイラを作ること
- 特に TinyCC でブートストラップ可能である必要があり、システムにはCコンパイラとごく基本的なシェル以外に有用なツールがないことを前提としている
Rustコンパイラが自分自身をビルドする問題
- Rustコードを実行するにはコンパイルが必要で、一般に
cargo build は内部で rustc を呼び出す
- rustc自体も Rustで書かれたRustコンパイラ なので、新しいrustcは以前のバージョンのrustcでコンパイルされる
- rustc 1.80.0は rustc 1.79.0 でコンパイルされる
- この連鎖は rustc 1.78.0 など、さらに古いバージョンへと続く
- 初期段階は Rust 0.7 までさかのぼり、この時点のコンパイラは OCaml で書かれていた
- OCamlコンパイラも必要なため、ブートストラップの連鎖はさらに別の言語実装へとつながる
Bootstrappable Buildsの下位チェーン
- Bootstrappable Builds は、小さなバイナリシードからシステム全体をブートストラップする流れを扱う
- Linux bootstrap process は 512バイトのバイナリシード から始まる
- このシードには、16進数を受け取って対応する生バイトを出力する、非常に単純なコンパイラが含まれる
- コメントと空白を除いた16進バイト列も、技術的には解析可能なソースコードとして扱われる
- その後の段階では、より高水準のツールを段階的にビルドしていく
- 非常に単純なオペレーティングシステム
- 基本的なシェル
- もう少し発展したコンパイラ
- アセンブリコードのように見える段階
- 非常に基本的なCサブセット
- そのCサブセットで書かれた、より発展したCコンパイラ
- 数段階後には TinyCC をコンパイルでき、その後
yacc、基本的なcoreutils、Bash、autotools、GCC、Linuxへと続く
- 各段階は live-bootstrap parts.rst に列挙されている
Rustの登場がブートストラップチェーンでは遅すぎる
- 現在、Rustはこのプロセスのかなり後半で登場する
- 使われている実装は mrustc で、C++で書かれた代替Rust実装 である
- mrustcは rustc 1.56 をコンパイルでき、その後の現代的なRustコードのコンパイルへとつなげられる
- ただし、C++がブートストラップチェーンに導入される時点では、ブートストラップは実質的にほぼ完了している
- C++導入前の段階でRustを使うには、Cからブートストラップ可能なRustコンパイラ が必要になる
Dozerの現在の実装状況
- Dozerは約2か月にわたって開発されており、拡張なしで書かれている
- 現在、TinyCC と cproc の両方で問題なくコンパイルできる
- バックエンドには QBE を使用している
- 実装はまだ初期段階
- レキサ は完成している
- パーサはかなりの部分が実装されている
- マクロ/モジュール拡張は可能な限り後回しにしている
- 型検査は現在
i32 のみをサポートしている
- コード生成はまだ粗い状態
- 現在、次のRustコードを正常にコンパイルできる
fn rust_main() -> i32 {
(2 - 1) * 6 + 3
}
rustcまでつなげる計画
- Dozerを段階的に発展させ、基本的な
libc 利用例をコンパイルし、その後 libcore、rustc までコンパイルすることを目標としている
- rustcのコンパイルには Cranelift バックエンドを使う予定
- CraneliftバックエンドはすべてRustで書かれている
- C++がない前提のため、LLVMはコンパイルできない
- DozerでRustパッケージをコンパイルできる cargo代替ツール も作る計画
- rustcソース中の自動生成ファイルを見つけて除去する必要がある
- Bootstrappableプロジェクトの規則では、自動生成コードは許可されない
- 最終目標は、rustcと
cargo をコンパイルした後、自分でコンパイルしたrustc/cargo で canonical rustc/cargo を再コンパイルするプロセスを作ること
- このプロジェクトはこれまで引き受けた中で最も難しい作業であり、完成できるか疑わしくても挑戦を続けるという立場だ
1件のコメント
Hacker News の意見
Rust をブートストラップするなら、Rust 全体より機能の少ない proto-Rust を C で作り、その proto-Rust で完全な Rust コンパイラを書くと思う
たとえば proto-Rust には借用チェッカがなく、マクロ対応は限定的か存在せず、メモリを解放しないかもしれず、良いコードを生成する必要もない
実質的には Rust 構文を持つ C に近いだろうが、Rust 愛好家の立場からすると、このプロジェクトが目指す「C 構文の C」で Rust コンパイラを書くよりは良さそうに見える
なぜこの経路を選ばなかったのか気になる
借用チェッカを取り除いても正しいプログラムは壊れず、不正なプログラムが大量にコンパイル可能になるだけ
mrustc の主な用途は rustc をコンパイルすることで、rustc が借用チェックのエラーなしに自分自身をコンパイルできることはすでに分かっているので問題ない
Scala コンパイラが非効率なコードを作るため、その後、本物のコンパイラを自分自身で再コンパイルする
こうすると最終的に、良いコードを生成する効率的な本物のコンパイラが得られ、この過程は言語の標準ビルドに含まれている
https://github.com/mozart/mozart2
趣味で Rust で C コンパイラを作っていて、Rust は C より当然重いという冗談で Small C Compiler と呼んでいる。「Tiny C Compiler」のパロディ
バックエンドには Cranelift を使っているが、コンパイラ全体の構造は多くの trait で差し替えられ、ハックしやすいように作っている
printf("%s", "Hello World!")を処理できる程度に動くまでは、オープンソースとして公開するつもりはないプリプロセッサとパーサを実装しようとしていて、悪名高い typedef 問題のために rust-peg と HimeCC にも関わった
業界では typedef の文脈を保つためにシンボルテーブルを使うことは知っているが、下の方の型を読めないという限界があった。学術的な解法が何なのか気になっていて、思いつくのはトランザクションメモリくらい
役に立つものがあれば、結局公開することになりそう
後に James Hendrix がこれを、より完全な実装を載せた本へと拡張した。子どもの頃に CompUSA の割引ワゴンでこの本を見つけたおかげで C を学ぶことになり、今でもその本を持っている
https://archive.org/details/dr_dobbs_journal_vol_05_201803/p...
https://www.amazon.com/Small-Compiler-Language-Theory-Design...
本当に素晴らしいが、興味深いのは同じ種類の ブートストラップ問題 がハードウェアにもあること
コンピュータは何が作るのか？ 以前に作られたコンピュータと、その上で動くソフトウェアが作る。考えれば考えるほど興味深い
数か月前、建設プロジェクト向け資材配送／フルフィルメントを手がけるスタートアップで働く人に会った
こうした仕事には Amazon のような一般配送とは違う専門性が必要で、資材が特殊だったり危険な物性を持つことが多いだけでなく、配送先にまだ住所がない場合もよくあるため
解決は可能だが、現代の配送業者の一般的な能力を超える専門性が必要に見える
理由は、欧州企業と協業する中で、規制当局にバックドアがないことを証明するためだった
非常に興味深いがとても難しい問題で、私たちのチームは間接的にしか関わっていなかったものの、すべてのデータを監査可能にし、送ってはいけないものを送らないよう保証するプロキシを通してデータを渡す作業をしていた
完了する前に会社を去り、後で難しすぎるという理由で廃止されたと聞いた
その後 x86 が巨大な予算や大口購入者なしに登場し、可能な限り効率的で高密度になるようアセンブリを設計した
その結果、他のマシンでは容易に持てていた特性を失うことになった
理論上は、個別部品だけで非常に単純なコンピュータを自作できる
大きく、非効率で、ものすごく遅いだろうが、特定の命令セットアーキテクチャに従わせることはでき、その上でブートストラッププログラムをビルドできる
そうすれば、完全に理解可能な出来の悪いコンピュータから得た結果が、完全には信頼していない現代のハードウェアで得た結果と同じだと主張できる
一種のブートストラップ問題だ。たとえば現在の石油埋蔵地は 100 年前より採掘が難しいが、そこまで再びブートストラップできるのか気になる
ブートストラップの利点を説明する高レベルの根拠を探すのにリンクを4回もたどらなければならず、少しイライラした
タイトルの「Why」の部分がそれを扱ってくれると期待していた
https://bootstrappable.org/benefits.html
セキュリティは大きな理由であり、bootstrappable チームが主に強調している点でもある
trusting trust 問題や最近の xz バックドアのような攻撃を避けるには、すべてを純粋なソースコードからブートストラップできなければならない
彼らは、手で書かれて監査可能なものだけに依存するよう、事前生成ファイルまで全部削除している。たとえば Python のブートストラップは、ソースに Python スクリプトが生成したコードが入っているため、かなり複雑になる
私はむしろ文化保存の側面により関心がある。Arctic World Archive のような場所に現代のメディアを未来の考古学者のために保存したいが、解読する方法がなければ意味がない
仕様を保存することはできるが、彼らが x265 と必要なものすべてをゼロから実装してくれるとは期待できない。バイナリを保存すれば、千年前のハードウェアを動かすか、千年前の CPU を仮想化しなければならない
単純な Lisp の定義と、その上で動くコードを渡すこともできるが、いったい誰が基本的な Lisp で x265 を実装するのか。現実的ではない
そこで私のプロジェクトでは単純な仮想マシンを作り、その上に C をブートストラップした
現在のアーキテクチャだけでなく、未来や地球外のアーキテクチャにも非常に簡単に移植できる。未来の考古学者や地球外文明は 1 日で VM を実装し、その上で C ブートストラップを走らせてから ffmpeg などをコンパイルし、私たちのメディアを解読できる
ブラックボックスはなく、すべてデバッグ可能で監査可能な、オープンな手書きソースコードだ
https://github.com/ludocode/onramp?tab=readme-ov-file#why-bo...
https://en.wikipedia.org/wiki/Arctic_World_Archive
少し混乱している。記事の途中になってようやく、タイトルにある旅を始めた理由が出てくるが、要点は C++ がブートストラップチェーンに入ってくる時点では実質的にブートストラップは終わっているので、その前に Rust を使いたくても方法がない、ということだ
だから C、具体的にはまだ有用なツールがないと仮定したシステムで、TinyCC からブートストラップ可能な Rust コンパイラがあるとよい、という趣旨に見える
しかし前半の前提と矛盾している。rustc は 1.80.0 が 1.79.0 で、1.79.0 が 1.78.0 でコンパイルされるという形で 0.7 までさかのぼり、その時点のコンパイラは OCaml で書かれていた
また、Guile で OCaml コンパイラをコンパイルすることに成功しているプロジェクトがあり、Guile インタプリタは C で書かれているとも述べていた
そうであれば、著者が望む C++ なしの経路はすでに存在することになり、単に rustc チームが日常的に使っている経路ではないだけだ
結局、動機が明確ではない。より良い C ベースのブートストラップ過程を作りたいのか、それを rustc の日常的なブートストラップ方式にしたいのか、なぜ C++ の段階をなくしたいのか、なぜ C の段階を好むのかが分からない
単にやりたいからやっているのなら問題ないが、かなり長い記事を読んでも、それ以外の目的はよく分からなかった
各段階に数時間ずつかかり、1.80 は 1.79 を、1.79 は 1.78 を要求する、という具合なので 0.7 までどの段階も飛ばせない
完全に自動化しても、このブートストラップには数か月かかる可能性がある
さらに初期の rustc バージョンは LLVM だけを出力していたはずなので、いずれにせよ LLVM をコンパイルするには C++ コンパイラをブートストラップする必要がある
C++ コンパイラがあるなら、単に mrustc をコンパイルすればよい。現在の mrustc は rustc 1.54 までしかサポートしていないため、それでも約35個のバージョンを経てコンパイルしなければならない
この全過程は実用的ではない。Dozer の目標は、小さな C コンパイラをブートストラップし、Dozer をコンパイルした後、最新の rustc を直接コンパイルすることだ
そうすれば C++ や中間段階をブートストラップせずに、すぐ Rust を得られる
GCC 4 と binutils を元のビルドスクリプトから切り離せるなら、リストの半分くらいは削れる気がする
そこにある項目のかなりの数は、autoconf 系とその依存関係を繰り返し再ビルドしているだけだ
https://github.com/fosslinux/live-bootstrap/blob/master/part...
要点がよく分からない。対象マシンで動く新しいバイナリを作るには、rustc が対象アーキテクチャをサポートしていなければならない
そのサポートを rustc に追加したのなら、単に rustc に自分自身をビルドさせればよい
ときどき Scheme で C++ インタプリタやコンパイラを書くことを想像する
Scheme から直接現在の GCC へ行けるなら、ものすごい近道になり得る
ただ、一般的には C++ コンパイラを書くのはほぼ不可能に近いと考えられている。それでも学習には役立ちそうだ
サブアセンブラからスタック全体を見ると、これは trusting trust 問題を回避する方法になり得るのだろうか？
https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
それでも https://en.m.wikipedia.org/wiki/Underhanded_C_Contest のようなものがあり、その一部の応募作は自分が監査していても見逃していた気がする
Cを少し学んでいたとき、人々がCでC++のようなことをどうやっているのか調べて、オブジェクト、例外、並行性のような実装を見た
mrustcがC++で書かれているなら、そうした C++風のCプリミティブ を使って、動作するC++コードをCへポートするほうが簡単かもしれないのでは？
C++とCの強い相互運用性を利用して、少しずつ移していく方法も可能に見える
もちろん、落とし穴の多い難しいポーティング作業だということは分かっている。ただし比較対象が、RustコンパイラをCで新たに書くことだという点は覚えておく必要がある
以前存在していたC++ to Cコンパイラも思い浮かぶ。まだあるのかは分からない
今日でもRust to C/C++や、C++から人間が読めるCへ変換するコンパイラは有用そうだ。一方の安全性の利点と、もう一方のツールエコシステムを組み合わせられるからだ