「Nand2Tetris」について、最後に記事を書いてから4ヵ月も経過してしまった。
決して怠けていたわけではなく、この間に「Nand2Tetris」の11章の「コンパイラ作成」までクリアした。
おさらいになるが、Nand2Tetrisは「ハードウェア」と「ソフトウェア」２つのパートから構成されている。 ハードウェアまでは1章ごとに、感想を書きながら進められたのだが、ソフトウェアパートからの演習は非常に手応えがあり（ありすぎて）、感想を書く余裕がなかった。
というわけで、今回は「Nand2Tetris」の感想をまとめて記事にした。
5章 : コンピュータアーキテクチャ
ハードウェアの総仕上げ：CPU構築
このパートでは1章～3章で作成した論理ユニットを組み合わせて、Hackコンピュータと呼ばれるNand2Tetris専用のコンピュータを作成する。
この章の山場はなんといっても「CPU構築」だ。
HackCPUはとても単純なアーキテクチャなので、レジスタも２つしか用意されていない。そのうちの１つのはAレジスタと呼ばれ、メモリアドレスを指定するモード、値として仕様するモードがあるため、概念理解に苦戦した。
ちなみに本書には答えは載ってないものの、大まかな素案が提示されているので、それを参考にしてCPUを作成した。
そしてCPUの肝は、デコーダー(decode)だ。デコーダーはCPUの命令セットを解釈するためのユニットで、CPUの命令セットデコードには、機械語の理解が必要不可欠だ。本書ではデコーダーの部分だけは自分で考えて、実装することになっている。5章までは丁度いい難易度だと感じた。（6章から大変なことを意味する）
作成したCPUは下記。 https://github.com/i-net-singularity/nand2tetris_projects/blob/main/05/CPU.hdl
CPUの単体テストをクリアすることを優先したため、ロジックの最適化は2周目の楽しみに取っておく。（言い訳） あとは、「メモリ」を組み上げ、先に述べたCPUとつなぎ合わせ「Hackコンピュータ」を作るところまでが5章の内容だ。
6章 : アセンブラ
6章からソフトウェアパートになる。 正直「CPU」作成したら、残りのソフトウェアパートは楽勝だろうと思っていたが、大間違いだった。
ソフトウェアパートでは最初に、HackCPU用のアセンブラを作成する。 "好きなプログラム言語を使ってアセンブラを作成せよ" というのが本書の方針なので、勉強も兼ねてPythonを選んだ。この辺は本当に好みだが、Pythonで作っている方が多いかな。
※結果的にPythonを選択したのは正解だった。 Pythonが持っている組み込み関数の力が大いに発揮された。
ちなみにアセンブラとは、アセンブリ言語で記載された原始的なソースコードを機械語に変換するプログラムのことだ。 アセンブリはソースコードの1行＝機械語の1行に対応している。アセンブラの動きは入力されたソースコードを1行ずつ機械語に変換していくという単純なものになる。Python学習も兼ねるには丁度良い難易度だ。
この章で学ぶ最初の重要な概念は「シンボルテーブル」かと。 …と言っても難しいものではなく、入力されたソースコードに登場するシンボル（変数）を管理するテーブルだ。 「シンボルテーブル」の登録/参照がアセンブラの肝だった。アセンブラ開発は考える部分も少なく、1週間ぐらいで作成できた。
成果物
作成したアセンブラは下記。 https://github.com/i-net-singularity/nand2tetris_projects/blob/main/06/n2t_hack_assenbler_byPy/n2t_hack_assembler.py
7章～8章 : バーチャルマシン言語
7章～8章の目的は、バーチャルマシンと呼ばれるスタックベースの仮想コンピュータの言語を学び、バーチャルマシン言語(以下VM言語)をアセンブリに変換するVMトランスレータを作成することだ。
この章から、1章ごとの演習ボリュームが多くなり苦戦した。
7章8章の肝はスタックマシン。 スタックマシンの働きはとても単純なのに複雑な演算ができてしまうのは本当に良く考えられている。 バーチャルマシンで、以下概念をしっかり理解すれば先に進めるはずだ。
- バーチャルマシンのメリット
- スタックマシン
- メモリセグメント
7章 : 前半パート
下記機能を記した中間コードをアセンブリ言語に変換するプログラムを作成する。
- 算術演算
- メモリアクセス
算術演算でスタックマシンの働きを学び、メモリアクセスではHackコンピュータのメモリセグメントの働きを学ぶ。 メモリセグメントは後々の高水準言語で変数のスコープを実現するために必要な概念となる。 この章の時点だと、自分はメモリセグメントの重要性に気づけなかった。
8章 : 後半パート
7章で作成したプログラムを拡張し下記機能を追加する。 8章の演習を全てクリアした暁には、VM言語をアセンブリに変換できる完全なVMトランスレータが完成しているはずだ。
- プログラムフロー
- サブルーチン呼び出し
サブルーチン呼び出しの仕組みは非常に面白く感じた。 スタックマシンのシンプルでエレガントな働きによってサブルーチンが見事なまでに実現されていた。
成果物
作成したVMトランスレータは下記。 https://github.com/i-net-singularity/nand2tetris_projects/blob/main/08/n2t_hack_vm_translator.py
9章 : Jack言語
9章では、Jack言語という高水準言語を学ぶ。 Jack言語は、JavaやC#に似た文法を持つ、本書専用の学習用オブジェクト指向言語だ。 コンパイラ作成がしやすいようにかなり上手く設計された言語で、本章でJack言語の文法習得を通して、コンパイラ作成の基礎を固めることになる。
この章は、他の章と違ってJack言語の文法を学ぶためだけの章なので少し毛色が違う。自分は1回読んだだけで、次に進んだ。
しかしながら、次章のコンパイラ作成の段階になってから、9章は何度も読み返した。 基本的に大切な仕様がさらっと書かれていることが多く、見落とすことが多々あった。
10章～11章 : Jackコンパイラ
いよいよコンパイラだ。 コンパイラは10章～11章の2章に分けて開発する。
Jackコンパイラは、Jack言語のソースコードを読み込みVM言語を出力する働きをもつ。実際のコンパイラと違って出力結果はテキストファイル形式のVMファイルなので、出力結果の確認は容易な部類になる。
自分はコンパイラ理論など全くの無学だったため、コンパイラ作成が一番苦労した。 人によっては１週間で出来る人もいるらしいが、私は2ヵ月弱ぐらい要した。 とはいえ、ステップを踏みながら、1歩1歩進めば、必ずコンパイラを作成できるようになっているから安心してほしい。
ファーストステップ
コンパイラ作成にあたり、いくつか重要な概念を学ぶ。 解説したいところだが余白がたりないため、説明は他者様に委ねる。
10章 : 前半パート
10章では、まずソースコードをトークナイザーでトークンと呼ばれる最小構成要素に分解する。 次にパーサーでJack言語の文法に従ってツリー構造のXMLファイルを生成する。
- トークナイザー
- パーサー
この章の演習をクリアしないと11章に進めないので、この章は非常に重要だ。
11章 : 後半パート
10章をクリアできれば、あとはパース内容をコードに変換する「コードライター」を作成するだけだ…。 自分の場合「コードライター」が本書の中で一番苦戦した。 ちなみに多くの人は、前章の「パーサー」で苦戦や挫折するようだ。
開発の流れ的には本書の構成どおり、下記を順番に作るのが良いだろう。
- シンボルテーブル作成
- データ変換
- コードライター
コードライターでは、パース結果に応じたVM言語を出力する。 ここで、「コンストラクタ」や「インスタンス」といったオブジェクト指向言語の重要な概念をVMレベルでどのよう実現するかを通して、オブジェクト指向の真の意味を学べた気がした。（あくまで個人の感想です）
その他、シンボルテーブルだが、似たような概念を既に学習済みだ。そう、アセンブラだ。 アセンブラでは機械語生成のためにソースを2度読みする必要があったが、コンパイラは最初の1回の読み込みで解析が完了するところだろうか。
データ変換はシンボルテーブルに基づいて、Jack言語内の変数をインデックスに変換する処理だ。この辺りは、特に苦戦する箇所はなかった。実際のコンパイラでは、実用的なシンボルテーブルはハッシュテーブルがチェインした構造になるようだ、Jackは単純な仕様のため2つのシンボルテーブルだけで済む。
コンパイラ作成方針
コンパイラは無学者が取り組むには非常に手ごわい。 そこで、以下方針でコンパイラを作成した。
公式サイトに用意している講義形式PDFをちゃんと読む
公式サイトの講義形式PDFは、本書の内容の詳細について説明がある。 本書の内容を一通り読んだあとに講義資料を読むと、より深く理解できる。 何よりも、講義資料にはコンパイラ作成のヒントが満遍なく書かれているので必読だ。
-
本書ではXML出力からVM出力に切り替えていたが、私はXML出力を止めずに追加でVM出力をするようにした。 理由は簡単で、XMLの構文解析結果が「コードライター」のデバッグに役立ったからだ。
公式サイトのJackコンパイラの出力結果を解析した
自作コンパイルだけだとデバッグはとても難しいものとなる。 そこでちょっとズルいけど、お手本のコンパイル結果と比較解析する手法を採った。 しかし、おかげで自身のコンパイラの間違っている箇所を効率的に見つけることができた。
成果物
P 作成したコンパイラは下記。 https://github.com/i-net-singularity/nand2tetris_projects/blob/main/11/n2t_jack_analyzer.py
コンパイラに関しては、他の方々が作成したコンパイラを大いに参考にした。
総括と今後の課題
本書の醍醐味は、ハードウェアからソフトウェアまでの知識が一直線に繋がったときの達成感かと思う。 コンピュータサイエンスに興味がある方は、取り組む価値があるはずだ。
突っ込みどころは、Nand2Tetris と謳いながら、Tetris が登場しないでPong と呼ばれるピンポンゲームで終わったことだろうか。
実はまだ12章(オペレーティングシステム作成)は未着手だ。 「コンパイラまでやりきる」と決めて取り組んだので、いったん一区切りつけることにした。
11章まで終わった段階だと自作コンパイラができていて、OSはビルトインのVMライブラリを使っている状態だ。 この状態では、「コンパイラを自作してプログラムを動かせた」とは言えないので、時間と心の準備が整い次第、12章に取り組む所存だ。
その他の課題としては、「各章の成果物の最適化」、「テトリス開発」、「FPGAへの実装」などを考えたい。 やるべきことが沢山ありすぎて、どれから手をつけていいか…こういう状態を楽しみたい。
進展があり次第、また報告するのでよろしくです！
