プログラミング初学者の私がNand2tetrisを終えるためにやったこと

昨年、9ヶ月かけてNand2tetrisをやりきりました！

AtCoderにハマり本格的にプログラミングの勉強を始めて、１年と少しが過ぎたところでした。

この記事ではNand2tetrisの紹介と、プログラミング初学者の私がNand2tetrisを進めるために参考にした本や、進め方などを紹介したいと思います。

 

目次

  

Nand2tetrisとは

正確には「コンピュータシステムの理論と実装　モダンなコンピュータの作り方」という本になります。

www.oreilly.co.jp

この本では、Nandゲート(AndゲートやOrゲートのようなもの)と言うたった１種類のパーツをひたすら、組み合わせてパソコンを作ります。

そして好きなプログラム(例えばテトリス)を作り、それを自作のコンパイラとアセンブラで機械語に変換し、先ほどのNandゲートから作った自作パソコンの上で動かす、というのが最終目的の本です。
そのため通称Nand2tetrisと呼ばれています。

公式サイトはこちらから。ちなみに英語なら無料ですべて読めます。

 

目次の前にある「訳者まえがき」と著者の「まえがき」「イントロダクション」が、この本がどんな本か大変分かりやすくまとまっていると同時に、素晴らしくワクワクさせてくれる内容になっています。もしこの本に興味を持った方は、この部分を読んでもらうと魅力がより伝わると思います！

 

自分の自由な時間のかなりをこの本に費やし、昨年は”趣味はNand2tetris”と言っても過言ではありませんでした。まさかサンリオピューロランドで娘のために順番の列に並んでいる時や、温泉に浸かっている時に、プログラミングを考えることになるとは思いませんでした。春先に始めたのに、シュトーレンを焼く間に最後の実装をしていました。

 

とにかく難しかった、苦しかった、それ以上に気になって進めずにはいられないワクワクがずっと続いていた幸せな時間でした。


この記事を書いている人

  • 大学は理系ですが、専門は梁の曲げとかリンクとかの方で、情報系卒ではないです。仕事でプログラミングをしたこともないです。
  • パズルが好きでMETIQという団体に所属しています。Nand2tetrisの至る所にパズル的な要素を感じたので、パズル好きは楽しめると思います。
  • プログラミングは趣味でちょっと違うことを勉強したくなり始めました。2019年の11月頃にAtCoderを始めたので、ちょうど１年と少し経ったところです。
  • AtCoderでは、A,B問題は解けるレベルでこのNand2tetrisを取り組み始めました。
  • 関数は作れるけど、クラスやメソッドは作れませんでした。
  • コンパイラとアセンブラの違いも分かっていませんでした。

取り組んだきっかけ

  • コンピュータがどうなっているか知りたかった。特に「コンピュータは0と1で処理している」とよく言われるけど、そのレベルから理解したかった。(興味)
  • 長いまとまったプログラムを書いてみたかった。C++で複数ファイルにまたがるプログラムを書いてみたかった。(憧れ)
  • Makeとかして見たかった(憧れ)
    と、興味と憧れが全てでした。結果としては、コンピュータの理解を深めることができ、コードもたくさん書け(全部で7600行ほど)、Makeも飽きるほどできました。

 

できたもの

なかなかこの本は壮大で全体像が把握しにくいので、見通せる図を作成しました。

f:id:hananirawataru:20210109055904j:plain

Nand2tetris全体のフロー

青背景の物がこの本を通して作るものです。私が使用した言語と、対応する章番号も記載しています。

図の上部から下に向かって、オブジェクトベースのJack言語で作成したテトリスプログラムとOSプログラムに、自作のコンパイラ、VM変換器(VMtranslator)、アセンブラで変換を重ね、最後は0と1にしてNandで作ったコンピュータで実行します。(※この説明は正確には少し違っていて、詳細は最後の"今後やりたいこと"に記載しています)

小さいですが黒背景の中にプログラムの抜粋をいれています。

 

最終的にテトリスを実行した様子はこのような感じです。（キャプチャしながら動作させているので、少しもっさりしてて悔しい。もう少しスムーズに動くように頑張って改善したのに…）

youtu.be

この本の素晴らしいところ

・各章ごとに、解説と作るものの仕様と、テストケースが準備されています。

解説(仕組み)を理解して、仕様に沿ってプログラムを書き、テストケースを通すことで、徐々に私だけのNand2tetrisが出来上がって行きます。(もちろんオリジナル仕様でも作れます)

例えるなら「週間自分だけのパソコンを作ろう」 みたいな感じで、コツコツ出来上がっていきます。

 

