Nand2Tetris 日本語講義資料

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

Nand2Tetrisは、NANDゲートの1つから始まり、コンピュータ、コンパイラ、オペレーティングシステムまで直接作成するプロセスです。 各章を別々に見ると、HDLコードやPythonコードの集まりのように見えますが、実際には前の章の結果が次の章の材料になります。

いいですね。 この記事では、既存の1章から12章までのコードを1つの流れにリンクしてみましょう。

全体の流れ

NAND
  ↓
論理ゲート
  ↓
加算器とALU
  ↓
レジスタとメモリ
  ↓
Hack CPUとコンピュータ
  ↓
アセンブラ
  ↓
VMトランスレータ
  ↓
Jack コンパイラ
  ↓
Jackオペレーティングシステム

1-5章はハードウェアを作り、 6-8章は低レベル翻訳機を作る。 9-12章は、高級言語、コンパイラ、オペレーティングシステムを上げています。

第1章火の論理と基本ゲート

目標

• NANDだけを使用して別の論理ゲートを作成します。
• 真理値表を見てHDL接続を考える。
• MuxとDMuxがデータを選択して配布する方法を理解してください。

NANDは、両方の入力が1の場合にのみ0を出力します。 単純に見えるが、入力を同じ線に接続すればNOTになり、NOTを再び組み合わせればANDとORも作れる。

Not(a) = Nand(a, a)
And(a, b) = Not(Nand(a, b))
Or(a, b) = Nand(Not(a), Not(b))

Muxはselに従ってaまたはbを選択します。 DMuxは逆に1つの入力をaまたはbのいずれかに送信します。

1章コードを見る

確認の問題

1. NANDの2つの入力に同じ値を入れると、なぜNOTになるのですか？
2. MuxとDMuxの違いをデータの方向で説明しましょう。
3. Mux16は1ビットMuxと何が同じであるか。

第2章火の算術とALU

目標

• 半加算器と全加算器の違いを理解する。
• 複数ビットの加算でキャリーが渡される過程を見る。
• 制御ビットで複数の演算を実行するALUを理解してください。

半加算器は2ビットを加えてsumとcarryを作る。 全加算器は前の席から渡されたキャリーまで入力として受け取る。

HalfAdder: a + b
FullAdder: a + b + carry-in
Add16: FullAdder を接続した 16 ビット加算器

ALUの鍵は、演算ごとに別々の回路を作成することではありません。 zx, nx, zy, ny, f, no信号で入力と出力を切り替えながら、1つの回路をさまざまな方法で使用します。

2章コードを見る

確認の問題

1. XORが加算のsumとして使用されるのはなぜですか？
2. 16ビット加算で最後のキャリーを捨てるとどうなりますか？
3. ALUのzr, ng出力は次の章のどの機能に使用されますか？

第3章シーケンシャルロジックとメモリ

目標

• 組み合わせ論理と順次論理の違いを理解する。
• DFFが時間を格納する最小単位であることを理解してください。
• Bit、Register、RAM、PCがどのように拡張されるかを見る。

1章と2章の回路は、現在の入力だけで出力が決まります。 しかし、メモリは前のクロックの値を記憶しなければなりません。

DFFの出力は現在の入力ではなく、前の時点の入力です。 ここにMuxを付けると、loadが1のときだけ新しい値を保存するBitを作成できる。

DFF → Bit → Register → RAM8 → RAM64 → RAM512 → RAM4K → RAM16K

PCはreset, load, incの優先順位が重要である。 通常resetが最も強く、次のload、最後がincである。

3章 コードを見る

確認の問題

1. loadが0のときにBitが既存の値を保持するプロセスをMuxで説明しましょう。
2. RAM8でDMuxとMuxがそれぞれ必要なのはなぜですか？
3. PCの制御信号優先順位が逆になると、どのようなバグが発生するのだろうか？

第4章Hack機械語

目標

• A命令とC命令を区別する。
• A、D、Mレジスタの役割を理解してください。
• 分岐と反復ステートメントがアセンブリでどのように表現されるかを見てください。

