「コンピュータシステムの理論と実装」のエッセンス

けったん（エンジニア）

2023.12.05

IT技術

アセンブラコンパイラコンピュータサイエンス構文解析

はじめに

なんとなく動く形のプログラムを作成する〜なぜ実際に動作するのか説明できない〜ブラックボックスではあるけれど実用的な「コンピュータ」が謎だらけな人は多いはずです。
一昨年くらい前、「コンピュータシステムの理論と実装を読む」という勉強会に参加しました。コンピュータの動作を理解しよう！と気軽に参加したのですが、内容は濃く、理解するには理論的な知識も必要になり結構大変でした。
一通り読破&実装が完了して今思うことは、素晴らしい料理人が材料や道具の事をよく知っているように、プログラマも人生で一回はコンピュータというブラックボックスに向き合うべきだということです。「新しい視点」を持てるようになり、素晴らしいプログラマになる階段をさらに登っていけると信じています。それは早ければ早いほどいいと思っています。

新しい視点

最初に述べた新しい視点について詳しく説明します。新しい視点とは「発見」や「気付き」ともとれるのですが、学びで得られる本質だと思っています。

プログラマとしての視点

エラーへの対応が的確になります

プログラミング言語、スクリプト言語、DSLであれ、一定の法則（文法）の基に定義されたsyntaxErrorへの深い理解が醸成されます。本書のコンパイラの作成時に構文解析を行う中で理解することができます。
エラーがどの段階で起きているかを推定できるようになります。ライブラリなのか、標準言語ライブラリなのか、OSなのか。それぞれの役割を理解することで対処への道しるべが推定できます。本書でのコンパイラ作成時に理解することができます。

新しい言語への障壁が圧倒的に低くなります

先ほども触れたように構文解析を実装する中でsyntaxへの理解が深まるからです。また、言語の特徴を掴むのが早くなります。この言語はどこに重点を置いているのかを把握して理解を進めていくことができるようになります。

クラス、オブジェクト、配列について理解が深まります

オブジェクト、配列、文字列などのデータ構造、ライフサイクル、プロシージャ（メソッドもしくはファンクションなどの処理をまとめたもの）について理解が圧倒的に深まります。バーチャルマシン実装、OS実装をする中で、メモリにどのようにデータを格納するかを学んだり、プロシージャ呼び出しを抽象データ構造にstackを用いることでこれを解決していく過程が驚愕です。

いつかあなたがオープンソースプロジェクトへの貢献をしたいときに役立ちます

本書で標準言語ライブラリ、OS、コンパイラの実装をする中で、この機能ほしい！と気づいたとき、自分で実装する方法の参考になるはずです。ぜひ人類への貢献をお願いします。

ビジネスとしての視点

なぜAppleはアップルシリコンを開発するのでしょうか？

それはアップル製品でより良いユーザ体験を可能にするためにハードウェア、機械語、OS、プログラミング言語までの一貫した最適化を狙っているからだ、と理解できるようになります。

日本はなぜ半導体の復活に力を入れ、微細化を追求するのでしょうか？

それが圧倒的なパフォーマンスの向上、省電力につながることが理解できるようになります。本書ではNANDという論理ゲートを用いてコンピュータを作成していきますが、たとえナノレベルの距離でも何億回〜何兆回も往復することが必要ならば全体的な効率は格段にアップします。

Go, Rustなどがなぜ勢いを持っているのでしょうか？

より低レベルのシステム操作をユーザが簡潔に記述できるようにしているからです。低レベル（より機械語に近い）の効率を上げることはその上の階層での命令の処理を飛躍的に向上させ、アプリケーションに求められるパフォーマンス、安全性、並行処理を達成します。今後はこの分野への知識を持つことが必要不可欠になっていきそうです。

どんなお話？

