( ꒪⌓꒪) ゆるよろ日記

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

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

Rust Nand2Tetris

どうも、しいたけです。

去年あたりからローレイヤー周りの知識を充実させようと思い、 低レイヤを知りたい人のための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はプロセス管理やファイル管理、ネットワークなどはサポートせず、単純にキーボードやスクリーンなどメモリマップドされたハードウェアを操作するための便利ライブラリのような位置づけです。

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

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

さて本の構成ですが、おおまかにハードウェア、コンパイラ、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は書いたことがなかったのですが、本書で扱うものは非常に単純なルールなのですぐに覚えることができました。

こんな感じでやっていきます。

回路設計に悩むようすです

CPUの実装でこのページが出てきたときはめっちゃテンションあがりましたね？

シミュレーター上で、自分がHDL書いたCPUがHack機械語を実行できるようになったときの様子です。やりきった感あった。

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について悩んでいた

スタックマシンはCコンパイラ作成入門で一度実装したことがあったので、関数呼び出し時のスタックとかリターンアドレスとかそのあたりは理解していたのですが、Hackはレジスタ2個しかなくて実装しんどかったです。

コンパイラに感謝する様子です

Rustへの理解が深まっていく様子です

VM実装終わったとき

Jack言語コンパイラに関しては再起下降パーサーを書いたことがあるので実装面で悩むことはなかったです

12章: オペレーティングシステム

正直ここからはおまけです。Jack言語でOSを書くのですが、このOSは上で述べたとおりハードウェアとのやりとりをするためのメモリアクセスを便利にしてくれるライブラリみたいなものです。 Jack言語も非力な言語なので書くのはダルかったです。 ただ、自作したコンパイラがちゃんとシンタックスエラーを検出してくれたときはちょっとしたうれしみが湧き上がりましたね?

たとえば、画面に文字を出力するのにDMAされた画面のピクセルに対応するメモリのビットをフォントにしたがって立てる処理とか書くのダルかったです。

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

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

まとめ

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

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

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

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

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

12月は忙し目なので、年末年始からまた腰を据えて取り組みたいと思います。

あと、Rust完全にマスターしました(光を放ちながら消滅)

f:id:yuroyoro:20201210001321p:plain
Rust完全に理解した