コンピュータシステムの理論と実装

https://www.oreilly.co.jp/books/9784873117126/

概要

本書は NAND ゲートを用いてハードウェアを作り，その上で動作するシステムを構築する． つまり，NAND ゲートからボトムアップでコンピュータを作り上げる経験を得ることができる． 構築には本書用に用意されたハードウェアやシンプルな VM，高水準言語を用いる． これを通じてコンピュータシステムの overview を手に入れることができる．

原著は 2005 年出版であるためモダンではない部分が多くあるだろうが，本書の目的はあくまでコンピュータシステムの overview を提供することにある． モダンな構成を知りたい人に本書は向かない．

感想

ソフトウェアエンジニアとして普段から Web アプリケーションの開発運用を行っているが，実際にアプリケーションが細部レベルでどのように動作しているかを意識する必要はない． 細部を意識しなくても動作するのは正しいが，そのままの開発運用を続けていてもエンジニアとしてのレベルを上げられるイメージを抱けなかったため，低レイヤを知るという目的で取り組んだ． 本書では実際に低レイヤから積み重ねて開発するため，上位のレイヤでは低レイヤを意識しないで済むことを実感できた． 本書を通してコンピュータシステムの overview を手に入れたことにより，コンピュータシステムの知識を深めていくためのネクストアクションの方針がより明確になった． このため，コンピュータシステムの overview を持っていない人がまず取り組む本としておすすめできる． また，ものづくりを行う際にできるだけ作りやすくなるよう分割した上で作るという観点でも得られるものがあるため，開発経験があまりない人にもおすすめできる．

コード

https://github.com/4m1t0/nand2tetris

詳細メモ

本書は本書用に単純化された言語を用いている． 実装はそれらの仕様に依存するが，ここではそれらに依存した内容のメモは記さない．

1 章　ブール論理

コンピュータはスイッチング素子の上で動作する． スイッチング素子はゲートの機能が実現するように設計されている． コンピュータとしては 0/1 の入力に対して出力を出すことができるものであれば何でも良く，スイッチング素子が何から作られようと問題ない．

本章ではスイッチング素子の上で動作するブールゲート（ブール関数を物理的に実現したもの）と呼ばれる単純な回路に焦点を当てる． ブール関数は入力としてブール値を受け取り，ブール値を返す関数である． どのようなブール関数でも NOT, AND, OR が使用可能であれば，正準表現と呼ばれるブール式で表現可能である．

本書では NAND ゲートは与えられており，まずは NAND ゲートを利用して NOT, AND, OR を実装し，その後 XOR, Multiplexor, Demultiplexor を実装していく． 実際に真理値表を書き，それを満たせるようなゲートを本書用ハードウェア記述言語で構築する． この際カルノー図を用いるとシンプルなゲートを書くことができる．

2 章　ブール算術

本章では前章で作成した論理回路を用いて算術演算を実装する．

nn 桁の 2 進数は 2n2^n 通りのビット配列を生成できる． この配列を用いて均等な正数から負数の範囲（e.g. -128~127）を表したい． 現代のコンピュータではほぼ 2 の補数表現を採用し，これを達成している．

2 の補数表現で正数の最上位ビットは 0，負数の最上位ビットは 1 で，2 の補数表現の最大値最小値はそれぞれ 2(n−1)−12^{(n-1)} - 1 と −2(n−1)-2^{(n-1)} である． xx から −x-x を得るためには最下位ビットから桁を確認していき，1 が出現するビットに遭遇したら，その 1 の場所より上位のビットを全て反転させる (e.g. 0110 → 1010)． 2 の補数表現では演算対象の正負を気にすることなく行うことができる． 例えば (−2)+(−3)=−5(-2)+(-3)=-5 は 2 の補数表現で (1110)2+(1101)2=(1011)2(1110)_2 + (1101)_2=(1011)_2 となる．

