『コンピュータシステムの理論と実装』という本を買いました。
最近勉強したいと思っていた事と近そうな内容で、レビューも良かったので楽しみ。
プロプラグラマでもなく趣味で書いてるだけの私ですが、備忘録的に各章の回答を載せて行くことにします。

実行環境~
MacBook Air(M1, 2020)
macOS Big Sur 11.5.1
コンピュータシステムの理論と実装　初版第7刷

準備 Hardware Simulatorの実行（超初心者向け)

Simulatorの準備を表示する

本書 C.3　ソフトウェアツールの実行方法 MACユーザー及びUnix/Linuxユーザーより

注意　以下3つの記述はnand2tetrisをdesktopに置いている人のみ。
違う所に置いた人はcdのところを各々変えてください。
蛇足でしょうが下のコードは1行ずつ入力してね。

ターミナル

cd desktop
cd nand2tetris
cd tools
chmod 777 HardwareSimulator.sh

僕のMacにはjavaが入っておらずこのままでは実行できなかったので下記。
Homebrewが入っていない人は「Homebrew インストール」とかで調べて、
Homebrew入れてから実行してください。

ターミナル

brew install java
sudo ln -sfn $(brew --prefix)/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk

パスワードが求められるので入力してEnter。
その後

ターミナル

cd .. 
cd ..
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &

desktopまで戻って本書に書いてある実行用のコマンド入力。

「1.5 プロジェクト」に挑戦

※詳細な画面操作などについて書いてます。忙しい方はこの次のタグの「回答」をご覧ください。

ターミナル

~/Desktop/nand2tetris/tools/HardwareSimulator.sh &

本書に記載の方法でHardware Simulatorを開きました。ここに編集したファイルを入力してテストするんですね。

ではNotから実装してみます。~/nand2tetris/projects/01/内のNot.hdlを編集。編集にはSublime Text4を使いました。

ちなみに回路の話は全くの初心者なので、実際にLEDとか使って組んでいる人の記事を色々参考にしました...後は本書の11ページ、XorのHDLプログラムのソースと図を読んでいる内になんとなく分かってきました。int 理解力 =　0。

//Put your code here:はデフォで書かれてます。あえて残しました。
その下が僕が書いたものになります。

Not.hdl

/**
 * Not gate:
 * out = not in
 */

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    // Put your code here:
    Nand(in=a, in=b, out=out);
}

.hdlファイルを編集して保存したら、Hardware Simulatorの左上FileからLoad Chipを選択。Not.hdlを選んでLoad Chip。

次にLoad Scriptからtstを選択してload。同じ手順です。

多分Simulatorが下のように更新されたはずです。

そうしたらこれ↓を押してテスト開始です。

Simulatorの左下にEnd of Script -Compression ended successfullyが
出たら文字通り成功です。

そうすると、~/nand2tetris/projects/01/内にNot.outというファイルが勝手に出来上がります。みてみましょう。

Not.out

|  in   |  out  |
|   0   |   1   |
|   1   |   0   |

入力が0の時は1を返す、入力が1の時は0を返すの2通りしかないので、成功です！
なお一々.outファイルを見に行くのも面倒なので、Hardware Simulatorの右上のView:からoutputで自分のtest結果を、compareで模範解答を見られます。

View:

Output　テスト結果

Compare　模範回答

結果と模範回答の出力結果が同じなので、今回書いたNot回路が正解ということがわかります。

男子個人　詳細な操作説明記載　日本代表

回答

Not
入力 in　出力 out 関数 If in=0 then out=1 else out=0
入力と逆の出力をします。
Nandの入出力には4パターンありますが、そのうち「aとbの出力が両方0なら1を返す」、「両方1なら0を返す」という2パターンはNotと同じです。
なのでNandの入力の2つを1つに結べばNot回路になります。(...と、こちらの記事に書いてありました。)

Not.hdl

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a=in, b=in, out=out);
}

And
入力 in　出力 out　関数 If a=b=1 then out = 1 else out = 0
Nandの結果を反転させればAndの結果になります。
Nandで2つ入力→出力されたものを(Nandで作った)Notにかける =　And。
Nandだけで表現するのが目標なので2パーツともNandで書いていますが、
分かりやすく書くと下のコメントアウト内のパーツになります。

And.hdl

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=b,out=Nout);
    Nand(a=Nout,b=Nout,out=out);

/* 
    結局こういうこと
    Nand(a=a,b=b,out=Nout);
    Not(in=Nout,out=out);
*/
}

