『コンピュータシステムの理論と実装 第2版』を読んだので感想を書く。割と長いので得られた学びだけ読みたい方は## 学び、得た経験 までジャンプしてください。

本書の構成#

本書はnand2tetrisという通称の通り、NANDゲートからスタートして、CPUやコンパイラやOSなどを実装し、最終的にはそのプラットフォーム上でテトリス(のようなアプリケーション)1が動くところまで実装するという内容のコースになっている。

roadmap https://drive.google.com/file/d/1BPmhMLu_4QTcte0I5bK4QBHI8SACnQSt/view P3より引用

上図のとおりだが、大まかな流れとしては以下。

  1. NANDゲートを使ってnot, and, orなどの基本的なチップを実装
  2. 加算機やALUを実装
  3. レジスタ、RAM、Program Counterを実装
  4. Memory、CPU、Computerを実装
  5. アセンブラを実装(機械語の記号表現をバイナリ表現に変換する)
  6. 仮想マシンを実装
  7. コンパイラを実装
  8. OSを実装

各章末に課題とそれをパスしたことを確認するテストがある。基本的にはテストコードを使って動作確認ができるようになっているため、自分の実装が合ってるかを機械的に確認できるようになっており、手を動かしながら理解を深めやすいようになっている。

参考までに各章の実装に用いる言語を記しておく。

章 実装言語
第1章 ブール論理 HDL(Hardware Description Languageの略で論理回路の構造を記述できる言語)
第2章 ブール算術 HDL
第3章 メモリ HDL
第4章 機械語 アセンブリ言語(Hackプラットフォーム独自の仕様)
第5章 コンピュータアーキテクチャ HDL
第6章 アセンブラ 任意の言語
第7章 仮想マシンI：処理 任意の言語
第8章 仮想マシンII：制御 任意の言語
第9章 高水準言語 Jack言語(本書で実装するJavaライクな独自言語)
第10章 コンパイラI：構文解析 任意の言語
第11章 コンパイラII：コード生成 任意の言語
第12章 OS Jack言語

第6章 ~ 第8章と第10章 ~ 第11章は決められた入出力を持つCLIツールを書けばいいので任意の言語で書くことができる。筆者はRustで実装した。特にEnumとパターンマッチのおかげで構文解析関連の処理が書きやすかった。

ここからは各章の学びを簡単に書いていく。

第1章 ブール論理#

NANDを使って以下の論理回路をHDLを使って実装した。

  • not
  • and
  • or
  • xor
  • マルチプレクサ
  • デマルチプレクサ
  • not(16bit)
  • and(16bit)
  • or(16bit)
  • マルチプレクサ(16bit)
  • 8入力or
  • 4入力マルチプレクサ(16bit)
  • 8入力マルチプレクサ(16bit)
  • 4入力デマルチプレクサ
  • 8入力デマルチプレクサ

マルチプレクサの実装に悩んだがいい感じの実装を思いついたときの爽快感がすごかった。

真理値表を丁寧めに書きながら進めた結果マルチプレクサの実装以外はそこまで悩まなかった。

第2章 ブール算術#

以下の論理回路を作成した。

  • 半加算器
  • 全加算器
  • 16bit同士の加算
  • 16bitの入力に1をインクリメントする回路
  • ALU(Arithmetic Logic Unit: 算術論理演算装置)

学び:

  • 内部ピンにインデックスアクセスするには次のように書く必要がある。 
    Mux16(a=calculateResult, b=notCalculateResult, sel=no, out=out, out[0..7]=out0To7, out[8..15]=out8To15, out[15]=ng);
  • 愚直な実装をしている箇所があったが、Mux16でスマートに書き直せることを知って感動した。

第3章 メモリ#

この章では、DFF(Data Flip-Flop)を用いて1-bit registerを作成し、それを組み合わせて16-bit registerを作成し、さらにそれを組み合わせてRAMを作成した。

from-dff-to-ram.webp https://drive.google.com/file/d/1boFooygPrxMX-AxzogFYIZ-8QsZiDz96/view P47より引用

読み書き可能なメモリを作成したことで、コンピュータを作っている感が強まってきた。

作成した回路は具体的には以下。

  • Register(1bit)
  • Register(16bit)
  • RAM(8bit)
  • RAM(64bit)
  • ProgramCounter
  • RAM(512bit)
  • RAM(4K-bit)
  • RAM(16K-bit)

