Nand2Tetrisって何？
『コンピュータシステムの理論と実装』(通称 nand2tetris)という本があります。
一言で言うと「ゼロからコンピュータを作る」本です。Nand回路から始めて最終的にテトリスを作ります。
とても面白い本なのですが、なかなかハードルが高いものでもあるためもっと気軽に近い内容を楽しむことができるゲームを紹介します。
Turing Completeって何？
steamで販売されているゲーム(現在早期アクセスで2050円)です。
「宇宙人に攫われた主人公が生存のため知能テストを受ける」という設定でゲームが始まります。
コンピュータを作れないと食われるらしい。
我々は生き残るためにコンピュータをゼロから作れるようにならなければいけない。
ノイマン型コンピューターとして動くものを作るために、ステージ型で課題をこなしていきます。
ステージ構成は以下のような感じ。緑の四角形が全部ステージです。
長い。実はまだ上もありますが、ひとまず動くコンピュータを作ってプログラミングするまでの流れをざっと解説、紹介していこうと思います。
シンプルに実装の答えを知りたい方はsteamのコミュニティにわかりやすいガイドがあるのでそちらをご覧ください。
https://steamcommunity.com/app/1444480?l=japanese
BASIC LOGIC
最初はNAND回路のみを与えられて、これを用いて基本的な論理回路を作っていくところから始まります。
以下はNOT回路。
AND回路とか
OR回路とか。
こうして作ったものは後のステージで(再構成しなくても)独立した1つの回路として使いまわすことができます。
いろいろ作っていき、XNOR回路を作るあたりで第1チャプターは終了です。
この次は算術回路とメモリーを作るチャプターを平行で進めていきます。
ARITHMETIC
算術(arithmetic)回路を作ります。
まず半加算器を作り
全加算器を作ったり
さらにそれを8ビットに拡張し、255+255の足し算をしたり
同様に8ビット同士のOR回路を作ったり。
最終的に8ビット同士のOR, NAND, NOR, AND, ADD, SUB演算を作り、命令用の制御信号(0~7)で行う処理を切り替えられるようになれば完成です。
上記画像は秘伝のタレ方式で作った回路なのでひどいことになってます
MEMORY
メモリを作成します。
まず「1クロック前の入力を出力する」という新パーツが与えられます。下記画像なら毎クロックでオンとオフが切り替わります。
これを使ってメモリを作ります。
「制御信号がオン」なら入力値を記録し、「制御信号がオフ」なら今持っている値をループして保存させておく回路を作ります。
これを8ビットに拡張します。
これで8ビットのレジスタが完成。
CPU ARCHITECTURE
メモリと算術回路ができたので、CPUを作っていきましょう。
CPUは「レジスタ」6個(REG0~REG5)で構成を行います。プログラムからの制御信号と標準入力が1つずつ与えられ、1つの標準出力を行います。
制御信号のうち7, 8ピンは以下の4種の命令のうちどれかに分岐するために使用します。
- 「00」命令: 制御信号の値をレジスタ(REG 0)に直接挿入する
- 「01」命令: レジスタ(REG 1)とレジスタ(REG 2)で計算(AND, OR, ADD, SUB等)を行い、レジスタ(REG 3)に挿入する
- 「10」命令: 任意の入力元(標準入力またはレジスタのどれか(REG0~REG5))から任意の出力先(標準出力またはレジスタのどれか(REG0~REG5))にコピーを行う
- 「11」命令: レジスタ(REG 0)の値を条件式(>0, =0, NEVER, ALWAYS等)にかけ、条件を満たすならレジスタ(REG 0)の値に基づいてプログラムの実行位置を変更する
それぞれの細かい制御は1~6番目のピンで行います。
これを実装したものが以下の回路となります。
いやーーーー汚い。内容も無駄だらけなので間違っても参考にはしないでください。
とにかく、これでコンピュータが完成しました。
PROGRAMMING
完成したコンピュータを自分でプログラミングして動かしてみましょう。ここからは回路に手を加えるのではなく、プログラムに手を加える作業になっていきます。
主に以下の4種類のような命令になります。左の2ケタが命令の種類を表し、残り6ケタで命令の詳細を表しています。
- 「00」命令: レジスタ(REG 0)に対して指定した値(この場合は1)を挿入します。
- 「01」命令: レジスタ(REG 1)とレジスタ(REG 2)で計算(この場合はADD)を行い、レジスタ(REG 3)に挿入する
- 「10」命令: 任意の入力元(この場合は標準入力)から任意の出力先(この場合は標準出力)にコピーを行う
- 「11」命令: レジスタ(REG 0)の値を条件式(>0, =0, NEVER, ALWAYS等)にかけ、条件を満たすならレジスタ(REG 0)の値に基づいてプログラムの実行位置を変更する
条件式をALWAYSにするとGOTO文として使えます。
こうしたバイナリコードのままではプログラミングも大変なので、数値に名前を付けて登録できます。
これを元にプログラムを書きました。
- レジスタ(REG 0)に対して値「1」を入れる(00命令)
- レジスタ(REG 0)の値をレジスタ(REG 1)にコピーする(10命令)
- レジスタ(REG 3)の値をレジスタ(REG 2)にコピーする(10命令)
- レジスタ(REG 1)の値とレジスタ(REG 2)の値を足してレジスタ(REG 3)に入れる(01命令)
- レジスタ(REG 3)の値を標準出力する(10命令)
- レジスタ(REG 0)に対して値「0」を入れる(00命令)
- 条件(ALWAYS)を満たした時プログラムの実行位置を0番目に戻す(11命令)
これを行っていくと、1, 2, 3,...と順番に値を標準出力していくことができます。
こういうものを作っていき、ロボットを動かして迷路探索アルゴリズムを作るまで行えばひとまずゲームクリアです。
(右下の子がロボット。これを標準出力の値で操作する。)
その先へ…
上のアルゴリズムを書いたところでこのゲームは一区切りとなりますが(実績 Turing Complete 解除)、まだこのゲームには続きがあります。
(以下がまだできてないたくさんのステージ)
CPUのビット数を増やしたり、関数を作ったり、さらに複雑なアルゴリズムを作ったりしていくそうです(まだ未着手)。
まとめ
- CPUを実際に作ってみる経験を持つことで、低レイヤーという苦手意識があった分野の理解が深まりました。アセンブラかつ使えるメモリが少ない(レジスタ6つだけ！)制限だらけのプログラミングもなかなか面白かったです。
- 何よりその体験をゲームでできたことがよかったです。環境の用意は簡単ですし、誘導も丁寧、操作も簡単にできました。
興味のある人、特に『コンピュータシステムの理論と実装』に挫折した人はやってみてほしいです。