XXIX 目 次 賞賛の声・ 訳者まえがき : NAND からテトリスへ・・ まえがき・ イントロダクション : こんにちは、世界の下側・ 1 章プール論理 1.1 背景・ V11 IX XI XIX 1 1 -1 1 1 -1 っ 1 っ 4 っ 4 プール代数・ 1.1.1 論理ゲート・ 1.1.2 実際のハードウェア構築・ 1.1.3 ハードウェア記述言語 (HDL) 1.1.4 ハードウェアシミュレーション・ 1.1.5 Nand ゲート・ 1.2.1 基本論理ゲート 1.2.2 多ビットの基本ゲート 1.2.3 多入力の基本ゲート・ 1.2.4 1.2 仕様・・ ク 工 ジ 装望ロ 実展プ つけ 4 1 り 1 -1 1

xxx 一目次 2 章プール算術 2.1 背景・ 2.2 仕様・・ 2.2.1 加算器 (Adder) 2.2.2 ALU ( 算術論理演算器 ) 2.3 実装・・ 2.4 展望 . 2.5 プロジェクト・ 7 っ 1 つっ 0 っ 0 っっ 0 2 3 章順序回路 3.1 背景・ 3.2 仕様・・ 3.2.1 D 型フリップフロップ・・ 3.2.2 レジスタ・ 3.2.3 メモリ・ 3.2.4 カウンタ・ 3.3 実装・ 3.4 展望・ 3.5 プロジェクト・ ワ 1 一 8 一一ト一 1 っっ 0 冖ー -4 -4 -4 4 ). 一り 1 り れっ 6 冖ー冖ー「ー 4 5 五ロ 章 4 4.1 背景・ 4.1.1 機械・ 4.1.2 に 1 ロロ 4.1.3 コマンド 4.2 Hack 機械語の仕様・・ 4.2.1 概要・・ 4.2.2 A 命令・・ 4.2.3 C 命令・・ 4.2.4 シンポル・ 4.2.5 入出力操作・ 4.2.6 シンタックスとファイルフォーマット・ 4.3 展望・・

目次ー xxxi 4.4 プロジェクト・ 5 章コンビュータアーキテクチャ 5.1 背景・ 5.1.1 プログラム内蔵方式・ 5.1.2 ノイマン型アーキテクチャ・ 5.1.3 メモリ 5.1.4 CPU ・・ 5.1.5 レジスタ・ 5.1.6 入出力・ 5.2 Hack ハードウェアのプラットフォーム仕様・・ 5.2.1 概観・ 5.2.2 CPU ・・ 5.2.3 命令メモリ・ 5.2.4 データメモリ・ 5.2.5 コンピュータ・ 5.3 実装・・ 5.3.1 CPU ・・ 5.3.2 メモリ 5.3.3 コンピュータ・ 5.4 展望・ 5.5 プロジェクト・ 6 章アセンプラ 6.1 背景・ 6.2 Hack アセンプリからバイナリへの変換の仕様・・ 6.2.1 構文規約とファイルフォーマット・ 6.2.2 命令・ 6.2.3 シンポル・ 6.2.4 例・ 6.3 実装・・ 6.3.1 Parser モジュール・・ 6.3.2 Code モジュール・ ・ 79 -6 一つい冖ー一 8 一・ 1 っ 1 っ 1 4 1 り一 0 一 1 っ 4 一り「ー 5 8 1 1 -1 1 1 -1 -1 111 112 116 117 118 120 121 121 ・ 123 124

XXXii 一目次 6.3.3 6.3.4 6.3.5 展望・ シンポルを含まないプログラムのためのアセンプラ・ SymboITabIe モジュール・・ シンポルを含むプログラムのためのアセンプラ・ 6.4 6.5 7 章 7.1 7.2 7.3 7.4 7.5 8 章 8.1 8.2 プロジェクト・ バーチャルマシン # 1 : スタック操作 背景・ 7.1.1 バーチャルマシンの理論的枠組み・ 7.1.2 スタックマシン・ VM 仕様 ( 第 1 部 ) 7.2.1 7.2.2 7.2.3 7.2.4 7.2.5 7.2.6 実装・・ 7.3.1 7.3.2 7.3.3 展望・ 概要・ 算術と論理コマンド・ メモリアクセスコマンド・ プログラムフローと関数呼び出しコマンド・ Jack-VM-Hack プラットフォームにおけるプログラム要素・・ プログラムの構造・ VM 実装の設計案・・ VM プログラムの例・ Hack プラットフォームの標準 VM マッピング ( 第 1 部 ) プロジェクト・ 7.5.1 7.5.2 7.5.3 7.5.4 実装についての提案・ ツール・ 助言 テストプログラム・ バーチャルマシン # 2 : プログラム制御 背景・ 8.1.1 プログラムフロー VM 仕様 ( 第 2 部 ) 8.1.2 サプルーチン呼び出し・ 125 125 ・ 126 ・ 127 128 133 135 ・ 135 137 ・ 142 142 143 144 146 ・ 147 ・ 148 154 ・ 154 158 158 ・ 160 162 ・ 163 164 ・ 164 166 ・ 174 ・ 170 ・ 169 ・ 167 167