学びメモ#

  • 第2章までは時間に依存しない回路のみを扱っていたがこの章では過去の状態を保持する回路を作成した。
  • ここでは時間をクロックという単位で区切って扱う。
  • 非同期チップ(組み合わせチップ): 入力値の組み合わせのみに反応し時間の進行には影響を受けない
  • 同期チップ(順序チップ): 以前の時間単位での変化に対応する用に設計されたチップ
  • 同期チップを利用することでシステム内のチップ間で信号が伝播するのにかかる時間を無視できる。
  • ただしクロックサイクルは「システム内のチップ間で信号が伝播するのにかかる時間の最大値」と「1チップ内で最も処理時間がかかる演算を完了するのにかかる時間」の合計値よりも大きく設定する必要がある。

DFFはout(t+1) = in(t)で表される出力を持つ。DFFを用いることで過去の状態を論理回路上で表現できる。

dff.webp https://drive.google.com/file/d/1boFooygPrxMX-AxzogFYIZ-8QsZiDz96/view P41より引用

次のようにマルチプレクサとDFFを組み合わせることで1-bit registerを作成できる。

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    Mux(a=dffOut, b=in, sel=load, out=mux);
    DFF(in=mux, out=out, out=dffOut);
}

1-bit registerは時刻tにおいてloadビットがアサートされるとout(t+1)がin(t)の値になり、アサートされていない場合はout(t+1)はout(t)の値になる。換言するとレジスタを利用することで過去の状態を保持できる。

1-bit-register.webp https://drive.google.com/file/d/1boFooygPrxMX-AxzogFYIZ-8QsZiDz96/view P25より引用

第4章 機械語#

第4章では以下のプログラムを機械語で書いた。

  • 掛け算を行うプログラム
  • キーボードが押されているときだけ画面を黒くするプログラム

機械語#

  • ハードウェアプラットフォームが実行するように設計されている基本的な命令セット
  • 高水準言語は表現力やプラットフォーム間の互換性を目標に設計される一方で機械語は特定のハードウェアで直接実行され、そのハードウェアを完全に制御できるように設計されている。
  • 機械語は決められた形式に従いプロセッサとレジスタを用いてメモリを操作するように設計されている。
  • バイナリ形式、記号形式の2パターンで記述できる。

メモリ#

  • データや命令を保存するハードウェアデバイス。各セルはメモリ位置やメモリレジスタと呼ばれ、それぞれ固有のアドレスを持つ。

プロセッサ#

  • プロセッサは中央演算装置(CPU) と呼ばれ、あらかじめ決められた基本的な命令セットを実行できる。
  • プロセッサは選択されたレジスタとメモリ位置からデータを取り出し、選択されたレジスタとメモリ位置に出力を書き込む。
  • プロセッサはALUとレジスタ、バイナリ命令の解析と実行を可能にする論理ゲートによって構成される。

レジスタ#

  • プロセッサとメモリはそれぞれ独立したチップとして実装されており一方から他方へデータを移すには比較的時間がかかる。そのためほとんどのプロセッサにはいくつかのレジスタが備わっており、高速なローカルメモリとして機能する。
  • CPUに存在するレジスタは2つのタイプに分類される。
    • データを保持するデータレジスタ(Dレジスタ)
    • アドレスを保持するアドレスレジスタ(Aレジスタ)

Hackコンピュータのアーキテクチャ#

Hackコンピュータは以下のようなアーキテクチャを持つ。

hack-computer-architecture.webp https://drive.google.com/file/d/1HxjPmIZkFHl-BVW3qoz8eD9dqEuEyuBI/view P23より引用

アセンブラの役割#

機械語はバイナリ形式、記号形式の2パターンで記述できると書いたが、記号形式で@xのように変数を宣言した場合にその変数を実際のメモリのどこに置くかを知るのがアセンブラである。アセンブラのおかげで記号形式のプログラム側は実装詳細を意識することなく変数を初期化、利用できる。

命令タイプ#