この性質を用いて本章では 2 つのビットの和を求める半加算器，3 つのビットの和を求める全加算器，入力に 1 を加えるインクリメンタ，そして 1, 2 章で作成した論理演算・算術演算を実行できる ALU（算術論理演算器）を作成する．

3 章　順序回路

1, 2 章で作成した組み合わせ回路は状態を持つことができない． しかしながらコンピュータは値を保存し呼び出すことができなければならない． 本章では状態を持つための機構を構築する．

ほとんど全てのコンピュータでは，2 値 (low/high, tick/tock) で表現可能な継続的に変化する信号をマスタクロックが送信することによって時間の経過を表現する． tick の始まりから次の tock の終わりまでに経過した時間を周期と呼び，このクロックの 1 周期を単位時間としてモデル化する．

コンピュータで利用される順序回路の中で最も基本的なものはフリップフロップである． 実際に状態管理を実装するには同期，クロッキング，フィードバックループなどが複雑に関係するみを構築する必要があるが，本書では D 型フリップフロップを与え，この複雑さをブラックボックス化する． D 型フリップフロップのインターフェイスは 1 ビットの入力とクロック入力，そして 1 ビットのデータ出力である． これにより D 型フリップフロップは時間に基づく振る舞いを表現可能になる． この振る舞いは out(t)=in(t−1)out(t)=in(t-1) という式で表され， inin と outout は D 型フリップフロップの入出力を，tt は現在の単位時間を表す． つまり，D 型フリップフロップは 1 つ前の単位時間の入力を出力している．

次にレジスタを考える． レジスタとはデータを格納したり，呼び出すことができる記憶装置である． レジスタはストレージの振る舞いとして out(t)=out(t−1)out(t)=out(t-1) を実現する． 1bit レジスタを n 個並べることで n ビットの値を保存でき，そうした値をワードと呼ぶ．

任意の数のワードを記憶できる機構をメモリと呼ぶ． メモリに n ビットレジスタを任意の個数を積み重ね，それらに他と重複しないユニークなインデックス (0 から l-1 までの整数) をアドレスとして割り当てる． そしてアドレス j に対して j 番目のレジスタを個別に選択できる論理ゲートを構築する． このような構造のメモリを RAM (Random Access Memory) と呼ぶ．

コンピュータを動作させる上ではメモリに演算を格納しておき，逐次演算を処理していく必要がある． これを実現するのがカウンタである． カウンタは単位時間が進むごとに out(t)=out(t−1)+cout(t)=out(t-1)+c となるように定数 cc が加算される． 通常は c=1c=1 である． 一般にカウンタは，カウンタの値を 0 にする，新しいカウンタ値を読み込む，加算の代わりに減算を行うなどの機能を持つが，本書では考慮しない． メモリ上には演算が格納されており，カウンタの出力を次の演算のアドレスとして用いる．

1, 2 章で作成した組み合わせ回路は状態を持っておらず，与えられた入力に対して計算結果を出力する． 例えば x+yx+y という演算を行うとして，xx と yy のレジスタの距離が非常に離れていたとする． このとき距離，抵抗，干渉，ノイズなどにより xx と yy が ALU までに到達する時間は異なるため，計算結果が正しいとは限らない． 一方で，順序回路の出力は単位時間で離散化されている. 順序回路を経由して ALU に入力を行うようにし，かつクロックの単位時間をアーキテクチャ内で最も距離が長い回路間を移動する時間よりも少し長い時間とすれば，次の周期の始まりにおいて ALU が受け取る値は常に正しいことを保証できる． つまり，順序回路の出力は離散化されるという性質により，独立したコンポーネントを同期して動作させることができる．

4 章　機械語

ハードウェアを操作するための言語をアセンブリと呼ぶ． アセンブリはバイナリコードと記号や英単語で記されるニーモニックを用いて記される． アセンブリをバイナリコードに変換するプログラムはアセンブラと呼ばれる．

