コンピュータシステムの理論と実装
前情報
通称nand2tetris
課題を解きながら進められる
低レイヤからボトムアップで進めていくので、困ったときに振り返ることができる
112.7時間かかる
関連書籍
体験記
courseraで著者の講座が公開されている
お金を払うとちゃんと課題を解くことができて力がつく
ただしコンパイラを書く言語はJavaかPythonに限定される
なぜnand2tetrisを作ったのかのTED講座
所感
課題での実践が非常に重要
これまで文章で読んで理解したつもりのことが理解できてなかったとわかる
テストに重きを置いているのがとても良い
VM変換器からかなり難しくなってくる
以下、読書ログ
1章 論理ゲート
すべてのデジタル機器は情報の保存と処理を行う回路からできている
その回路の構成要素は論理ゲートである
ゲート（gate）はブール関数を実装するための物理デバイス
ブールゲート
ブール関数を物理的に実現したもの
ブール代数
真理値表
ブール関数を表現する最も単純な方法は組み合わせを全列挙して関数の結果を埋めていくこと
関数の入力はバイナリ値なので$ 2^N の組み合わせがある
ブール式 boolean expression
AND OR NOT
どのようなブール関数もこの3つを組み合わせるだけで表現できる正準表現を持つ
たとえそれがどれだけ複雑であったとしても、3つのブール演算And、Or、Notを用いて表現できる
簡潔に示す慣例的な表現
NOR関数 $ \lnot (X \lor Y)
NAND関数 $ \lnot (X \land Y)
XOR関数 $ (\lnot X \land Y) \lor (X \land \lnot Y)
Equivalance関数 $ (X \land Y) \lor \lnot (X \land Y)
NAND
NAND（もしくはNOR）はそれ単体でAND, OR, NOTを作ることができるという性質がある
つまりNANDだけですべてのブール関数を表現できる（冗長にはなる）
NANDを実装した物理デバイスがあればハードウェアが作れる
論理ゲート
n個の変数を入力として受け取り、m個のバイナリを返すブール関数fがあった場合（これまでの例ではすべてmは1であった）、fを実装するゲートはn個の入力ピンとm個の出力ピンを持つ
最も単純なゲートは、あるスイッチ素子を特定の配線経路（ゲートの機能が実現するように設計されている構造）でつなぎ合わせることで作られる。このスイッチ素子はトランジスタ（transistor）と呼ばれる。
現代のデジタルコンピュータのほとんどすべてが、2値データの表現と伝達（ゲートからゲートへの伝達）を行うために電気を用いている。しかし、スイッチング（切り替え）や伝送を行うことができる技術が電気の他にあれば、それを採用することもできる。実際、過去50年間の間に、ブール関数を実現するために多くの研究がなされており、その中には、磁石、光、バイオ、水圧、空気圧などのメカニズムが使われているものもあった。今日においては、ほとんどのゲートがシリコンから作られたトランジスタにより実現されており、そのようなゲートは回路（またはチップ）としてパッケージされている。ちなみに、本書では「回路」と「ゲート」という用語を同じ意味で用いている。
論理ゲートの入力と出力はすべて0と1からなる要素であるため、それらを互いに組み合わせて複合ゲートを構成する
設計対象のゲートのインタフェースは1つだが実装方法は複数存在する
一般的には少ないゲートの組み合わせで多くのことを実現できると良い
do more with less
実際のハードウェア構築
設計書に従って組み立ててテストしているわけではない
ハードウェア記述言語（HDL）を使い、コンピュータ上で回路のアーキテクチャ設計と最適化を考える
テストもハードウェアシミュレータを用いる
シミュレートされた回路の検証を終えたものが設計図となり実際の回路製造に繋がる
基本的な論理ゲートたち
マルチプレクサ (Mux)
セレクタと呼べる
入力 a, b, sel
選択ビット
出力 out
If sel=0 then out=a else out=b
デマルチプレクサ (DMux)
Muxの反対
入力 in, sel
選択ビット
出力 a, b
If sel=0 then (a=in, b=0) else (a=0, b=in)
多ビットの基本ゲート
And16, Not16, Or16, Mux16
多入力の基本ゲート
多入力Or (Or8Way), 多入力/多ビットマルチプレクサ (Mux4Way16), 4出力デマルチプレクサ (DMux4Way)
扱わなかったこと
回路の最適化
複数ある実装方法の比較検討
ゲートの数の考慮、設計によって生じるワイヤの交差への対応
幾何学の公理と証明
物理的な実装方法、電子工学
トランジスタの仕組み
スピード、消費電力、製造コスト
課題
2.5時間ぐらいかかった
HDLですぐif && || !とか書きたくなってしまう
論理ゲートの組み合わせだけで実現するのは新しい体験
ohbarye.icon コンビネータだ
ohbarye.icon むかし大学で論理学の授業とったのを思い出した。すべて忘れたけど…
ohbarye.icon 同時期にOCaml触っていたので代数的データ型に思いを馳せたりした
2章 ブール演算
算術論理演算器（ALU）をつくる
2進数加算
最下位ビットから足し合わせていく
桁の繰り上がりメモをキャリービットという
最上位ビットの計算まで終えたあとにキャリービットがある場合はオーバーフロー
3ビット加算器
2つのビットとキャリービットの和を計算する論理ゲート
nビットの2進数の加算は3ビット加算器から構築できる
符号付き2進数
n桁の2進数で$ 2^n を表現できるが負の数も扱いたい
同じ桁数で負の数を表現するために、2の補数が広く用いられている
加算すると0になる値 (桁あふれは無視する)
この表現方法が優れている点としては、2の補数で表した符号付き数の和は、正の数の和と同じ手順で計算できること
2の補数を用いることで、単純なビット単位の加算が行えるハードウェアがあれば、特別なハードウェアを用いることなく正と負のどちらの加算も行える、ということになる
符号付き数字xを反転する、つまり−xにするには、xのすべてのビットを反転させ1を足せばよい ... したがって、x−y＝x＋(−y)であるから、引き算は足し算として扱うことができる。これにより、ハードウェアの複雑さを最小限に保つことができる
算術論理演算器はは初歩的な算術演算と論理演算の両方をまとめられる
加算器
半加算器（halfadder）：ふたつのビットの和を求める
全加算器（fulladder）：3つのビットの和を求める
加算器（adder）：ふたつのnビットの和を求める
オーバーフロー検出はしない
インクリメンター：与えられた数字に1を加算する
オーバーフロー検出はしない
ALU
上記の加算器回路は一般的なコンピュータでも使われる
このALUはこの本で実装するHack特有
とはいえ小さい部品の組み合わせで多くの機能を実現する好例
課題
3時間ぐらいかかった
HDLでさらに悩んだ
Muxでif文が書けて文明開化
ALUはぱっと見てすごく難しそうだったが積み上げていけばなんとかなった
x + yで加算器AddするところをOrにするというミスのデバグにだいぶ時間を取られた
やらなかったこと
キャリー先読み
低水準の改良はコンピュータ全体のパフォーマンスを向上させる
乗算、除算、浮動小数点演算
3章 順序回路
これまでの論理演算や算術演算のための回路はすべて組み合わせ回路と呼ばれる
入力値の演算によって値が決定する
状態を保つことはできない
記憶素子
コンピュータの演算では記憶素子が必要
記憶素子は順序回路から構築することができる
記憶素子の実装は複雑
同期、クロッキング、フィードバックループなどが関連する
フリップフロップという順序回路を用いると複雑さを押し込めることができる
クロック
「記憶する」という行為は本質的に時間に依存する行為である。つまり、「前に記憶したものを今思い返す」という行為が記憶することの本質である。そのため、情報を記憶するための回路を構築するには、時間の経過を表す方法を考案しなければならない。
ほとんどすべてのコンピュータでは、継続的に変化する信号をマスタクロックが送信することによって時間の経過を表現する
tickの始まりから次のtockの終わりまでに経過した時間を周期（cycle）と呼ぶ
このクロックの1周期がタイムユニット（単位時間）としてモデル化される。現在のクロックフェーズ（tickまたはtock）は2値信号によって表すことができる。ハードウェアの回路網を使って、この信号はプラットフォームの隅から隅まで、すべての順序回路に送られる。
フリップフロップ
ここではD型フリップフロップ（DFF）を用いる
インターフェイスは1ビットのデータ入力と1ビットのデータ出力である。さらにDFFにはクロック入力があり、このクロック入力にはマスタクロックからの信号が絶えず送られる。データ入力とクロック入力が合わさることで、DFFは「時間に基づく振る舞い」が可能になる。
レジスタ
レジスタとはデータを“格納”したり、“呼び出し”たりすることができる記憶装置である。レジスタは、伝統的なストレージの振る舞いであるout(t)＝out(t−1)を実現する
1 bitのin, select bitとしてのload bit (inから読むかoutから読むのか)を入力とするマルチプレクサを挟む
1 bitレジスタを並べるとn bitレジスタになる（16, 32, 64）
幅nのレジスタが持つ値をワードと呼ぶ
メモリ
レジスタをたくさん積むとRAMを実現できる
ランダムアクセスの由来は、ランダムに選ばれたワードに対して、ワードの位置に関係なく書き込みと読み込みができることからきている
RAMの各ワードに対して、ユニークな番号をアドレスとして割り当てる
このアドレスは物理的な位置は決定しない
アドレスがj番目のレジスタを個別に選択することができる論理ゲートを構築すること
RAMの設計で決めること
幅 width: 各レジスタの幅
サイズ size: ワードの個数
32bit, 64bit RAMでは百万を超える
カウンタ
タイムユニットが進むごとに整数値が加算される
out(t) = out(t-1) + c
cはたいてい1
フィードバックループ
組み合わせ回路の出力は入力に依存するので、出力を入力とすると矛盾が生じる
制御不能のデータレースが起きる
順序回路はDFFによって問題を生じなくさせている
DFFは時間遅延という性質を内在させているので、時刻t-1の出力を時刻tの入力にできる
時間
DFFが組み込まれると出力値が変化するのは次のクロック周期の始まりになる
クロック周期の間は不安定な状態であることを許容する
この性質（離散化）によりコンピュータアーキテクチャ全体を同期させることができる
ALUがx+yを計算するとき、xとyが離れたレジスタに格納されているとする
それぞれがALUに到着するまでの時間には、組み合わせ回路からはゴミデータが出力される
しかし、レジスタやRAMを用いるALUでは順序回路を必ず通過するため、クロック周期を適切に設定すればこの問題は気にしなくて良くなる
アーキテクチャ内で最も距離が長い回路間を移動するのに必要な時間を調べ、それより少し長い時間をクロック周期の間隔とすることで、、順序回路が状態を更新するまでには（次のクロック周期の始まりにおいて）、ALUから受け取る値は常に正しいことが保証される
課題
上記回路の実装
時間の概念を理解するまで難しかった
過去に作った回路を組み合わせるのだが、登場人物が多くて選ぶのが難しかった
やらなかったこと
フリップフロップの実装（ビルトインとして提供されているものを使う）
ハードウェアの教科書的には組み合わせ回路からフィードバックループを用いて作成する
まずはクロックを用いず双安定したラッチと呼ばれる回路を作る
ラッチを2つ組み合わせるとクロック対応のフリップフロップができる
やや複雑なのでこの本では抽象化された部品のみを扱った
4章 機械語
どんなに洗練されたソフトウェアであっても、その根本にあるものは基本的な命令コードの集まりであり、その命令コードは単純でプリミティブな操作命令をハードウェアに実行させているだけ
コンピュータ全体において最も重要なインターフェイスは何か？最も重要なインターフェイス、それは「機械語」である。機械語においてハードウェアとソフトウェアが交わる
機械語においてはハードウェアは抽象化された存在として考えることができる
ここでは3つの抽象についてのみ考えればよい
プロセッサ
仕様で決められた基本的な命令セットを実行することができる
算術演算と論理演算、メモリアクセス演算、制御演算
演算対象オペランドはすべてメモリから取り出すバイナリデータ
メモリ
コンピュータでデータや命令を保存するハードウェアデバイスのこと
プログラマーの視点からはすべてのメモリは同じ構造
それぞれがユニークなアドレスを持つ
レジスタ
メモリアクセスはCPUからすると時間がかかる処理
プロセッサにレジスタを備えておくことで高速化をはかっている
機械語
16ビットコンピュータであれば1010001011010111のような命令コードになる
命令コードがどのような操作にあたるかはハードウェアプラットフォーム次第
ニーモニック
バイナリコードの読み書きは難しいので記号や英単語で命令を把握できるようにしたもの
プログラムが書ける！
このプログラムをアセンブリ（アセンブリ言語）という
アセンブリから機械語であるバイナリコードへ変換するプログラムはアセンブラという
コマンド
コンピュータが異なれば機械語も異なるが一般的なコマンドは共通している
加算、減算、ビットシフト、否定など
ADD R2,R1,R3 R1とR3の演算結果をR2に書き込む
メモリアクセス
様々な方法があるが以下の3つはおおよそサポートされている
direct addressing
メモリアドレスを指定して読み込む
LOAD R1,67 67番地のデータをR1に読み込む
immediate addressing
命令中に現れる値をそのままレジスタに読み込む
LOADI R1,67 67をR1に読み込む
indirect addressing
メモリアドレスをハードコーディングせず、メモリ位置が命令によって決定される
ポインタを扱うのに用いる
x=foo[j]という高水準言語での命令を考える
コンパイラは配列の初期化時にメモリセグメントを割り振る
セグメントのベースアドレスを参照する記号としてfoo
配列の1要素が1ワードだと仮定するとfoo[j]はfooアドレスにjを加算すれば求められる
実際にC言語ではx=*(foo+j)と等価である
分岐命令
Hack機械語の仕様（この本で利用するコンピュータ）
メモリ
16bit幅で15bitのアドレス空間を持つ
$ 2^{15} = 32768 (32K) のメモリサイズ
命令メモリ
CPUはここにある命令のみ実行可能
read only
命令セットを交換するには、必要なプログラムが書き込まれたROM回路を用いなければいけない
ゲームのカセット交換に似ている
データメモリ
レジスタ
16bit レジスタ
Dレジスタ
データ値だけを保持する
Aレジスタ
データとアドレス両方を保持する
命令に応じてデータ値と解釈されたりアドレスと解釈されたりする
メモリへ直接アクセスするために用いられる
Hackの命令は16 bit幅で、アドレス指定には15 bitが必要なのでひとつの命令で命令コードとアドレスを同時に指定することはできない
そのためMというラベル付けされたメモリアドレスを使う
Mが参照するメモリのワードは、現在のAレジスタの値をアドレスとするメモリワードの値である、ということにする
たとえば、「D=Memory[516]-1」のような操作を行いたい場合、まずAレジスタに516を設定する命令を実行し、続いて「D=M-1」を行う命令を実行する。
ジャンプ命令においても、特定のアドレスを指定するのではなくAレジスタの値をアドレスとするメモリワードの位置へ移動することとする
@value (@17 @sum etc.) は特定の値をAアドレスに格納するコマンド
A命令: 3つの用途がある
Aレジスタを用いて定数を代入する
プログラムによって定数を代入する方法は、このAレジスタを用いる方法しか存在しない
メモリ操作
あらかじめAレジスタにメモリのアドレスを設定することで、その後に続くC命令において、Aレジスタで指定したメモリ位置にあるデータを操作することができる
移動命令
あらかじめAレジスタに移動先のメモリアドレスを読み込むことで、その後に続く移動を行うためのC命令（jump命令）を用いて、次に実行する命令の位置を移動することができる
C命令: Hackプラットフォームでのプログラミングの中心。何を計算するか？計算した結果をどこに格納するか？次に何をするか？
課題
乗算するHackアセンブリを書く
今回のALUには乗算を行う機能はないので加算を繰り返すことで実現した
キーボードの入力を監視して画面の表示を切り替えるHackアセンブリを書く
ohbarye.icon 特にイベントハンドリングの課題が難しいと感じた
省メモリ、省レジスタで書いていくことが強制される
code jumpがつらすぎる
DRYに書いても処理を追いかけづらくなるのである程度は諦めて書く
ohbarye.icon 記述が異なっても同じ機械語に変換されるのであれば可読性の高いほうを選べば良いと思えた
5章 コンピュータアーキテクチャ
一般的な機械と比べてのコンピュータの特徴は、驚くほどの柔軟性を備える
実現するのがプログラム内蔵方式
プログラムのロジックはハードウェアに埋め込まれたものではないが、コードはまるでデータのようにコンピュータのメモリに格納され操作される
これが"ソフトウェア"の正体
万能チューリングマシン
主にコンピュータシステムの理論的な側面を分析するために用いられる
ノイマン型アーキテクチャ
CPUを中心として、メモリデバイスを操作し、入力デバイスからデータを受け取り、出力デバイスへデータを送信する
このアーキテクチャの心臓部は、「プログラム内蔵」という方式にある
プログラム内蔵が意味することは、コンピュータのメモリに格納されるデータは、コンピュータが計算したデータだけではなく、コンピュータに何を行うべきかを指示する「命令」も含まれる、ということである
メモリ
データとプログラミング命令の両方を格納する
いずれもバイナリで格納されている
ランダムアクセス構造
データメモリ（RAM）
高水準言語の高水準なデータ（文字列、配列、オブジェクト etc.）もすべてバイナリで各ワードに保存される
ワードを指定して読み出す、書き込む
命令メモリ（ROM）
高水準言語のコマンドが機械語に変換されるとバイナリのワードになり、機械語の命令を表現する
命令はコンピュータの命令メモリに格納される
コンピュータが命令を実行するたび以下の一連の処理が行われる
CPUは命令メモリから命令をフェッチし（読み込み）
命令をデコード（解読）
指定された命令を実行
次に実行すべき命令の場所を計算
命令メモリの内容を変更すれば、コンピュータによってまったく別の操作を行うことができる
命令メモリに存在する命令は仕様に従う形式
命令とオペランドを表すためのコードはのワード数はコンピュータによって異なる（1,2,3ワードなど）
CPU
現在読み込まれているプログラムの命令を実行する役割
命令がCPUに指示すること
さまざまな計算を実行
メモリから値を読み書き
条件に応じてプログラム中の他の命令場所に移動
CPUはこのようなタスクを次に挙げる3つのハードウェアを用いて実行する
ALU
論理演算、算術演算を行う
レジスタ
レジスタはCPUの物理的内部に存在する
メモリは遠いうえにアクセスにステップが多い一方、レジスタへのアクセスは超高速
レジスタの数はメモリと比べて非常に小さいのでメモリアドレスのように位置を表すのに大量の情報を必要としない
わずかなビットでよいので機械語の命令フォーマットを短くできる
各レジスタは1ワードを保持することができる
CPUが異なればレジスタの役割や数や種類は変わる
データレジスタ
簡易メモリ用途
(a-b)*cを計算するときに(a-b)の結果を一時保存しておくなど
アドレスレジスタ
データ読み書きの際にはメモリアドレスが必要
現在の命令にアドレスが含まれるのではなく、1つ前の命令の実行結果に依存してアドレスが決定する場合、専用のレジスタにアドレス値を格納しておく
Hackコンピュータではデータ値、RAMアドレス、ROMアドレスのいずれかになる
プログラムカウンタレジスタ
プログラム実行時、命令メモリから次にフェッチすべき命令のアドレスがどこなのか、CPUは追いかける必要がある
このアドレスは、「プログラムカウンタ」または「PC」と呼ばれる特別なレジスタに保持される
PCにはアドレスが格納されており、このアドレスは命令メモリからフェッチを行うアドレスである
現在の命令を実行する過程でCPUはPCを更新する
現在の命令に「goto」命令が含まれなければ、プログラムの次の命令を指すようにPCの値はインクリメントされる
現在の命令に「goto n」命令が含まれれば、CPUはPCにnを書き込む
制御ユニット
バイナリコードの命令をデコードする
次にどの命令をフェッチして実行するか？という情報も保持する
CPUの命令はループ処理のようになる
命令（ワード）をフェッチ
解読（デコード）
実行する
ALUでの計算、レジスタの操作、メモリ読み込み・書き込み
次の命令をフェッチ
入出力
コンピュータの外の環境とインタラクティブにやりとりするため、コンピュータはI/Oデバイス（入出力装置）を用いる
スクリーン、キーボード、プリンタ、スキャナ、ネットワークカード、USBデバイスなど
メモリマップドI/O（memorymappedI/O）
すべてのデバイスがコンピュータにとってまったく同じに見えるようにする仕組み
その中でも最も単純な部類
I/Oデバイスのための領域をメモリ上に割り当てることでデバイスをCPUにとっては通常のメモリ領域のように見せかける
各I/Oデバイスにとって排他的なメモリ領域を確保し、専用の“メモリマップ”を構成する
入力装置の場合（キーボード、マウスなど）、デバイスの物理的な状況を常に“反映”するようにメモリマップを作る
出力装置の場合（スクリーン、スピーカなど）、デバイスの物理的な状況を常に“駆動”するようにメモリマップを作る
キーボードのキーを押す、マウスを動かすなど外部のイベントが入力装置に影響を及ぼした場合、対応するメモリマップに値が書き込まれる
操作したい場合（たとえば、スクリーンに何かを描画する、音を鳴らすなど）、対応するメモリマップに値を書き込む
ハードウェアの視点から考えると、各I/Oデバイスにメモリと同じインターフェイスを提供すれば、この仕組みを成り立たせることができる。ソフトウェアの視点から考えると、各I/Oデバイスにはインタラクション仕様が定義されている必要があり、それが定義されていればプログラムは正しい場所にアクセスすることができる。ちなみに、コンピュータプラットフォームとI/Oデバイスがたくさん存在することを考えると、「規格」が果たす役割がいかに重要であるか、ということがわかるだろう。メモリマップドI/Oは実用面で非常に重要である。なぜなら、CPUの設計やプラットフォーム全体の設計はI/Oデバイスとは完全に独立して行うことができるからである。つまり、I/Oデバイスの数や性質、その構成について考えることなく、CPUやプラットフォームを設計できる、ということである。もちろん、将来現れるであろうI/Oデバイスのことも考えなくてすむ。新しいI/Oデバイスをコンピュータに接続した場合、やるべきことは新しいメモリマップを割り当て、そのベースアドレスを覚えておくことだけである（この一度限りの設定は、通常オペレーティングシステムによって行われる）。これをさらに進めれば、どのようなプログラムであっても、I/Oデバイスを操作することができる。なぜなら、やるべきことはメモリ中のビットを操作することだけだからである。
ohbarye.icon インタフェースに対して実装せよ、めちゃめちゃ賢い
課題
Memory
KeyboardとScreenと接続
CPU
ohbarye.icon これまでで一番むずかしい
Computer
本の回路図がそのまま答えだった
ohbarye.icon 付録Bでテストの重要性を説いているのが良かった
この本にテストが付属しているのもそのためのようだ
補足
コンピュータは次のふたつに分類することができる
汎用コンピュータ（generalpurposecomputer）
プログラムの差し替えが容易に行えるように設計されている。
専用コンピュータ（dedicatedcomputer）
ゲーム端末やデジタルカメラ、武器システムや工場設備などのように他のシステムに埋め込まれたコンピュータ
この専用コンピュータでは、どのような用途であれ、単一のプログラムが専用のROMに書き込まれており、それが唯一実行されるプログラムである（たとえば、ゲーム端末の例では、ゲームソフトは外部のカートリッジに存在し、このカートリッジは交換可能なROMにすぎない）。以上の点を除けば、汎用コンピュータと専用コンピュータはアーキテクチャについて同じ構造――格納プログラム、「フェッチ/デコード/実行」のロジック、CPU、レジスタ、プログラムカウンタなど――に基づいている。
やらなかったこと
単一アドレス空間でデータと命令の両方を保持すること
ほとんどの汎用コンピュータではデータと命令の両方を格納するための単一のアドレス空間を用いる
Hackでは分離しているが、このために動的にプログラムを書き換えることができなくなっている
リアルRead Only
より複雑なI/O制御
一般的なスクリーンの動作原理は同じだが、、通常のコンピュータでは複数のビットを用いて輝度レベルやカラー制御を行っている
Hackスクリーンのメモリマップは単純であり、ピクセルとメモリ中のビットは直接マッピングされている
現代のほとんどのコンピュータでは、スクリーンを制御するためのグラフィックカードに高水準なグラフィック命令を送信することで描画を行う。このようにして、CPUは円や多角形などを描画するといった退屈な作業から解放される。グラフィックカードは、専用の回路セットを用いてそのような描画作業を行う。
最適化
コンピュータハードウェアの設計において、ほとんどすべての努力や創造性がパフォーマンスを向上させるために費やされる
メモリキャッシュ、I/Oデバイスへの高速アクセス、パイプライン、並列化、命令のプリフェッチ（先読み込み）、etc.
プロセッサのパフォーマンス向上における2つの歴史
CISC
「Complex Instruction Set Computing（複合命令セットコンピュータ）」の略
複雑な命令セットを提供しパフォーマンスの向上を達成することを目的としたアプローチ
RISC
「Reduced Instruction Set Computing（縮小命令セットコンピュータ）」の略
できるかぎり高速なハードウェア実装を行うために、より単純な命令セットが用いられる
6章 アセンブラ
ここからはソフトウェア階層
アセンブリ言語のコマンドと機械語には直接的な関連性がある
基本的には一つ一つ翻訳していけばよい
どのような言語でも書ける
ユーザー定義のシンボルを扱う必要がある
ユーザーの定義した変数名やラベルを実際のメモリアドレスへ対応づける処理は難しい問題である。実際、この「シンボル解決」は、ハードウェアのレベルからソフトウェア階層へと登る歩みにおいて、最初に遭遇する試練でもある
課題
まずはシンボルを扱わないアセンブリをアセンブルできるようにする
次にシンボルを扱えるようにする
symbol tableのinitializeで規定のシンボルとRAMアドレスをテーブルに突っ込む
ソースコードを2回parseする
1周目では(Xxx)のようなシンボルを見つけたらsymbol tableに突っ込む
このシンボルはジャンプ命令に使われる goto (Xxx)
命令の位置を記憶する必要があるので、このシンボル以外の命令（C or A命令）を見つけるたびにincrementしていく値がROMアドレスになる
プログラムカウンタで見ている行数と一致する
2周目ではparseした内容をバイナリとして吐き出しつつ、@Xxxのようなシンボルを見つけたらsymbol tableに突っ込む
こっちはRAMアドレスを予約されていない領域に割り当てていく
ohbarye.icon だんだんヘヴィになってきた
7章 バーチャルマシン#1：スタック操作
コンパイラを作るという作業は相当に困難である
高水準プログラムははじめに中間コードに変換される
中間コードは機械語に変換される
中間コードは実際のプラットフォームではなくバーチャルマシン Virtual Machine で実行される
移植性に優れる
write once, run anywhereというやつ
VMの実装方法はいくつかある
ソフトウェアであるインタプリタによるもの
専用に設計されたハードウェアによる方法
VMプログラムを対象プラットフォームの機械語に変換する方法
コンパイラを実装するには「高水準言語」と「機械語」ふたつの組み合わせに依存したプログラムを書かなければならない
対象とするコンピュータと言語の組み合わせに応じて、別のコンパイラが必要になる
「高水準言語」と「機械語」による依存性の分離
最初のステージで高水準言語をパースしてそのコマンドを中間コード（“高水準”でも“低水準”でもないコード）に変換
高水準言語の仕様だけに依存
次のステージで中間コードを対象とするハードウェアの機械語に変換
対象とする機械語の仕様だけに依存
1970年代のPascalからJavaコンパイラ、.NETまで広く使われる
概念https://gyazo.com/b175f351714a05d6978aeaad763b0888
スタックマシン
VM言語の構成要素はプログラミング言語と類似している
重要な問いは「オペランドとVM命令の結果をどこに格納するか」
スタックマシンという計算モデルにおいては算術命令はスタックの一番上からオペランドを取り出す
単純だがどんな算術命令、論理命令でもこのモデルで評価器を実装できる
コンピュータサイエンスという分野においては、「シンプルさと優美さを兼ね備えたものは表現力も豊かである」というのが常である。
スタックのつかいかた
VMにおけるすべての算術命令と論理命令を扱うため
サブルーチン呼び出しとメモリ配置を行う（次章）
課題
まずはVMで算術とメモリアクセスのコマンドを実装する
VM実装の作業
対象のプラットフォーム上でVMの世界をエミュレートする
スタック、仮想メモリセグメント
VMコマンドを命令に変換する
VM命令から機械語へのマッピングを標準マッピングと呼ぶことにする
このマッピングを実現するソフトウェアを「VM実装」「VM変換器」と呼ぶことにする
スタック
VM命令で、とあるセグメントのメモリのデータを別のセグメントに単純に移動することはできない
move ${segment1} ${index1} ${segment2} ${index2}のようなことはできない
スタックを経由する必要がある
ヒープ
VMの背後に存在している、もうひとつのメモリ要素はヒープ
「オブジェクト」と「配列」を格納するためのRAMの専用領域
この「オブジェクト」と「配列」はVMコマンドによって操作することができる
メモリアクセスコマンド
前提
RAMの0番地をスタックポインタ@SPとする
初期値256
各セグメントにも初期値を与えて領域を確保しておく
@LCL @ARG @THIS @THATにメモリアドレスを入れておく
indexはVM命令として与えられるのでVM変換器では数値の管理をしなくてよい
indexが{0,4,6}のようにdistancingに与えられても気にしない
push
push ${segment} ${index}
constant
indexを即値としてスタックにpushする操作
e.g. push constant 1
メモリアドレス@SPに${index}を書き込む
stackのtopの1つ先を指す
@SPをインクリメントする
local, argument, this, that
from segment[index] to スタックという操作
indexは各segment内でのインデックス
push to segmentではない
e.g. push local 0
メモリアドレス@LCL+0の値を読み込む
メモリアドレス@SPに${index}を書き込む
@SPをインクリメントする
pop
pop ${segment} ${index}
e.g. pop local 0
@SPをデクリメントする
メモリアドレス@SPの値を読み込む
デクリメントしているのでstackのtopを指す
メモリアドレス@LCL+0に値を書き込む
8章 バーチャルマシン#2 : プログラム制御
スタックによって複雑な仕事をこなすことができる
ネスト化されたサブルーチン呼び出し、引数の受け渡し、再帰処理、メモリ割り当て
プログラムフロー
条件分岐
スタックの最上位の値でジャンプ先を決定する
サブルーチン
フレーム
呼び出すたびに関数フレームを（概念上の）スタックに突っ込む
フレームとは、サブルーチンのローカル変数・引数・メモリセグメント・ワーキングスタックなどサブルーチンごとの実行に必要な状態の集合を指している
グローバルスタック
現在のサブルーチンとそのリターンを待つ他のすべてのサブルーチンのためのフレームを含むメモリ領域
現サブルーチンのワーキングスタックはグローバルスタックの一番上に置かれる
call X
呼び出し側のフレームをスタックに格納する
呼び出された側のローカル変数のためのメモリ領域を確保する
サブルーチンのコマンドを実行する
ラベルXへジャンプする
return
戻り先は関数を呼び出したcallの次の行で、これをリターンアドレスと呼ぶ
呼び出すタイミングでリターンアドレスをグローバルスタックにpushする
returnコマンドに出くわしたらpopし、ジャンプする
ブートストラップ
複数の.vmファイルを変換して1つの.asmファイルになる
VM変換器が生成する.asmにおいて最初に実行される命令はSys.init関数の呼び出し
スタックポイントの初期化も行っておく必要がある
ROMアドレス0から始まるコードセグメントをブートストラップコードと呼ぶ
9章 高水準言語
Jack言語の仕様解説
ohbarye.icon どうせ後の課題で見るのでスッと読み飛ばした
10章 コンパイラ#1 : 構文解析
コンパイルとはソース言語で書かれたプログラムをターゲット言語に変換すること
変換プロセスは概念的に2つの作業に基づく
構文解析
ソースプログラムの構文を理解し、プログラムの意味を明らかにすること
さらに2つのモジュールに分かれる
トークナイザ tokenizer
ソースコードに対して意味を持つコードの最小単位であるトークン（字句）に変換
パーサ parser
一連のトークンを言語の構文ルールに適合させて構文構造を明らかにする
構文解析の作業はターゲット言語と完全に独立している
解析結果をコード生成に使わずにXMLに出力したりしても良い
ohbarye.icon FormatterとかLinterとか
コード生成
構文解析器を作るために必要なコンセプト
字句解析 lexical analysis
単に文字が並べられたものであるプログラムを読み込み、文字のグループをトークン（言語の構文として定義済）としてまとめること
スキャニング scanning、トークナイズ tokenizingとも呼ばれる
code:c
while (count <= 100) {
count++;
// Body
...
}
のようなプログラムを
while ( count <= 100 ) { ( count ++ ; ...
文脈自由文法 context-free grammer
プログラミング言語は通常、文脈自由文法と呼ばれる生成規則によって記述される
文脈自由文法は、ある言語の構文要素がより単純な要素からどのように構成されるかを指定したルールの集合
構文木 parse tree
文法ルールは階層構造であり、パーサの出力は木のデータ構造になる
https://gyazo.com/bc84a3b9e1b2bd8abd086d50e61f64aa
再帰下降アルゴリズム
その他にも理解すべきコンピュータサイエンスのトピックがある
言語変換と構文解析
木やハッシュテーブルなどのデータ構造
再帰的なコンパイルアルゴリズム
なぜコンパイラを作るのか？
コンパイラの内側を知ることによって、より優れたプログラマーになれる
プログラミング言語を記述するために使われるルールや文法は、他の分野においても応用できる
コンピュータグラフィックスやデータベース管理、通信プロトコルやバイオインフォマティクスなど、さまざまな分野に及ぶ
ほとんどのプログラマーは仕事でコンパイラの開発は行わない一方で、複雑な構文を持つファイルの構文解析や処理操作を行う必要が出てくるであろう。そのような作業では、本章で述べるような技術（プログラミング言語の構文解析のための技術）が使われる。
ohbarye.icon 心に響いた
構文解析
文法が入力テキストを正しいものとして受理するか確認する作業
テキストと文法のルールの間での正確な対応関係を決定する
再帰下降構文解析 recursive descent parsing
構文木を構築するアルゴリズムの一つ、トップダウン的なアプローチ
言語の文法によって規定されるネスト化された構文を使い、トークン列に対して再帰的に構文解析を行う
LL(1)文法
再帰下降アルゴリズムはシンプルだが、非終端記号（最小単位のトークン以外）をパースする際に複数の可能性があるのが複雑
文を構文解析しようとしたときにその文がwhileなのかifなのかを事前に知ることはできない
複数の選択肢は文法によって決められていて、ある場合は簡単に決定することができる
トークン列の最初がwhileから始まる場合、while文であることは明らか
whileというトークンで始まる生成規則は文法中に1つしか存在しないため
非終端要素の種類を決めるにあたり、いくつかの選択肢があった場合、最初のトークンだけから、そのトークンの種類を決定することができる。この性質はLL(1)とも呼ばれる。この性質を満たす文法は、再帰下降アルゴリズムによって簡単に扱うことができる。
最初のトークンだけから要素の種類を決定できない場合、次のトークンを“先読み”することで、問題を解決できるかもしれない。そのようなパースを行うことは可能ではあるが、より多くのトークンを先読むに従って、物事は複雑になる。
これから示すJack言語の文法はほとんどLL(1)であり、再帰下降を行うパーサによって比較的簡単に扱うことができる。唯一の例外は式をパースするときであり、その場合は先読みが必要になる。
課題
と思ったらこんな文があったのでゴリゴリ書いていくことにする
構文解析器はスタンドアロンなプログラムではないこと、構文解析器をゼロから書くことはめったにないこと、を追記しておく。プログラマーは通常、LEX（lexicalanalysis）やYACC（YetAnotherCompilerCompiler）などの“コンパイラ生成器”を使ってトークナイザやパーサを作る。それらのツールは文脈自由文法を受け取り、その文法で書かれたプログラムをトークン化し、パースすることができる構文解析コードを出力する。生成されたコードは、コンパイラのニーズに適応するようにカスタマイズすることができる。本章では、我々が掲げる“中身を理解する”精神に則り、そのようなツールをブラックボックスとして使用することは避け、ゼロからすべてを構築した。
11章 コンパイラ#2 : コード生成
高水準言語をVM命令へ変換する
アセンブリへの変換は遠すぎる
VM命令ですら大きな溝がある
プログラムは、本質的には、データを操作する一連の命令である。そのため、高水準言語から低水準言語へのコンパイル作業は、主にふたつの変換に焦点が当てられる。ふたつの変換とは、データ変換（datatranslation）とコマンド変換（commandtranslation）である。
シンボルテーブル
その識別子はソースプログラムにおいて何を表しているのか、そして、その識別子は対象言語でどの構成要素に対応するか、ということを記録する必要がある。ほとんどのコンパイラはこの情報をシンボルテーブルを用いて記録する。ソースコードで初めて新しい識別子に出くわすたびに（たとえば、変数の宣言など）、コンパイラはそのテーブルにその識別子を追加する
探索するスコープを広げていく
ローカル変数->クラス変数->グローバル変数...
データ変換
変数操作
様々な型をプラットフォーム上へどのように対応づけるか
変数の型が異なれば必要なメモリサイズが異なる
変数の属性が変わればライフサイクルも異なる
変数のメモリ割り当てはこれまでに実装したVM変換器、コンパイラのバックエンドで行う
割当と破棄に関する詳細はグローバルスタックと仮想メモリセグメントを使ってVMのレベルで扱われる
配列操作
オブジェクト操作
コマンド変換
式の評価
フロー制御
12章 オペレーティングシステム
13章 さらに先へ