Hack言語には2つの命令タイプがある。

  • A命令
    • A命令はAレジスタに15ビットの値を設定する。
    • A命令は1ビットのオペコード + 15ビットの値で構成される。(Hack機械語ではA命令のオペコードは0)
    • A命令は3つの目的で使用される。
      • プログラムによってコンピュータに定数を入力する
      • Aレジスタのアドレスを設定することでその次のC命令でRAMレジスタを操作できる
      • Aレジスタにジャンプ先のアドレスを設定することでその次のC命令でジャンプを実行できる
  • C命令
    • C命令では次の3つを指定する。
      • どういう計算をするか(comp)
      • 計算された値をどこに保存するか(dest)
      • 次に何をするか(jump)
    • Hack機械語では一番左端の1ビットが1
    • C命令は次のような形式で構成される。111accccccdddjjj
      • 111: 先頭の1がオペコードで、左から2,3ビット目は使用されないが慣例として1が設定されている。
      • a: ALUへの入力がAレジスタからの値化Mからの値か決定する(1ビット)
      • c: compフィールド。(6ビット)ALUに対して計算内容を指定する。
      • d: destフィールド。(3ビット)計算結果の値をどこに保存するかを表現する。左から順にDレジスタ、Aレジスタ、RAM[A]に値を保存するかを表現する。

the-hack-language-specification https://drive.google.com/file/d/1HxjPmIZkFHl-BVW3qoz8eD9dqEuEyuBI/view P129より引用

外部デバイス#

Hackのハードウェアプラットフォームでは画面とキーボードの2つの外部デバイスに接続できる。どちらのデバイスもメモリマップを通してコンピュータと会話する。(メモリの中に画面とキーボード用のメモリ領域があり、そこに画面の各ピクセルの値や押下されているキーのキーコードが格納される。)

Hackプログラムの例#

以下は掛け算を行うHackプログラムのソースコード。(Hackアーキテクチャで動作する機械語で書かれている) ハードウェアの構成要素を理解しながら手続き型チックに記述する必要があるため難しかったが理解が進んだ。

// 0に対して(R0-1)回R1を足すことで掛け算を実現する

  // n = 0
  @n
  M=0

  // R2 = 0
  @R2
  M=0
(LOOP)
  // if n == R0 then goto END
  @n
  D=M
  @R0
  D=D-M
  @END
  D;JEQ

  // R2 += R1
  @R2
  D=M

  @R1
  D=D+M

  // R2 = D
  @R2
  M=D

  // n++
  @n
  M=M+1

  // go to LOOP
  @LOOP
  0;JMP
(END)
  @END
  0;JMP

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

第5章では、これまでの章で作成した論理回路を組み合わせてついに1つの汎用コンピュータを作成する。このコンピュータは第4章に登場した機械語のプログラムを実行できる。

  • ノイマン型アーキテクチャ:
    • CPUがメモリデバイスと相互作用する。
    • 入力デバイスからデータを受け取り出力デバイスへデータを送信する。
    • コンピュータのメモリに保存されるデータはコンピュータが計算したデータだけではなくコンピュータに何を行うべきかを指示する「命令」も含まれる。
  • メモリ:
    • 物理的にはアドレス指定可能な固定サイズのレジスタの並びで、それぞれが固有のアドレスを持つ。
    • 概念的にはアドレス空間はデータと命令の保存という2つの役割を果たす。
    • ランダムに選択されたメモリレジスタに瞬時に到達できるという要件からRandom Access Memoryと呼ばれている。
      • たしかにRAMはレジスタの木構造になっていたのである程度大きいRAMでも少ないホップ数で指定したレジスタにアクセスできそうだ。
    • データ専用のメモリ領域をデータメモリ、命令専用のメモリ領域を命令メモリと呼ぶ。
  • CPU:
    • CPUは現在読み込まれているプログラムの命令を実行する。
    • 各命令はCPUに対して以下を指示する。
      • どの計算を実行するか
      • どのレジスタにアクセスするか
      • 次のどの命令をフェッチして実行するか
    • CPUはこれらのタスクをALU、レジスタ、制御ユニットを使って実行する。

第5章の課題ではこれまでの章で作成した論理回路を組み合わせて以下を作成した。

  • Memory
  • CPU
  • Computer

正直CPUの実装、デバッグがはかなり大変だったが公式が提供してくれているテストツールとデバッガのおかげで効率的にバグを見つけることができた。

こんな感じで各ピンの出力や期待する結果とのdiffを比較的見やすい形式で表示してくれるのでありがたかった。

cpu-debug.webp

ここで作成したCPUの回路は次のようなもの。ここではヒントとして大まかな回路設計が与えられておりそれを参考にしつつ足りない部分を埋めていく形で実装を進めた。

