Nand2Tetris(コンピュータシステムの理論と実装)でCPUからOSまで一気通貫で作るのが最高に楽しかった話
どうも、しいたけです。
去年あたりからローレイヤー周りの知識を充実させようと思い、 低レイヤを知りたい人のためのCコンパイラ作成入門 を読んでCコンパイラを書いてみたりx86_64の勉強をしたりしていました。
今年に入ってから、よりローなレイヤー、具体的にはハードウェアやOSについてもう少し知りたいと思い始め、手頃な書籍を探していました。 CPUなどのハードウェア周りについては概要しか知らなくて手を動かしたことがないので、実際に何か作りながら学べるものとして、 O'Reilly Japan - コンピュータシステムの理論と実装 に挑戦することにしました。
O'Reilly Japan - コンピュータシステムの理論と実装
成果物は以下のリポジトリに置いてあります。
結論から言うと、やってみて大変楽しめました!
特にハードウェア周りは今まで挑戦したことのない分野で、回路の設計がとても新鮮で楽しんで取り組めました。 ちょこちょこ間が空いたりしたので、全部完走するまで10ヶ月ちょっとかかりましたが……。
コンパイラやVMの作成は、Cコンパイラ書いてみたりした経験があったのですんなりできましたが、実装言語にRustを採用することでRustの習熟にも役立ちました。 (というかハマったのは主にRustの学習で、使い慣れた言語だったらおそらくすぐに実装できたはずです……)
OSに関してはかなり物足りなかったので、こちらは別な教材で改めて学びたいと思います。
Nand2Tetrisってなに?
「コンピュータシステムの理論と実装」(通称Nand2Tetris: NANDからテトリスへ)は、コンピューターの基本的な構成要素であるCPUやメモリから始めて、そのアーキテクチャ向けの機械語を生成するコンパイラ、アプリケーションとハードウェアの橋渡しをするOSまでを 順を追って作成することで、基本的なコンピューターシステムの動作原理が理解できるような構成になっています。
Courseraにコースがあって、著者のShimon Schocken教授とNoam Nisan教授がインストラクターとしてオンラインで受講することができます。
僕はヘタレなので受講はせずに独学しましたが、気合入れて取り組むつもりなら受講するのもありではないでしょうか。
Nand2Tetrisでは、Hackという本書独自のアーキテクチャ用のCPUやメモリなどをNand回路から始めて作成し、Jackという本書独自のプログラミング言語のHackアーキテクチャ向けコンパイラを実装し、そのJack言語を用いてOSを書くことで、ハードウェアからOS、アプリケーションまですべてを自前で作っていきます。 とはいえ、Hackアーキテクチャで作成するCPUは16bitでデータレジスタとアドレスレジスタがそれぞれひとつしかない単純なCPU(乗除算すらできません!)ですし、Jack言語はオブジェクト指向言語ですがJavaをかなり単純化した言語仕様です。 また、OSはプロセス管理やファイル管理、ネットワークなどはサポートせず、単純にキーボードやスクリーンなどメモリマップドされたハードウェアを操作するための便利ライブラリのような位置づけです。
それでも、順番に実装していくと(シミュレーター上とはいえ)このようなゲーム(アプリケーション)を動作させることができます!
終わった。Nand2Tetris、Jack言語コンパイラのコード生成の実装が。
— 極限生命体しいたけNA (@yuroyoro) November 13, 2020
CPU、アセンブラ、スタックマシンVM、コンパイラと作ってきて、ようやくアプリケーションがエミュレータ上で動くようになったぞォ……!! pic.twitter.com/KmojKek9wT
テトリスちゃうやんけ!!
さて本の構成ですが、おおまかにハードウェア、コンパイラ、OSの3つのパートに分けられており、各パートはいくつかの章で構成されます。 章ごとに演習問題が用意されており、実際にその問題で作ったパーツが次の章で利用される仕掛けになっています。 例えば、回路設計では最初の1章でANDやORゲートを作り、次の2章ではそれらを組み合わせて加算器を作る、といった具合です。
本書はテストするための回路シミュレーターやCPUシミュレーターがすでに用意されており、また章ごとの課題もテストケースが用意されています。 課題の内容にしたがってHDLを書いたりプログラムを作成して、シミュレーター上で用意されているテストをパスすればその章はクリアです。
このシミュレーターやテストが用意されているのが非常に取り組みやすく、テストをパスすることを目標として実装すればよいので迷わなくてすむのがよかったです。 そうしてテストをパスするように章ごとの課題をこなしていけばいつのまにかコンピューターシステムが完成しているのです。
1章から5章: ハードウェア
まず、最初はNandゲートを組み合わせて論理ゲートを作り、それらのパーツを組み合わせて加算器やメモリやALUなどを実装します。 作ったALUをベースにCPUを設計し実装するところまでが、ハードウェアのパートでやることです。
- 1章 ブール論理 : Nandゲートを組みわせてAND, ORなどの論理ゲートを作成します。
- 2章 ブール算術 : AND, ORなどのパーツをもとに加算器やALU(算術論理演算器)を作ります
- 3章 順序回路 : フリップフロップを用いて1bitレジスタから始めて16KBメモリ, プログラムカウンタを作ります
- 4章 機械語 : 機械語についてHackアーキテクチャ向けのアセンブラを書いて学びます
- 5章 コンピュータアーキテクチャ : ここまで作ってきたカウンタやALUを組み合わせて、4章で学んだHackアーキテクチャの機械語を実行できるCPUを作り、メモリや入出力と組み合わせます
回路設計ですが、HDLを書いてシミュレーター上でテストしながら進めていきます。 本書のサポートサイトからダウンロードできるツールチェインにハードウェアシミュレータがあり、実装したHDLをそのシミュレーター上でテストします。 HDLは書いたことがなかったのですが、本書で扱うものは非常に単純なルールなのですぐに覚えることができました。
こんな感じでやっていきます。
駆け出しエンジニアなので論理ゲートの実装の勉強をしています pic.twitter.com/bdMv0B0wzM
— 極限生命体しいたけNA (@yuroyoro) February 6, 2020
回路設計に悩むようすです
Nand2Tetris、今日はプログラムカウンターの実装まで。わからんくなったので回路図書いたわ… pic.twitter.com/PkQZtmPl5l
— 極限生命体しいたけNA (@yuroyoro) May 6, 2020
CPUの実装でこのページが出てきたときはめっちゃテンションあがりましたね?
たのしい。さいこう pic.twitter.com/iHPZJmWqQB
— 極限生命体しいたけNA (@yuroyoro) May 13, 2020
シミュレーター上で、自分がHDL書いたCPUがHack機械語を実行できるようになったときの様子です。やりきった感あった。
CPUとMemoryを実装したので組み合わせて、シミュレーター上で機械語が動くようになったゾォ……
— 極限生命体しいたけNA (@yuroyoro) May 15, 2020
HWはこれで一段落 #nand2tetris pic.twitter.com/Vx8hfZRowL
6章から11章: コンパイラ
6章からはコンパイラの実装です。 本書独自のJack言語のコンパイラを実装して、Jack言語ソースコードからHack機械語を生成できるようになるまでが目標です。
- 6章 アセンブラ : Hack機械語を生成するアセンブラを実装します
- 7章 バーチャルマシン#1:スタック操作 : スタックベースのVMを実装します。VMソースコードから6章で作ったアセンブリを生成できるようにします。
- 8章 バーチャルマシン#2:プログラム制御 : VM実装の続きで主に関数呼び出しを実装します。
- 9章 高水準言語 : Jack言語の言語仕様についての説明です。実際にこれから作るJack言語を書いてみます。
- 10章 コンパイラ#1:構文解析 : Jack言語コンパイラのフロントエンド部分の実装です。再起下降パーサーを書いてAST生成まで実装します。
- 11章 コンパイラ#2:コード生成 : Jack言語コンパイラのバックエンド実装です。ASTからVM向けのコード生成を行います。
コンパイラの章は大きく分けて3部構成で、アセンブラ、バーチャルマシン、Jack言語コンパイラに分けられます。 それぞれのパートで実際にアセンブラやコンパイラを実装するわけですが、言語仕様を満たす実装ができるのであれば使用するプログラミング言語は何を用いても構いません。
「せっかくだから俺はこのRustという言語をを選ぶぜ」
アセンブラやVMの実装では、生成された機械語やアセンブラがCPUシミュレーター上で動作するかを確認します。 ハードウェアではHDL上で回路をテストしましたが、コンパイラは生成したコードをシミュレーターでテストします。 テストケースとして入力となるソースコードとその期待する動作をテストするためのスクリプトが用意されているので、テストがパスするような機械語/アセンブリ/VMコードを生成できるよぅに頑張るだけです。
アセンブラの実装はasmファイルを行ごとに読んでパースして機械語に変換するだけなので悩みはなかったです。この頃は主にRustについて悩んでいた
Nand2Tetris、ようやくRustでのアセンブラ実装が終わってVMの実装に入ったぞ
— 極限生命体しいたけNA (@yuroyoro) September 8, 2020
VM作るのたのしい
たのしい
Nand2Tetrisのアセンブラ、GoとかRubyとかjsとか手慣れた言語で書いたら多分2, 3時間で実装できたと思うけど、うっかりRustを勉強しながら書いてみたら実質2週間くらいかかって学習効率よくなかったですね面白かったけど
— 極限生命体しいたけNA (@yuroyoro) September 8, 2020
スタックマシンはCコンパイラ作成入門で一度実装したことがあったので、関数呼び出し時のスタックとかリターンアドレスとかそのあたりは理解していたのですが、Hackはレジスタ2個しかなくて実装しんどかったです。
配列のn番目への書き込みにn回の命令が必要なアセンブリ吐いてすみません……レジスタが足りない
— 極限生命体しいたけNA (@yuroyoro) September 18, 2020
オフセットレジスタの有り難さを身を持って体感してるぞラ
レジスタ2個しか無いのでレジスタ割付とか実装しなくてよくて楽ですね😇
— 極限生命体しいたけNA (@yuroyoro) September 18, 2020
汎用データレジスタとアドレスレジスタが一つづつしか無いHackアーキテクチャで単純とは言えスタックマシン実装するのはダルかった。ツールチェインにCPU Emulatorがあって助かった
— 極限生命体しいたけNA (@yuroyoro) September 28, 2020
asm生成で最初はjmp命令を駆使してサブルーチン化したasmを吐いていたが、どうせ命令数変わらない(どころかjmpの分増える)のでインライン展開することにしたわ
— 極限生命体しいたけNA (@yuroyoro) September 17, 2020
コンパイラに感謝する様子です
アセンブリ書くのダルすぎるので、高水準言語からアセンブリや実行可能な機械語を生成してくれるコンパイラは最高という気持ち高まっています
— 極限生命体しいたけNA (@yuroyoro) September 24, 2020
コンパイラが頑張ってjump命令吐いてくれるおかげでGOTOから書かなくてもよいんだぞコンパイラに感謝して?
— 極限生命体しいたけNA (@yuroyoro) September 28, 2020
Rustへの理解が深まっていく様子です
Rust、所有権と借用についてはなれてきたけど、LIfetime修飾子だけは使いこなせる気がしないです
— 極限生命体しいたけNA (@yuroyoro) September 24, 2020
迷ったら、コピーですよ? (知能)
Rust、構造体メンバに参照もたせるとLIfetime修飾子で死ぬけど、std::rc::Rcで参照カウントで持たせたらLifetime考えなくても参照カウントで勝手に管理してくれるので解決では??
— 極限生命体しいたけNA (@yuroyoro) October 27, 2020
(なお参照リークについては考えない事とする😇)
Rust、「こんなダルい思いするくらいならコピーのコストくらい払ったるわ」という誘惑と戦うプログラミング言語だという実感です
— 極限生命体しいたけNA (@yuroyoro) October 31, 2020
Rustのmacro、便利😇
— 極限生命体しいたけNA (@yuroyoro) November 4, 2020
Rust書いてる僕です pic.twitter.com/cmdQHAOBi1
— 極限生命体しいたけNA (@yuroyoro) September 14, 2020
現状です pic.twitter.com/Q70KBkJEyO
— 極限生命体しいたけNA (@yuroyoro) September 30, 2020
VM実装終わったとき
Nand2Tetris、RustでJack VMの実装まで終わったぞhttps://t.co/v18qXGtFZy
— 極限生命体しいたけNA (@yuroyoro) September 28, 2020
Jack言語コンパイラに関しては再起下降パーサーを書いたことがあるので実装面で悩むことはなかったです
再帰下降パーサー、好き♡
— 極限生命体しいたけNA (@yuroyoro) October 14, 2020
Rustで再帰下降パーサー書いてるけど、意図せずにstreamを消費するようなバグが起きにくいのでよい感じです
— 極限生命体しいたけNA (@yuroyoro) October 29, 2020
ただしコンパイル通すまでが厳しい
Rustで抽象構文木のような再帰的な構造を定義するとどうしてもBoxに入れざるを得なくて、rustcはどうやってるか見てみたらやっぱりBoxに入れてたので間違ってなかった
— 極限生命体しいたけNA (@yuroyoro) November 4, 2020
Rustでparserをベタで書いてみたけど、コンパイルエラーにすべき箇所がちゃんと型チェッカで網羅できたのでよかったです ᕕ( ᐛ )ᕗ
— 極限生命体しいたけNA (@yuroyoro) November 8, 2020
できた。Nand2Tetris 10章のJack言語コンパイラのフロントエンド部分のRust実装が。https://t.co/zXeqwuf4tN
— 極限生命体しいたけNA (@yuroyoro) November 8, 2020
12章: オペレーティングシステム
正直ここからはおまけです。Jack言語でOSを書くのですが、このOSは上で述べたとおりハードウェアとのやりとりをするためのメモリアクセスを便利にしてくれるライブラリみたいなものです。 Jack言語も非力な言語なので書くのはダルかったです。 ただ、自作したコンパイラがちゃんとシンタックスエラーを検出してくれたときはちょっとしたうれしみが湧き上がりましたね?
自作コンパイラ、ちゃんとコンパイルエラー検出してくれてすごい
— 極限生命体しいたけNA (@yuroyoro) November 16, 2020
たとえば、画面に文字を出力するのにDMAされた画面のピクセルに対応するメモリのビットをフォントにしたがって立てる処理とか書くのダルかったです。
画面に文字を出力するのマジでダルかったわ pic.twitter.com/vqEok7c89y
— 極限生命体しいたけNA (@yuroyoro) November 23, 2020
あと、画面に●を描画する際の高速なアルゴリズムとか勉強になりましたね多分もう使うことないだろうけど
- Midpoint circle algorithm - Wikipedia
- 伝説のお茶の間 No007-09(1) 円の描画(1) MichenerとBresenham
- QuickDrawはどのように素早く円を描いていたのか? - ザリガニが見ていた...。
とはいえ、自分で書いたOS(っぽいライブラリ)でゲームが動いたときは達成感ありましたね。
Nand2Tetris 「コンピュータシステムの理論と実装」、完走しました
— 極限生命体しいたけNA (@yuroyoro) November 23, 2020
CPUからOSまで一気通貫で作るのは楽しかったですhttps://t.co/m223NjRcdS
まとめ
O'Reilly Japan - コンピュータシステムの理論と実装 、楽しいのでみんなやるといいですよ?
とくに、コンピューターサイエンスに苦手意識があるとかローレイヤー怖いとかの人におすすめです。やってみると、とてもシンプルな仕組みの積み重ねでコンピューターが動作していることが実体験として理解できます。 そして、現代のCPUやOSがどれだけ進歩しているかも……
僕が今勉強で作ってるレジスタ2個しかなく乗除算すらできない16bitCPUに比べると、マルチコアでL1,L2キャッシュを持ちパイプライン化されて分岐予測やリオーダーを行い、浮動小数点演算どころかSIMDとかSHA計算までサポートする現代のCPUは超文明が残したオーパーツにしか見えないです
— 極限生命体しいたけNA (@yuroyoro) November 20, 2020
本書で取り扱うそれぞれのトピックは概要レベルですので、例えばコンパイラについてもっと学びたいとかOSを詳しく知りたいというニーズには適してはいませんが、全体を俯瞰する入り口としては最適だと思います。
そして、理解を深めるにはものすごく単純でもいいから自分で作ってみるてっとり早いのですが、本書はそれを手助けしてくれる素晴らしい内容でした。 今後は、自作ブラウザとか自作TCP/IPプロトコル・スタックとか自作RDBMSとか、挑戦してみたいものが山積みです。
で次ですが、Nand2TetrisではOS部分が薄くて物足りないかったので、OSを作ってみることにしました。
買いましたよ?
— 極限生命体しいたけNA (@yuroyoro) November 17, 2020
30日でできる! OS自作入門【委託】 - 達人出版会 https://t.co/WfHOtXQSS6
12月は忙し目なので、年末年始からまた腰を据えて取り組みたいと思います。
あと、Rust完全にマスターしました(光を放ちながら消滅)