1.はじめに

「コンピュータシステムの理論と実装(通称:nand2tetris)」という本で低レイヤーの勉強をしました。本記事はそのまとめです。

記事を書くにあたって、Github のリポジトリを見直したところ、

nand2tetris/golang

“Initial Commit”が今年の 1 月 21 日なので、半年以上開発に取り組んだことになります(現在、8 月 8 日)。

頑張ったね！！！… と褒めてやりたいところですが、まだ完走はしていません。コンパイラが一部未実装です。そのため、本書が設定するゴールである「テトリス」が動きません。

代わりに、と言っては微妙ですが、“Hello,World”を表示するところまでできました。

テトリスはまだ動かないのですが、”Hello,World”を表示するという象徴的なコードが動作し、非常に切りがいい、また、これから夏インターンやら研究やらで、実装を進めることができなさそうなので、一度まとめておくことにしました。

2.nand2tetris とは？

nand2tetris は「コンピュータシステムの理論と実装」という本で取り組むプロジェクトの通称です。

「NAND ゲートからテトリスが動くようなコンピュータを作ろう」というのが本プロジェクトのコンセプトであり、名前の由来です。

NAND ゲートから…テトリス 🤔🤔🤔？

このプロジェクトに取り組む前はあまりにかけ離れたスタートとゴールがどのようにつながるのか、全くイメージが湧きませんでした。ゴールまでの手順をざっくりと説明すると、

• NAND ゲートから、機械語(0101…)が動作する CPU を作り、
• アセンブリを機械語に変換するアセンブラを作り、
• 中間言語をアセンブリ言語に変換する変換器を作り、
• 高水準言語・Jack(like Java)を中間言語に変換するコンパイラを作り、
• Jack でテトリスを実装する。

という流れです。

このように、NAND ゲートを最小単位として、CPU や機械語,コンパイラ,OS と言ったトピックを実際に作りながら、理解していきます。

僕は普段、React,TS,などの上位レイヤーのイケイケ Web 技術に触れる機会が多いですが、本書を通して「コンピュータシステム」をゼロから作った経験は低レイヤーを勉強・理解する大きな手助けになったと思います。

3.やろうと思ったきっかけ

僕が nand2tetris で低レイヤー勉強しようと思った理由は以下の点が挙げられます。

コンピュータサイエンスの基礎知識を学ぶ

プロフィールを見ればわかりますが、私は一応理工学部の情報通信学科に通う、コンピュータサイエンス専攻の学生です。そのため当然、必修授業はコンピュータサイエンスに関連するものばかり。

人並み以上に「成績を取る」ことには力を入れてきたつもりですが、

• 授業を通して得る知識は手を動かして学ぶ知識と比較して、理解度にどうしても差が生じてしまう。
• 「アルゴリズム」「離散数学」「言語処理系」と言った苦手そう・興味を持てなかった授業を避けていた節がある。

などの理由から、大学を通じて基礎的なコンピュータサイエンスを学ぶことがあまりありませんできなかった気がしています。

コンピュータサイエンスの基礎が情報学科のくせに欠落しているなぁ… 。僕にはそんなコンプレックスがあり、学び直しがしたかったというのが理由の一点目として挙げられます。

• 低レイヤーに対する知見があるという圧倒的ハッカー感.

「低レイヤーを理解している人ってなんか強そうだよなー」というのが 2 つ目の理由です。「コンパイラ作れる」「CPU の構造考えながらコード書いてる」「このコードの機械語は 0101~で…」とか言えたら、スーパーかっこいいじゃありませんか。これが理由の二点目です。

ということで、以上の動機から、もともと興味があった nand2tetris に取り組むことにしました。以下に現時点で完成している部分のみを雑に振り返っていきます。

4. 実装

4.1 ハードウェア編 (1 ~ 5 章)

ハードウェア編(1 ~ 5 章)ではノイマン型アーキテクチャのハードウェアを 0 から作ります。各章でざっと以下の通りです。

• 1 章:nand ゲートを組み合わせて、XOR や AND,マルチプレクサといった論理ゲートを作る.
• 2 章:1 章で作った論理ゲートを組み合わせて、加算器や ALU(算術論理演算器)を作る.
• 3 章:クロックや記憶という概念の登場。フリップフロップを最小単位として、値を保存してくれるレジスタやメモリ,カウンタといった素子の開発
• 4 章:機械語やアセンブリの文法.
• 5 章:機械語が動作する CPU やメモリも含むコンピュータの開発.

こうして出来上がったキャッシュなし・シングルコアのハードウェア。コンピュータの性能的には貧弱なのでしょうが、機械語を入力したら、意図した動作をする CPU ができたときは感動ものでした。

4.2 コンパイラ(6 ~ 11 章)

次にコンパイラの実装です。ここでは本書が用意したプログラミング言語 jack を機械語に変換するコンパイラの実装を行います,

• 6 章: アセンブリを機械語に変換するアセンブラの実装
• 7 章: 中間言語をアセンブリに変換する変換器の実装(前半)
• 8 章: 中間言語をアセンブリに変換する変換器の実装(後半)
• 9 章: Jack の紹介
• 10 章: Jack を中間言語に変換するコンパイラの実装(字句解析,構文解析)
• 11 章: Jack を中間言語に変換するコンパイラの実装(中間言語の生成,評価)

10 章辺りからは言語処理系の知識がある程度ないとキツイと思います(自力でやろうとして、かなり迷走しました。)

そのため、10 章以降の実装は 「Go で作るインタプリタ」で知識を補填しながら行いました。

4.5 OS

まだやってないですが、jack を用いて OS の実装を行います。

5.まとめ

以上がざっとした振り返りになります。

今回、断続的ではありますが、半年以上の時間をかけて nand2tetris に取り組みました。

本プロジェクトでコンパイラや CPU のフルスクラッチ実装をやったわけですが、やってみたことを通して、

• プログラミング言語が機械語に変換され、回路で動作するまでのイメージが鮮明になった。
• 構文解析が好きになった。
• Go が初心者レベルから、任意の処理・ソフトウェアをテスト駆動で実装できるぐらいまで書けるようになった。
• テスト駆動開発によるインクリメンタルな開発の習慣がついた。

といった点が良かったと思います。

一方でプロジェクト管理が自分の今後の課題だなぁ、とも思いました。この nand2tetris、当初は春休みで終わらせる予定でしたが、夏休みにまで食い込んでしまいました。

大きなプロジェクトを小さなプロジェクトに分割して、そのプロジェクトをタスクに分割して、そのタスクを TODO リストに分割して…とプロジェクトを始める前に、必要な作業をタスクレベルまで分割し、小さなタスクにかかる所要時間の足し算によって工数を見積もる習慣をつけるべきだなぁと思いました。

テトリスを動かすことができていないのが非常に悔しいのですが、1 ~ 9 章まではできているので今年中にコンパイラと OS を実装して、完全制覇したいと思います。

nand2tetris、一旦休憩。

【追記】

11 月 10 日完走しました！！