A命令は値をAレジスタに入れます。

@10

C命令は、計算、保存位置、ジャンプ条件を1行で表現します。

D=M+1;JGT

Mは別々のレジスタではありませんRAM[A]を意味する。 この点を見逃すと、Aレジスタを値として書き込むかアドレスに書き込むかが分かりやすい。

4章 コードを見る

練習

1. RAM[2] = RAM[0] + RAM[1]を作成する。
2. 1から10まで加算する繰り返し文を作成します。
3. FillコードでSCREENアドレスがなぜ16384なのかを確認します。

第5章Hackコンピュータ構造

目標

• CPU、メモリ、ROM32Kを1つのコンピュータに接続します。
• 命令のビットがALUとレジスタをどのように制御するかを理解してください。
• fetchとexecuteが繰り返される構造を見る。

CPUは現在の命令を解釈し、ALU結果をA、D、Mのどこに保存するかを決定します。 ジャンプ条件が真の場合、PCにAレジスタの値を入れ、次の命令に進みます。

メモリはアドレス範囲に応じてRAM16K、スクリーン、キーボードを選択します。 つまりメモリアドレスを読み書きするだけで画面やキーボードも扱える。

5章 コードを見る

確認の問題

1. instruction[15]でA / C命令を区別する理由は何ですか？
2. writeMこれが1のとき、実際にどのアドレスに値が格納されますか？
3. キーボードはなぜロード信号を必要としないのですか？

第6章Hack アセンブラ

目標

• .asmファイルを16ビット.hackファイルに変換する。
• ラベルと変数シンボルを処理します。
• 二度読む方法が必要な理由を理解する。

ラベルは実際の命令ではないため、ROMアドレスを増やすべきではありません。 したがって、最初のパスで(LOOP)同じラベルのアドレスを収集し、2番目のパスで実際の命令を変換します。

一次パス：ラベル→ROMアドレス
2次パス：A / C命令→16ビットコード
変数シンボル：RAM[16]から順に割り当て

6章 コードを見る

練習

1. スペースとコメントを削除する前処理関数を作成します。
2. 同じ変数が何度も出ていても、アドレスを一度だけ割り当てるようにしてください。
3. dest, comp, jumpテーブルにない入力に出会ったときにエラーを出力します。

第7章VMトランスレータI

目標

• スタックベースの仮想マシンを理解する。
• 算術命令とメモリセグメントをHackアセンブリに置き換えます。
• 比較操作で固有のラベルが必要な理由を理解してください。

VM命令はほとんどスタックの値を取り出して計算し、結果を書き戻します。

push constant 7
push constant 8
add

local, argument, this, thatは基準アドレスに従い、 temp, pointer, staticは自己定義された住所規則を使用する。

7章 コードを見る

確認の問題

1. プッシュとポップがSPを変更する順序が異なるのはなぜですか？
2. eq, gt, ltそれぞれ独自のラベルを作成しないとどうなりますか？
3. static変数名にファイル名を含める必要があるのはなぜですか？

第8章VMトランスレータII

目標

• label、goto、if-gotoを関数の範囲内で処理します。
• function、call、returnのスタックフレームを理解する。
• bootstrapコードが何をしているのか理解してください。

関数を呼び出すときは、返すアドレスと現在のフレーム状態を保存する必要があります。

return-address
LCL
ARG
THIS
THAT

returnはFRAME = LCL, RET = *(FRAME - 5)を最初にアーカイブしてから発信者のセグメントを回復します。 回復中にLCLが変わるため、RETを最初に保存する必要があります。

8章 コードを見る

練習

1. 再帰関数呼び出しでreturn labelが重ならないことを確認してください。
2. 複数.vmファイルの静的セグメントが競合していないことを確認してください。
3. bootstrapでSPを256に設定し、Sys.initを呼び出します。

第9章Jack 高級言語

目標

• Jackのクラス、コンストラクタ、メソッド、ファンクションを区切ります。
• オブジェクトと配列がメモリに保存される方法を理解してください。
• OS APIを使用して入力と出力を処理します。

