「コンピュータシステムの理論と実装: モダンなコンピュータの作り方」を読みました
こんにちは。ほとんど外出しない生活が始まってから約1年経ちました。友達とワイワイやったり、海外に行ったりみたいなことが待ち遠しいです。
コンピューターシステムの理論と実装を読み終えたので、それの読了エントリです。
この本は別名nand2tetrisとも呼ばれており、NandゲートからOSレベルまでを一気通貫で体験しコンピューターアーキテクチャへの理解を深めるというコンセプトです。私は書籍で取り組みましたが、Courseraには著者であるヘブライ大学の教授による授業もあるようです。
各章の内容と難易度をまとめてみます。
Part1 ハードウェア
ハードウェア記述言語(HDL)でコンピューターをモデリングします。
1章 ブール論理
難易度1 ★☆☆☆☆
この本での最小の論理回路であるNandゲートを用いて、And・Or・Xor・マルチプレクサ・デマルチプレクサを実装します。多ビット・多入力の回路も後で使うので実装しますが、特に難しくはないです。
2章 ブール算術
難易度2 ★☆☆☆☆
半加算器・全加算器・加算器、そしてCPUのコアとなる部分のALU（算術論理演算器）を実装します。一見複雑ですが、仕様どおりに作れば問題ないです。
3章 順序回路
難易度2 ★★☆☆☆
最小の順序回路であるフリップフロップから、レジスタ・メモリ (RAM)・カウンタを実装します。論理回路では値を計算するだけですが、順序回路を用いることにより「状態」を扱えるようになります。
4章 機械語
難易度2 ★★☆☆☆
今回作るコンピューターでの機械語の仕様が与えられます。その仕様に合わせたアセンブラを書く課題があります。
5章 コンピューターアーキテクチャ
難易度4 ★★★★☆
今まで作った回路を総動員して、メモリ (RAM, ROM), CPUを実装します。基本的には仕様に忠実に作れば問題ないですが、私はCPUの制御ビットの処理でかなり悩みました。
Part2 ソフトウェア
何らかの高水準言語を用いて、アセンブラからVM、コンパイラ、OSまでを実装します。
6章 アセンブラ
難易度2 ★★☆☆☆
アセンブリから機械語への変換をおこなうアセンブラを実装します。私はPythonで実装しましたが、基本的には文字列処理が中心なので言語は何でも良いと思います。高水準言語で作るのでそれほど実装は難しくはないですが、一番最初に機械語でアセンブラを作った人は素晴らしいですね。
Ken Gregg's answer to How did the first assemblers get built in machine code? - Quora
7章 バーチャルマシン スタック操作
難易度3 ★★★☆☆
スタックベースのバーチャルマシンを実装します。ここら辺から仕様が難しくなってきるので、なるべく固有の文字列は定数で宣言しておき、生の文字列を書くことのないようにするといいと思います。この章を取り組んでいるときに、アセンブラがスラスラ読めるようになったのを感じました。
8章 バーチャルマシン プログラム制御
難易度5 ★★★★★
前章から、関数呼び出しができるようにします。関数を呼び出した際に、呼び出し側のリターンアドレスや各セグメントのベースアドレスなどをpushし、関数のリターンでそれを元に戻すのですがなかなかデバッグが難しいです。課題のユニットテストが全部通った時にはガッツポーズをしました。
9章 高水準言語
難易度1 ★☆☆☆☆
この本での独自言語であるJack言語の仕様が書かれています。特にやることはありません。
10章 コンパイラ 構文解析
難易度3 ★★★☆☆
Jack言語をVMコードに変換するためのコンパイラを作っています。この章ではJack言語の構文解析をおこないます。再帰下降構文解析というトップダウンからの再帰によるパーサーを実装するのですが意外と直感的に書けるのですんなり課題は終わると思います。
11章 コンパイラ コード生成
難易度5 ★★★★★
この本の最大の山場です。前章で作成したパーサーを用いて、コード生成部分を実装します。ずっとVMの仕様とテストの出力とを睨めっこしながら完成させましたが、丸4日ほどかかり 全てのテストケースが通った際にはガッツポーズをしました。 (2回目)ここまで終わるとJack言語から機械語までを一気通貫で生成することができるようになります。
12章 OS
難易度4 ★★★★☆
ここからはおまけです。OSというよりはJack言語によるライブラリのようなものを作ります。人によっては飛ばす人もいるようです。メモリのallocやdeallocの実装方法はとても参考になるので、ここだけでも取り組んで欲しいです。
感想
前提知識が特になくても、コンピューターのアーキテクチャを手を動かすことで理解できる良書だと思います。作るものに意味があるというよりは、作る過程で獲得できるイメージとCSの知識が結び付けられるのが一番良い点だと思います。特にCSを自分で学びたい人の一冊目にオススメです。
