プログラミングを初めて半年の初心者がCPU ・コンパイラ・ OSを自作した話

はじめに

「コンピュータシステムの理論と実装」という本をもとに、HDLによる基本回路の設計から、CPU、コンパイラ、OSと、その上で動くアプリケーションをエミュレーター上で自作しました。
私自身はプログラミング歴半年の初心者で、文系出身なのでコンピューター科学の基礎知識も全くない状態でしたが、時間は掛かったものの何とかやり切ることが出来ました。
せっかくやり切ったので、備忘としてやったことの記録を残すとともに、これから低レイヤーを勉強したいと考えている方の参考になればと思い記事にしました。

低レイヤーを学ぼうと思ったきっかけ

プログラミングを始めて半年で、ある程度プログラムは書けるようになりました。
しかし、プログラムは書けるようになったのですが、**「なぜそのように書かなければいけないのか？」**というプログラミング言語の文法に対する素朴な疑問がありました。

例えば、

• StringやIntegerなど、なぜ変数にわざわざ型を指定しないといけないのか？
• 関数に、なぜわざわざ引数として変数を渡さないといけないのか？
• 関数は、なぜ1つの値しかリターンしないのか？、など

「プログラミングとはそういうもの」と言ってしまえばそれまでなのですが、プログラミング言語自体も誰かが作ったものである以上、文法にも理由があるはずです。
それはコンピューターの動作原理と深く結びついているのではないかと思い、それを理解したいと思いました。

コンピュータの動作原理を理解するには、実際に自分で作ってみるのが一番だろうと考え、「コンピュータシステムの理論と実装」をやってみることにしました。

「コンピュータシステムの理論と実装」の紹介

@y-meguroさんの記事が分かりやすいので、詳しくはそちらを見てもらえればと思います。(私もこの本をやる前に読ませて頂きました。有難うございます！)
各章の最後に課題があり、課題を実装していくとNAND回路から始まり、最後は自作したOS上で動くアプリケーションまで段階的に作ることが出来ます。
本に答えは書いていないので、指定された仕様を満たしているか、用意されたエミュレータを通じてテスト・デバックしながら進める形式です。

以下は本の裏書き：

コンピュータを理解するための最善の方法はゼロからコンピュータを作ることで、その構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できる。本書では、これらの構成要素をひとつずつ組み立てる。具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計。オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション(テトリスなど)を動作させる。実行環境はJava(Mac、Windows、Linuxで動作)。

「コンピュータシステムの理論と実装」をやって良かったこと

コンパイラ・OS・CPUがどのように役割分担しながらプログラムを解釈し実行しているのか高い解像度でイメージ出来るようになった

コンパイラがどのようにソースコードを解釈し機械語に置換え、OSが提供する機能と共に、CPUやメモリ上でどう実行されるのか、具体的にイメージ出来るようになった。
また、その役割分担も一つとは限らず、例えば乗算を実装するのも、CPUの命令セットとしてハードウェアで実装する方法もあれば、OSが提供する機能としてソフトウェアで実装する方法もあるなど、設計思想により様々な可能性がある。

コンピュータの構造自体は単純な中で、複雑なプログラムを実現出来るようにした先人の様々な叡智に感動した

コンピューター(CPUやメモリ)自体は、2つの値の加算や減算、命令アドレスへのジャンプや、メモリアドレスからのデータの読取り・格納など、実は単純なことしか出来ない。
その中で、スタックや連結リストといったデータ構造を用いることで、プログラムのフロー制御や関数呼び出し、動的なメモリ割当てなど、複雑なプログラムも実現できてしまうことなどに感銘を受けた。
(このあたりはきっかけに書いた疑問にも関係する内容だったので、疑問も解消しすっきりした)

各章でやったことと感想

第１章ブール論理

• NAND素子から計15種類の基本ゲートをHDLで実装
• マルチプレクサとか「知ってる〜、単に入力信号セレクトするやつでしょ！」みたいに思いつつ、いざ実装しようと思うと意外と悩む。作った基本ゲートをパーツとして組合せることで、複雑なゲートも作れるようになるのが面白い

第2章ブール算術

