「コンピュータシステムの理論と実装」をやりきりました

コンピュータシステムの理論と実装 をやりきったので、メモを残しておきます。

本の紹介

コンピュータシステムの理論と実装 では、NAND ゲートからはじめて、最終的にはアプリケーションを動作させるところまで、ボトムアップの視点でコンピュータシステムの説明が記載されています。通称「Nand2Tetris」。名前がかっこいいですね。

とてもわかりやすい裏書きの説明は以下

コンピュータを理解するための最善の方法はゼロからコンピュータを作ることで、その構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できる。本書では、これらの構成要素をひとつずつ組み立てる。具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計。オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション(テトリスなど)を動作させる。実行環境はJava(Mac、Windows、Linuxで動作)。

自分のモチベーション

ソフトウェアエンジニアとしての業務経験はありますが、情報系の出身ではなく、コンピュータサイエンスの基本的な知識がないため、勉強しています。CPU から OS 周りの基礎を勉強する上で、全体観を掴むために、この本をやることに決めました。低レイヤから順に進めていく、というアプローチに惹かれました。

この本の良かったところ

課題を解きながら理解を深められる

なんといっても、各章の最後に課題が用意されているのが良かったです。テストファイルやエミュレーターも配布されているので、自分のコードが正しいかどうか簡単に確認することもできます。また、有名な本なので、たくさんの方がコードをアップしてくれています。どうしても詰まった時はそういうコードを参考にしながら進めることも可能なので、とても助かりました。
自分のコードも y-meguro/nand2tetris にあげています。一応テストは全部通ったので、正しいはず。もし、明らかな間違いを見つけたらご指摘ください。
※ 1〜11章は ikenox/nand2tetris さん、12章は havivha/Nand2Tetris さんのコードを参考にさせていただきました。ありがとうございました

低レイヤからボトムアップで進めていくので、困ったときに振り返ることができる

低レイヤから徐々に上がっていくという構成は、とてもわかりやすかったです。学習している要素の基礎となる部分（下側の部分）を学習しているので、困った時には振り返って確認できますし、全体の流れを見渡しやすかったなと思います。
具体的には、ブール論理 → ブール演算 / 順序論理 → ALU / メモリ → コンピュータアーキテクチャ → 機械語 → アセンブラ → バーチャルマシン → コンパイラ → オペレーティングシステム → 高水準言語 / アプリケーション と進んでいきました。もともと全体観をわかっていなかった自分でしたが、すべての部分についてなんとなくですが、イメージを掴めたのは良かったです。

大変だったところ

当初思っていたより、はるかに時間がかかりました。自分の場合は112.7時間かかりました。
段々と課題の内容も重くなっていくのですが、特に最後の11章は重かったです（ここだけで23時間かかりました）。ただ、真面目に課題を解いていくと、最後 OS のコードを書いて、Pong アプリケーションが無事に動いた時に「NAND からはじまってアプリケーションを動かせた！」という感動を味わえるので、スキップせずに進めていくのがおすすめです。

次に勉強したいこと・まだわからないこと

• 各分野のなんとなくの雰囲気はわかったけど、詳細なところは全然わかっていないので、CPU / コンパイラ / OS の詳細な内容を勉強したい。またより高度なものを作ってみたい
• パフォーマンスまわりも扱われていないので、勉強したい

各章の内容メモ

最後に、各章のメモを載せておきます。

1章: ブール論理

• スイッチング素子（例えばトランジスタ）から NOT や NAND などの論理ゲートを作れる
• NAND から NOT / OR / AND は作れる
• どんなブール関数も、すくなくとも1つの正準表現で表せるので、NOT / OR / AND があれば、どんなブール関数も表現できる
• 実際に NAND だけ与えられた状態から、NOT / OR / AND / XOR / MUX / DMUX を実装

2章: ブール算術

• 1章の論理演算に加えて、算術演算を学ぶ
• 論理ゲートを組み合わせると、算術演算も表現できる
• 1章で作った論理ゲートから、半加算器 / 全加算器 / 加算器 / インクリメンタ / ALU（1章・2章で出てきた論理演算・算術演算を計算できる機能を持つ）を実装

3章: 順序回路

• これまでの組み合わせ回路に加えて、順序回路を学ぶ（これで状態も保てるようになった）
• D 型フリップフロップだけが与えられた状態から、レジスタ / メモリ / カウンタを実装