8.3 8.4 8.5 9 章 9.1 9.2 9.3 9.4 9.5 8.2.1 8.2.2 8.2.3 8.2.4 実装・・ 8.3.1 8.3.2 8.3.3 展望・ プログラムフローコマンド 関数呼び出しコマンド・ 関数呼び出しプロトコル・ VM 実装の設計案・・ 例・ 初期化・ Hack プラットフォームの標準 VM マッピング ( 第 2 部 ) プロジェクト・ 8.5.1 テストプログラム・ 8.5.2 助言 高水準言語 背景・ 9.1.1 9.1.2 9.1.3 9.1.4 9.2.1 9.2.2 9.2.3 9.2.4 9.2.5 9.2.6 9.2.7 例 1 : Hello WorId ・・ 例 4 : リンクリストの実装・・ 例 3 : 抽象データ型・・ 例 2 : 手続きプログラムと配列処理・ Jack 言語仕様・ シンタックス要素・ プログラム構造・ 変数・ 文・ 式・・ サプルーチン呼び出し・ Jack 標準ライプラリ・ 9.5.1 Jack プログラムのコンパイルと実行・ プロジェクト・ 展望・ Jack アプリケーションを書く・ 目次ー xxxiii ・ 210 ・ 208 ・ 207 ・ 206 ・ 202 ・ 200 199 ・ 199 198 194 193 192 ・ 192 191 188 186 185 ・ 184 184 181 177 176 176 175 174 174 ・ 221 ・ 219 ・ 218 ・ 216

XXXiV 一目冫欠 10 章コンバイラ # 1 : 構文解析 10.1 背景・ 10.1.1 10.1.2 10.1.3 川 .2 仕様・・ 10.2.1 10.2.2 10.2.3 川 .3 実装・・ 10.3.1 10.3.2 10.3.3 10.4 展望・・ 字句解析・ 文法・ 構文解析・ Jack 言語のための構文解析器・・ Ja. ck 言語の文法・ 構文解析器への入力・ 10.2.4 構文解析器の出力・ JackAnalyzer モジュール・ JackTokenizer モジュール・ CompilationEngine モジュ 11 章コンバイラ # 2 : コード生成 10.5.3 第 2 段階 : パーサ・ 川 .5.2 第 1 段階 : トークナイザ・ 10.5.1 テストプログラム・ 10.5 プロジェクト・ 11.1 背景・ 11.1.1 11.1.2 11.2 仕様・・ 11.2.1 11.2.2 11.3 実装・・ 11.3.1 11.3.2 11.3.3 11.3.4 1 工 3.5 データ変換 . コマンド変換・ バーチャルマシンへの標準マッピング・ SymbolTabIe モジュ JackTokenizer モジュール・ JackCompiler モジュ コンノヾイルの例 CompilationEngine モジュ VMWriter モジュール・・ 223 ・ 268 ・ 268 ・ 266 ・ 266 ・ 266 ・ 264 ・ 264 ・ 261 ・ 261 ・ 258 ・ 251 ・ 250 249 ・ 247 ・ 246 ・ 244 ・ 243 ・ 242 ・ 240 ・ 239 ・ 239 ・ 237 ・ 236 ・ 235 ・ 234 ・ 232 ・ 231 ・ 229 ・ 227 ・ 226 ・ 224