NANDという論理ゲートから最終的にテトリスを作るとういうお話です。
流石にアセンブラくらいから実装かと思いきや、まさかの論理ゲートから、HDLという言語を用いてALU、レジスタ、プログラムカウンタを実装してCPUを構築、データメモリとメモリマップドI/Oを構築してHackコンピュータ（今回作成するバーチャルで動作する PC）を作成するまでが前半となります。
後半では（自分の好きな言語で）アセンブラ、バーチャルマシン、コンパイラをHack用に自作し、Jackという高級言語（簡潔なオブジェクト指向言語）でOS、標準言語ライブラリも実装していきます。
ワクワクしてきました？
自作はすこし語弊があるのですが、全ての章で構築する要件定義、指針、テストケースを示してくれます。ですので、自分のペースでじっくり進めていくことをお勧めします。

こちらお勧めです。

本書で学ぶこと

新しい視点を持つために、この本で学ぶことを説明します。

コンピュータの動く仕組み

以下のJack（簡潔なオブジェクト指向で本書で使用する高級言語）で書かれたプログラムがあります。

1class Main {
2function void main() {
3    do Output.printString("Hello World");
4    do Output.println(); // 改行
5    return;
6    }
7}

たいていどの言語を学ぶときもHello Worldを出力するのがお決まりになっていますが、本書ではこのHello Worldがどのように画面に表示されるかを考えていきます。
そのためにまずは２つの世界、ソフトウェアの世界とハードウェアの世界に話を分けます。

ソフトウェアの世界でやるべきこと

ユーザが記述したテキストデータを最終的にハードウェアが実行できるバイナリのテキストデータに変換します。具体的には本書で構築するコンピュータは16bitのシステムを採用しているので以下のような16桁のバイナリの集合になります。たった7行のプログラムが膨大な行のバイナリデータ（OSのプラグラムも含む）へと変換されます。ここまでがソフトウェアの世界で行うことです。

1// （例）
2// メモリのアドレスが7（Memory[７]）に格納されている値を1だけ加算して、
3// Dレジスタ（今回作成するコンピュータのデータレジスタ）とMemory[７]に格納する命令
40000 0000 0000 0111
51111 1101 1101 1000

ハードウェアの世界でやるべきこと

バイナリデータを実行し、実際に表示を行うまでとなります。本書のコンピュータのスクリーン、キーボードはそれぞれのロケーションごとにメモリマップされています。バイナリコード１行ごとにCPUがメモリの値を読み込み、書き込み、演算等の処理を実行し、制御します。基本的にはバイナリデータを順番に実行してメモリの値を操作しているということになります。結果としてスクリーンに"Hello World"が表示されます。

本書で分割したインターフェイス

ざっと書きましたが、それぞれの世界で行なっていることは以下のようなインターフェイスに分割することができ、本書ではそれぞれを実装していきます。
この抽象化は達人の領域でどの順番で実装しても最終的には目的を達成することができます。

ハードウェア、ソフトウェアの世界

ハードウェアとソフトウェアが出会う場所

最も重要なインターフェイスは何か？というと「機械語」となります。

どのような高級言語も紆余曲折を経て「機械語」に変換されます
ハードウェアは「機械語」を実行できるように作成されます

機械語は仕様によって決められた形式に従い、プロセッサとレジスタを用いてメモリを操作するように設計されています。結局のところ、高級言語で記述していることは最終的にメモリを操作するという行為になります。
本書のHackコンピュータではHello Worldを画面に表示する、という行為がscreenのメモリマップに応じたアドレスの値を1に設定する、ということで実現されます。
この機械語の「仕様」がそれぞれのコンピュータを特徴づけます。

「メモリの操作」には以下のようなものがあります。

指定されたアドレスのメモリに格納されている値を読み込み、指定されたアドレスにデータを格納する
指定されたアドレスのメモリに格納されている値（１つまたは２つ）を読み込み算術演算を行い、指定されたアドレスにデータを格納する
指定されたアドレスのメモリに格納されている値（１つまたは２つ）を読み込み論理演算を行い、指定されたアドレスにデータを格納する

Hackコンピュータでは命令メモリとデータメモリという２つのアドレス空間を持ちます。
CPUは命令メモリに格納されている命令だけを読み込み実行していきます。この命令メモリに格納してあるデータが「ソフトウェアの世界」で作成されたバイナリの16bitデータです。
このHackの命令メモリのデータは２種類の命令に大別することができます。