cpu-implementation.webp https://drive.google.com/file/d/1Z_fxYmmRNXTkAzmZ6YMoX9NXZIRVCKiw/view P31より引用

第6章 アセンブラ#

第6章では第5章で書いた機械語の記号表現をバイナリ表現に変換するアセンブラを開発する。

  • 変数やラベルのアドレス管理を行うためにシンボルテーブルを利用する。シンボルテーブルには以下のような情報が格納される。
    • ラベルの位置 e.g. (LOOP)
    • 変数のアドレス e.g. @i(Hack機械語では変数は16以降のアドレスに順に割り当てられる)
    • 定義済みシンボルのアドレス e.g. @SCREEN, @KBD

シンボル処理#

アセンブリプログラムではシンボルが定義される前にシンボルラベルを使用できる。(goto命令の行き先を指定するのに利用する)

この挙動も考慮しつつバイナリを生成するには2パス・アセンブラと呼ばれる手法を用いる。

  • 第1パス: シンボルテーブルを作成しすべてのラベルシンボルをテーブルに追加する。
  • 第2パス: 変数シンボルを処理し、シンボルテーブルを使用してバイナリコードを生成する。

第6章からは好きな言語で実装できるのでRustで実装した。構文解析系はenumがある言語だと書きやすくて良い。

第7章 仮想マシンI：処理#

第7章ではVM変換器の一部を実装した。第8章で残りの部分を実装してVM変換器が完成する。ここまでの課題の中では一番大変で丸3日かかった。

HackプラットフォームのVMアーキテクチャとその利点#