・仕様に合わせて作っていけば、不足や手戻りなく出来上がります。

後から「CPUにあの回路を追加しないと〇〇が実現できない」みたいなことはありませんでした。

 

・お手本としてちゃんと動くものが準備されています。

Nand2tetris Software Suiteとして、正しく動くCPUやアセンブラ、コンパイラなどが準備されています。(上記の公式サイトで誰でも無料でダウンロードできます)

それと、自分のプログラムで処理して出来たものとの差分を取れば、どこが誤っているかを理解できます。これらが無かったら、例えばうまく動かない時、それがOSのバグなのか、コンパイラのバグなのか、アセンブラなのか、判別するのに苦労しそうです。

 

私のすすめ方

  1. まずこれから進める章をざっと読んで課題を理解する。
  2. 次にとりあえず作りながら、わからないところが出てきたら、都度必要なページをもう一度きちんと読む。
  3. 全然わからなかったら、参考になる他の本を読む

という流れで進めました。
本にはヒントや、指針がきちんと書かれてして、わからない場合は改めてよく読むと「なるほど、ここに書いてあったのはそういうことか！」となることが多かったです。手を動かし始めてやっと本の意味が理解できることがあるので、最初に読んだときに理解できなくても、とりあえず取り組んでみてみたのが良かったと思います。

それ以前に、あまりに本の内容が理解できない時は、他の本で理解を深めました(具体的には後述します)。

 

また、自分はNand2tetrisに関しては、目標も計画も立てず、ただ興味の赴くままに取り組むことにしていました。もともとかなりストレッチしたチャレンジだと思っていたので、極論「いつ止めてもOK」くらいの気持ちで、楽しむこと第一で臨んでいました。

あえて先を急ぐこともせずに、動くようになっても気が済むまでコードに手を入れてました。

 

分かったことと感じたこと

  • CPUで実装した、びっくりする位少ない種類の演算命令(なんと18しかない)と、スタック操作を使った緻密なカラクリによって、オブジェクトような便利で、かつ物の本質を抽象的にプログラムに落とし込めるような仕組みが出来上がっている。
  • CPUでできる処理の種類が少ないので、とにかくasmファイルまで変換すると、長くて泥臭い感じになる。しかし実行スピードが凄いので魔法のように動いているように感じる。(すごいと言っても私の実行環境では推定120"k"Hz程度)
  • 人とコンピュータの対話の歴史　ソフトウエアの20世紀という本によると、パソコンやアセンブラ、コンパイラが発明されたのは1940〜1950年代とのこと。まだ人類が手にして100年も経っていない技術を、こうして趣味で作れてしまうことに感銘を受けました。

www.shoeisha.co.jp

 

章ごとの内容と感想など

1章 ブール論理

プログラミング上でNandをつないで、NotやAnd、Orを作ります。
シミュレーション上でそれらを動作させることで、論理の確認をします。
ここで作ったものが後の章でPCのパーツとして使用します

 

2章 ブール算術

前の章で作ったパーツで、足し算をする回路(加算器 Adder)を作ります。ブール理論で計算の実現の仕方を学びます。
そして早速ALUをここで作ります。ALUは18種類の演算をするCPUの中心部的な存在で、本書で与えられた仕様を満たす回路を作ります。
18種類というと多い気がしますが、2つの入力x,yに対して、x+yで1種類、x-yで1種類という感じで、かなり簡素な処理です。
Nand2tetrisで作るパソコンの演算はここで作るの18種類が全てで、これで掛け算、割り算はもちろん、嘘みたいですが最終的には高水準言語で書かれたオブジェクトベースのプログラムも実行します。

 

3章 順序回路

情報を保存するパーツ(メモリなど)がどのようにできているかを学びます。
DFFを使ってPCのメモリを作ります。
ここまでの章で、PCに必要なパーツはほぼ揃います。
(この章で作るカウンタが地味に難しく、人の回答を参考にしました。)

 

4章 機械語

ついに全てのパーツを組み合わせてパソコンを作る…と思ったらここで機械語とアセンブリ語について学びます。
なぜここで？と思ってしまいますが、次の5章で作るコンピュータをまずは使ってみて、コンピュータに慣れるためです。
この"作る前に使ってみる"流れは本の後半でも同じで、9章でJackという(この本ために設計された)言語でプログラミングしてみて、10、11章でJackのコンパイラを完成させることになります。
使う側として接してから、読み解く側として取り組むというのは、この本の一つの特徴かと思います。この時の視点がガラッと切り替わるのが個人的には快感でした。

 

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

