手を動かしてGo言語で実装しながら『コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方』を読んだ（後半）
前回の記事
6章 アセンブラ
本章で説明する内容は、アセンブリ言語で書かれたプログラムをバイナリで書かれたプログラムへ変換するために、アセンブラがどのようなことを行っているか、ということである。
実装したプログラム
Go言語を用い、記号表記で書かれている低水準言語の xxx.asm ファイルを、16ビットのバイナリコードで表現される xxx.hack ファイルへと変換するアセンブラの実装を行った。
アセンブラはユーザーの定義したシンボルを扱う事ができるようにする必要があるので、シンボルテーブルを使って、シンボルから物理メモリアドレスへと変換する考え方が学びとなった。
7章 バーチャルマシン#1：スタック操作
本章はコンパイラの構築へ向けた初めの一歩である。このコンパイラは、オブジェクトベースの一般的な高水準言語をコンパイルする。コンパイラを作るという作業は相当に困難であるため、我々はその作業を2段階に分けて取り組むことにする。このふたつの段階にはそれぞれ2章分のページが割かれ、合計で4章に渡って説明を行う。高水準プログラムは初めに中間コードへに変換され(10〜11章)、その中間コードは機械語へと変換される。(7〜8章) この2段階による変換処理のモデルは1970年代までさかのぼる古くからあるアイデアに基づいている。1990年代後半には、JavaやC#などのモダンな言語においてもそのアイデアが取り入れられ、再び脚光を浴びることとなった。
中間コードは実際のプラットフォーム上で実行される代わりに、VM上で実行されるように設計されている。これが基本となるアイデアである。VMは抽象化されたコンピュータであり、実際には存在しない。しかし、他のコンピュータ上で再現することができる。このアイデアの優れている点はたくさんあるが、そのうちのひとつは「コードの移植性」についててである。VMを複数のプラットフォームを対象に実装することは比較的容易であろうから、元となるソースコードを修正することなく、VM用のソフトウェアを他のプロセッサとOS上でも実行させることができる。
高水準言語で書かれたプログラムを特定のコンピュータ上で実行するためには、プログラムをそのコンピュータの機械語に変換しなければならない。この変換作業は「コンパイル」という名前で知られている。いくぶん複雑な工程となる。コンパイラを実装するには、どのような「高水準言語」と「機械語」を対象とするのであれ、そのふたつの組み合わせに依存したプログラムを書かなければならない。そのため、対象とするコンピュータと言語の組み合わせに応じて、別のコンパイラが必要になる。 この「高水準言語」と「機械語」による依存性の分離は、コンパイルという作業全体をふたつのステージに分けることで行うことができる。最初のステージにおいて、高水準言語がパースされ、そのコマンドが中間コードへと変換される。そして、次のステージにおいて、その中間コードが対象とするハードウェアの機械語へと変換される。このふたつのステージへと分離することによってもたらされる恩恵は、ソフトウェア開発の観点から見ると、とても魅力的である。なぜなら、最初のステージは高水準言語の仕様だけに依存し、2番目のステージは対象とする機械語の仕様だけに依存するからである。
実装したプログラム
- VM変換器（スタック算術/メモリアクセスに対応）
Go言語を用い、VMの中間コードで書かれている xxx.vm ファイルを、アセンブリ言語である xxx.asm ファイルへと変換するVM変換器の実装を行った。
ここからスタックというデータ構造が登場し、この章以降、全てのデータや計算結果のやりとりがスタックを通じて行われる。
8章 バーチャルマシン#2：プログラム制御
コンピュータサイエンスにおいて"処理コンテスト"のようなものがあるとしたら、スタック処理は優秀部門でノミネートされるだろう。前章では、算術演算とブール演算が基本的なスタック操作によって計算できることを示した。本章では、この驚くべき単純なデータ構造が、驚くべき複雑な仕事をこなせることを示す。複雑な仕事とは、ネスト化されたサブルーチン呼び出しや引数の受け渡し、再帰処理やメモリ割当などである。ほとんどのプログラマーは、これらの機能をコンパイラが何らかの方法で実現しているとは知りつつ、当たり前のことだと思っている。我々は今、このブラックボックスを開く場所に来た。このプログラミングにおける基本的なメカニズムは、スタックベースのVMによって、実際どのように実装されているのか？ 本章は、この問題について考える。
実装したプログラム
- VM変換器（プログラムフロー/サブルーチン呼び出しまで対応）
Go言語を用い、前章で構築したVM変換器の拡張を行った。
if 文や while 文がどのようにアセンブリ言語で記述され、関数呼び出し時に、呼び出し側関数に渡された引数、ローカル変数の保存、制御がどのように呼び出された関数に移され、返り値がどのようにかえってくるか、それが全てスタック上でどうやって処理されるか、VM変換器を構築することで理解することができた。
9章 高水準言語
これまで本書で提示してきたハードウェアとソフトウェアはすべて低水準（低レイヤ）に関するものであった。低水準とは、つまり、人が直接読み書きすることを想定していない、ということである。本章では、Jackと呼ばれる高水準言語について説明を行う。Jackは、人であるプログラマーが高水準なプログラムを書くために設計されている。 Jackは、シンプルなオブジェクトベースの言語である。基本的な性質を備えており、モダンな言語であるJavaやC#と同じような見た目であるが、より単純化された言語であり、「継承（inheritance）」はサポートしていない。
本書で提供されているJackというプログラミング言語の仕様が説明されている章で、10章と11章でJackプログラムをVMコードへ変換するコンパイラを書く際に主に参照した。
10章 コンパイラ#1：構文解析
本章では、Jack言語のコンパイラを作る。コンパイラは、一言で言えば、変換を行うプログラムである。ソース言語で書かれたプログラムを目的の言語で書かれたプログラムへ変換する。この変換のプロセスをコンパイラと呼ぶ。この変換プロセスは概念的にふたつの作業に基づいている。 ひとつ目の作業は、ソースプログラムの構文を理解し、そこからプログラムの意味を明らかにすることである。たとえば、コードを構文解析することによって、そのプログラムは配列を宣言していることが明らかになる、ということがそれに該当する。そのパースした情報を用いることで、目的とする言語の構文からプログラムのロジックを再構成することができる。最初の作業は一般的に構文解析と呼ばれ、本章のテーマである。ふたつ目の作業であるコード生成は次の11章で扱う。
コンパイラをゼロから書くには、コンピュータサイエンスにおける重要なトピックを学ぶ必要がある。学ぶべきことは、言語変換と構文解析、木やハッシュテーブルなどのデータ構造の使い方、再帰的なコンパイルアルゴリズムなどである。そのため、コンパイラを作る作業はたいへんな仕事でもある。
なぜ我々は骨を折ってまでしてコンパイラを作ろうとしているのか？ ひとつ目の理由は、コンパイラの内側を知ることによって、より優れたプログラマーになれるからである。ふたつ目の理由は、プログラミング言語を記述するために使われるルールや文法は、他の分野においても応用できるからである。
実装したプログラム
一般的なコンパイラは主にふたつのモジュールからなる。
それは構文解析とコード生成を行うモジュールである。構文解析を行う作業は、通常さらにふたつのモジュールにわけられる。それはトークナイザとパーサである。トークナイザは、ソースコードに対して意味を持つコードの最小単位である「トークン」に変換する。パーサは、一連のトークンを言語の構文ルールに適合させ、その構文構造を明らかにする。
本章では、コンパイラの構文解析器だけに焦点を当てた。
構文解析器が行う仕事は「プログラムの構造を理解する」ということである。
Go言語を用い、入力プログラムの構文構造を反映したXMLを出力するコード生成機能を備えない構文解析器を実装した。
11章 コンパイラ#2：コード生成
多くのプログラマーにとって、コンパイラはあたりまえの存在である。しかし、少し時間をとってコンパイラについて考えてみれば、高水準言語をバイナリコードへと変換する能力は魔法のように感じられるのではないだろうか。本章では、この変換作業を理解するために、実際にコンパイラを開発する。
10章では、Jackプログラムを理解できる構文解析器を構築した。本章で、この構文解析器を完全版のコンパイラへと拡張する。完全版のコンパイラは、理解された高水準言語を、同等の内容である一連のVM命令へと変換する。このアプローチは「分析と合成(analysis-synthesis)」のパラダイムに従ったものである。ほとんどすべてのコンパイラも、これに従う。
実装したプログラム
コンパイラ全体の作業はバイナリコードまでの変換を含む。しかし、VMコードから機械語へと変換する部分はこれまでの章で構築したので、本章で作成するコンパイラは高水準言語からVMコードを生成することだけを目標とすればよい。
前章のコンパイラを拡張して実装を行ったが、ただXMLを出力するのとは大違いで大変であった。
VMコードを生成するためJack言語の文法を更に深く理解して構文解析を行い、全ての変数・配列・オブジェクトをシンボルテーブルを用いて処理し、フロー制御、サブルーチン呼び出しがメモリ・スタック上でどのように表現されるか把握しながら、VMコードの仕様も理解し変換するコンパイラを実装した。
12章 オペレーティングシステム
これまでの章は全て実装を行ってきたが、本章は迷ったが実装を割愛した。
理由は本書で提供されているJack言語を用いて OSを構築する必要があり、Go言語を用いることができない。
また結果としてできあがるJackOSは商用のOSと似た特徴を多く持つが、プロセス操作やディスク管理、通信などといった商用OSが持つ機能を欠いている。
このプロセス操作や通信という部分をもっと深く学びたい、かつ JackOS の各クラスで提供する機能はどれもシンプルな物であり、これまでの章で遭遇してきた高い山の様には感じないので、この本にはいったん区切りをつける事とした。
まとめ
本書で最初に提供されるNAND素子から、Not/Andという単純な回路をHDL言語を用いて作り、マルチプレクサ、最初の山であるALU(算術論理演算器)を構築し、レジスタ、メモリ、CPUとハードウェア部分を実装してきた。
ソフトウェア部分では、アセンブリ言語を機械語へ変換するアセンブラ、コンパイラを2段階に分けて（高水準言語→VMコード/VMコード→アセンブリ言語）、Go言語を用い、基本的には全てロジックを考え実装を行った。
後半に進むにつれて必要とされるコード/ロジックを想像するに、最初はどれも途方にくれたが、時間をかけて作り上げることができた。
１年以上この本に取り組み低レイヤについて理解を深めることができたが、学びたい事はまだまだあるため、さらに学んでいきたい。
本書は"発見の旅"である。 本書によって、読書は次の3つのことを学ぶことになる。それは「コンピュータの動く仕組み」「複雑な問題を扱いやすいモジュールに分割する方法」そして「ハードウェアとソフトウェアからなる巨大なシステムを開発する方法」である。 本書では、実践的な作業を通じて、完全なコンピュータシステムを作り上げていく。この作業を通じてあなたが学ぶであろう教訓は、コンピュータそれ自体よりも価値があり普遍的なものである。心理学者であるカール・ロジャーズは言う「人に重要な影響を与える唯一の学びは、自己発見・自己本位による学び、つまり、経験によって理解された真実のみである」と。
コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方
