Rustで『コンピュータシステムの理論と実装』を演習した
n番煎じ。
演習問題回答のリポジトリはこれ。ライセンスは本書P.361の記載に則りGPLとしていますが、問題等ありましたらご指摘頂ければ幸いです。
https://github.com/guricerin/nand2tetris
いわゆる『nand2tetris』と呼ばれる本。本書独自のHDL（ハードウェア記述言語）を用いて仮想的な回路を作成、回路から仮想的なハードウェアを構築、アセンブラの作成、独自のプログラミング言語処理系の作成と続き、最終的には仮想コンピュータ（以下、Hackコンピュータ）上で簡単なゲームの作成を目指す。
低レイヤといえばRustな感じがあるのでRustで演習問題をこなしたが、実際にRustの出番があるのはアセンブラ作成の6章からで、それまでは本書独自のアセンブリなどを使ってせっせと問題を解く。なので別にRustにぴったりの題材というわけでもなく、むしろテキスト処理・言語処理が得意な言語を使うほうが楽に演習できるだろう。
1章
ぶっちゃけるとこの記事を書き始めたのが7章に入ってからなので、1~6章に関してはメモが少ない。
HDLを書くことでHackコンピュータ上の回路を作成する章。はじめに用意されているのはNAND回路のみ。
マルチプレクサのあたりからいきなり難易度が跳ね上がる。これらが実質的にif文などの制御構文を担当することになるので、後の章で大活躍する。
問題が難しいのでプログラムに解かせる方法ないかなとあほなことを思いつきググってみたら、どうやらブール関数を簡略化するアルゴリズムがあるらしく、カルノー法やクワイン・マクラスキー法などの種類がある。結局これらを使うことはなかったが（なぜなら理解できなかったから）、頭の片隅にとどめておこうと思う。
2章
ブール演算で2進数の計算を表現する章。前半は真理値表を自分で書いて照らし合わせていけば、そこまで難しくない。
山場はALU（算術論理回路）の設計となる。ノートが数ページに渡ってごちゃごちゃになり、右手が黒ずんでいた。こんな経験何年ぶりだ？
このあたりで公式ページのPDFをみることを覚えた。正直、本書よりヒント多い気がする。
3章
メモリやレジスタの基盤となる順序回路を設計する。FlipFlop回路が用意されている。
HDLの文法がよくわからなくなって頭がこんがらがった記憶がある。
4章
Hackアセンブリを手書きしてプログラムを作成する。
やってるときはウンウン唸ってたような気がするが、後の章を経た今になって見返すとずいぶんぬるく感じる。
5章
Hackコンピュータのハードウェア設計を最後まで行う。CPU以外は流し作業のようなもの。
ALUのときみたく、やはりCPU設計のためにノートが真っ黒になった。
6章
好きなプログラミング言語を使ってアセンブラを作る。ここからやっとRustの出番。
Hackコンピュータのアセンブリ仕様を把握しておく必要があるため、今までのページを頻繁に見返すことになる。
7章
Jackコンパイラ作成に向けて、Jack中間言語（VM）をアセンブリに翻訳するソフトを構築する。
個人的に一番しんどかった章。中間言語は仮想マシン上のスタック操作を前提として書かれているため、アセンブリ側でスタックの動きをエミュレートしなければならない。
アセンブリ側で実際に見えているのはむき出しのメモリとレジスタだ。しかも格納されるデータが定数値なのかどこかのメモリアドレスなのか、こちらがすべて把握する必要がある。型付けされていないポインタと常に向き合う章と表現すれば、その凶悪さが伝わるだろうか。
また、スタックのプッシュをエミュレートするアセンブリを吐くコード、といった共通化できそうな部分は都度、関数としてまとめるなりしていかないと、あとでえらい目にあう。
8章
7章の続き。サブルーチン呼び出しや制御構文を扱う。
スタックでどうやって関数呼び出しなどを管理するのか常々疑問に思いつつスルーしていたが、本章を読むことで少しは理解できた。
解説イラストが気合入っているせいか（というかまんま答えが書いているようなもの）、7章と比較すれば難しくない。あくまで比較すればだが。
ただ、おれのコードでラベルのつけかたが盛大にミスっていたので延々とバグらせてしまった。
9章
Jack言語の仕様説明。演習はJackを使って自由にコードを書けというもの。
本書にもあるようにJackに精通する必要性は皆無なのでとばした。10, 11章での実装の際に見返すための章。
10章
Jackコードを中間言語に翻訳するコンパイラを作成していく。
言語処理系といえば抽象構文木、抽象構文木といえば代数的データ型なので、Rustの選択が光る章（まあ代数的データ型のある言語ならぶっちゃけなんでもいい）。
F#でSchemeインタプリタを作ったことはあるが構文解析ライブラリの力に依存しているものなので、nand2tetrisの方針に則り今回は一から自作してみた。Lisp以外の言語実装がどれだけかったるいかが身にしみる章だった。
また、字句解析・構文解析の実装には『実践Rust入門』第9章が非常に参考になったことを付記しておく。
この章では、抽象構文木を同じく木構造であるXMLにダンプする機能までを実装する。ちなみに構文解析につきものの左再帰問題にはでくわさなかった。たぶんnand2tetris側が初心者に配慮したBNFを用意してくれたからかもしれない。
11章
10章の続き。抽象構文木をJack中間言語に変換する。
抽象構文木に変換したJackコードの動きをスタックマシンによってエミュレートする。7章よりはましだが、やはりきつい作業だった。
おれが書いたパーサに、二項演算子であるべき-を単項演算子として解釈するというバグが埋まっており、10章のテストでは検知されなかったようなのではまりにはまってしまった。おかげで予想以上に時間のかかった章だった。
12章
Jack言語を用いてHackコンピュータOSの機能を実装する。OSというよりは標準ライブラリ。
本書でもっとも競プロ要素の強い章。ちなみにおれの競プロ力は底辺中の底辺なので、辛く厳しい章だった。数学が得意な人間にとっては楽勝すぎて鼻くそほじれるだろうことを思うと涙がちょちょぎれる。
結局、他の人たちの実装をがっつりカンニングすることに。あれ、ということは7章よりむずいな。
この本で学べないこと
本書でも言及されているが、ぱっと思いついたものであれば
- 最適化（ハードウェア・ソフトウェア関わらず）
- ファイルシステム
- 並行・並列処理
- 通信、ネットワーク
- セキュリティ、暗号理論
- ラムダ計算
- ソフトウェア工学（設計や運用など）
技術書としては一般的な厚さながらやたらと中身の濃い本書をやり遂げたとしても、まだまだ学ぶべきことは大量にある。
まとめ
情報工学の教育をまともに受けていない身からすると大変ありがたかった本。
でももう一回演習したいかと聞かれれば、NOと言わざるを得ない。とろとろにとろけきった脳みそをしばらく休めたい。