11.4 展望・・ 11.5 プロジェクト・ 11.5.1 第 1 段階 : シンポルテープル・ 11.5.2 第 2 段階 : コード生成・ 11.5.3 テストプログラム・ 12 章オペレーティングシステム 12.1 背景・ 12.1.1 12.1.2 12.1.3 12.1.4 12.1.5 12.1.6 12.1.7 数学操作・ 数字の文字列表示・ メモリ管理・ 可変長な配列と文字列・ 入出力管理・ グラフィック出力・ キーポード操作・ 12.2 Jack OS の仕様・・ 12.2.1 12.2.2 12.2.3 12.2.4 12.2.5 12.2.6 12.2.7 12.2.8 12.3 実装・・ 12.3.1 12.3.2 12.3.3 12.3.4 12.3.5 12.3.6 12.3.7 12.3.8 Math ・・ String ・・ Array ・・ Output ・・ Screen ・ Keyboard ・ Memory ・ Math ・・ String ・・ Output ・・ Screen ・ Keyboard ・ NIemory ・ 目次ー xxxv ・ 269 ・ 270 271 272 ・ 273 277 ・ 279 ・ 279 ・ 283 284 ・ 288 ・ 288 ・ 289 ・ 294 ・ 307 ・ 306 ・ 306 ・ 305 ・ 305 ・ 304 ・ 304 ・ 303 ・ 302 ・ 302 ・ 301 ・ 3 ( ) 1 ・ 300 ・ 299 ・ 299 ・ 298 ・ 297 ・ 297

XXXVi 一目冫欠 12.4 展望・ 13.3 高水準言ロロ 13.2 ハードウェアの改良・・ 13.1 ハードウェアの実現・・ さらに先へ 12.5.2 OS クラスとテストプログラム・ 12.5.1 テスト方法・ 12.5 プロジェクト・ 13 章 13.5 通信・・ 13.4 最適化・・ 付録 A ハードウェア記述言語 (HDL) A. 1 A. 2 A. 3 A. 4 A. 5 A. 6 A. 8 A. 9 例題・・ 規則・ ハードウェアシミュレータへの回路の読み込み・ 回路へッダ ( インターフェイス ) 回路ボディ ( 実装 ) A. 5.1 パーツ・ A. 5.2 ピンと接続・ A. 5.3 バス・ ビルトイン回路・・ A. 7 順序回路・・ A. 7.1 クロック・ A. 7.2 クロック回路とピン・ A. 7.3 フィードバックループ・ 回路操作の視覚化・ 新しいビルトイン回路・・ B. 2 ユ例・・ B. 2 ハードウェアシミュレータでの回路テスト・ B. 1 ファイルフォーマットと使用方法・・ 付録 B テストスクリプト言語 ・ 308 ・ 309 ・ 310 ・ 311 315 ・ 316 ・ 316 ・ 317 ・ 342 ・ 342 ・ 340 339 ・ 335 ・ 332 ・ 331 ・ 330 ・ 329 ・ 328 ・ 326 ・ 325 ・ 324 ・ 323 ・ 323 ・ 322 ・ 321 ・ 321 ・ 319 319 ・ 317 ・ 317

B. 2.2 B. 2.3 B. 2.4 B. 2.5 B. 2.6 データ型と変数・ スクリプトコマンド ビルトイン回路の変数とメソッド・ 最後の例・ デフォルトスクリプト・ B. 3 B. 4 CPU 工ミュレータでの機械語プログラムのテスト・ VM 工ミュレータでの VM プログラムのテスト・・ B. 3.4 デフォルトスクリプト・ B. 3.3 コマンド B. 3.2 変数・ B. 3.1 例・ B. 4.1 B. 4.2 B. 4.3 B. 4.4 例・ 変数・ コマンド デフォルトスクリプト・ 付録 C Nand2tetris S0ftware Suite の使い方 コラム目次 ソースコード・ 使用方法・・ ソフトウェアツールの実行方法・・ Nand2tetris ソフトウェアツール・ ソフトウェアについて・・ 索引・ C. 5 C. 4 C. 3 C. 2 C. 1 フィードバックループの有効 / 無効・・ 回路の " クロック " 属性・ API 表記についての注意点・ 目冫欠ー XXXVii ・ 343 ・ 344 ・ 348 ・ 350 ・ 352 ・ 352 ・ 352 ・ 353 ・ 354 ・ 354 ・ 355 361 ・ 359 ・ 359 ・ 357 ・ 356 ・ 332 ・ 330 ・ 122 ・ 373 ・ 371 ・ 368 ・ 367 ・ 362 ・ 362

索 引 己号 1 三ロ ・・・ 9 , 319 イはっ 1 2 進数・・ 2 値・・ 2 値素子・・ 2 の補数・・ ・・ 218 , 220 ・・・ 200 ・・・ 210 ・・ 161 ・・・ 161 Jack OS ・・ Jack のシンタックス要素・・ Jack 標準ライプラリ・ Java Runtime Environment ・ ・・ 68 JRE ・・ ・・ 31 , 34 ・・・ 123 A 命令・・ ALU ・・ API ・・ ・・ 138 ・・・ 231 ・・ 28 LIFO ・ LL(I) 文法・・ ・・・ 279 LSB ・・ 法 一三ロ CISC ・・ CPU ・・ CPU 工ミュレータ・ ・・ 28 ・・・ 361 Nand2tetris Software Suite ・・ D 型フリップフロップ・・ ・・・ 42 , 48