1章～3章のパーツを使って、ついに最上位のコンピュータを組み立てます。
CPUはこの本の中でも一つの難所かと思います。4章の機械語の仕様と、3章のALUの仕様をじっくり眺めながら、簡単な命令から組み立てていきました。(A命令→ジャンプ以外のC命令→ジャンプを含むC命令)
コンピュータ内を、電圧の高低(0/1)が色んなパーツを通過しながら、カチャカチャと切り替わりながら動いていく。それを人間から見ると意味のある動きになっている。そんな様子を俯瞰的に眺めることができました。
1章からここまでは、自作CPU系で名著と呼ばれる「CPUを創りかた」も同時に読みながら進めました。DFFに代表される順序回路は、理解したと思ってもすぐに分からなくなることがあり、その度にこの本の"Chapter7 1bitCPU(らしきもの)"の章を読み直していました。
またCPUの簡単な命令から一つずつ回路を組み立てていくプロセスも、この「CPUを創のつくりかた」がとても参考になりました。

 

6章 アセンブラ

個人的には一番難しく感じた章でした。
それまで私は前述の"この記事を書いている人"にあるように、シンプルなプログラムしか書いたことがなかったため、クラスやメソッド を使うという実装の仕様を読んでも、全く意味がわかりませんでした。
3章のカウンタ以外に、この章だけは人のプログラムをいろいろと見て参考にしたのですが、それを見たところで基礎的な点で理解が追いついていなかったので、それでも理解できませんでした。(プログラムの冒頭のint main(int argc, char* argv[]) のargc, argvって何？と言う感じでした)

そこで「ロベールのC++」を購入し、半分くらいまで読んでクラスやメソッド、ヘッダファイルとソースファイルに分けて書く書き方、makeファイルの書き方などを勉強しました。
初めてコンストラクタ内でファイルを開いて、適当な文字を書き込み、デストラクタで閉じられた時は、「これでやっとスタートラインに立てた。あとは正しく変換していくだけだと」感激したと同時にほっとしました。

アセンブリ言語は機械語と1対1の対応で、まさに機械的に変換をしていくだけなので、後に作るコンパイラに比べると単純ではあります。
ただ上記のように私のスキルが追いついていない事もあり、この本を通してこのアセンブラが完成した時がもっとも達成感がありました。(2ヶ月くらいかかりました)

 

 

 

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

ここからは中間言語をアセンブリ言語に変換するVM translatorを書きました。
中間言語のイメージは、push1, push2, addのような感じで、それをアセンブリ言語に変換できるようにしていきます。(簡単な.vmファイルを.asmファイルに変換する)
ここまでとは異なる全く新しいことが始まる感じがしますが、ファイルを開く/閉じるのような部分は、アセンブラで作ったものがそのまま生かせたので、いきなり本質的な問題に着手できて嬉しかったです。(6章で苦労したので)
また、単純なプログラミングのバグに悩まされることも減り、純粋にスタック操作のパズルを解くような感覚で楽しく進めれました。
作成したVM translatorで出力されるアセンブリ言語のボリュームが、直接コンピュータで実行する量になるため、アセンブリ言語にするときに少しでも少ない行数にできないかいろいろ考えたりしました。

 

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

ここでは、7章で作ったVM translatorに、中間言語で書かれたifやcall, returnを、アセンブリ言語に変換できるようにしました。
関数のcallとreturnをアセンブリ言語に変換する所は、この本の中でも1、2を争う難所でしたが、純粋にややこしいパズル的な感じでなかなか楽しく、テストをパスした時はかなり快感でした。

 

9章 高水準言語

この本のために作られた高水準言語のJackについて学びます。(あとの章になると分かりますが、コンパイルしやすくなっている分、書くことは多めです)

例の"作る前に使ってみる"流れで、Jackのコンパイラを作る前にその言語に慣るのが目的で、何を作るかも自由に設定されています。
仮に作らなくてもJackで書かれたサンプルプログラムがあるので、この章はパスしても大丈夫です。
自分は、せっかくのnand2tetrisなのでテトリスのプログラムをJackで書きました。


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

Jackで書かれたプログラムを読み解き、中間言語にするための準備として、構文解析器をつくります。

具体的にはその文の意味、その変数の意味を、Jackの文法の仕様から読み解いていきます。例えば「行頭にifとあったら、つぎは"("があって、")"が出てくるまでは、式があるはず」というような思考で、プログラムを読み解いていきます。
全く新しいことをする感じですが、ここでも基本的なファイルの読み書きは6章のものを再利用することができます。