• 加算器、インクリメンタ、ALUをHDLで実装
• 本に指定はなかったけど、ALUに使う16ビット入力を反転させる基本ゲートも別に構築。プログラミングで使う真偽値(0かそれ以外か)の判定が、多入力Or回路で実装出来るのがアハ体験だった

第3章順序回路

• レジスタ、各種RAM、カウンタをHDLで実装
• カウンタは8入力マルチプレクサで実装したけど、通常(2入力)のマルチプレクサいくつか使った方が良かったかも。8入力マルチプレクサ使うと可読性がやたら低くなった

第4章機械語

• アセンブリ言語で乗算＆入出力操作プログラムを実装
• 入出力操作プログラムのスクリーンを描画するループで、アドレスが隣のキーボードのメモリマップまで書き換えているバグに気付かず、2時間くらいはまった。(条件分岐の境界値の誤り)

第5章コンピュータ・アーキテクチャ

• 最初の山場と思われるCPUとROM, RAM回路をHDLで実装
• デコード回路の実装がなかなか大変だった。でもそのおかげか2進数の機械語がなんとなく読めるようになった(気がするだけ)

第6章アセンブラ

• PHPでアセンブラを実装
• ハードウェアが終わり、これからいよいよソフトウェア階層の実装。今まで変数のアドレスってどうやって割当ててるんだろうと疑問に思ってたけど、"シンボルテーブル"や"2パス"など、その仕組みへの理解が深まった

第7章バーチャルマシン#1：スタック操作

• PHPでVMのスタック操作モジュールを実装。コンパイラ構築に向けた第一歩
• 条件分岐の実装部分で少し詰まった。最初ラベル使わずに、単純にプログラムカウンタにジャンプ先の行数分を加算して実装しようとしたのは我ながらアホだった

第8章バーチャルマシン#2：プログラム制御

• PHPでVMのプログラム制御モジュールを実装(VM完成)
• アセンブリのデバッグが下手すぎてやたら時間かかった。スタックという一見単純なデータ構造で、プログラムのフロー制御や関数呼び出しまで実現出来てしまうことに、ある種の美しさを感じた

第9章高水準言語

• Jack言語(これからコンパイラを作る独自言語)に慣れるために、サンプルのPongゲームを対戦式(1人2役)に改修した

第10章コンパイラ#1: 構文解析

• コンパイラのトークナイザとパーサをPHPで実装。再帰下降構文解析アルゴリズムが本だけだと説明少なすぎて、以下のウェブサイトを参考にした：
• (参考1) 構文解析
• (参考2) JavaScriptでゆるく学ぶ再帰下降構文解析
• 数十時間は余裕でかかった・・でもパースの基本が理解出来てよかった

第11章コンパイラ#2: コード生成

• コンパイラのコード生成モジュールを実装＆コンパイラ完成
• コンパイラが複雑なソースコードを、単純なROM(命令)とRAM(仮想レジスタ・スタック・ヒープ等)にどのように置換えているか、１つの線で繋がって理解出来た気がする

第12章OS

• メモリ管理・I/Oドライバ・数学&文字列操作等をカプセル化するOS機能を実装
• 言語自体もエミュレータもデバッグ機能が貧弱すぎて、めっちゃ時間かかった。ただ連結リストを使った動的メモリ割当てとか、数学的なアルゴリズムを使う描画機能とか、なるほどと思う内容で面白かった

第13章さらに先へ

• 読了＆全章完了！当初目標通り、NAND回路から始まり、CPU、コンパイラ、OSと、その上で動くアプリケーションまで自作した
• 色々学べて面白かったんだけど、ただ一つだけ分からなかったのは、なんで「Nand2Tetris」ってサブタイトルなのに、最後作るのがPongゲームなのだろうか？笑

終わりに

当初思ってた以上に時間がかかり、特に後半のコンパイラとOSの章が重く大変でした。恐らく200時間は優に超えたと思います。
ただ、学びながら自分の手で全てを作っていくのはとても楽しかったです。
初心者でコードもめちゃくちゃなので、あまり参考にならないかもしれませんが、GitHubにコードを上げましたので、この記事と合わせて何かの参考になればと思います！