ー索引 374 キーポード・ キーポード操作・・ 機械語 ・・ 136 基数の補数・ 基本論理ゲート・ 逆ポーランド表記法・・ ・・ 44 組み合わせ回路・ グローノヾルスタック・ ・・・ 107 クロック・ 計算命令・・ 形式言語・ ゲート・ ・・ 133 後置表記法・・ ・・ 166 構文解析・ ・・・ 134 構文解析器・・ 構文木・ コード生成・ コマンド変換・ ・・ 62 , 112 ・・ 62 コンノヾイラ ・・ 62 , 112 コンノヾイル・ ・・ 61 ・・ 68 ・・ 91 ・・ 63 最下位ビット・ ・・ 64 再帰下降構文解析・・ ・・ 7 最上位ビット・ サプルーチン呼び出し・ ・・・ 221 算術論理演算器・・ ・・・ 291 式の評価・ ・・・ 256 ・・ 61 字句解析・ 終端記号・ ・・・ 277 出力ピン・ 順序回路・・ 条件分岐・ 乗算・・ ・・・ 285 ・・ 6 除算・・ シンボル・ ・・・ 322 シンボル解決・ ・・・ 323 シンポルテープル . ・・ 52 ・・ 31 真理値表・・ スイッチング素子・ ・・・ 133 スキャニング・ ・・ 133 ・・・ 254 スクリーン・ ・・ 64 スタック・ ・・ 76 , 98 ・・・ 294 ・・ 61 ・・ 29 ・ XXI ・・・ 259 ・・ 41 , 47 , 328 ・・・ 177 ・・ 42 , 329 ・・ 68 ・・・ 243 ・・ 5 , 6 ・・・ 259 223 , 229 ・・ XXV, ・・・ 223 ・・・ 229 ・・・ 223 ・・・ 258 ・・ 133 ・ XXI p コード・ RAM ・ RISC ・・ タ レ 】エ変 あ行 アセンプラ・ アセンプリ アセンプリ言語 . アドレス・ アドレス命令・ アドレスレジスタ・ アドレッシングモード・ イミディエイトアドレッシング・ インターフェイス・ 工ラーコード 円描画・ オプジェクト操作・ オペランド オペレーティングシステム・ か行 ガーベッジコレクション・ 回路・・ 回路へッダ・・ 回路ボディ・ カウンタ・ 加算器・・ 仮想機械・ 仮想マシン・ 間接アドレス指定・・ 間接アドレッシング・・ さ行 ・・ 28 ・・・ 230 ・・ 28 ・・ 65 ・・・ 31 , 34 ・・・ 258 ・・・ 226 ・・・ 236 ・・・ 325 ・・ 41 , 46 , 49 , 328 ・・ 65 ・・・ 280 ・・・ 281 ・・ 74 , 113 ・・ 114 ・・ 111 , 251 ・ XXI ・・・ 226 ・・ 75 ・・ 134 , 137