また、ここでは再帰関数を使うシーンがありました。事前に勉強済みだったので、なんとか実装できましたが、全く初めての場合は簡単な例に触れておくとスムーズかと思います。
再帰関数に関しては、Atcoderの下記のサイトが参考になりました。
https://atcoder.jp/contests/apg4b/tasks/APG4b_v

テストでは、JackのプログラムをXML形式で「ここはif文」「ここは関数呼び出し」みたいにタグ付けをしていきます。
正しくタグ付けされたお手本があるため、それと自分の出力結果をdiffコマンドで調べて、コツコツと直していきました。

 

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

Jackを中間言語変換して書き出していく作業になります。
10章で正しく文を読めるようになっているので、あとは具体的に中間言語で書き出す処理を追加していきます。ここはif文だから、if文用の書き出し内容の中間言語を書き出す、と言うイメージです。
変数をまとめたシンボルテーブルを都度呼び出して、変数を具体的なメモリの場所に置き換えていくのは、なるほどこれが変数のスコープか、と納得しました。
テストが全て通った時は、あまりの嬉しさに、ベランダから「コンパイラができたー！」と叫びたくなりました。(自制しました)

 

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

簡単なOSをJack言語で作っていきます。(全部で8ファイル)
本も終盤に近づいてきて、この章は軽く流してゴールできるウイニングロードだと思ってましたが大間違いでした。かなり大変で、終わるまでに3ヶ月もかかりました。

特に画面表示系のOutputやScreenで苦労しました。すでに書き込み済みのアドレスに上書きする際には、今あるデータとORを取る、といった操作は「30日でできる! OS自作入門」をざっと読んだ時に紹介されていて、参考になりましました。

メモリ管理の部分では、凝って書こうとすると単方向リストのデータ構造の考え方が必要でしたが、この部分で初めて遭遇しても(ここまで来ていたら)なんとかなると思います。

全てが正しく動くのを確認した後に、いざ9章で作ったテトリスのプログラムを、自分のOSで実行すると、速度が遅かったり(OSのアルゴリズムの問題)、テトリスの挙動が満足できなかったりで、納得いくまでコツコツと1ヶ月ほど手を加えていました。

 

 

今後やりたいこと

ここまでCPUからテトリスまでを全部作ってきたわけですが、実はまだ出来てないことがあります。
それは自分の作ったCPUで、自分が作ったテトリスを実行することです。
まるでそれはやっていたかのように書いてましたが、実際は中間言語から、提供されているVMエミュレータソフトで直接実行していました。

f:id:hananirawataru:20210109204901p:plain

中間言語(.vm）までにしたら、提供されているVMエミュレータで直接実行(オレンジのライン)


もう少し手間をかけて機械語まで変換したらいいのでは、と思いましたが、出来上がる機械語のコードが16万行のため、この本で作る16bitのCPUでは実行できないものになっていました。

それは、例えば16万行目にジャンプと命令したくても、このCPUではアドレスを(先頭の1bitはアドレス命令か計算命令かの判断に使うので)15bit分しか表現できないので約3万行目(=2の15乗)までしか正しく飛べないためです。

ではプログラムを短くしたらいいのでは？と思って頑張ってみたのですが私のスキルでは機械語で6万行が精一杯で、ここからさらに半分にする必要があり、(今の自分には)無理そうに感じました。(そのあたりVMエミュレータはうまく設計されているようです。)

そこでやっと最初のやりたいことに戻ってきましたが、最終的にはやっぱり自分で作ったCPUで動かしてみたい！というのがあるので、いつかFPGAでこのCPUを実装してテトリスを実行できたらいいな、と思ってます。

 

Terasic DE0-CV 開発キット 【P0192】

Terasic DE0-CV 開発キット 【P0192】

  • メディア:
 

（すでにだいぶ前にFPGAは購入済みです。ちなみに16bitのALUまではできています。)
完成したら、その時はまた記事にしたいと思います。

 

16万行なら、素数でキリのいい(?)19bitのCPUで足りるな
そしたらALUの回路を改造して、実行できる命令を増やせないかな
なんだかこれまた長いチャレンジになりそう…笑

 

参考にした書籍

CPUの創りかた

https://book.mynavi.jp/ec/products/detail/id=22065

CPUの創りかた

CPUの創りかた

 


表紙は可愛いですが、CPUの仕組みが本当によく学べる本でした。
アナログ回路についての解説も多く、最終的には電子工作でCPUを作ることも可能です(!)

この本で設計するCPUは、TD4という名前が付けられているので"TD4 作ってみた"と検索すると、出来上がったCPUを多数見ることができます。

 

ロベールのC++入門講座

http://www7b.biglobe.ne.jp/~robe/

ロベールのC++入門講座

