「コンピュータシステムの理論と実装」をやりきりましたという記事に憧れて

この記事について

この記事は約1年前の私がWebエンジニア1年生のときに「コンピュータシステムの理論と実装」をやりきりました - Qiitaという記事に憧れてコツコツ書いていた記事ですが10章で挫折していまい下書きのままお蔵入りした記事になります。

せっかく途中までいい感じにかけているので公開して供養したいと思います。

適切でない表現や誤っている解釈があるとご指摘いただけると幸いです。

この本を読んだきっかけ

本当の仕組み、本質を知ることで応用が効くエンジニアになりたいと思ったからです。

ざっくりですが、以下のような点を目的にやりました。

• 低レイヤーの全体像を理解したい
• 今後の方向性も含めて、いろんな視点で興味がある分野を見つけるため

結局、読んでよかったの？

読んで良かったです。

自分の手を動かしながら、体系的に低レイヤーの全体像を学ぶという目的に非常にマッチしている本だと思います。

自分の場合、業務にはすぐには直結しないので、短期的なコスパを求めるなら確実に業務で使う言語や業務で使う技術を深堀りするなりなんなりしたほうが良いと思いました。

でも、後ほどこの本の良いところでも紹介しますが、Webエンジニアが最短で低レイヤーの全体像を手を動かしながら学べる最良の本だと思うので気になる人はやってみて損はしないとは思います。

本の紹介

コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。
コンピュータの構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できます。
本書では、これらコンピュータの構成要素をひとつずつ組み立てます。

具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計します。
そして、オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション（テトリスなど）を動作させます。

実行環境はJava（Mac、Windows、Linuxで動作）。

この本の良いところ

自分の手でゼロからコンピュータを作り上げることでプログラムがなぜ動くのか学べる

Webエンジニアが普段触れない箇所で一番気になるであろうなぜプログラムが動くのかという疑問を自分の手でゼロからコンピュータを作り上げることで理解できます。

コンピュータを構成する最小要素のNAND素子から論理回路を構築してシミュレータ上ですが、実際に動作するCPUを作ることができました(理解する努力は必要でした・・・)。

そして、6章から先は実際に自分が作ったハードウェア上で動かすソフトウェアを作りつつ最終的にはテトリスを動かす過程までがあり、その全ての過程で課題があり、自分で考え自分の手で作り上げる楽しさと達成感を味わうことができます。

低レイヤーが初めてでも最短距離で深く学べるような構成になっている

新人研修のときの一番初めにさらっとコンピュータ装置について学んだときに、CPUがすごい気になって調べていくとレジスタに行き着きましたが、それ以上は前提知識が足りなさすぎて諦めた経験があります。

本書であれば、各章ごとに課題があるのですが、それを解くための解説が充実しています。
とはいってもある程度考えるように作られているので1から10すべての解説が載っているわけではなく、1から7くらいまでのことしか書いていない印象です。何度も読み返すと気づきがたくさん得られます。

以前はレジスタで諦めていた自分ですが、NAND素子から実際に手を動かしながら、順を追って作っていくことでレジスタについても理解することができます。もちろん、最後までやることでコンピュータが何なのか理解することができると思います。

大変だったところ

章が進むごとに難易度は着実に高くなります。
9割くらいは本だけで解決できる問題だと思います。
残り1割は、HDLとかCPUエミュレータとかアセンブラとかツール系や特別な言語の書き方のPDFが公式サイト(英語)から見れるのですがそちらを読まないと進めなかったりします。

1章は、とにかく回路図を紙に書きまくりました。
また、ANDとORがなかなか覚えられなくて、調べても良い覚え方がなかったので自分で考えて覚えました。

 わお！   席が安藤の隣
(和 OR  積  AND)

=> 和とORがセット
=> 積とANDがセット
で覚えました。

3章では、フリップフロップ回路が気になって先に進めなかったりしました。YouTubeにフリップフロップ回路の解説動画があがっていたのでそちらを参考にしたりしました。
(本書ではフリップフロップ回路については無視して進むことができるようの配慮がされており、抽象化されています)

ですが、クロックの概念が入ってくるといまだに混乱します・・・

また、HDLの書き方はこんな書き方できるのかというのはGithubで他の人のコードを見ているときに発見が多かったです。

A命令、C命令を機械語で書くところもかなり苦戦しました。

スクリーンをただ塗りつぶすプログラムをかけたときは感動しましたね。

正直5章は諦めかけたというか、今までのように何周しても解けそうになくて、draw.ioを使って一文一文理解しながら読んで部品を組み上げて、つなげっていってやっと完成したという感じです・・・(あとからわかりましたが、章が進むごとに難易度が急に上がっていきます・・・)

この本のすごいところは1章終えるごとに着実に成長できるところと実際に動かせる環境が整っているところです。

諦めなければですが、100%この本と公式サイトとネットの情報があれば、クリアできると思います。 私は10章で挫折してしまいました…

各章の学習メモ

自分が実装した内容については、GtiHubにあげています(10章で挫折しました…)。
https://github.com/snyt45/nand2tetris

ハードウェア階層

1章 ブール論理