Or
入力 in 出力 out　関数 If a=b=0 then out = 0 else out = 1
どちらか若しくは両方が1なら1を返します。

Nandは両方１の時のみ0を返します。Nandへの入力をNotで逆にして、
aの逆、bの逆を再度NandにかければOrと同じ結果が得られます。

(0,0) 逆に (1,1) Nand-> (0)
(1,0) 逆に (0,1) Nand-> (1)
(0,1) 逆に (1,0) Nand-> (1)
(1,1) 逆に (0,0) Nand-> (1)
これで0,0の入力時に0出力、他は1を再現できました。

Or.hdl

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=a,out=Nouta);
    Nand(a=b,b=b,out=Noutb);
    Nand(a=Nouta,b=Noutb,out=out);

    /*
    Not(in=a,out=outa);
    Not(in=b,out=outb);
    Nand(a=outa,b=outb,out=out);
    でも可
    */
}

Xor
入力 in 出力 out　関数 If a ≠ b then out = 1 else out = 0
入力abが異なる場合にだけ1を返します。

入力(0,0)出力(0)
入力(1,0)出力(1)
入力(0,1)出力(1)
入力(1,1)出力(0)

これに関しては本書11ページ、XorのHDLのソースと図を見た方がイメージ湧くと思います...
ただNandだけで実装することが目的なので長いですがコードを書いていきます。

Xor.hdl

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // Not
    Nand(a=a,b=a,out=NotOutA);
    Nand(a=b,b=b,out=NotOutB);

    //And
    Nand(a=a,b=NotOutB,out=NandOutA);
    Nand(a=NandOutA,b=NandOutB,out=AndOutA);

    Nand(a=b,b=NotOutA,out=NandOutB);
    Nand(a=NandOutB,b=NandOutB,out=AndOutB);

    //Or
    Nand(a=AndOutA,b=AndOutA,out=OrOutA);
    Nand(a=AndOutB,b=AndOutB,out=OrOutB);
    Nand(a=OrOutA,b=OrOutB,out=out);
}

Multiplexor
aとb2つの入力から、selが0ならaから、selが1ならbを選択して出力するゲートとのこと。
入力 a,b,sel　関数 If sel = 0 then out = a else out = b
要はselが0の時はaだけ見て、selが1の時はbだけ見るので

a	b	sel	out
0	-	0	0
1	-	0	1
-	0	1	0
-	1	1	1

の表のように考えれば良いです。
aを見るときはselをNotで逆にしAndを通し、bを見る時はNotを使わずにAndを通す...すると、

a=0,sel=1 -> And 0　aを見たが0、bは見ていないので結果は0。
a=1,sel=1 -> And 1　aを見ると1、bは見ていないので結果は1。
b=0,sel=1 -> And 0　bを見たが0、aは見ていないので結果は0。
b=1,sel=1 -> And 1　bを見ると1、aは見ていないので結果は1。

とシンプルになります。つまり両方0なら0、片方が0でももう片方が1なら1を返せばOK。
両方1はあり得ません。これはOrを使えば実装することができます。

Mux.hdl

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    //aを見る用のNot sel作成
    Nand(a=sel,b=sel,out=NotSel);
    
    Nand(a=a,b=NotSel,out=AndA);
    Nand(a=AndA,b=AndA,out=NotSelA);

    Nand(a=b,b=sel,out=AndB);
    Nand(a=AndB,b=AndB,out=SelB);
    //Or 
    Nand(a=NotSelA,b=NotSelA,out=outA);
    Nand(a=SelB,b=SelB,out=outB);
    Nand(a=outA,b=outB,out=out);
}

Demultiplexor
Multiplexorの反対。入力 in,sel 出力 a, b
関数 If sel=0 then (a=in,b=0) else (a=0,b=sel)

出力が2つに増えましたが、実装はMultiplexorより簡単です。
inが1でもselが0ならb=0、つまりinもselも両方1の必要があるのでbの出力はAndが必要です。
aですが、selをNotで逆にしないとin=sel=1と確認できません。
実装は下記の通りです。※そろそろ全てNandで書くのに疲れてきました。

DMux.hdl

CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
    Not(in=sel,out=NotSel);
    And(a=in,b=NotSel,out=a);
    And(a=in,b=sel,out=b);
}

多ビットNot

本当にこんな力技？と思って色々調べたんですが、変数宣言もforも失敗しました。そしてNandじゃなくてNotで書けばよかった..

Not16.hdl

CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
    Nand(a=in[0],b=in[0],out=out[0]);
    Nand(a=in[1],b=in[1],out=out[1]);
    Nand(a=in[2],b=in[2],out=out[2]);
    Nand(a=in[3],b=in[3],out=out[3]);
    Nand(a=in[4],b=in[4],out=out[4]);
    Nand(a=in[5],b=in[5],out=out[5]);
    Nand(a=in[6],b=in[6],out=out[6]);
    Nand(a=in[7],b=in[7],out=out[7]);
    Nand(a=in[8],b=in[8],out=out[8]);
    Nand(a=in[9],b=in[9],out=out[9]);
    Nand(a=in[10],b=in[10],out=out[10]);
    Nand(a=in[11],b=in[11],out=out[11]);
    Nand(a=in[12],b=in[12],out=out[12]);
    Nand(a=in[13],b=in[13],out=out[13]);
    Nand(a=in[14],b=in[14],out=out[14]);
    Nand(a=in[15],b=in[15],out=out[15]);
}

多ビットAnd
ゴリ押し

And16.hdl

CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    And(a=a[0],b=b[0],out=out[0]);
    ・・・略・・・
    And(a=a[15],b=b[15],out=out[15]);

}

多ビットOr
ゴリ押し

Or16.hdl

CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    Or(a=a[0],b=b[0],out=out[0]);
    ・・・略・・・
    Or(a=a[15],b=b[15],out=out[15]);
}

多ビットマルチプレクサ

割愛

Mux16.hdl

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);

}

多入力Or

Orに7回通せば良いだけなので簡単。

Or8Way.hdl

CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
    Or(a=in[0],b=in[1],out=out1);
    Or(a=out1,b=in[2],out=out2);
    Or(a=out2,b=in[3],out=out3);
    Or(a=out3,b=in[4],out=out4);
    Or(a=out4,b=in[5],out=out5);
    Or(a=out5,b=in[6],out=out6);
    Or(a=out6,b=in[7],out=out);
}

多入力多ビットマルチプレクサ

Mux4Way16
inとselが倍になった分、2つのMux16に一度通して最後に
もう1度Mux16を通すことで実装。

Mux4Way16.hdl

CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];

    PARTS:
    Mux16(a=a, b=b, sel=sel[0], out=outA);
    Mux16(a=c, b=d, sel=sel[0], out=outB);
    Mux16(a=outA, b=outB, sel=sel[1], out=out);
}

Mux8Way16
Mux4からinが倍になっただけなのでMux4を2つ使い、最後にinが2つのMux16に通せば完了。ただsel[0..1]に辿り着くのに時間がかかった。
これ32や64bit用の基本ゲートとかを作ればもっと大きな入出力も簡単に実装できそう。

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:
    Mux4Way16(a=a,b=b,c=c,d=d,sel=sel[0..1],out=outA);
    Mux4Way16(a=e,b=f,c=g,d=h,sel=sel[0..1],out=outB);
    Mux16(a=outA,b=outB,sel=sel[2],out=out);
}

DMux4Way
Mux4wayの要領で実装。同じ様に、

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
    DMux(in=in, sel=sel[1], a=outA, b=outB);
    DMux(in=outA, sel=sel[0], a=a, b=b);
    DMux(in=outB, sel=sel[0], a=c, b=d);
}

DMux8Way
も、1度Dmux4Wayを通して、出力が8個になる様にselを変えたDmuxを
4種類実装すれば完了。

DMux8Way.hdl

CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
    DMux4Way(in=in, sel=sel[1..2], a=outA, b=outB, c=outC, d=outD);
    DMux(in=outA, sel=sel[0], a=a, b=b);
    DMux(in=outB, sel=sel[0], a=c, b=d);
    DMux(in=outC, sel=sel[0], a=e, b=f);
    DMux(in=outD, sel=sel[0], a=g, b=h);
}

感想戦

準備〜テストで3時間くらい、qiita書くのに何故か2時間くらいかかったので、日曜日の午前中が無くなりました。
NandからNot、And、Orを作った感動は束の間、forが使えないゴリ押しの状況で多ビットが始まり「なんだこれ合ってんのか...」という感じでしたが、
多ビットを使って多in多outが簡単に作れたので達成感がありました。上でも触れましたが、応用すれば32bit、64bitの実装もできるのかな？？？

以上、githubにコード上げれば良いのに丁寧に書きすぎて失踪不可避ですが
『コンピュータシステムの理論と実装』最後まで頑張ります。