有名な書籍『コンピュータシステムの理論と実装』の実装（Nand2Tetris）を完走したので、やってみた感想と、これから挑戦する方へのアドバイスなどをまとめます。
※ 公式サイトのライセンスのページ にソースコードを Web に公開したりしないでほしいと書かれているので、ソースコードは非公開です。
書籍『コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方』とは
『コンピュータシステムの理論と実装』は、背表紙で
コンピュータを理解するための最善の方法はゼロからコンピュータを作ること
と説明されている通り、NAND 回路 (と、フリップフロップ回路) だけを与えられ、そこからコンピュータを作っていく書籍です。
最終的にはテトリスのようなアプリケーションが動かせるコンピュータを作るということで、「Nand2Tetris」とも言われています。
Nand2Tetris で作るもの
先述の通り NAND 回路 (と、フリップフロップ回路) だけが定義された状態で、
- HDL を書き、ハードウェアエミュレータで動く ALU、レジスタ、CPU、メモリなどを実装
- アセンブリ言語を機械語に変換するアセンブラを実装
- VM プログラムをアセンブリ言語に変換するバーチャルマシンを実装
- 高級言語を VM プログラムに変換するコンパイラの実装
- メモリ管理などを担う OS (というか標準ライブラリ) の実装
といった流れでコンピュータを実現していくことになります。
400 ページにも満たない書籍ですが、これだけの内容を、しっかり自分で考えながら進めることができるようになっています。
感想
まず全体を通して感じたのは、「論理回路と普段書いているプログラムは、思ったほどは遠くない」ということです。
最近はプログラミングの入門も容易になっており、低レイヤがかなり隠蔽されている言語を使うことが増えていると思います。
コンピュータは最終的に回路で実現されているということは知りつつも、普段書いているプログラムと低レイヤの動作の間に魔法のようなものを想像している方も少なくないと思います。
この本は、そんな「コンピュータが魔法に見える」という現象を解くのにぴったりです。
CPU の実装
Nand2Tetris はまず、ALU や CPU などのハードウェアの実装から始まります。
CPU を作るというとすごく難しいことのように聞こえますが、Nand2Tetris の CPU であれば、要件を満たす HDL を記述するのは難しくありません。 (リングプロテクションや分岐予測といった高度な機能を持たない CPU です)
このレイヤを解く鍵となるのはマルチプレクサだと思います。
アセンブラの実装
CPU が完成したら、機械語のプログラムを動かすことができます。
次のステップは、アセンブリ言語で作られたプログラムを機械語に変換するアセンブラを実装することです。
Nand2Tetris は全体として実装が比較的簡単にできる設計されており、プログラミングに慣れた方であれば、アセンブラの実装に大きな難点はないと思います。
バーチャルマシンの実装
アセンブラの次は、Java でいう JVM のような、バーチャルマシンの実装に入ります。
書籍の中でも絶賛されていますが、「スタックマシン」による計算機の実現は本当にすごいと思います。
どれだけ込み入った計算であっても、スタックというシンプルなデータ構造により、1 つ 1 つの小さな問題に帰着されてしまいます。
この書籍は CPU とコンパイラの実装に注目されやすい気がしますが、個人的にはスタックマシンが最も重要な鍵を握っていると思います。
コンパイラの実装
中間言語をアセンブリ言語に翻訳するバーチャルマシンができたら、あとは高級言語を中間言語に変換するコンパイラを実装するだけです。
コンパイラは書籍によっては yacc などのツールを利用して実装していきますが、この書籍ではフルスクラッチでトークナイザ・パーサ・コード生成を実装していくことになります。
コンパイラは特に魔術的なものに見えるのではないかと思いますが、Nand2Tetris のコンパイラを実装すると、「コンパイラもプログラムの一種に過ぎない」と思えるようになります。 (もちろん最適化などは非常に難しい話だと思います)
OS (標準ライブラリ) の実装
最後には、メモリ管理などを担う簡易的な OS (というか標準ライブラリ) を実装します。
コンパイラの完成という山場を超えるとこの章はスキップしてもいいかなという気持ちになるかもしれませんが、個人的にはやってよかったと思います。
というのも、コンパイラに加えて低レイヤを扱うライブラリまで実装したことで、今まで以上に色々なプログラミング言語に感謝しようと思えるようになりました。
世の中には、
- C 言語や Nand2Tetris の Jack 言語のような、低レイヤを意識しやすい言語
- 関数型のような、低レイヤを強く隠蔽した言語
などがあると思います。
個人的には抽象化の進んだ言語が好きだったのですが、Nand2Tetris を通して、抽象化されていないコンピュータの面白さと、そんな低レイヤを扱える言語の面白さを感じました。
全体を通して
ということで一通り完成になるのですが、完了してみて思うのは、「特別難しくなく、別に普通だった」ということです。
それがこの本の本当にすごいところなのですが、最適化について考慮せず、シンプルに実現できるように設計されたコンピュータは、ふつうのプログラミング能力で実装できてしまうのです。
論理演算をしたり仕様を読み解いたりにはある程度頭を悩ませることになりますが、
- 仕様が実装しやすいように定義されている
- 設計方針が与えられている
- テストがしっかり用意されている
といった工夫により、とても進めやすくなっています。
挑戦しようと思っている方へ
ここから、Nand2Tetris に挑戦しようと思っている方に向けて、前提知識やアドバイスを書いていきます。
前提知識
Nand2Tetris が必要としている前提知識はかなり少ないです。
具体的には、
- 基本情報処理技術者試験・応用情報処理技術者試験程度の論理演算ができる
- Java のようなオブジェクト指向の言語が書ける (通常の処理でコンパイルエラーが解決できないことがない程度)
- ポインタやオブジェクトの参照について理解している
- (できれば) C 言語などでポインタの演算をしたことがある
くらいです。
書籍で言えば、
- 『プログラムはなぜ動くのか 第３版 知っておきたいプログラミングの基礎知識』
- 『コンピュータはなぜ動くのか 知っておきたいハードウエア＆ソフトウエアの基礎知識』
- 『オブジェクト指向でなぜつくるのか 第３版 知っておきたいOOP、設計、アジャイル開発の基礎知識』
くらいを読んでおくと手が出しやすいと思います。
プログラミングの練習にもとても良い内容ですし、例えばプログラミングの研修後の発展課題にも良いと思います。
アドバイス
Nand2Tetris に着手する上では、いくつかアドバイスがあります。
本をちゃんと読んで進める
この本は、仕様や設計が非常によくまとまっています。
その仕様や設計をしっかり読み解くことが、完走するうえでは何より重要です。
短期でやる
ゼロからコンピュータを作り上げるという性質上、あるレイヤを実装する際は、ひとつ手前のレイヤの仕様が前提になります。
仕様を忘れないよう、ある程度短期集中で取り組むのがおすすめです。
ちなみに、人によって使える時間も違うので参考までですが、私の場合は最初から最後までで半月ほどかかりました。
TDD する
書籍に付属しているテストツールも便利ですが、アセンブラ・バーチャルマシン・コンパイラの実装の際は、別途自動テストツールも導入したほうが楽です。
これらは自分の好きな言語で実装することになるので、慣れた言語で、できれば TDD で実装するとスムーズになると思います。
とにかく始めてみる
最後に、とにかく始めてみることが大事です。
やってみると面白くて、続きをやりたくなります。
まずは NAND ゲートをもとに各種論理ゲートを作るところから、気軽に始めてみてください。
完走すれば、CPU とコンパイラを作ったことがあると言えるようになります。 (CPU はハードウェアエミュレータなうえ、どちらも簡易的なものですが…)
今後やりたいこと
ということで、感想や、これから取り組む方へのアドバイスなどを書いてきました。
これで CPU とコンパイラは作りましたが、個人的にもう少し低レイヤを勉強したいと思っています。
具体的には、今年中には簡易的な OS (カーネル)、シェル、デバイスドライバあたりを自作してみるつもりです。
また、コンパイラ周辺では Lex、yacc、LLVM あたりを勉強したいなと思っています。
これらもやってみたらまた記事にします！