JackはJavaに似ているようですが、機能ははるかに単純です。 オブジェクトのフィールドはヒープに格納され、メソッドでは現在のオブジェクトのアドレスがthisになる。

コンストラクタは必要なサイズだけメモリを割り当てた後thisを返します。 配列も特別なデータ構造というより連続したメモリブロックに近い。

9章 コードを見る

練習

1. Counterオブジェクトを2つ作成し、値が別々に保持されていることを確認します。
2. キーストロークが押し続けられた状態で重複処理されないようにします。
3. 使用済みオブジェクトにdisposeが必要な理由を説明します。

第10章。 Jackパーサー

目標

• tokenizerがソースコードをトークンに分割するプロセスを理解します。
• Jack文法を再帰下降パーサとして実装する。
• パスツリーをXMLで出力します。

文字列内の記号とコメント以外の記号は異なる方法で処理する必要があります。 したがって、単に空白に分割すると、正しいtokenizerを作成できません。

パーサーは現在のトークンを見て、どの文法関数を呼び出すかを決定します。

class
 ├─ classVarDec
 ├─ subroutineDec
 └─ statements

10章 コードを見る

確認の問題

1. 文字列内//を錫で消すとなぜならないのか？
2. expressionとtermを分離すればどんな点が楽なのか？
3. トークンを消費する前に予想タイプを調べると、何が良くなりますか？

11章。 Jack コンパイラ

目標

• パスツリーをVM命令に変換します。
• クラス範囲とサブルーチン範囲シンボルを区別します。
• メソッド呼び出しとコンストラクタ呼び出しの隠れた動作を理解してください。

シンボルテーブルは名前だけを保存しません。 タイプ、種類、インデックスを一緒に保存して、どのVMセグメントを使用するかを決定します。

static   → static
field    → this
argument → argument
var      → local

methodは最初の argument として現在のオブジェクトを受け取りますpointer 0に接続する。 コンストラクタはフィールド数と同じMemory.allocを呼び出した後、戻りアドレスpointer 0に入れる。

11章 コードを見る

練習

1. 同じ名前のローカル変数がフィールドを隠すときにどのシンボルが選択されているかを確認します。
2. 配列の代入で、アドレスと値をどの順序でスタックに保存する必要があるかを整理します。
3. do問い合わせの戻り値temp 0に捨てる理由を説明する。

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

目標

• Jackプログラムが使用する基本ライブラリを直接実装する。
• Math、String、Array、Memoryの責任を区別する。
• ハードウェアと高級言語の間の最後の空白を埋めます。

オペレーティングシステムだからといって、巨大なカーネルから作るわけではない。 Jackプログラムが期待する関数をJack言語で実装することが重要です。

• Math: 乗算、除算、絶対値
• String: 文字保存、長さ、出力変換
• Array: 連続メモリ割り当て
• Memory: ヒープの割り当てと解放
• Screen: ピクセルと図形出力
• Keyboard: キーストローク
• Output: 文字と数値出力
• Sys: 初期化、待機、終了

12章 コードを見る

確認の問題

1. 乗算と除算をCPU命令なしで実装できるのはなぜですか？
2. Stringオブジェクトがlengthとcapacityを別々に持つ理由は何ですか？
3. メモリを解放しないと、Jackプログラムで何が起こりますか？

推奨学習シーケンス

各章は次の順序で進むことをお勧めします。

1. 完成コードを見る前に、入出力と真理値表を先に書く。
2. 小さな部品からテストする。
3. テストが合格したら、次のステップの部品として使用します。
4. 失敗した場合は出力だけを見てはいけませんが、どの階層で値が変わったのかを調べます。
5. 最後に、既存のブログコードを自分のコードと比較します。

正解コードをそのまま入力すると、プロジェクトはすぐに終了します。 しかし、Nand2Tetrisにとって重要なことは、正解自体よりも1つのレベルの下の階層が現在の階層をどのように支えるかを理解することです。

NAND 1つがオペレーティングシステムまで続くという流れが見えれば、コンピュータはもはや魔法のように見えなくなる。