これは 言語実装のカレンダー | Advent Calendar 2024 - Qiita の1日目の記事です。
このカレンダーを読んでいる皆さんの中には、 「AI兵器」の衝撃 “機械は犠牲を理解できず” ウクライナの無人機 イスラエル軍は？暗い未来の不安 | NHK | WEB特集 | イスラエル など、 スカイネット の実現間近な近年の国際情勢から、 Collapse OSの作者と同様に 人類文明の崩壊を心配する方々がいるかと思います。 或いは激化する米中対立を背景に、外国産パソコンに仕込まれた ハードウェアレベルのバックドアの噂とか コンパイラに仕込まれた細工とシステムのセキュリティの話 とかを真に受けた上司の暴走で、 半導体の一切無い部屋に監禁されて 「バックドア汚染の心配の無い、コンパイラとハードウェアを作れ!」 という業務命令を受け、 Jeremiah Orians氏 の Stage0 Bootstrap for the Free Software をダウンロードしたは良いが、 ハードウェアを構築できずに挫折した経験をお持ちとか。 そうではなく単に技術的興味で、 命令セットの設計とそれに対応したアセンブラの作成に挑戦したい方々もいるかと。
当記事では、文明崩壊後にアセンブラのセルフホスティングを行なう手法として、 小さなバイナリサイズのフィルタプログラムを組み合わせるものを紹介します。 成果物は stage0risc からダウンロードできます。
文明崩壊後のハードウェア
まず必要なのは、文明崩壊後でも用意できるハードウェアですが。 実際にハードウェアを製作するのは大変なので、 当記事では、入出力が連続したバイト列のみの、 極めて単純な仕様のエミュレータで済ませます。 UNIX系OSでいうところの「標準入出力」のみです。 実際、コンピュータ産業など未だ存在しない黎明期のコンピュータの入出力は 穿孔テープ や テレタイプ端末 でしたから、同様にコンピュータ産業がもう存在しない文明崩壊後でも、 これらの入出力装置は製作できるでしょう。 冒頭で触れたJeremiah Orians氏のstage0を使ったことのある方々なら、 「プログラムはどうやって読み込ませるんだ?」 と疑問に思うかもしれません。 Orians氏のstage0では、標準入出力とは別に プログラムを読み込ませる装置を仮定しています。 対して当記事では、入力装置を節約するため、 ブートローダを焼いた書き換え不能なROMをコンピュータ起動時に使います。 このブートローダが、起動時に標準入力からプログラムを読み込みます。 読み込まれたプログラムが標準入力を用いる場合は、 読み込むデータをプログラムの直後にくっつけます。 これは先述の穿孔テープであれば、手作業で可能です。 ちなみに、冒頭でお知らせした成果物では、 テープの繋ぎ合わせ作業を現在の環境でエミュレーションするのに、 複数のファイルをつなぎ合わせるUnixコマンドの「cat」を使っています。
CPUについては、ハードウェアを新規に作るなら、3オペランドマシンより スタックマシン や 1オペランドマシン の方が部品点数などが少なく作り易いです。 とはいえ、1オペランドマシンといえども新規にCPUを作るのは大変なので、 まだ使える既存のCPUが残っているならそれらを使いたいところです。 が、それらの殆どはレジスタマシンです。 また、エミュレータを噛ませることで、当記事のバイナリがそのまま動き、 文明崩壊後の手間を軽減するだけでなく、 崩壊前の現在でのお試しもラクチンになります。 エミュレータ上での動作を前提にするなら、 Virtual Machine Showdown: Stack Versus Registers で明らかにされた様に、3オペランドが有利です。 なので当記事では、簡略化した3オペランドRISCのエミュレータを用います。
文明崩壊後のソフトウェア
初期のコンピュータでは、主記憶装置(メモリ)の容量が非常に限られていました。 日本初のコンピュータ FUJIC のメモリ容量は8415ビット(255ワード。ワード当たり33ビット。)。 1バイト当たり8ビットに換算すると、1052バイトに1ビット足りません。 文明崩壊後でも同様でしょう。 あるいは、現在で最も大量に生産されている、 すなわち文明崩壊後に最もサルベージし易いであろうコンピュータは、 1個当たりのお値段が数百円にも満たないワンチップマイコンですが。 それらに積まれているメモリ容量もキロバイト単位です。 なので、ソフトウェアの設計も、メモリをあまり必要としない方向で行きます。
まずは、 プログラミング言語Pascal に倣ってのワンパスコンパイル。 ソースコードを読み終える前にコンパイル結果を出力し始めれば、 出力した部分のソースコードや結果をメモリに残す必要が無くなります。 ただし、これを実現するためには、ソースコードの文法に様々な制限が掛かります。 アセンブラの場合は、 まだ読み込んでいない後方ラベルアドレスを使えなくなります。
そして、バイナリ生成とマクロ機能を別々のプログラムに分割します。
プログラムが小さければ、それを格納するのに必要なメモリも少なくて済みます。 また、プログラムの機能が少ないならば、 その機能を実現するのに必要なメモリも少なくて済みます。
製作し易さを最優先すべき文明崩壊後のアセンブラに、 マクロ機能は余計と思われるかもしれません。 しかし、Orians氏のstage0アセンブラでは、 英単語などの文字列「ニーモニック」で表された命令を 機械語ビット列に変換する処理を、 各ソースコード冒頭に追加するマクロ定義ファイルで行なっています。 このマクロ定義ファイルが肩代わりしているおかげで、 各ニーモニックに対応する機械語ビット列についての情報が stage0のアセンブラコードには不要となり、バイナリサイズの削減になります。 例によって、マクロ定義ファイルをソースコード冒頭に追加するのは、 穿孔テープであれば手作業で可能です。
結果、当記事の成果物であるstage0riscでは、 仮想マシンのメモリ量を1512バイトに設定しても、 アセンブラのセルフホスティングが出来ました。
分割した部分を置き換える
バイナリ生成とマクロ機能の分離には、 文明崩壊後のコンピューティング以外にも効能がありました。 それぞれの部分を別のプログラムに置き換えるのが簡単なことです。
stage0riscの開発当初は、 マクロ機能プログラムにはC言語プリプロセッサを使っていました。 成果物内のcheatsディレクトリ にその名残りのコードがあります。 あるいは逆に、 バイナリ生成プログラムだけ取り替えて マクロ機能プログラムを使い回すことが出来ます。 これを利用して、仮想マシンではなくx86実マシン上で セルフホスティングされたアセンブラを構築しました。 st0l86ディレクトリ にありますが、 セルフホスティング前にx86バイナリを構築するのに、 stage0risc仮想マシン用のマクロ機能プログラムを流用しています。
やり残したこと
当記事では低水準言語であるアセンブラを構築しましたが、 高水準言語なのに容易く実装できるものがあります。 バイナリサイズが小さいのであれば、 機械語手書きから言語処理系をブートストラップする のように、何らかのバイナリエディタに16進数の羅列を入力する方法が使えます。 小さいバイナリサイズといえば、 PC/AT互換機のマスターブートレコード(512バイト)に収まる処理系が幾つかあります。
ガベージコレクタ付きの処理系が512バイトでお釣りが来るなんて、 早過ぎか遅過ぎか分かりませんが、時代を間違えているのは確かでしょう。
にも拘らず当記事でアセンブラを取り上げたのは、当記事で取り上げたCPUが、 スタックマシンとかではなくレジスタマシンだからです。 高水準言語でその豊富なレジスタの恩恵を受けるには、 レジスタ割付が必要となり実装難度が大きく跳ね上がります。 アセンブラであれば、「人間コンパイラ」に最適化を任せることが出来ます。 エミュレータの性能だけでなく現在普及していることも合わせて、 当記事ではレジスタマシンを取り上げました。
しかしレジスタマシンと違ってスタックマシンには、 まだ十分に研究の進んでいない分野、"stack scheduling"があると私は感じます。 レジスタマシンとスタックマシンとの違いは、 各命令でのオペランドの指定方法が、固定したレジスタ番号なのか、 スタック先頭との相対位置なのか、でしかありません。 そして先に述べたように、 レジスタマシンの恩恵を得るためにはレジスタ割付が必要であり、 多くの研究者の努力によりその方法が確立されています。 しかしスタックマシンでは、レジスタマシンのレジスタ割付に当たる、 「スタック割付」があまり研究されていません。
- A Preliminary Exploration of Optimized Stack Code Generation
- Inter-Boundary Scheduling of Stack Operands: A preliminary Study
など、ないわけではないのですが。 レジスタマシンでのレジスタ間コピー命令(x86アセンブラのレジスタ間mov)に当たる、 スタックマシンでのスタック操作命令(dup,swap,rotなど)の削減には 至っていないようです。 レジスタ割付の主目的の一つがコピー命令の削減であることを考えると、 まだ研究の余地があるように私は感じます。 そして関数呼び出しは、コピー命令などで適切なレジスタ・スタックに 引数・返り値を配置しなければならない「0オペランド命令」であり、 多くのスタックマシンでの基本命令と同じです。 なので、stack schedulingは、 高度にリファクタリングされて関数呼び出しだらけのコードであっても、 スタックマシンの性能向上に寄与すると私は考えます。 絶対位置であるレジスタ番号でオペランドが指定されるレジスタマシンでは、 関数間での引数・返り値の場所が衝突するのを解決するのは簡単ではありません。 特に、引数などの配置方法が「呼び出し規約」として 同一位置に固定されている外部関数だと、 レジスタ割付で削減したはずのコピー命令を追加するしかありません。 スタックマシンであれば、 スタックポインタが変化すれば各命令オペランドの参照する位置も変わるため、 関数を呼び出す順番を並び替えてスタックポインタを操作することで、 スタック操作命令など追加の命令を用いずに 各関数の引数・返り値の衝突を減らせるかも知れません。 ならば、実行速度よりコード密度を重視し、 インライン化せずに関数呼び出しを多用するコードを使う用途であれば、 スタックマシンの方がレジスタマシンより優位になります。
なので、スタックマシンがあまり生産されない現在の状況が、 文明崩壊後まで続くという確信を私は持てません。 そうでなくてもコード密度の優位は、メモリの少ない文明崩壊後では重要です。 stack schedulingの確立を前提とするなら、 当記事の取り上げるべきCPUはスタックマシンであり。 スタックマシンならば、冒頭に述べたCollapse OSが そうした ように、アセンブラではなく、 一部のスタックマシンの低水準言語として実装されたこともある高水準言語 forth を検討しないわけにはいかなかったでしょう。