Hackプラットフォームにおいて、Hackプログラムは2段階コンパイルによって機械語に変換される。(更にその後アセンブラが機械語(記号表現)を機械語(バイナリ表現)に変換する)

    graph LR
    A[Jackコード
e.g. Foo.jack] -->|コンパイラが変換| B["VMコード(中間コード)
e.g. Foo.vm"]
    B -->|VM変換器が変換| C["機械語(記号表現)
e.g. Foo.asm"]
    C -->|アセンブラが変換| D["機械語(バイナリ表現)
e.g. Foo.hack"]

中間コードは仮想マシン(Virtual Machine; VM) と呼ばれる抽象化されたコンピュータ上で実行されるように設計されている。

高水準言語のプログラムを直接機械語に変換する方式だとハードウェアプラットフォームごとにコンパイラを作成する必要がある。この場合、コンパイラはソース言語(高水準言語)とターゲット言語(機械語)の両方に依存するためそれぞれの変更に追従する必要がある。

2段階でコンパイルする方式を採用するとコンパイラはソース言語の詳細に、VM変換器はターゲット言語の詳細にのみ依存するため変更への追従コストを下げることができる。 この方式ではコンパイラはハードウェアプラットフォームによらず利用することができ、ハードウェアごとにVM変換器さえ実装すればよい。そのためクロスプラットフォーム対応が比較的容易になるという利点がある。

VMフレームワークは上記の利点の代償として効率性が低下するという欠点がある。2段階の変換プロセスで生成するコードは直接コンパイルで生成するコードよりも冗長なことが多く、効率性が落ちる。

VM言語の設計#

VM言語の設計にはバランスが重要で以下の要求を同時に満たす必要がある。

  • 高水準側からの要求: 高水準言語のコードを表現できるだけの表現力と構造性を持たなければならない
  • 低水準側からの要求: VMコードから生成される機械語がコンパクトで効率的になるようにVMコードは十分に低水準でなければならない

このような一見矛盾するような要件をスタックマシンが解決する。スタックマシンに基づく中間のVM言語を用いることで高水準言語の表現力と低水準言語の効率性という相反する要求を満たすことができる。

スタックマシンの挙動#

スタックマシンの中心はスタックと呼ばれるLIFOのデータ構造にある。ここではいくつかの操作について説明する。(ここではスタックは下方向に成長するように記述する)

push操作の例# 

graph LR
    A[Stack: empty] -->|push 10| B[Stack:
10]

pushを行うとスタックの先頭に値が追加される。スタックではSP(スタックポインタ) という値を使ってスタックの先頭位置を保持している。SPはpush操作を行う際に値を追加する領域を指し示している。スタックのメモリアドレスが0からスタートすると仮定すると今回の例ではアドレス0に値がpushされたときにSPの値が0から1になる。

アドレス 値
0 10
1 
graph LR
    A[Stack: empty] -->|push 10| B[Stack:
10]
    B -->|push 20| C[Stack:
10
20]

push操作を行うとスタックの先頭に値が追加される。このときSPの値は1から2になる。(補足:ここではSPは0-originとする)

pop操作の例# 

graph LR
    A[Stack:
42] -->|pop local 0| B["Stack: empty
local[0] = 42"]

pop segment_name indexと記述するとスタックの先頭の値を取り除き、指定したメモリセグメント、インデックスの位置に値を書き込む。

pop操作はスタックの先頭の値を取り除く。

算術演算(add)の例# 

graph LR
    A[Stack: empty] -->|push 10| B[Stack:
10]
    B -->|push 20| C[Stack:
10
20]
    C -->|add| D[Stack:
30]

算術演算の例としてx+yを行うケースを考える。

この処理は次のような流れで行われる。

  1. スタックからオペランドx, yをpopする
  2. x+yを計算する
  3. 計算結果をスタックにpushする
graph LR
    A[Stack:
10
20] -->|pop y=20| B[Stack:
10]
    B -->|pop x=10| C[Stack: empty]
    C -->|push x+y=30| D[Stack:
30]

この方法を拡張することで一般的な算術演算をスタックマシンで評価できる。

第7章では、以下の演算子を実装した。

  • push
  • pop
  • 算術演算子
    • add
    • sub
    • neg
    • eq
    • gt
    • lt
    • and
    • or
    • not

仮想メモリセグメント#

ここで実装するVMにはシンボル変数は存在しない。そのかわりに変数はstatic, local, argument, this, that, pointer, tempのような名前を持つ仮想セグメントの要素として表現される。たとえばコンパイラは高水準言語プログラムで見つかった最初のスタティック変数をstatic 0に、その次に見つかったスタティック変数をstatic 1に、というように変換する。

ここでのVM実装では以下のような仮想メモリセグメントを持つ。

名前 場所 使用法
SP RAM[0] スタックポインタ：スタック最上位の次のメモリアドレス
LCL RAM[1] localセグメントのベースアドレス
ARG RAM[2] argumentセグメントのベースアドレス
THIS RAM[3] thisセグメントのベースアドレス
THAT RAM[4] thatセグメントのベースアドレス
TEMP RAM[5-12] tempセグメントを保持
R13, R14, R15 RAM[13-15] VM変換器が生成するアセンブリコードに変数が必要な場合、これらのレジスタを使用可能

P175より引用

LCL, ARG, THIS, THATには各セグメントのベースアドレスが格納されている。たとえば次のように指定されていた場合、pop this 2はスタックの先頭の値をRAM[2202]に書き込む。

アドレス 値 備考
0 256 SP
1 2000 LCL
2 2100 ARG
3 2200 THIS
4 2300 THAT

VM変換器の動作例#

例として実際の変換例を示す。

push constant 7
push constant 8
add

今回作成した実装では上記のvmコードは次のようなアセンブリコードに変換される。

// init
@256
D=A
@SP
M=D
// body
// push
@7
D=A
@SP
A=M
M=D
@SP
M=M+1
// push
@8
D=A
@SP
A=M
M=D
@SP
M=M+1
// add
@SP
A=M
A=A-1
A=A-1
D=M
@SP
A=M
A=A-1
D=D+M
@SP
A=M
A=A-1
A=A-1
M=0
@SP
A=M
A=A-1
M=0
@SP
M=M-1
M=M-1
@SP
A=M
M=D
@SP
M=M+1
// end
(END)
@END
0;JMP

VM変換器の実装はハードウェアの構造を意識しながらだいぶ手続き的なコードを書く必要があるので大変だった。(記述量も多いしミスるポイントも多い。)

現代のおいては低レイヤを隠蔽してくれる便利な仕組みがあるおかげでソフトウェアエンジニアが少ない記述量でアプリケーションを動かすことができていることを実感した。

ただ、隠蔽されているからこそ自主的に潜っていかないと構造の理解を深めるのが難しかったりするので引き続きやっていきたい。

第8章 仮想マシンII：制御#

第7章では

  • push
  • pop
  • 算術演算子
    • add
    • sub
    • neg
    • eq
    • gt
    • lt
    • and
    • or
    • not

以下の演算子を実装したが、第8章では以下の演算子を実装し、VM変換器を完成させた。

  • label
  • goTo
  • ifGoTo
  • call
  • function
  • return

これを実装することで次の操作が可能になりよりプログラムっぽい処理を行えるようになる。

  • 任意のラベル位置へのジャンプ
  • if分岐
  • 関数の宣言と呼び出し

関数の呼び出し(call)#

Hackプラットフォームにおいてはcall {function_name}コマンドを使って関数呼び出しを行う。

スタックを利用することで関数の呼び出しと戻り値の取得をシンプルに行うことができる。

ここではfunc_aからfunc_bを呼び出すシナリオを例に関数呼び出しをスタックで実現する際の操作を説明する。

  1. (func_aからfunc_bを呼び出す)
  2. func_aの以下の呼び出し側の情報をスタックにpush(これらの情報はフレームと呼ばれる)(画像の灰色の部分)
    1. リターンアドレス(: func_bの呼び出しが完了してreturnする際に戻るアドレス)
    2. func_aのLCLセグメントのベースアドレス
    3. func_aのARGセグメントのベースアドレス
    4. func_aのTHISセグメントのベースアドレス
    5. func_aのTHATセグメントのベースアドレス
  3. ARG, LCLセグメントの値を更新
  4. func_bのコマンドが定義されているアドレスにジャンプ
  5. リターンアドレスラベルをコードに挿入

call.webp https://drive.google.com/file/d/1BexrNmdqYhKPkqD_Y81qNAUeyfzl-ZtO/view P58より引用

関数からのreturn(return)#

呼び出された関数の終了はreturnコマンドで行う。このコマンドが呼ばれることで呼び出し側に処理が戻る。

ここではfunc_aからfunc_bを呼び出した際にfunc_bからfunc_aに戻るシナリオを例にスタックの操作を説明する。

  1. frameのアドレスを一時変数に格納
  2. リターンアドレスを一時変数に格納
  3. ARGに返り値を格納
  4. SPをARG+1に設定
  5. THAT, THIS, ARG, LCLを復元
  6. リターンアドレスにジャンプ

return.webp https://drive.google.com/file/d/1BexrNmdqYhKPkqD_Y81qNAUeyfzl-ZtO/view P73より引用

第9章 高水準言語#

第10章、第11章でコンパイラを実装するJackの言語仕様を解説した章。

Javaに近い感じの文法。

class Main {
   function void main() {
      var Array a; 
      var int length;
      var int i, sum;

      let length = Keyboard.readInt("How many numbers? ");
      let a = Array.new(length); // constructs the array
     
      let i = 0;
      while (i < length) {
         let a[i] = Keyboard.readInt("Enter a number: ");
         let sum = sum + a[i];
         let i = i + 1;
      }

      do Output.printString("The average is ");
      do Output.printInt(sum / length);
      return;
   }
}

第10章 コンパイラI：構文解析#

第10章の内容に入る前にJackのソースコードが実行可能な形式になるまでの流れをおさらいしておく。

    graph LR
    A[Jackコード
e.g. Foo.jack] -->|コンパイラが変換| B["VMコード(中間コード)
e.g. Foo.vm"]
    B -->|VM変換器が変換| C["機械語(記号表現)
e.g. Foo.asm"]
    C -->|アセンブラが変換| D["機械語(バイナリ表現)
e.g. Foo.hack"]

Jackコンパイラは構文解析器とコード生成器からなり構文解析器はトークナイザとパーサ2からなる。

compiler-roadmap https://drive.google.com/file/d/1CM_w6cxQpYnYHcP-OhNkNU6oD5rMnjzv/view P4より引用

トークナイザはソースコードをトークンと呼ばれる「プログラムにおいて意味を持つコードの最小単位」に変換する処理を担う。

トークンのような表現に変換してからパースを行うことでプログラムの複雑性を軽減することができる。

例として以下のJack言語のコードのトークン列をXMLで表記すると以下のようになる。

class Main {
    static boolean test;

    function void main() {
      do Output.printString("Hello world!");
      return;
    }
}

<class>
  <keyword> class </keyword>
  <identifier> Main </identifier>
  <symbol> { </symbol>
  <classVarDec>
    <keyword> static </keyword>
    <keyword> boolean </keyword>
    <identifier> test </identifier>
    <symbol> ; </symbol>
  </classVarDec>
  <subroutineDec>
    <keyword> function </keyword>
    <keyword> void </keyword>
    <identifier> main </identifier>
    <symbol> ( </symbol>
    <parameterList>
    </parameterList>
    <symbol> ) </symbol>
    <subroutineBody>
      <symbol> { </symbol>
      <statements>
        <doStatement>
          <keyword> do </keyword>
          <identifier> Output </identifier>
          <symbol> . </symbol>
          <identifier> printString </identifier>
          <symbol> ( </symbol>
          <expressionList>
            <expression>
              <term>
                <stringConstant> Hello world! </stringConstant>
              </term>
            </expression>
          </expressionList>
          <symbol> ) </symbol>
          <symbol> ; </symbol>
        </doStatement>
        <returnStatement>
          <keyword> return </keyword>
          <symbol> ; </symbol>
        </returnStatement>
      </statements>
      <symbol> } </symbol>
    </subroutineBody>
  </subroutineDec>
  <symbol> } </symbol>
</class>

パーサはトークン列を言語の構文ルールに照らし合わせその構造を構文上の要素に変換する処理を担う。

ここでは再帰下降構文解析というアルゴリズムを使って構文解析を行った。

ちなみに、Jack言語の構文は次のように定義されている。簡単な部類の言語とはいえ実装量はこれまでの課題と比べると多めだった。趣味でCコンパイラを書く人をたまにTwitterで見かけたりするがすごいなぁという気持ちになった。

jack-grammer

第11章 コンパイラII：コード生成#

第11章では、コード生成器を実装する。具体的には構文解析した結果をもとにVMコードを生成する。

compiler-roadmap https://drive.google.com/file/d/1CM_w6cxQpYnYHcP-OhNkNU6oD5rMnjzv/view P4より引用

一般的にはソースコードをVMコードに変換する層をフロントエンド、VMコードを機械語に変換する層をバックエンドと呼ぶらしい。本書では第10章と第11章の内容がフロントエンドに、第6章~第8章の内容がバックエンドに該当する、と言えそう。

シンボルテーブル#

コンパイラがlet y = foo(x);のような文に遭遇するたびにx, yが何を表しているのかを知る必要がある。

Jackではクラススコープとサブルーチンスコープの2つのスコープがある。クラススコープの変数にはフィールド変数、スタティック変数の2種類があり、サブルーチンスコープの変数にはローカル変数、引数の2種類がある。

ここではこれらの変数の情報はシンボルテーブルと呼ばれるデータ構造に格納することで管理する手法が紹介されていた。シンボルテーブルは変数の名前、型、スコープ、種類、インデックスを保持する。

symbol-table https://drive.google.com/file/d/1CYOcXKxfAwRHaOERvoyuNKSwdlxMo_e3/view P6より引用

Jackではクラススコープとサブルーチンスコープの2つのスコープがあるのでそれぞれ別のシンボルテーブルを保持する必要がある。Jackでは内側のスコープが外側のスコープよりも優先されるため、コンパイラはxという変数に出会ったときにまずサブルーチンスコープのシンボルテーブルを検索し、見つからなければクラススコープのシンボルテーブルを検索する。

コンストラクタのコンパイル#

  1. 特定のクラス型の変数を宣言する。e.g. var Point p
  2. クラスのコンストラクタを呼び出して実際にインスタンス化する。 e.g. let p = Point.new(2, 3)
    1. 新しいPointインスタンスを表現するために必要な2ワード分のメモリブロックをヒープ上に確保する
    2. 確保された2ワードがコンストラクタの引数として与えられた2と3で初期化される
    3. pに新しく確保したメモリブロックのベースアドレスを割り当てる

実装自体が難しいというケースは少なかったが、純粋にVM変換器の仕様を忘れて思い出すのに時間がかかったりしたので可能な方は時間を開けずにやると思い出しにかかるコストを減らせておすすめです。

第12章 OS#

第12章では最小限のOSを実装した。

ここではOSは以下の役割を果たす。

  • ハードウェア操作の抽象化
  • Jack言語でよく使われる処理を関数/メソッドとして提供

それぞれ具体的には次のようなクラスによって実現されている。

  • ハードウェア操作の抽象化
    • Outputクラス: printString, printlnなどのスクリーンへのテキストの書き込み処理を提供
    • Screenクラス: drawLine, drawCircleなどのスクリーンへの図形の書き込みを処理を提供
    • Keyboardクラス: keyPressed, readLineなどのキーボードからの入力の読み取り処理を提供
    • Memoryクラス: alloc, deAlloc, peek, pokeなどのメモリアクセス処理を提供
    • Sysクラス: プログラム実行に必要な処理の提供
  • Jack言語でよく使われる処理を関数/メソッドとして提供
    • Mathクラス: abs, devideなどの基本的な算術演算を提供
    • Stringクラス: 文字列データ型とlength, setCharAtなどの関連処理を提供
    • Arrayクラス: 配列の初期化とメモリの解放を行う機能を提供

この章ではこれまでまったく意識したことがなかったメモリ操作によってハードウェアを制御するという経験が得られた。クラスインスタンスの初期化のためにメモリから任意の大きさの空き領域を探して確保する処理や、2点の座標が与えられたときにそれらを結ぶ直線をスクリーン上に描画する処理など。想像に難くない通り、基本的にかなり泥臭い実装が多かったがその泥臭さを吸収するための層でもあるので仕方ないとは思う。

その過程でメモリ操作やビットを扱う処理に少し慣れられたのは大きな収穫の1つだった。普段のWeb開発ではbit演算やメモリ操作をする機会はなかなかないので貴重な経験だった。

軽く調べた感じでは、現実世界では(Linuxでは)システムコールやデバイスドライバがそれらを担っているらしい。

実装に関しては整数型のオーバーフローが原因で数時間費やしてしまった。CS50でC言語で課題を解いていたときも同様のハマり があったのであるあるかもしれない。普段書いている言語は簡単にオーバーフローしなかったり場合によっては静的解析で指摘してくれたりするのでなかなか気付くことができなかった。

学び、得た経験#

  • 普段はWebアプリケーションばかり触っているので、それよりも数段下のレイヤーの解像度を上げることができた。今後新しい知識の習得やトラブルシューティングがスムーズになるといいなと思う。
    • あとは普段触っているソフトウェア、ハードウェアの仕組みを知ることができて純粋に楽しかった。
  • 難しい概念に出会ったときに「順を追って理解を整理したり、労を惜しまずに手を動かしていけばきっと体得できるはず」という感覚を持てるようになった。
    • 自分のコンピュータサイエンスの知識と経験が薄いのもあり、本書を通して未知の概念とのたくさんの出会いがあった。
    • まったく知らない概念でも、順を追って理解を進めて手を動かすことで知識を自分のものにすることができた。その過程で未知の技術に対する恐れや及び腰になる感覚が減った。
    • 余談だが、大学受験のときにセンター試験の数2Bで一見すると難しそうな問題が出ることが多いように感じていて「いけるいける難しくない落ち着いて考えればわかる」と何回も念じながら問題文を読んでいたのを思い出した。「難しそう」と考えるよりも「わかりそう」とか「なんかいけそう」みたいな方向性のマインドを持っていたほうがパフォーマンスも高くなるなーと改めて思うなどした。3
  • 難しい課題も小さい部分に分割して段階的に進めるとうまくいくことを実感できた。
    • 0からコンパイラを実装するのは気が引けるが、仕組みを理解していくつかの部品に分解して進めることで、複雑なソフトウェアを着実に構築する経験を得ることができた。
  • コンパイラやアセンブラの実装で泥臭い処理をたくさん書いたおかげで泥臭さへの耐性が多少ついた。そもそも複雑なものは実装も複雑になりうるのでそういうケースでは特に実装力が大事だなーと思うなどした。

おわりに#

『Goならわかるシステムプログラミング』を読んでからかなり気になっていた本だったので無事完走できてよかった。

最近のテーマであるCS力の強化をまた一歩進めることができた。

次は『体験しながら学ぶ ネットワーク技術入門』 でネットワークの理解を深めていこうかなと思う。

あとはソフトスキル系でいうと『エンジニアリングチームのリード術-―Googleに学ぶインディビジュアルコントリビューターとマネージャーのための実践ガイド』 も良さそうなので読んでみようと思う。

  1. 実際はテトリスではなく別のブロック崩しのようなゲームではある ↩︎

  2. Twitterを見ているとパーザと表記する流派も存在する模様 ↩︎

  3. 近い話が何かがそれほど得意でなくても、世の中の平均よりは得意だと思っておいたほうがよい - Lambdaカクテル で綺麗に言語化されている。 ↩︎