アセンブリの視点では演算実行とデータの保存・参照ができればよく，その詳細に関心はない． つまり，アセンブリを設計する際は CPU とメモリ操作の方法が明確であれば良い． ただメモリアクセスは比較的時間のかかる操作であり，命令コードのフォーマットも長くなりやすい． このためほとんどの CPU はレジスタをいくつか備えており，各レジスタは 1 つだけ値を保存できるようになっている． レジスタは CPU から近い場所にあるため，極めて高速にアクセスできる． これにより，プログラマはメモリアクセスを行うコマンドを減らし，プログラムの実行を高速化できる．

メモリアクセスはメモリに対してロード（読み込み）もしくはストア（格納）するときに行われる． メモリのアドレスを指定する方法をアドレッシングモードと呼び，それにはいくつかの種類がありえる． コンピュータによってアドレッシングモードの振る舞いや表現は変わることがあるが，一般に直接アドレッシング (direct addressing)，イミディエイトアドレッシング (immediate addressing)，間接アドレッシング (indirect addressing) はサポートされている．

  • 直接アドレッシング 以下のように直接アドレスを指定する，もしくはシンボルを用いて特定のアドレスを参照する方法．

    LOAD R1, 67  // R1 ← Memory[67]

// bar の参照する値が67であるとする．
LOAD R1, bar  // R1 ← Memory[67]

  • イミディエイトアドレッシング このモードでは命令中の数字領域をアドレスではなく定数として扱う．

    LOADI R1, 67  // R1 ← 67

  • 間接アドレッシング

    このモードではメモリのアドレスを命令中にハードコーディングせず，必要なアドレスを保持しているメモリ位置を命令によって指定する．

    // x=foo[j] もしくは x=*(foo+j) の変換
ADD R1, foo, j  // R1 ← foo+j
LOAD R2, R1  // R2  ← Memory[R1]
STR R2, x  // x  ← R2

通常プログラムにはループ処理や条件分岐，サブルーチンの呼び出しが含まれるため，これを実現するみも必要である． アセンブリでは，ある処理を行ったあとに指定された位置へ移動することでこれらの機能を実現する． 移動先にはシンボルを用いる場合があり，その場合，ラベルを指定する何かしらのシンタックスが用いられる． 以下にサンプルを示す． JMP beginWhile のような無条件分岐を行うコマンドは目的とする位置のアドレスを指定し，JNG R1, endWhile のような条件分岐ではブール条件を何かしらの方法で指定する必要がある．

// 高水準言語
while (R1 > 0) {
  code segment 1
}
code segment 2
// 低水準言語
beginWhile:
  JNG R1, endWhile  // もし R1 < 0 であれば endWhile へ移動
  ...  // "code segment 1" の変換コード
  JMP beginWhile  // beginWhile へ移動
endWhile:
  ...  // "code segment 2" の変換コード

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

ノイマン型コンピュータは CPU とメモリ，そして I/O デバイスからなる． メモリはデータと命令を保存し，CPU は演算とレジスタへの格納，そして次の命令のフェッチを行う．

I/O デバイスは CPU に繋ぐことができる． I/O デバイスにはデバイス用のメモリ領域を割り当てることで CPU はデバイスの実体を意識することなく，メモリと同様に操作することが可能になる． この仕組みをメモリマップド I/O と呼ぶ．

6 章　アセンブラ

アセンブリはバイナリとニーモニックで構成される． このためアセンブリをマシン上で動かすにはバイナリに変換する必要がある． これを実現する機能をアセンブラと呼ぶ．

アセンブラはニーモニックを適切なバイナリに変換できなければならない． ニーモニックは引数にメモリアドレスを格納している変数であるシンボルを取ることもできる． アセンブラはシンボルが指しているメモリ位置を考慮してバイナリコードに変換しなければならず，これを実現するためにはシンボルテーブルを用いる．

