The Elements of Computing Systems: Building a Modern Computer from First Principles（コンピュータシステムの理論と実装）

引用

Nisan, N., & Schocken, S. (2021). The Elements of Computing Systems: Building a Modern Computer from First Principles (2nd ed.). MIT Press.

章の要約

第2版は約344ページで、それぞれプロジェクトと組になった12の章を通じて、単純だが完全なコンピュータシステムを作り上げる。まずハードウェアのプラットフォームを、次にその上に載るソフトウェアの階層を作る。Nand to Tetrisとして知られるこの道のりは、Nandという最も基本的な論理ゲート一つから始まり、テトリスでも他のどんなプログラムでも動かせる汎用コンピュータで終わる。出版社によれば、この版は大幅に改訂された。6つずつのプロジェクトを含む第I部「ハードウェア」と第II部「ソフトウェア」に分けられ、すべての章とプロジェクトが抽象と実装の分離を重視して書き直され、技術的・理論的な話題を集中的に扱う充実した付録が新たに加えられた。すべてのプロジェクトは、ハードウェアシミュレータ、CPUエミュレータ、VMエミュレータなど、著者のNand to Tetrisウェブサイトにある無料のソフトウェアツールで行うので、物理的なハードウェアは必要ない。Google Booksは章題を短い形で載せており、ウェブサイトのプロジェクトページから、仮想マシンの2章と、コンパイラの2章がどれかがわかる。

第1章：Boolean Logic（ブール論理）

唯一の基本素子であるNandゲートから出発し、基本的な論理ゲート（Not、And、Or、Xor、マルチプレクサ、デマルチプレクサ）とその16ビット版・多入力版を作る。これらが、後にCPUとRAMを作るための部品となる。

第2章：Boolean Arithmetic（ブール算術）

二進算術のためのゲート論理。半加算器と全加算器、16ビットの加算器とインクリメンタ、そして最後にHackコンピュータの算術論理演算装置（ALU）を作る。ALUはこの一連のチップの中で、このアーキテクチャに固有の唯一のチップである。

第3章：Memory（メモリ）

ゲート論理でどのようにビットを時間を越えて保持し、メモリのレジスタをどうアドレス指定するか。基本素子のデータフリップフロップを使い、1ビットレジスタ、16ビットレジスタ、8個から16K個のレジスタから成るRAM、そしてプログラムカウンタを作る。

第4章：Machine Language（機械語）

プログラマの側から見たコンピュータ。完成したハードウェアが実行するHack機械語と、その記号的なアセンブリ形式を扱う。プロジェクトでは、提供されたCPUエミュレータ上で2つの低水準アセンブリプログラム（一つは数の乗算）を書いてテストする。

第5章：Computer Architecture（コンピュータアーキテクチャ）

前の章のALUとRAMを組み合わせて、Hack CPU、メモリのアドレス空間全体、最上位のComputerチップを作る。こうして第4章の機械語で書かれたプログラムを実行する汎用コンピュータができあがる。

第6章：Assembler（アセンブラ）

最初のソフトウェアプロジェクト。記号的なHackアセンブリを二進の機械語に翻訳するプログラムである。この章で第I部が終わり、次のページから独自の序論を持つ第II部「ソフトウェア」が始まる。

第7–8章：Processing（処理）；Control（制御）

仮想マシンの2章。Javaや.NETのプラットフォームにならって、本書はスタックベースのVM言語を定義し、VMコードをHackアセンブリに翻訳するトランスレータを読者に書かせる。第7章（プロジェクト7「VM I：スタック算術」）はVMの仕様、算術・論理コマンド、8つのメモリセグメントに対するメモリアクセスコマンド、そしてVMのHackプラットフォームへの対応づけを扱う。第8章（プロジェクト8「VM II：プログラム制御」）はトランスレータを分岐と関数呼び出しに拡張する。

第9章：High-Level Language（高水準言語）

単純でJavaに似たオブジェクトベースの言語Jackを紹介する。対応するプロジェクトでは、Jackオペレーティングシステムのサービスを使って、Jackで小さなゲームや対話的なプログラムを書き、コンパイルする前に言語に慣れる。

第10–11章：Syntax Analysis（構文解析）；Code Generation（コード生成）

コンパイラの2章（プロジェクト10と11、「コンパイラI」と「コンパイラII」）。Jackコンパイラは2層構造で、第7–8章でバックエンドを作り、この2章でフロントエンドを作る。第10章はトークナイザと、Jackの文法に従うパーサを開発し、XML出力によってテストする。第11章は30ページを超える本書最長の章で、記号表を加え、パーサをVMコードを出力するコード生成器に作り変える。

第12章：Operating System（オペレーティングシステム）

ハードウェアとアプリケーションソフトウェアの隔たりを埋めるサービスの集まりとしてのオペレーティングシステム。読者はJack OSの8つのクラス（Math、Memory、Array、String、Output、Screen、Keyboard、Sys）をJack自身で実装する。プロジェクトページは、これが応用計算機科学の古典的なアルゴリズム群に触れることになると述べている。

第13章：More Fun to Go（まだまだ楽しみは続く）

4ページの締めくくりの章。

付録

約40ページの付録が、プロジェクトを支える技術的・理論的な話題を集中的に解説する。

主要概念

第I部：ハードウェア（第1–6章）

• 万能ゲートとしてのNand：他のすべての論理ゲート、ひいてはコンピュータ全体をNandゲートから作れること。
• 組み合わせ論理と順序論理：出力が現在の入力だけで決まるチップと、クロックサイクルをまたいで状態を保持するチップ。
• 算術論理演算装置：二進数に対して算術関数と論理関数を計算するチップ。
• 機械語とプログラム内蔵型コンピュータ：メモリに保持され、CPUによって実行される命令。
• アセンブラ：記号的なアセンブリ言語から二進の機械語への翻訳器。