• ブール関数は入力としてブール値(1と0)を受け取り、出力としてブール値を返す関数。
• どのようなブール関数であれ、3つのブール演算AND、OR、NOTで表現できる。
• AND、OR、NOTは、NANDだけから作ることができる。つまり、NANDさえ実現できれば全てのブール関数を実現できる。
• 真理値表から正準表現を導く方法は、①関数の出力が1である行に注目。②入力リテラルをANDで結合し、それらをORで結合。
• NOTは否定、ANDは掛け算、ORは足し算、XORは足し算したときに1桁目
• 16ビット配列の各ビットにアクセスするには、data[0]、data[1]、 ..、data[15]と書く。(0から始まる)

2章 ブール算術

• 符号付き数字を表現するには、2の補数(領域を均等に2つに分け、一方を正の数、一方を負の数とする方式)を用いる。
• 2の補数方式で-xを得るには、xのすべてのビットを反転させ、その結果に1を足す(xが1なら-1は、1111で表現できる。1は2進数では0001なので、1110となり、最終的に1111が-1となる。)。
• 2の補数方式の良いところは、引き算を足し算として扱うことができること。これにより、ハードウェアは加算ができればよくなりハードウェアの複雑さを最小限に保つことができる。

3章 順序回路

• データ入力とクロック入力が合わさることで、D型フリップフロップは「時間に基づく振る舞い」が可能になる(記憶が可能になる)。
• レジスタはデータを格納したり、呼び出ししたりすることができる記憶装置である。1ビットレジスタの実装はMUX回路とDFF回路からなる。
• RAMは、レジスタをたくさん積み重ねることで構築することができる(ベースはレジスタ)。また、アドレスを入力として与えることで該当するレジスタに読込/書込を行うことができる。

4章 機械語

• 機械語とはハードウェアを直接制御することができる言語であり、バイナリコードを人間が分かりやすいように記号や英単語に置き換えたもの。
• DとAのふたつのレジスタがあり、Dはデータ値だけ保持。Aは、データレジスタとアドレスレジスタの二役。
• Mが参照するメモリのワードは、現在のAレジスタの値をアドレスとするメモリワードの値
• どのようなジャンプ命令もAレジスタの値をアドレスとするメモリワードの位置へ移動する
• A命令はAレジスタに値を設定するために用いられる。
• C命令は計算命令と呼ばれ、バイナリコードが111で始まりcomp領域(なにを計算するか)、dest領域(どこに保存するか)、jump領域(次にどこに移動するか)に分かれている。

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

• CPU、RAM、ROMを組み合わさてコンピュータ回路を実装する。特にCPUが一番重要。
• CPUを実装するにあたって、何度も本書を読み返した。今思い返してもこの章は格段に難易度が高いと思う。下記は、CPUについて整理したもの。

ソフトウェア階層

6章 アセンブラ

• アセンブリ言語で書かれたプログラムをバイナリで書かれたプログラムに変換するプログラム。
• シンボルを含まないプログラムのためのアセンブラとシンボルを含むプログラムのためのアセンブラの二段階で実装
• シンボルには定義済みシンボルと変数シンボルとラベルシンボルがあり、メモリワードと対応する必要がある(シンボル解決)。
• シンボル解決は、1回目のパスでラベルはラベル名とROMアドレスの値を対応づけてシンボルテーブルに追加する。2回目のパスでA命令のシンボルで数値でなく、シンボルであればシンボルテーブルから同じ名前のシンボルを探し、見つかれば対応する数値に置き換え、見つからなければ新しい変数としてシンボルテーブルに変数名とRAMアドレスの値を対応付けてシンボルテーブルに追加する。

7章 バーチャルマシン#1：スタック操作

• VM言語をアセンブリ言語に変換する実装をする
• スタック、算術コマンド、メモリアクセスコマンドについて学べる
• 特にスタックは汎用的な概念なので勉強になる。
• 7.2.6章で配列操作、オブジェクト操作をスタックを介して行われていることが学べる

8章 バーチャルマシン#2：プログラム制御

• 8章は7章で未実装であったプログラムフロー、関数呼び出し、ブートストラップの実装を行う
• 関数呼び出しでは、どのようにしてネストされた関数が実行されているのかメモリレベルで学べる
• ブートストラップはVMの初期化の実装で、スタートアップ時に何をやっているのかが学べる
• 7章と8章でVM言語をアセンブリ言語に変換するVM実装をやるが、VM言語側からは読み取れない仕様がたくさんあるので、何度も読み返さないと漏れがあり、正しく動作させるのに苦労した。

9章 高水準言語

やりましたが、整理できるほど理解できていないため割愛…

10章 コンパイラ#1:構文解析

やりましたが、整理できるほど理解できていないため割愛…

11章 コンパイラ#2:コード生成

未着手

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

未着手

さいごに

ボトムアップ的に進めていくので、章が進むにつれて、低レイヤーから高レイヤーの話になってきて最初は地下世界のような世界で冒険している感覚から6章以降はソフトウェア階層の話でVMや高水準言語、OSの話が出てきて身近な話に繋がってくるので最後までモチベーションを切らさずにやりきることができました。 10章までやりました。

ちなみに、仕事をしながら平日や休日を使ってやりながら5ヶ月くらいかけてやりきりました。ペースは遅い方だと思います。

タイトルと内容は「コンピュータシステムの理論と実装」をやりきりました - Qiitaを意識しました。