スタックコマンド スタック処理・・ ・・ 46 , 332 ・・ 11 , 324 ・・・ 9 , 319 ・・ 17 , 325 た行 スタックマシン・ データレース・ データメモリ 直線描画・ 直接アドレッシノグ 抽象データ型・・ 抽象化・ 中間言ロロ き五 中央演算装置・・ チップ・・ 多ビットバス・ タイムユニット・ 専用コンピュータ・ 全加算器・・ セル・ 正準表現・ 制御ユニット 制御ビット・ トランジスタ・ トークン化・ トークナイザ・ 動的メモリ割り当て・ 導出木・・ デマルチプレクサ・ 手続き型プログラミング・ テストスクリプト言 テスト・ データレジスタ・ ノイマン型コンピュータ・ ノイマン型アーキテクチャ・ 入力ピン・ ーモニック・ 内部ピン・ な行 ・・ 144 ・・・ 134 ・・ 137 ・・ 34 ・・ 89 ・・ 61 ・・ 32 ・・ 106 ・・・ 329 ・・・ 325 ・・ 6 ・・ 61 , 87 は行 ノヾーチャルマシン・ ハードウェアアーキテクチャ・ ハードウェア記述言語・ ハードウェアシミュレータ・ 索引ー ・ XXV , ・・ 136 , 161 375 ・・ 136 ・ XXII ・・・ 138 ・・ 63 ・・・ 290 ・・ 66 ・・ 90 .. 12 ・・・ 339 ・・ 193 ・・ 17 ・・・ 229 ・・・ 224 ・・・ 226 .. 5 ・・ 62 ・・・ 325 ・・ 86 ・・ 87 ・・ 254 , 284 排他的論理和・ 反復・・ 万能チュ 半加算器・ ノヾック、エン バス・ 配列操作・ バイナリ値・ ノヾイナリ バイトコード・ ド・ ーーリングマシン・ 非終端記号・ ピクセル描画・ ヒープ・・ 汎用コンピュータ・ プログラムカウンタ・ フロー制御・ フリップフロップ・ フ。ッシュ・ 複合ゲート・ フェッチ・ プール値・ プール代数・ プールゲート プール関数・ プートストラップコード・ ビルトイン回路・ 標準マッピング・・ 変数シンポル・ べースアドレス・ 平方根・・ 文脈自山文法・・ フロントエンド プロセッサ・ プログラム内蔵方式・・ プログラムカウンタレジスタ・ ・・・ 224 133 ・ XXI ・・ 12 ・・ 10 ・・ 112 ・・・ 254 ・・ 31 ・・ 87 ・・ 65 ・・ 106 ・・・ 285 ・・・ 289 ・・・ 236 ・・ 49 ・・・ 155 ・・ 136 , 161 ・・・ 260 ・・ 42 ・・ 138 ・・ 52 ・・・ 180 ・・・ 326 ・・・ 46 , 93 ・・ 75 ・・・ 113 ・・ 64 ・・・ 282 ・・ 161 ・・ 61 ・・ 86 ・・ 91 ・・ 226 , 227

376 ー索引 変数操作・ ポインタ・ ポップ・・ レ カ一 出ュ 字ジ 文モ つひ -4 一 8 一 一りっ 0 っ 4 ・・・ 293 ・ XXII や行 ま行 ラベル・ ・・ 16 ラベルシンボル・ レジスタ・ ・・ 65 ・・ 66 ロケーション・ 論理ゲート ・・ 44 , 51 , 61 面理設計・ ・・ 144 ・・・ 284 ・・・ 156 ・・ 75 ワード・ ・・ 91 つけ -4 ( 1 、 1 一りー -4 -4 マルチプレクサ・ 無条件分岐・ 命令メモリ・ メモリ メモリアクセスコマンド・ メモリ管理・ メモリセグメントマッピング・ メモリマップ・ メモリマッブド I/O ・ わ行 ・・・ 44 , 61

コンビュータシステムの理論と実装 モダンなコンピュータの作り方 2015 年 3 月 23 日初版第 1 刷発行 著 訳 発 制 行 者 者 人 作 印刷・製本 発 行 所 「兀 Noarn Nisan ( ノーム・ニッサン ) Shimon Schocken ( サイモン・ショッケン ) 斎藤康毅 ( さいとうこうき ) テイム・オライリー 株式会社トップスタジオ 日経印刷株式会社 株式会社オライリー シャノヾン 〒 160 ー 0002 東京都新宿区坂町 26 番地 27 インテリジェントプラザビル IF TEL ( 03 ) 3356 ー 5227 FAX ( 03 ) 335 い 5263 電子メール japan@oreilly.co.jp 株式会社オーム社 〒 101 ー 8460 東京都千代田区神田錦町 3 ー 1 TEL ( 03 ) 3233 ー 0641 ( 代表 ) FAX ( 03 ) 3233 ー 3440 Printed ⅲ J 叩 a11 ( ISBN978 ー 4 ー 87311 ー 712-6 ) 落丁、乱丁の際はお取り替えいたします。 本書は著作権上の保護を受けています。本書の一部あるいは全部について、株式会社オライリー ジャパンから文書による許諾を得すに、いかなる方法においても無断で複写、複製することは禁じ られています。

・著者紹介 Noam Nisan ( ノーム・ ェルサレム・ヘブライ大学 ( イスラエルの国立大学 ) の Computer Science and Engineering 研究所の教授。 Shimon Schocken ( サイモン・ショッケン ) 情報技術の IDB 教授。 lnterdisciplinary Center Herzliya ( イスラエルの私立大 学 ) の Efi Arazi school of Computer Science 学部長。 ・訳者紹介 斎藤康毅 ( さいとうこうき ) 東京工業大学にて学士号、東京大学にて修士号 ( 学際情報学 ) を取得。株式会社 チームラボにて、コンピュータビジョン・機械学習に関する研究、またインタラ クテイプシステムの開発に従事する。翻訳書に『実践機械学習システム』 ( オライ ・ジャパン刊 ) がある。