ロベールのC++入門講座

  • 作者:ロベール
  • 発売日: 2007/11/15
  • メディア: 単行本（ソフトカバー）
 

プログラミング初学者かつ、C++初学者だったので、全般的なプログラミングの基礎をこの本で学びました。上記のHPでも学べますが、私は本を買いました。
本の索引が、一番メインの説明のページが太字で、少しでも出てきたページは普通の太さで網羅的にまとまっているのでとても便利です。
私は半分くらいまで通しで読んで、あとはわからない時に辞書的に調べる使い方をしました。とてもお世話になった本です。 

 

30日でできる! OS自作入門

https://book.mynavi.jp/ec/products/detail/id=22078

30日でできる! OS自作入門

30日でできる! OS自作入門

 

実際に手を動かしたわけではないのですが、Nand2tetrisを取り組む前に一通り読みました。OSを作るのはこういう雰囲気なのかと勉強になりました。
Nand2tetrisの12章でOSを作る際は、すでに書き込み済みのアドレスに上書きする際には、今あるデータとORを取る、といった操作を事前に学んでおくことができてよかったです。
ちょっと話がそれますが、この本のポインタの説明がわかりやすかったのでおすすめです。

 

コーディングを支える技術

http://nhiro.org/langbook/

コーディングを支える技術――成り立ちから学ぶプログラミング作法 WEB+DB PRESS plus

コーディングを支える技術――成り立ちから学ぶプログラミング作法 WEB+DB PRESS plus

 

プログラミング言語の設計思想を、様々な言語で横断的に学べました。
直接的に参考になったわけではないですが、プログラム言語を使う側ではなく、作る側の視点に立ってみることは、コンパイラを作る時の理解に役立ったように思います。

 

ソフトウェアの20世紀　ヒトとコンピュータの対話の歴史

https://www.shoeisha.co.jp/book/detail/9784881359488

ソフトウェアの20世紀―ヒトとコンピュータの対話の歴史

ソフトウェアの20世紀―ヒトとコンピュータの対話の歴史

 

コンピュータ史を、同じ時期の日本や世界での出来事(時代)とあわせて学ぶことができました。Nand2tetrisで作っていくものは、まさにコンピュータ史をなぞるように進むのでとても楽しく読めました。また自分は近代史に疎いこともあり、コンピュータ史以外の歴史の勉強にもなりました。

 

感謝の言葉

著者と翻訳者には、この素晴らしい本を作っていただいたことに、ただただ感謝しかありません。また、以下の方に勝手ながら感謝の言葉を送らせてください

 

読書猿さん

twitter.com

学び方、独学の進め方に限らず、あらゆる面で読書猿さんのホームページや書籍のお世話になっています。困った時はいつも「〇〇　読書猿」で検索して気づきを得ています。
上記で紹介した「コーディングを支える技術」と「ソフトウエアの20世紀」も、「プログラミング　読書猿」でヒットした以下のページで紹介されていたものです。

プログラミングとなら、できること／図書館となら、できること番外編 読書猿Classic: between / beyond readers

 

またこの記事を書く際には、以下の記事に背中を押してもらいました。

もっとうまく書けるかもという妄執をやめれば速くうまく書ける－遅筆癖を破壊する劇作家 北村想の教え 読書猿Classic: between / beyond readers


リリアンさん

twitter.com

まず何の本を読んで学べばいいかわからない時、リリアンさんが定期的にアップしている勉強した本のリストがとても参考になりました。

 「CPUの創りかた」「ロベールのC++入門講座」「コーディングを支える技術」はリリアンさんが(も)紹介していた本になります。貪欲に学び続けるリリアンさんの姿勢にいつも影響を受けています。

 

妻

何か訳の分からない事にハマっている自分を放っておいてくれただけでなく、パソコンのことなんて何の興味もないのに
自分「ALU動いた！」　妻「すごい！！」
自分「コンパイラできたー！」　妻「すごいやーん！！」
こんな風にいつも付き合って喜んでくれてありがとう。

 

最後に

ここまで紹介してきたNand2tetrisですが、誰にでも勧められるかというと人を選ぶと思います。
ただ自分はこの本を終えてみて、例えばこれまでは、星をつないで星座を見つけれるくらいだったのが、”この星座を構成するこの星は〇〇という名前で、そこには陸地と海があって、巨大な海の端にある島国には、ヒトが1億人くらい住んでいる”のような、解像度をコンピュターの画面の向こうに感じられるようになりました。
それが何に活きるの？と言われると、分かりませんが、魔法の様に動くパソコンが少しだけ分かる様になったことが、素直に嬉しいですし、とても満足できました。