( ꒪⌓꒪) ゆるよろ日記

(　ﾟ∀ﾟ)o彡°ｵﾊﾟｰｲ!ｵﾊﾟｰｲ! ( ;ﾟ皿ﾟ)ﾉｼΣ ﾌｨﾝｷﾞｨｨｰｰｯ!!!

この広告は、90日以上更新していないブログに表示しています。

2020-12-10

Nand2Tetris(コンピュータシステムの理論と実装)でCPUからOSまで一気通貫で作るのが最高に楽しかった話

どうも、しいたけです。

去年あたりからローレイヤー周りの知識を充実させようと思い、低レイヤを知りたい人のためのCコンパイラ作成入門を読んでCコンパイラを書いてみたりx86_64の勉強をしたりしていました。

今年に入ってから、よりローなレイヤー、具体的にはハードウェアやOSについてもう少し知りたいと思い始め、手頃な書籍を探していました。CPUなどのハードウェア周りについては概要しか知らなくて手を動かしたことがないので、実際に何か作りながら学べるものとして、O'Reilly Japan - コンピュータシステムの理論と実装に挑戦することにしました。

O'Reilly Japan - コンピュータシステムの理論と実装

成果物は以下のリポジトリに置いてあります。

yuroyoro/nand2tetris

結論から言うと、やってみて大変楽しめました！

特にハードウェア周りは今まで挑戦したことのない分野で、回路の設計がとても新鮮で楽しんで取り組めました。ちょこちょこ間が空いたりしたので、全部完走するまで10ヶ月ちょっとかかりましたが……。

コンパイラやVMの作成は、Cコンパイラ書いてみたりした経験があったのですんなりできましたが、実装言語にRustを採用することでRustの習熟にも役立ちました。(というかハマったのは主にRustの学習で、使い慣れた言語だったらおそらくすぐに実装できたはずです……)

OSに関してはかなり物足りなかったので、こちらは別な教材で改めて学びたいと思います。

Nand2Tetrisってなに?

「コンピュータシステムの理論と実装」(通称Nand2Tetris: NANDからテトリスへ)は、コンピューターの基本的な構成要素であるCPUやメモリから始めて、そのアーキテクチャ向けの機械語を生成するコンパイラ、アプリケーションとハードウェアの橋渡しをするOSまでを順を追って作成することで、基本的なコンピューターシステムの動作原理が理解できるような構成になっています。

Courseraにコースがあって、著者のShimon Schocken教授とNoam Nisan教授がインストラクターとしてオンラインで受講することができます。

Build a Modern Computer from First Principles: From Nand to Tetris (Project-Centered Course) | Coursera

僕はヘタレなので受講はせずに独学しましたが、気合入れて取り組むつもりなら受講するのもありではないでしょうか。

Nand2Tetrisでは、Hackという本書独自のアーキテクチャ用のCPUやメモリなどをNand回路から始めて作成し、Jackという本書独自のプログラミング言語のHackアーキテクチャ向けコンパイラを実装し、そのJack言語を用いてOSを書くことで、ハードウェアからOS、アプリケーションまですべてを自前で作っていきます。とはいえ、Hackアーキテクチャで作成するCPUは16bitでデータレジスタとアドレスレジスタがそれぞれひとつしかない単純なCPU(乗除算すらできません！)ですし、Jack言語はオブジェクト指向言語ですがJavaをかなり単純化した言語仕様です。また、OSはプロセス管理やファイル管理、ネットワークなどはサポートせず、単純にキーボードやスクリーンなどメモリマップドされたハードウェアを操作するための便利ライブラリのような位置づけです。

それでも、順番に実装していくと(シミュレーター上とはいえ)このようなゲーム(アプリケーション)を動作させることができます!

終わった。Nand2Tetris、Jack言語コンパイラのコード生成の実装が。

CPU、アセンブラ、スタックマシンVM、コンパイラと作ってきて、ようやくアプリケーションがエミュレータ上で動くようになったぞｫ……！！pic.twitter.com/KmojKek9wT
— 極限生命体しいたけNA (@yuroyoro)November 13, 2020

テトリスちゃうやんけ！！

さて本の構成ですが、おおまかにハードウェア、コンパイラ、OSの3つのパートに分けられており、各パートはいくつかの章で構成されます。章ごとに演習問題が用意されており、実際にその問題で作ったパーツが次の章で利用される仕掛けになっています。例えば、回路設計では最初の1章でANDやORゲートを作り、次の2章ではそれらを組み合わせて加算器を作る、といった具合です。

本書はテストするための回路シミュレーターやCPUシミュレーターがすでに用意されており、また章ごとの課題もテストケースが用意されています。課題の内容にしたがってHDLを書いたりプログラムを作成して、シミュレーター上で用意されているテストをパスすればその章はクリアです。

Home | nand2tetris

このシミュレーターやテストが用意されているのが非常に取り組みやすく、テストをパスすることを目標として実装すればよいので迷わなくてすむのがよかったです。そうしてテストをパスするように章ごとの課題をこなしていけばいつのまにかコンピューターシステムが完成しているのです。

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を実装したので組み合わせて、シミュレーター上で機械語が動くようになったｿﾞｫ……
HWはこれで一段落#nand2tetris pic.twitter.com/Vx8hfZRowL
— 極限生命体しいたけNA (@yuroyoro)May 15, 2020

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の実装に入ったぞ

VM作るのたのしい
たのしい
— 極限生命体しいたけNA (@yuroyoro)September 8, 2020

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でJackVMの実装まで終わったぞ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

あと、画面に●を描画する際の高速なアルゴリズムとか勉強になりましたね多分もう使うことないだろうけど

とはいえ、自分で書いたOS(っぽいライブラリ)でゲームが動いたときは達成感ありましたね。

Nand2Tetris 「コンピュータシステムの理論と実装」、完走しました

CPUからOSまで一気通貫で作るのは楽しかったですhttps://t.co/m223NjRcdS
— 極限生命体しいたけNA (@yuroyoro)November 23, 2020

まとめ

O'Reilly Japan - コンピュータシステムの理論と実装、楽しいのでみんなやるといいですよ?

とくに、コンピューターサイエンスに苦手意識があるとかローレイヤー怖いとかの人におすすめです。やってみると、とてもシンプルな仕組みの積み重ねでコンピューターが動作していることが実体験として理解できます。そして、現代のCPUやOSがどれだけ進歩しているかも……

僕が今勉強で作ってるレジスタ2個しかなく乗除算すらできない16bitCPUに比べると、マルチコアでL1,L2キャッシュを持ちパイプライン化されて分岐予測やリオーダーを行い、浮動小数点演算どころかSIMDとかSHA計算までサポートする現代のCPUは超文明が残したオーパーツにしか見えないです
— 極限生命体しいたけNA (@yuroyoro)November 20, 2020

本書で取り扱うそれぞれのトピックは概要レベルですので、例えばコンパイラについてもっと学びたいとかOSを詳しく知りたいというニーズには適してはいませんが、全体を俯瞰する入り口としては最適だと思います。

そして、理解を深めるにはものすごく単純でもいいから自分で作ってみるてっとり早いのですが、本書はそれを手助けしてくれる素晴らしい内容でした。今後は、自作ブラウザとか自作TCP/IP プロトコル・スタックとか自作RDBMSとか、挑戦してみたいものが山積みです。

で次ですが、Nand2TetrisではOS部分が薄くて物足りないかったので、OSを作ってみることにしました。