本書ではシンボルを含むアセンブリをバイナリコードに変換するため，アセンブリを 2 回読み込むことで上記問題に対応する． 具体的には，1 回目の読み込みではアドレス命令と計算命令を見つける度にメモリアドレスの値を 1 つずつ加算する． 途中で (Xxx) のような疑似コマンドを見つけた場合は，Xxx と現在のメモリアドレスの値をシンボルテーブルに追加する． 2 回目の読み込みでは逐次バイナリコードに変換していく． このとき @Xxx の Xxx がシンボルである場合はシンボルテーブルを参照し，存在する場合はそのメモリアドレスに置き換えてバイナリに変換する． 存在しない場合は新たな変数定義であるため，シンボルテーブルに Xxx と次に利用可能なメモリアドレスをシンボルテーブルに追加する．

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

本書では最終的に Jack 言語でアプリケーションを作成する． この Jack 言語はバーチャルマシン上で動作する． したがって本書では Jack 言語 -> 中間言語, 中間言語 -> アセンブリへの変換を行う必要がある． 本章では後者を扱う．

バーチャルマシンの採用にはいくつかのメリットがある． 1 つ目は別のプラットフォームで動作させる場合にバーチャルマシンの実装を差し替えるだけで済むこと． 2 つ目は VM コードをバーチャルマシン上で動作させるため，複数言語でのコードの共有が可能になること． また，バーチャルマシンはモジュールであるために，その性能が改善されたとき， VM コードに変換可能な高水準言語は全てその恩恵を受け入れられる．

VM コードは高水準言語と同様に算術操作，メモリ操作，条件分岐，サブルーチン呼び出しなどを実行できる必要がある． この実装にはスタックが適している． スタックは LIFO (Last In, First Out) なデータ構造であり，push と pop の 2 つの操作を行うことができる． スタックの一番上の次の場所はスタックポイントによって参照される． pop するときはスタックポインタの 1 つ前の場所の値を取得し，メモリからその値は削除される．

スタックを利用した計算モデルをスタックマシンと呼ぶ． スタックマシンで算術演算を行うにはスタックにオペランドを格納し，算術演算命令を実行するだけで良い． そうするとオペランドはスタックから pop され，スタックポイントに演算結果が push される．

バーチャルマシンは条件分岐やサブルーチン呼び出しも実行できる必要がある． これらの実装にもスタックが適している． スタックマシンで条件分岐を行うには，スタックの最上位にある値が 0 かどうかで次に実行する処理を決定すれば良い． 算術演算の結果はスタックの一番上に push される性質を利用すれば実現可能である．

次にサブルーチン呼び出しを考える． サブルーチンは自身の再帰も含め更にサブルーチンを呼び出すことができるが，ある時点では必ず末尾処理を実施している． したがってサブルーチンの結果をスタックに push し，その結果を用いて自然な形で処理を継続できる． サブルーチンを実行するには，まず呼び出し対象のサブルーチンの引数をスタックに push する． その次に呼び出し側のサブルーチンの状態を保存する． 具体的には return するためのアドレス，ローカル変数，引数，保持しているメモリセグメントの情報をスタックに push する． その後，呼び出されたサブルーチンのローカル変数のためのメモリ領域を確保する． 最後にシンボル経由でサブルーチンのアドレスに移動し，そのサブルーチンの処理を実行する． 処理が完了したらリターンアドレスにジャンプすることで呼び出し側の処理を再開できる．

9 章　高水準言語

Jack 言語の話． 特にメモはなし．

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

一般にコンパイラは構文解析とコード生成を行う 2 つのモジュールから成り，構文解析は更にトークナイザとパーサに分割できる． トークナイザはソースコードからトークンを抽出し，パーサはトークンの並びから構文構造を明らかにする． 構文構造が明確に定義されていれば，並びからその関係性を機械的に明らかにすることは可能である．

ほとんど全てのプログラミング言語は文脈自由文法によって定義されている． 文脈自由文法は，ある言語の構文要素がより単純な要素からどのように構成されるかということを指定したルールの集合である． 一般に文法ルールは再帰構造をしており，終端要素と非終端要素で構成される． 以下に C 言語の文法の一部を示す．