第II部：ソフトウェア（第7–13章）

• 仮想マシン：高水準言語と機械語の間に置かれる、スタックベースの中間的な抽象化。
• スタック算術とメモリセグメント：VMがスタック上で計算し、変数をアドレス指定する仕組み。
• 構文解析：文法に従ってソースコードを解析すること。
• コード生成：解析されたプログラムをより低水準のコードに翻訳すること。
• オペレーティングシステムのサービス：高水準言語にメモリや入出力へのアクセスを与えるライブラリルーチン。
• 抽象と実装：この版で強調される、各層のインターフェースをその作り方とは別に規定するという原則。

批判的分析

長所

• 読者自身が作る、一貫した一つのシステム。 12の章にはそれぞれ、成果が後の章で使われるプロジェクトがあるので、学生はゲート、CPU、アセンブラ、VM、コンパイラ、オペレーティングシステムを別々の授業で学ぶのではなく、それらがどう組み合わさるかを体験する。出版社は、ハードウェア、アーキテクチャ、オペレーティングシステム、プログラミング言語、コンパイラ、データ構造とアルゴリズム、ソフトウェア工学を、こうして学べる分野として挙げている。
• 無料で完全なツール群。 著者のウェブサイトは、すべてのプロジェクトのためのシミュレータ、エミュレータ、テストスクリプト、比較ファイルを提供している。プロジェクト7のページが示すように、各プロジェクトには明確な仕様と段階的なテストが付いている。非営利の利用であればすべて無料でオープンソースであり、サイトによれば、Nand to Tetrisの授業は400を超える大学、高校、ブートキャンプで行われている。
• 抽象と実装の分離。 出版社によれば、第2版のすべての章は抽象と実装を分離するよう書き直された。プロジェクトページにもそれが表れており、どのプロジェクトも、学生の実装が満たし、それに照らしてテストすべき契約（チップのインターフェース、VMの仕様と対応づけ、API）を明示している。
• 柔軟な構成。 6つずつのプロジェクトから成る2部構成なので、授業はハードウェアの半分だけ、あるいはソフトウェアの半分だけを扱うこともできる。ウェブサイトは典型的な授業の詳しいシラバスも提供し、修了証の出る有料のCoursera版も案内している。

短所

• 意図的に単純な機械。 Hackコンピュータは教育用に設計されたもので、本書はパイプライン、キャッシュ、性能測定、実際の命令セットを扱わない。それらは標準的なアーキテクチャの教科書の主題である。
• 骨の折れるソフトウェアの半分。 第II部のプロジェクト（アセンブラ、VMトランスレータ、コンパイラ、OS）は、読者が選んだ言語での相応のプログラミング力とかなりの時間を必要とする。コード生成を扱う第11章は本書で最も長い章である。
• 無料資料の版の食い違い。 ウェブサイトによれば、一部のプロジェクトページがリンクしている本の章は主に初版のもので、初版は章の構成や題名が異なる（たとえば初版の第3章は「Sequential Logic」、第2版では「Memory」）。無料の章と第2版を併用する読者は、どちらの版を使っているのかを確認する必要がある。

コースにおける位置づけ

本書は、この分野に初めて触れる読者にとって、コンピュータアーキテクチャのコースの実践的な中核である。チャールズ・ペツォルドの Code は、スイッチやゲートから動作するCPUまでという似た範囲を、演習のない物語として扱う。第I部へのやさしい準備として、あるいはプロジェクトが抽象的に感じられるときの相棒として役立つ。ハリスとハリスの Digital Design and Computer Architecture, RISC-V Edition は、ハードウェア記述言語、実際の命令セット、パイプライン化されたプロセッサへとハードウェアをさらに進めるもので、第1–5章の後の自然な次のステップである。

ブライアントとオハラロンの Computer Systems: A Programmer's Perspective はプログラマの側から実際の機械を調べる本で（機械語、メモリ、リンク、プロセス）、第II部を補完する。ヘネシーとパターソンの Computer Architecture: A Quantitative Approach とシェンとリパスティの Modern Processor Design は現代のプロセッサの性能向上技術を扱い、コンピュータ構成論の授業を前提とする。本書の代わりにではなく、本書の後に読むべきものである。

本書の使い方

本書は、コンピュータシステムやコンピュータ構成論の授業を受ける1–2年生、高水準のコードの下に何があるかを知りたい独習者、そして実習形式の授業を行う教員に向いている。電子工学の背景は必要ない。第II部では、読者が選んだ言語でアセンブラ、VMトランスレータ、コンパイラを書くので、何らかの高水準言語でのプログラミング経験が必要である。

• 順番に取り組む。 各プロジェクトは前のプロジェクトに依存する。章を読み、提供されたツールでプロジェクトを実装し、先に進む前に提供されたテストを実行する。
• ハードウェアのみ： 第1–6章は、6つのプロジェクトから成るハードウェアとアセンブラの完結した授業になる。
• ソフトウェアのみ： 第II部は単独で学べる。提供されたツールと本書の仕様がハードウェアの代わりを務める。
• 第10–11章には時間を確保する。 コンパイラは最大の単一の作業である。
• 付録： プロジェクトの必要に応じて参照する。

Nand to Tetrisのウェブサイトからツールとプロジェクトファイルをダウンロードし、各プロジェクトの段階的なテストをプロジェクトページの勧めどおりに使うとよい。小さな部品を単体でテストし、それから全体をテストする。サイトからリンクされている無料の初版の章を使う場合は、実装する前に第2版の仕様と照らし合わせること。後のプロジェクトはそれ以前のプロジェクトの上に築かれるので、各プロジェクトで書いた自分のコードは保存しておくこと。