4章: 機械語

• 機械語は対象のハードウェアの利用を目的として設計され、通常バイナリコードとニーモニックの両方を用いて記される
• 機械語はプロセッサとレジスタを用いて、メモリを操作するように設計されている
• アセンブリ言語から、アセンブラによって機械語に変換される
• 実際にアセンブリプログラムを書いて、アセンブラで機械語に変換したものをCPUエミュレータで動かし、正しい挙動となることを確認した

5章: コンピュータアーキテクチャ

• ノイマン型アーキテクチャではメモリ（データ + 命令）、CPU（ALU、レジスタ、制御ユニット）、入出力からコンピュータが構成される
• メモリを HDL で実装（RAM はすでに実装済み。Screen と Keyboard は与えられた）
• CPU も HDL で実装（実装済みの ALU / レジスタ / PC / 論理ゲートを組み合わせた）
• ここまでに実装済みの CPU / メモリ / ROM を用いて、Hack コンピュータを実装
• これで論理ゲートから機械語までのハードウェアの世界を学んだ

6章: アセンブラ

• アセンブリ言語を機械語に変換するのがアセンブラ
• メインプログラムと次の3つのモジュールをベースに、実際にアセンブラを実装した
  • Parser モジュール: 入力に対してパースを行う
  • Code モジュール: アセンブリコードのすべてをビットコードに変換する
  • SymbolTable モジュール: シンボルを扱う

7章・8章: バーチャルマシン（スタック操作・プログラム制御）

• コンパイラの構築へ向けた第一歩として、中間コードからアセンブリコードへの変換を行う VM 変換器をスタックマシンで実装した
• スタックは単純な構造だが、どのような算術命令や論理命令であっても、スタックで表現することができる
• VM プログラムは以下の4種類のコマンドから成るので、それぞれに対する変換処理を実装
  • 算術コマンド / メモリアクセスコマンド / プログラムフローコマンド / 関数呼び出しコマンド
• メインプログラムと次の2つのモジュールをベースに、実際に VM 変換器を実装した
  • Parser モジュール: 入力に対してパースを行う
  • Code モジュール: VMコマンドをアセンブリコードに変換する

9章: 高水準言語

• 低水準とは、人が直接読み書きすることを想定していないもの。高水準は逆に人が直接読み書きするもの
• この本では Jack という高水準言語を扱う
• Jack アプリケーションが4つ用意されているので、それを動かしてみた

10・11章:コンパイラ（構文解析・コード生成）

• 高水準言語から VM コードへの変換を行うには、「構文解析」と「コード生成」の2つのステップがある
• 構文解析器を作るために「トークナイザ」と「パーサ」の2段階で実装
• トークナイザでは、テキストファイルを字句解析し、トークンという文字のグループにまとめる
• パーサでは、定められた文法に従って、トークンを形式的な構造にパースする
• コード生成では、データ変換とコマンド変換を行い、VM コードに変換する
• 実際に VM コードに変換するコンパイラを作成

12章: オペレーティングシステム

• OS はコンピュータのハードウェアとソフトウェアシステムのギャップを埋めるために設計されており、プログラマーやユーザーにとってコンピュータ全体がより扱いやすくなるように設計されている
• この章で作成する OS は以下の2つを目指し、Jack言語の標準ライブラリの形でまとめる
  • ハードウェアに特化したサービスをカプセル化し、ソフトウェアから使いやすいサービスを提供すること
  • 高水準言語を、様々なファンクションと抽象データ型で拡張すること
• 実際に Math / String / Array / Output / Screen / Keyboard / Memory / Sys の各クラスを作成し、基本的な処理を実装。11章で扱った Pong アプリケーションが動くことを確認した
• これで NAND ゲートからはじめて、アプリケーションが動かせるようになった

13章: さらに先へ

• エミュレータ・テストファイルなど、使用したソフトウェアはすべて nand2tetris から取得できる
• ハードウェアの実現 / ハードウェアの改良 / 高水準言語 / 最適化 / 通信など、修正・拡張の方向がある

終わりに

いろいろ書きましたが、本当におすすめの本でした。
時間を確保することが最大の困難かと思いますが、やり終わったあとの達成感もあるので、時間を取れる方はぜひどうぞ！