statement: whileStatement
            | ifStatement
            | ...  // 他の statement がくるかもしれない
            | '{' statementSequence '}'
whileStatement: 'while' '(' expression ')' statement
ifStatement: ...  // if の定義
statementSequence: ''  // 空のシーケンス (null)
                    | statement ';' statementSequence
expression: ...  // expression の定義
...  // さらに定義が続く

構文解析のためのアルゴリズムの 1 つに再帰下降構文解析がある． このアルゴリズムでは現在のトークンが非終端要素である場合は再帰的に構造解析を行い，終端要素である場合は出力を行う． このアルゴリズムは非常にシンプルであるが，例えば ( をパースする際には while, if，それとも { } で囲まれた文のいずれであるかを区別できない． 上記の文法の例では，( を利用しているのは while のみであることから，( は while 構文であることが明らかである． このように最初のトークンからそのトークンの種類を決定できる性質を LL(1) と呼び，この性質を持つ文法は再帰下降アルゴリズムを用いて容易に構文解析できる．

コード生成ではデータ変換とコマンド変換を行う必要がある． データ変換では整数やブーリアン，配列やオブジェクトなど様々な型を変数のライフサイクルやスコープ（ローカル変数，グローバル変数，スタティック変数，引数など）を意識した上で変換しなければならない． これらの情報はシンボルテーブルに記録する． 識別子のパースの際はシンボルテーブルを参照し，そのライフサイクルやスコープに相当するコードを生成する． データ変換の際は動作対象のプラットフォームに合わせて変数の型を対応付ける必要があるが，本書ではその処理は中間言語 → アセンブリの変換器で実装している． 配列は一般に連続したメモリ領域を確保する． 配列宣言ではその配列の先頭のアドレスをスタックに格納し，利用する際はその配列のメモリ領域に格納された値を参照する． オブジェクトについても，オブジェクトのフィールド変数は連続したメモリ領域を確保する． オブジェクトの例として以下を考える．

class Complex {
  int re;  // 虚数部
  int im;  // 実数部

  public Complex(int aRe, int aIm) {
    re = aRe;
    im = aIm;
  }

  public void mult(int c) {
    re = re * c;
    im = im * c;
  }
}

Complex a に対して mult を適用する場合，例として a.mult(5) を考える． このときコンパイラは呼び出し元のオブジェクトを隠れ引数として mult(a, 5) のように渡す． このためには動的コンパイルの場合は実行時に mult が a のオブジェクトに属しているかを決定し，事前コンパイルの場合はコンパイル時にそれを決定する必要がある．

次にコマンド変換を考える． コマンド変換では式の構文構造を解析し，その結果に従って変換先のコードを生成する必要がある． スタックベースのプラットフォームの場合は逆ポーランド表記法 (Reverse Polish Notation, RPN) で出力すれば良い． RPN では f(x, y) は push x, push y, call f のように表現する． 高水準言語では if や while, switch などによるフロー制御を行えるが，低水準言語では if-goto と goto の 2 つだけ用意されているのが一般的である． このためコンパイラは高水準言語のフロー制御を if-goto と goto だけを用いて再現しなければならない． とは言え，スタックの最上位の値を見て条件分岐をすればよいので複雑ではない．

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

オペレーティングシステムはコンピュータのハードウェアとソフトウェアシステムのギャップを埋めるために設計されている． 例えば Hello World という文字列をディスプレイに表示させるためには，ピクセルを特定の場所に描画する必要がある． このためには I/O デバイス用に確保されたメモリ上の適切な位置にビットを書き込む必要があるが，たかが文字列の表示にその操作を行うのは非常にコストが高い． このようなケースでソフトウェアとハードウェアの繋ぎこみの責務を担うのがオペレーティングシステムである．

本書のオペレーティングシステムは極端に単純化されているためメモはなし．

PreviousComputer SystemsNextComputer Applications

Last updated

Was this helpful?