アセンブラを実装した前回の記事に続いて、 The Elements of Computing Systems にしたがって仮想マシンを実装した。その所感を本記事にまとめる。
以下でも述べるが、仮想マシンとはいっても VirtualBox のような代物ではない。より限定的な意味における仮想マシンであるし、実装も学習用のものにすぎない。異なる目的を持ってこの記事を訪れていただいた方は注意のこと！
TL;DR
レポジトリを作成して公開している
sato11/the-hack-vm-translator (https://github.com/sato11/the-hack-vm-translator)
利用するテクスト
The Elements of Computing Systems は Nand2Tetris という愛称でも親しまれている、コンピューター・サイエンスの著名な教科書である。
基礎回路の設計から初めて、論理演算、CPU設計、機械語、アセンブリ、コンパイラそしてOSと、演繹的な手順でコンピューターを実装する過程が演習として読者に与えられる。
コンピュータシステムにおける仮想マシンの位置付け
高級言語を機械語にコンパイルするにあたって、「直接機械語にコンパイルし、マシンに実行させる」というやり方が考えられるが、これではプラットフォームの数だけコンパイラを実装しなければならないことになる。
そこで、いちど中間コードにコンパイルした上で、機械語にコンパイルし直す方式を考える。簡単にいえば、中間コードをインターフェイスとして定義することで、モノリシックなアーキテクチャを二つの疎結合なプログラムに分離するわけだ。こうすることで、プラットフォーム間の移植にあたっても、コンパイラを丸ごと作り直すのではなく、中間コードのインタプリタだけを実装すれば良くなる。端的にいって、より手軽に移植可能になるわけである。
このようにして要請される、中間コードのインタプリタのことを仮想マシンと呼ぶ。このパラダイムは70年代に pascal 言語が切り拓いた領域で、90年代以後に Java と C# がおのおののコンパイル方式に採用したことで、揺るぎない影響力をもつようになったのだそう。
今回はテキストが提供する Hack と呼ばれる言語の仕様に沿って、その中間コードを実行する仮想マシンを実装した格好となる。
なぜ Go を選んだか
アセンブラの実装に Go を選択した前回の記事をもっぱら踏襲している。
Go でアセンブラを作ってみた - ﾕﾕﾕﾕﾕ (https://jnsato.hateblo.jp/entry/2020/09/22/230000)
実装
テキストの指示に従って、スタックで実装している。このスタックひとつのおかげで、ネストした関数の秩序正しい処理や、再帰呼び出しの制御が適切にコントロールできている。この魔法のような仕組みを実装を通して学べたのが最大の収穫である
実装の詳細についていうと、プログラムは構文解析を行う parser パッケージと、解析された構文からアセンブリを自動生成する codewriter パッケージの二つからなる。 parser については、もっぱら空白文字と改行文字だけを区切りとみなす仕様の明快さによって、簡単に処理系を作成することができる。
問題は codewriter によるアセンブリコード生成の自動化である。レジスタとメモリを操作するコードを泥臭く書いていくのだが、しょっちゅうアドレスを取り違えてはプログラムがクラッシュしたり、無限ループを脱出できなくなるなど、大変な目にあった。
デバッグするにも1クロックごとにハードウェアが何をどう実行しているのか愚直に調べるほか手掛かりを得られず、何度も心が折れそうになりながら実装していた。数百行におよぶ低レベルの生成コードを読んで、どこで何を間違えたのか探し当てようとする作業は、目隠しをされたまま終わりの見えないトンネルを進むような心地だった。これは人生で一番辛いデバッグ作業のひとつに数えても遜色ない。
無事追えられたことが奇跡のようにすら思える、それくらい苦しく、厳しい実装だった。もちろん、それを終えられた達成感も滅多に味わえない甘美なものである。
反省点
CodeWriter 構造体の設計
構造体に内部状態を保存するためにプロパティをどんどん追加してしまったのはあまり満足のいく実装ではない。 Go の作法としてもバッドプラクティスだろうと直感している。洗練度に欠ける設計ではあるが、アセンブリの生成に精力を奪われて、コードの良し悪しにまで気をはらう余裕を失ってしまっていたし、それをリライトする元気も最後には残らなかった。
冗長なボイラープレート
スタックに対する push/pop の操作をあちらこちらで頻繁にアセンブリで記述している。決まり切った表現と知りつつも、レジスタの状態に依存していつでも動作が狂いうる手前、DRY原則に沿って整理する勇気を持てなかった。
結果として、似たような記述が乱立しており、行儀のいいコードとは評価しがたいだろう。他方で、仮に似た記述を整理したとして、それによってかえって出力コードを予期しづらくなるだろうという思いもあった。実際、似た記述と思って一箇所にまとめた結果、あとから判明したバグによって、再度別のルーチンとして分離し直さなければならないような場面もあった。
要するに、実装途中の段階で早々にコードをまとめるよりも、最後まで実装してみることを優先した格好である。よりよい手法もあるのだろうが、個人的には、ボイラープレートを量産してでもひとつひとつの構成要素がまとまりを持つ方が好みであると改めて実感した。ちょうど React コンポーネントの定義時に、その都度ボイラープレートを書いていく必要がどうしても出てしまうのも、同じ背景ではないだろうかと考えた。
文字列の扱いのぎこちなさ
文字列を組み立てるのがどうにもぎこちない思いであったが、これは Go の仕様上そうする他ないと割り切った。それは次のようなコードである。
initializeSP := "@256\n" +
"D=A\n" +
"@SP\n" +
"M=D\n"
codewriter パッケージをのぞいてもらえれば一目瞭然だろう。生成される行の単位で文字列を結合していっているわけだが、改行文字はつけ忘れるし、+の打ち忘れでコンパイラに怒られるしで、お世辞にも書きやすいとはいえなかった。
ヒアドキュメント的なものがあればいいなと何度も思ったが、標準パッケージには見受けられなかったので、文字列の結合で押し通した。とはいえもっといいやり方がないかはぜひ知りたいところである。
終わりに
もっとも基本的なデータ構造としてとうに知った気になっていたスタック構造が、高級言語のフロー制御をもっぱら一手に引き受けて管理しているということを知るのは、目からウロコの思いだった。それを実装してみて、ハードウェアが確かに期待した通りの動作を自律的に行っているのを眺めていると、人類の発明は偉大だという感慨に打たれた。
そしてそれを他ならない自分の手で実装できたのだという達成感は、初めての Hello World! を遥かにしのぐ驚きと喜びを与えてくれるものだった。テキストに従って進めただけとはいえ、無事にやり遂げられたことを誇りに思う。
一方で、学習用途の、限定された機能セットしか持たない言語の実装ですら、たいへん難渋するものだということがよくわかった。
「複雑なスキームを実現するためには、誰かがハードワークを背負わなければならない。つまり高級言語でより抽象的な表現を可能にするために、低級言語のレイヤでより複雑な実装を行うのだ」という記述がテキストに述べられていた。
日ごろは高級言語のレールに沿って仕事をしている。複雑な仕様であってもそれなりに難なく実装できるし、バグが起こってもロジカルに影響範囲を切り分けて対処することができる。しかしその平穏は、まさに今回実装したような、低レイヤにおける驚くべき着想と恐ろしく手のこんだ実装のおかげで実現せられているのだという学びが、今回の収穫である。
こうしたパラダイムそのものを考案してくれた先人たち（とりわけ Pascal の設計者である ニクラウス・ヴィルト氏 ）、そして今日でもこうした低レイヤでの実装を行ってくれている、世界のどこかの技術者たちに、心からの敬意を持つ。そして彼らが用意してくれた仕組みのおかげで、パワフルな高級言語の恩恵に浴することができるという幸福をよく自覚して、最大限に無駄のない、エレガントなコードを書きたいものだと思いを新たにもしている。