コンピュータシステムの理論と実装 第1章ゆるーく

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


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

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

<details>
<summary>Simulatorの準備を表示する</summary>
<div>
本書
<strong>C.3　ソフトウェアツールの実行方法</strong>
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まで戻って本書に書いてある実行用のコマンド入力。

</div></details>

#「1.5 プロジェクト」に挑戦
<details>
<summary>※詳細な画面操作などについて書いてます。忙しい方はこの次のタグの「回答」をご覧ください。</summary>
<div>

```:ターミナル
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &
```

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

![HardwareSimulator.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/a728a5ae-7234-2bf5-cedf-3acfba2bcfd4.png)

では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。

![select_file.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/fdab398f-61ff-3914-59a9-716455695179.png)

![chip_load.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/2409dc1a-cbe2-3237-4ca6-db604d2be365.png)

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

![test_load.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/5e69ad6f-6409-f98c-b720-e4bb1c371e0d.png)

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

![hardware.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/02145f0b-2cb7-26e8-ee03-4e2a2151a94f.png)

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

![kore.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/2ecdd20d-f25a-cf78-943a-3a21847df790.png)

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

![end.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/f5b424f9-2a20-beac-e113-c6a8518e92a6.png)

そうすると、~/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:
![menu.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/7ce6e1cb-aa04-4295-c8dc-3402d4de8dee.png)

Output　テスト結果
![output.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/017a1105-c7a3-d22c-a8f3-dd7be1d79ee3.png)
![result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/378d12d3-65b2-37a0-b2b5-5f4ccf1e42ed.png)

Compare　模範回答

![compare.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/20f49c93-a818-ca2b-783f-d96a4f7ac154.png)
![result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1741765/1f656da4-c799-8169-2d61-dab92ecd3f1f.png)

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

男子個人　詳細な操作説明記載　日本代表
</div>
</details>

# 回答

<strong>Not</strong>
入力 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回路になります。(...と、こちらの[記事](https://xtech.nikkei.com/it/members/ITPro/ITBASIC/20021009/1/)に書いてありました。)

```Not.hdl
CHIP Not {
    IN in;
    OUT out;

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

<strong>And</strong>
入力 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);
*/
}
```

<strong>Or</strong>
入力 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);
    でも可
    */
}
```

<strong>Xor</strong>
入力 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);
}
```

<strong>Multiplexor</strong>
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);
}
```

<strong>Demultiplexor</strong>
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);
}
```

<strong>多ビットNot</strong>

本当にこんな力技？と思って色々調べたんですが、変数宣言も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]);
}
```

<strong>多ビットAnd</strong>
ゴリ押し

```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]);

}
```

<strong>多ビットOr</strong>
ゴリ押し

```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]);
}
```

<strong>多ビットマルチプレクサ</strong>

<details>
<summary>割愛</summary><div>

```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]);

}
```

</div></details>

<strong>多入力Or</strong>

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);
}
```


<strong>多入力多ビットマルチプレクサ</strong>

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);
}
```

<strong>DMux4Way</strong>
Mux4wayの要領で実装。同じ様に、

```DMux4Way
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);
}
```

<strong>DMux8Way</strong>
も、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にコード上げれば良いのに丁寧に書きすぎて失踪不可避ですが
『コンピュータシステムの理論と実装』最後まで頑張ります。