「コンピュータシステムの理論と実装」を読んだ記録．
本の紹介
コンピュータシステムを下は電子回路から上はOSまで一つ一つ実装しながら概観できる本．通称 nand2tetris ．NANDゲートで回路を組むところから始め，最終的には自作の簡単なOSでテトリスを動かすところまで行く．ひどく長く険しい道のりのように思えるが，段階的に抽象化していき，低次の部品から高次の機能を組み上げていく過程を学べる．章ごとに重要な概念の解説と演習問題がある．演習問題を通して自らの手でコンピュータシステムを作り上げることができる．
神本です．
動機
大学の計算機学の授業（情報系の入門的な授業）で低レイヤの話を少し扱って興味を持った．これからもっと本格的に低レイヤを授業で学ぶことになると思うので予習も兼ねて，いろいろなところでおすすめされていたこの本を手に取った．
やったこと
各章の内容を簡単にまとめる．また，演習問題の自分の実装について説明する．あと感想とか．
僕の実装（Julia）はGitHubに上がっている．
github.com
第1章 ブール論理
様々な論理ゲートをHDL（ハードウェア記述言語）で実装する．NANDがあれば任意の論理演算が表現できるので，論理回路もNANDゲートの組み合わせで書ける．ここではNANDゲートは与えられるとして，種々の回路を実装する．
ハードウェアのレベルではすべての回路はNANDゲートだけで構築されているのかもしれないが（そうなの？），HDLで記述する段階では複雑な回路も全部NANDで書いていたら途方もなくめんどくさいので，よく使われる演算をモジュール化して使いやすいようにする．例えば，NANDからNOT，AND，OR，XORなどの基本的な回路を構築し，それらを用いてマルチプレクサや多入力ORなどの少し複雑な回路を実装する，というように段階的にやっていく．
実装
パズルみたいで楽しい．
forループがないので多ビット演算は頑張って16bit分全部書くしかなさそう．
第2章 ブール算術
第1章で実装した論理ゲートを組み合わせて，ALU （算術論理演算器）を実装することが目標．ALUでは，関数（例えば，加減算，bitwise AND, OR, NOTなど）を指定するコードとそれの引数を入力すると，指定された演算を実行して出力を返す．
まず加算器を実装するが，加算はXORとANDで表現できる．
ALUは，それが計算する関数ごとに別の回路を用意するという感じではない．加算とbitwise ANDとbitwise NOTを組み合わせることで種々の関数が統一的に表現できる（これ面白い）．そのためALUの内部は，それが提供する機能に比べて極めてシンプルである．
実装
加算器は素直に実装するだけ．ALUはシンプルだってさっき言ったが，それでも今まで実装した他の回路に比べると少々複雑で難しい．うまく出力ピンを分岐させたりするときれいに書ける．
第3章 順序回路
第1, 2章の回路はすべて組み合わせ回路と呼ばれる．これは，入力の組み合わせだけで出力の値が決定されるからである．
この章で実装する回路は順序回路という．この回路は状態を保持することが可能で，入力値に加えてその内部状態に依存して出力の値が決定される．これを使うと時間方向の広がりを持った機能（例えば，記憶）を実装できる．
組み合わせ回路ではNANDゲートが最も基本的な素子であったが，順序回路ではフリップフロップがそれに当たる．フリップフロップは入力を1タイムユニットだけ遅らせて出力する回路である．フリップフロップの出力を（マルチプレクサを通して）それ自身の入力に繋げば，フリップフロップは同じ値を出力し続けることができるという寸法である．
実装
あまり難しいところはない．本に書いてあることを素直に実装するだけ．
第4章 機械語
シミュレータ上で動く独自のアセンブリ言語を使っていくつかのプログラムを書く．アセンブリ言語は機械語と一対一に対応しているので，ハードウェアが直接扱える機能をアセンブリ言語で記述することができる．それは，メモリI/O，レジスタの操作，算術演算，ジャンプ命令といったものである．
計算の基本的な流れとしては，メモリから値を読み込んでレジスタに格納し，レジスタの値に対して演算を施し，結果をメモリに格納するということを繰り返す感じ．ジャンプ命令を使うと条件分岐や繰り返しが表現できる．
実装
アセンブリ自体は大学の授業で少し書いた（紙コーディングだが...）ので，if文やfor文無しでプログラムを書く雰囲気はなんとなく知っていた．ただ，この本のアセンブリはかなり独特なものなので考え方に慣れるまで少し時間がかかった．でも慣れると面白い．ここまでシンプルな言語でもちゃんとプログラムが表現できるのがすごい．
乗算について，\(O(N)\)でやるのが一番シンプルだが，そんなひどい計算量の掛け算なんてやりたくないので，僕は\(O(\log N)\)でやった．ビットごとに見ていってシフトしたりしなかったりするやつ．シフト演算がないのは，足し算で代用した．
第5章 コンピュータアーキテクチャ
ハードウェアの話はこの章がクライマックス．いままで実装したALUやメモリを組み合わせて，CPU（中央演算装置）を構築する．CPUはメモリから命令やデータを読み出して，内部のレジスタやALUを用いて演算や制御を行う．データだけでなく命令もメモリに格納する方法はプログラム内蔵方式と言われ，これのおかげでコンピュータの驚くべき柔軟性が生み出される．コンピュータに親しんでいる我々からすれば当たり前のことのように感じられるが，これは天才である．最初期のコンピュータはプログラムを変えるときにハードウェアのレベルで変えていたのだが，プログラム内蔵方式によってプログラムの変更がずっと簡単になった．ありがとう，フォン・ノイマン......．
その他特筆すべきことは，メモリマップドI/Oである．コンピュータはキーボードなどの入力装置やスクリーンとの出力装置とやり取りをする必要があるが，それはメモリを介して行うことができる．I/Oデバイスをメモリの特定位置に紐づける．入力装置から入力が受け取られると，対応する値がそのメモリ位置に書き込まれる．また，出力装置のメモリ位置に値を書き込むと，それに対応する動作が出力装置によって行われる．たとえば，キーボードが1000番のアドレスにマップされているとすれば，キーボードで入力されたキーのコードが1000番のアドレス位置に現れ，またスクリーンのあるピクセルが2000番に対応しているなら，そこに1を書き込むとそのピクセルが光る，という感じ．これで，すべてのデータがメモリ上で統一的に扱える．天才．
実装
一番難しいのはCPUの実装だが，うまく書けばALUより少し簡単くらいの実装量．本の図とにらめっこして一つ一つ配線していけば変なことしなくてもできるはず．
第6章 アセンブラ
アセンブリ言語から機械語への変換をするプログラムをアセンブラという．アセンブリ言語は機械語の命令に人間が読める名前をつけただけなので，変換は簡単．
実装
本に載っている，種々の命令の変換表を見てそれを打ち込むだけ．最初C++でやっていたのだが，あまりにもだるかったのでJuliaに切り替えた．C++の文字列操作は途方もなくめんどくさいのでPythonとかJuliaとか文字列操作の関数がたくさんある言語だと楽な気がする．
めんどくさかったので，入力のアセンブリファイルが正しいものだと仮定しているので，文法エラーの検出とかの例外処理は全然してない．やるべきなのかな......．
サボってあまり行儀の良くない書き方になってしまったが，今更直すのもめんどくさい．動けばよし．
第7章 バーチャルマシン#1: スタック操作
後の章で高水準言語のコンパイラを実装するが，高水準プログラムはまず中間コードに変換され，その次に機械語に変換される．中間コードは実際のプラットフォームで実行されるのではなく，バーチャルマシン上で実行される．バーチャルマシンは抽象化されたコンピュータであり，個々のハードウェアの差異を吸収する．バーチャルマシンがなかったら，ハードウェアの種類ごとに別々のコンパイラを書く必要があるが，バーチャルマシンがあれば，中間コードに変換する一つのコンパイラがあれば事足りる．もちろん，ハードウェアの種類ごとに別々のバーチャルマシンが必要になるが，別々のコンパイラを書くよりはましである．（例えば，\(N\)個の言語と\(M\)種類のハードウェアがあるとする．バーチャルマシンなしでは，\(NM\)個のコンパイラがいる．バーチャルマシンを使うと，\(N\)個のコンパイラと\(M\)個のバーチャルマシンを書くだけでいい．）
この本では一つのプラットフォームと一つの言語しか扱わないので，いらないといえばいらないのだが，それでもバーチャルマシンがハードウェアを少し抽象化してくれるので，直接機械語を吐き出すよりはコンパイラの実装が楽になる．
ここで作るバーチャルマシンは，スタックを用いて計算を行う．スタックは先入れ後出し（LIFO）のデータ構造で，演算の対象をスタックに積んでいって上から演算を施していけば複雑な計算も簡単できる．
シンプルで美しい．
実装
エラー処理もない雑なコードになってしまった......．が，動く．バーチャルマシンの各操作に対応するアセンブリのコードを埋め込んで，つなげていくだけ．やるだけなんだけど，めんどくさい．
第8章 バーチャルマシン#2: プログラム制御
前章では基本的なスタック操作と算術演算を実装したが，ここではプログラム制御の仕組みを実装する．ジャンプ，条件分岐，そして関数呼び出しである．関数は引数とかもスタックに積んでいくことでうまいこと制御できる．天才．本当に天才．シンプルかつ強力な仕組みって最高にかっこいい．
実装
関数呼び出しや初期化のコードで，新しくラベルを定義する必要があるが，ユーザが定義するラベルと重複しないような命名規則を用いる必要がある．ユーザ定義のラベルは "
あとは仕組みは本に全部書いてあるので，一つ一つ実装するだけ．前章とやることはあまり変わらない．忍耐強くやる．
第9章 高水準言語
アセンブリや中間コードで大規模なコードを書くのは地獄．人間はもっと抽象度の高い言語を用いて思考するべきなのである．高水準言語はもっと人間にわかりやすい構造を持っている．
ここではJackという，Javaに似た独自の言語を用いる．シンプルなオブジェクト指向の言語である．機能が少なすぎて実用には到底耐えられないが，中間コードよりはずっとマシである．
第10章 コンパイラ#1: 構文解析
アセンブラや中間コードの変換器は，前から見ていって一行一行変換していくことができたが，高水準言語は直線的な構造をしていないので，まず先に構文解析というのをやる必要がある．高水準プログラムのパーツを分解して木構造（構文木）に落とし込むと，再帰的にコンパイルできるようになる．
構文解析はトークナイザとパーサという2つのモジュールからなる．トークナイザはコードを「単語」に分解する．パーサは単語の間に構造をもたせる「文法」のようなものである．
パーサは再帰下降構文解析という方法で作る．前からトークンを順に読み込み，どの文法ルールを用いるのかを確定させていく．別の文法ルールを参照する必要があれば，その文法ルールを担当する関数に処理を渡し，帰ってきたらもとの文法ルールの処理に戻る．（これもスタックのような構造になっている）．例えば，最初が "while" というトークンだったら，今見ているのがwhile文であることがわかる．while文は "while (<式>) {<文>}" という文法ルールに従う．次に "(" を読み込む．次に式を読み込むが，これは式を読み込む用の関数を呼び出してその部分を解析してもらう．処理が戻ってきたら，次は ") {"となっているはずである．次に文を読み込む．分を読み込む用の関数を呼び出す．帰ってきたら，最後に "}" を読んで終わりである．このようにやると，トークンが木構造に並べられる．
実装
文法ルールをそのまま実装するだけ．最初の何トークンか（多くの場合1トークン）を読み込むと，どの文法ルールを適用するべきかが確定するので，それに従って前から読み込んでいく．他の文法ルールを参照する箇所に突き合ったったら，その関数に処理を受け渡し，帰ってきたら自分の処理を再開する．まあ，やるだけといえばやるだけなんだけど，簡単とは言っていない．頑張る．
第11章 コンパイラ#2: コード生成
前章で構文解析をした．今度は作られた構文木をもとにしてそれを中間コードに落とし込む．
実装
基本的なロジックは全部前章で実装してある．あとは変換コードを埋め込むだけ．だが実は，この章が一番大変だった．
途中，スタックに値を積むだけでなく，どこかに値を退避させておかないとどうしようもないところがあるが，その時はtempセグメントに適当に用いる．
第12章 オペレーティングシステム
Jack言語を用いて簡単なOSを実装する．OSは低レベルの機能を抽象化して簡単に利用できるようにするインターフェイスの役割を持つ．例えば，メモリ管理や入出力，基本的な数学的演算である．OSがなければプログラマが直接メモリを探して格納位置をきめたり，直接メモリをいじって描画したりしなければならない．OSがそれらの機能を提供してくれるので，プログラマは中心的なロジックに集中できる．
実装
疑似コードが本に書いてあるところはそれをそのままやるだけ．メモリ割り当てに関してはかなり自由度があるが，僕はfirst-fitでやった（楽なので）．空いたメモリ領域を本にあるようにlinked listで管理する．allocでは，前から見ていって，長さが足りているところを切り出す．詳しくは，ほしいサイズがsizeのとき，size + 3以上のサイズがあるところを見つける．（自分のサイズ，自分の次のアドレス，切り出された領域のサイズ）を格納する領域が必要だから+3である．そのような場所を見つけたら，後ろからsize + 1の領域を切り出して呼び出し元に返す．
deallocでは，解放する領域をlinked listの最後にくっつける．linked listの最後のアドレスは別にstatic変数で持っておく．
デフラグはやってない．
用意されているvmファイルはやたら速いんだが，自分で書いたOSをコンパイルしたやつは異常に遅い．特に描画がナメクジのような速度である．ただ高速化は退屈なので......やらない．
全体を通して
途中放置していた時期を除くと，2週間ほどで一通り終わった．非常に面白かった．
理論自体は基本的なところのみ説明されており，計算機学の授業でも扱ったような内容だったので，新たな知識をたくさん得られたという感じはあまりなかった（コンパイラ周りは初めて知ったことが多かったが）．しかし，実際に自分で手を動かしてこれらのシステムを実装するというのは非常に面白く価値のある経験になったと思う．実装してみて初めてわかることや，理解が深まることが多い．
NANDゲートのレベルからOSを作り上げるまで行くのは，途方もない道のりのように最初は感じられたが，徐々に抽象化していって複雑なものを作り上げていく一連の流れには感動した．NANDやフリップフロップを組み合わせて演算装置やメモリを構築する．それらを組み合わせてコンピュータのハードウェアを構築する．機械語は読みにくいのでアセンブリ言語でちょっと読みやすくする．個別のハードウェアを抽象化し，スタックマシンとして扱うためにVMを用意する．もっと高次の処理を表現しやすくするために，高水準言語から中間言語へコンパイルできるようにする．最後に，高水準言語で得た表現力で，OSの機能を実装する......という，少しずつはしごを登っていくようなアプローチは鮮やかだった．人類の英知という感じがする．
演習問題はとてもやりごたえがあった．最初の方の回路のあたりはやるだけだったが，アセンブラやコンパイラを自分で実装するあたりからかなり大変だった．本には大雑把な実装方針が書いてあるだけで，具体的な実装の詳細は全く書かれておらず，自力で実装する必要がある．プログラムがかなり長くなってしまうのでバグが生まれやすい．しかし，実装するのに十分な理論はちゃんと解説されているし，なによりテストや可視化のためのスクリプトが公式のウェブサイトから提供されているのが素晴らしい．
まあ，作られるものがおもちゃであるという感じは否めない．作るコンピュータは非常に単純な構成になっているので，実用には程遠い．演習問題も，単純な部品を組み合わせてそれっぽい形を作り上げるというパズル要素が強い．しかし，実用に耐えうるようなコンピュータを作るには，細かい最適化の話まで踏み込んで解説しなければならず，それこそこの本の1章分の話題で1冊の本がかけてしまうのだろう．重要なところを抑えつつ，1冊の本でnandからtetrisまで一気に眺められるのは，驚くべきことなのかもしれない．
コンピュータを完全に理解した気になった．この本は情報系の人にかなりおすすめ．
