nand2tetrisをちょっとした工夫で更に楽しむ - 1から全部Rustで書こう -

こちらはKyoto University Advent Calender 2020の17日目の記事です。

はじめまして

工学部電気電子工学科3回生の電タクです。最近のマイブームはRustで色々することです。

何やったの？

コンピュータシステムの理論と実装(通称:nand2tetris)のハードウェアパートを、提供されたツールを使わずRustでフルスクラッチで書きました。

目次

• nand2tetrisとは
• なぜわざわざRustで書くの？
• 実装上のルール
• 基本ゲート
  • NANDゲート
  • 基本論理ゲート
    • NOTゲート
    • ANDゲート
    • DMUX(デマルチプレクサ)
• ALU(算術論理演算器)
• 順序回路
  • Clock
  • DFF
• Computerの実装に向けて
  • ROM32K
  • Keyboard
  • Screen
• Computer
• 結び

nand2tetrisとは

nand2tetrisというのはコンピュータサイエンスの入門書として書かれた書籍です。内容としては、NANDゲート(0と1のディジタル信号を扱う基本回路)のみを部品として使い、基本論理ゲート、ALU、CPUとハードウェアを組み上げていき、その上で動くアセンブラ、VM、コンパイラ、OSを作り、最後にそれらを使ってテトリスなどを動かすことでコンピュータシステムをボトムアップ的に学ぼうという本です。

この本の特徴は、読み進めると共に実際にそれぞれ実装していくことができる点です。ハードウェアパート(NANDゲートからCPUまで)は提供されるハードウェアシミュレータを用いて実装し、ソフトウェアパート(残り)は仕様に沿って自分の好きな開発環境・プログラミング言語で実装することができます。

なざわざわざRustで書くの？

第一の理由はRustという言語が好きだからです。第二の理由は与えられた枠組みから外れ1から全て書くことで理解の甘い部分を生じさせないためです。

なお以下で示すサンプルコードはもちろんRustで書かれていますが、Rust特有の高度で強力な機能はほとんど使っていないのである程度プログラミングをしたことがある方なら問題なく読めると思います。
Rustの文法を知りたい方は手始めにこちらから見ても良いかもしれません。

実装上のルール

今回は、以下のような制約の元で仮想的なコンピュータを実装しました。

• 提供されるハードウェアシミュレータを使わずRustで全て実装する
• 使って良い基本パーツはNANDゲート、D型フリップフロップ、クロックだけ
• 基本パーツを組み合わせて実装するが、実際の回路が想像できないような組み合わせ方はしない(例えばif文を使ってビット演算の結果を書いてしまうのは実際の回路がイメージできなくなるので禁止)
• コンピュータは機械語で書かれたプログラムを受け取り、実行する
• キーボードからの入力やディスプレイへの出力もRustを用いて制御する
• 各パーツごとにテストを行い動作検証する

以上の制約のもと、実際に書いていきます。細かいロジックへの言及は避けRustで実装する上での話をメインでしていきますが、nand2tetrisのネタバレになってしまう部分はどうしてもあるので、そこはご容赦ください。

なお今回説明するプログラムはここのrust_implにもあげています。

以下に示すサンプルコードでは簡単のため一部省略しています。実際のコードは上のリンクに示すものを参照ください。

基本ゲート

まず基本ゲートを動かすには、「0」と「1」をプログラム上で扱えるようにしないといけません。普通に整数型の0と1を使っても良いのですが、明確に区別するために列挙型を用いてそれぞれ新しく宣言します。列挙型というのは、宣言したいくつかの値しか取らない新しい型を宣言できるものと思ってください。ここでは0を表すOと1を表すIを宣言します。

bit.rs

enum bit{
    O, // 0を表します
    I, // 1を表します
}

これから紹介する基本ゲートは全てこれらのbit型の値を受け取ってbit型の値を返す関数として定義します。

NANDゲート

NANDゲートはCMOSトランジスタを用いて電気的に実現されている論理ゲートです。NANDゲートは2つの入力を受け取って1つの出力結果を返します。電圧の高低をそれぞれ0と1に対応させた時、次の真理値表に示すような関係があります。

入力1	入力2	出力
0	0	1
0	1	1
1	0	1
1	1	0

NANDゲートは基本パーツとして扱いたいので、実際の回路素子がどうなっているかを考慮せずRustの機能を用いて実装しました。

nand.rs

fn Nand(a: bit, b: bit) -> bit {
    match a {
        O => match b {
            O => I,
            I => I
        },
        I => match b {
            O => I,
            I => O
        }
    }
}

これはbit型の値aおよびbを受け取り、Rustの強力な機能であるパターンマッチを用いて出力を返します。match構文はそれぞれの場合ごとに=>以後の式を評価します。上のサンプルコードはmatch構文がネストされていますが、aとbの値の各場合において評価される式を=>に沿って見れば、上の真理値表と同じ出力結果を返す^[1]ことがわかると思います。

テストコードは以下になります。実際にnand関数に各場合の入力を与えた結果が正しく出力されているのがわかると思います。

for_nand.rs

mod tests {
    use super::bit::{O, I};
    use super::Nand;

    #[test]
    fn for_nand() {
        assert_eq!(Nand(O, O), I);
        assert_eq!(Nand(O, I), I);
        assert_eq!(Nand(I, O), I);
        assert_eq!(Nand(I, I), O);
    }
}

このNand関数をNANDゲートとして扱います。論理関数NANDは単体で完全^[2]であるので、このNAND関数さえあれば全ての基本論理ゲートを作成することができます。

nand2tetrisで必要になるゲート全てを示すことはしませんが、いくつかだけ参考に実装を紹介します。

基本論理ゲート

以下では論理和を$\lor$、論理積を$\land$、否定を$\lnot$を用いて書くことにします。例えばaとbのNANDは$\lnot(a \land b)$のように書けます。

NOTゲート

NOTゲートは1入力1出力の論理ゲートで、入力を反転させたものを出力します。

入力	出力
0	1
1	0

これはNANDゲートを用いると次のように書けます。

$$\lnot a = \lnot(a \land a)$$

つまりNANDゲートの2入力を共にaと接続してあげれば良いことがわかるので、コードは次のようになります。

not.rs

fn Not(a: bit) -> bit {
    Nand(a, a)
}

ANDゲート

ANDゲートは2入力1出力の論理ゲートで、以下のような出力を返します。

入力1	入力2	出力
0	0	0
0	1	0
1	0	0
1	1	1

これはNANDゲートを用いると次のように書けます。

$$a \land b = \lnot((\lnot (a \land b)) \land (\lnot (a \land b)))$$

これではわかりづらいと思うので回路図で示したものが以下になります。

ANDゲート

これを実際のコードとして書いたものが以下になります。

and.rs

fn And(a: bit, b: bit) -> bit {
    Nand(
        Nand(a, b),
        Nand(a, b)
    )
}

DMUX(デマルチプレクサ)

デマルチプレクサは2入力2出力の論理ゲートで、inの値をselがOならaに、Iならbに出力します。

sel	a	b
0	in	0
1	0	in

Rustではタプル(tuple)を用いて2つの値を返すことができるので、aとbをそれぞれ論理関数で計算し返すことにします。

$$a = in \land \lnot sel$$

$$b = in \land sel$$

ここでは論理積および否定を用いて計算しましたが、それぞれANDとNOTはNANDを用いて構成しているのでルールには反しません。

そして実際のコードは次に示すようなものになります。

dmux.rs

fn DMux(a: bit, sel: bit) -> (bit, bit) {
    (
        And(
            a,
            Not(sel)
        ),
        And(
            a,
            sel
        )
    )
}

ここで入力をinではなくaとしているのは、inキーワードはRustの予約語になっていて変数名として利用できないからです。

このように各基本論理ゲートは全てNand関数を用いて実装することができます。

ALU(算術論理演算器)

ALU(Arithmetic Logic Unit)は基本的な論理ゲートを組み合わせて算術演算を行うための論理回路です。

nand2tetrisでは16bitを1つのデータのまとまりとして、各種の演算などを行う16bitのコンピュータを作ります。そのため今回実装するALUも16bitを一つのデータの単位として受け取り、演算します。これをWordとして定義しておくことで扱いやすくします。

word.rs

struct Word ([bit; 16]);

impl Index<usize> for Word {
    type Output = bit;
    fn index(&self, index: usize) -> &Self::Output {
        if 15 < index {
            panic!(format!("index fail: {} is out of range.", index));
        }
        &self.0[index]
    }
}

impl IndexMut<usize> for Word {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        if 15 < index {
            panic!(format!("index_mut fail: {} is out of range.", index));
        }
        self.0.index_mut(index)
    }
}

ここで、まず初めのコードブロックではstruct構文を使って構造体としてWordを定義しています。その中身はbitを16個持つ配列(スライス)です。

残りの二つのコードブロックでは、IndexトレイトおよびIndexMutトレイトを実装しています。これはRustを知らないとわかりづらいかもしれませんが、C++などでいう演算子オーバーロードに近く、これにより[]を使って要素を参照できるようにしています。

さて本題のALUですが、これは特にRustで実装する上で工夫したところはないのでコードを示すだけに留めておきます。詳しく知りたければnand2tetrisを参照してください。内容的には2つのWordと6つの命令信号を入力として、演算結果と演算結果の正負を返しています。

alu.rs

// see figre 2-6 in p.36
fn ALU(
    a: Word, 
    b: Word, 
    zx: bit, // zx : a -> 0 
    nx: bit, // nx : a -> !a
    zy: bit, // zy : b -> 0
    ny: bit, // ny : b -> !b
    f: bit,  // f : when 0 -> add, when 1 -> and
    no: bit  // no : out -> !out
) -> (Word, bit, bit)
{
    let a_muxed_by_zx = Mux16(
        a,
        Word::new([Not(zx); 16]),
        zx
    );
    let input_a = DMux16(
        Mux16(
            a_muxed_by_zx,
            Not16(a_muxed_by_zx),
            nx
        ),
        f
    );
    let b_muxed_by_zx = Mux16(
        b,
        Word::new([Not(zy); 16]),
        zy
    );
    let input_b = DMux16(
        Mux16(
            b_muxed_by_zx,
            Not16(b_muxed_by_zx),
            ny
        ),
        f
    );
    let integrated = Add16(
        And16(
            input_a[0],
            input_b[0]
        ),
        Add16(
            input_a[1],
            input_b[1]
        )
    );
    let r = Mux16(
        integrated,
        Not16(integrated),
        no
    );
    let zr = Not(
        Or(
            Or8Way([r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]]),
            Or8Way([r[8], r[9], r[10], r[11], r[12], r[13], r[14], r[15]])
        )
    );
    let ng = r[0];
    (r, zr, ng)
}

順序回路

今までに示した回路は組み合わせ回路といって、入力を与えれば一意に出力が決まる論理回路でした。それに対し、今から実装していくのは順序回路です。これは出力が現時点の入力のみでは決まらず過去の入力にも依存して出力がきまる論理回路です。

実はRustで書く上で一番頭を悩ませたのはここです。なぜかというと、現実世界では順序回路も組み合わせ回路を組み合わせることで実現しているわけですが、現実世界とプログラム上では時間の概念が異なります。現実ではクロックと同期させながら電気的に計算結果を保持することができますが、普通の関数では書かれた順に実行していき引数から出力を計算するだけなのでそれを表現することができません。

もちろん提供されるハードウェアシミュレータでも工夫されていて、それを参考にClock構造体とDFF構造体を定義することでプログラム中でも現実世界と同じように時間の概念に沿って実行できるようにしました。

Clock

現実世界のクロックは、周期的な矩形波を連続的に出力する素子です。そして各論理回路は、クロックの波形が立ち上がる時に、与えられた入力から計算していき次のクロックの波形が立ち上がるまでに全ての計算を終えます。

クロックの出力する矩形波

したがってプログラム上でも

1. 入力を元に計算する時間
2. 出力する時間

に分けてループを回せば周期的に矩形波を出力するクロックと同等のことができます。

この、入力を元に計算する時間をTick、出力する時間をTockとして、Clock構造体から出力させます。それぞれの順序回路からこの構造体を参照することで、全ての順序回路を同期させることができるはずです。

コードは以下のようになります。

clock.rs

// tick: input, update internal state
// tock: output 
enum ClockState {
    Tick, // 0 (clock's state starts with this)
    Tock  // 1 
}

struct Clock{
    state: ClockState,
}

impl Clock {
    pub fn state(&self) -> ClockState {
        self.state
    }
    pub fn next(&mut self) {
        self.state = match self.state {
            Tick => Tock,
            Tock => Tick
        };
    }
    pub fn new() -> Self {
        Clock{ state: Tick }
    }
}

まず列挙型としてClockStateを実装します。これはTickおよびTockの2値のいずれかをとります。

そしてClockState型の値を一つだけ保持するClock構造体を実装します。これはnextメソッドを使えばクロックを次の状態に進めることができ、stateメソッドを用いれば今の時間が上に示した1と2のどちらの時間かを知ることができます。

全ての順序回路はこのClock構造体を参照することで、順序回路としての機能を実現しています。

DFF

DFF(D型フリップフロップ)は1bit入力1bit出力の順序回路です。この出力は時間に依存していて、現在の入力が次の時刻の状態(出力)になっています。ちなみにこのDFFのDはDelay(遅延)を意味しています。式でかくと入力$D(t)$、出力$Q(t)$として

$$Q(t+1) = D(t)$$

となります。

これをプログラム上で扱うには、クロックの状態がTickの時は過去の入力を出力しつつ新しい入力を保存し、Tockの時には新しい状態を出力しなくてはなりません。それを実現したコードが以下に示すものになります。二つの状態を内部的に保持するDFF構造体を定義し、inputおよびoutputメソッドを各クロックで確実に使うことで、DFFの動作を実現しています。ここでいう確実にというのは、例えばinputメソッドが呼ばれずにoutputメソッドだけを使用すると状態の更新がされないので、それを避ける意図があります。

dff.rs

struct DFF {
    state_past: bit, // use when tick
    state_new: bit // use when tock
}

impl DFF {
    fn new() -> Self {
        DFF { 
            state_past: O,
            state_new: O
        }
    }

    fn input(&mut self, a: bit, clock: &Clock) {
        if clock.state() == Tick {
            self.state_past = self.state_new;
            self.state_new = a
        }
    }

    fn output(self, clock: &Clock) -> bit {
        if clock.state() == Tick {
            self.state_past
        } else {
            self.state_new
        }
    }
}

以上のClock構造体とDFF構造体を基本構成要素として、16 $\times$ 16KBのメモリやプログラムカウンターを実装することができます。ここでは示さないので実際の実装が気になる人は僕のGithubをみてください。

Computerの実装に向けて

さてここまでに作成した構成要素を組み合わせてComputer構造体を作るのが今回の目標なのですが、そのためにはもう少し工夫が必要になりました。ROM32K構造体、Keyboard構造体、Screen構造体について簡単に紹介しようと思います。

ROM32K

ROM32K構造体は、機械語で書かれたプログラムの命令を一つずつ、アドレスの0番目から順に保持する構造体です。

求められる要件としては、

1. プログラムが書かれたファイルから命令列の取り出し
2. 命令列を0番目から保存
3. 指定されたアドレスにある命令をフェッチする

の3つになります。このうち3はこれまでに実装したメモリを応用すれば簡単に実装することができるので、1および2の機能をRustで実装していきます。

先にROM32K構造体とloadメソッドの実装を示します。

rom32k.rs

struct ROM32K {
    rams: [RAM4K; 8]
}

impl ROM32K {
    pub fn load(&mut self, filename: &str) {
        let file = File::open(filename.clone()).expect(&format!("Fail to open {}", filename));
        let mut clock = Clock::new();
        let mut counter = Word::new([O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, O]);
        for line_result in BufReader::new(file).lines() {
            let line = line_result.expect("file reading error");
            let instruction = Word::from(line);
            let address = [
                counter[1],
                counter[2],
                counter[3],
                counter[4],
                counter[5],
                counter[6],
                counter[7],
                counter[8],
                counter[9],
                counter[10],
                counter[11],
                counter[12],
                counter[13],
                counter[14],
                counter[15],
            ];
            self.input_inner(&clock, instruction, address);
            clock.next();
            self.input(&clock);
            clock.next();
            counter = Add16(
                counter,
                Word::new([O, O, O, O, O, O, O, O, O, O, O, O, O, O, O, I])
            )
        }
        self.input(&clock);
        self.output(&clock, [I; 15]);
        clock.next();
        self.input(&clock);
        self.output(&clock, [I; 15]);
    }
}

ROM32Kの中身は32K本のレジスターです。

loadメソッドを説明します。まずloadメソッドは引数としてファイル名をとります。これにより、同じディレクトリにあればいつでも以下のようなプログラムの書かれたファイルを読み込むことができます。

機械語命令

この文字列からFileを開き、一行ずつ読み出していきます。この時、各行をROM32Kのアドレスと対応させるためにcounterという変数をもちこれを1行読むごとに1を加算していきます。アドレスは15bitなのでcounterのうち下15bitだけ取り出してaddressに保存しています。わざわざ16bitのWordを使ってcounterを計算しているのは、これまでにAdd16関数という、16bitの加算を計算できる論理回路を実装していたためこれを再利用したかったからです。以上によりファイルの中身を1行ずつ読み出し0番目のアドレスから順にメモリに書き出すことができます。

ですがこれだけでは駄目で、命令列としてファイルから読み出してきたlineは文字列なので、文字列からinstructionにするにはこれをWordにしなくてはいけません。そのためFromトレイトを実装しました。これはRustをある程度理解する必要があると思うので細かい説明は割愛しますが、文字列からWordに変換するために実装しています。これにより上でWord::from(line)とするだけで文字列からWordへの変換ができるようになっています。

word_from.rs

impl From<String> for Word {
    fn from(mut s: String) -> Self {
        s = s.split_terminator(' ').collect();
        let mut instruction = Word::new([O; 16]);
        let mut i = 0usize;
        for bytes in s.bytes() {
            instruction[i] = match bytes {
                48 => O,
                49 => I,
                _ => panic!("`Word::from_string` fail: cannot find 0 or 1.")
            };
            i = if i == 16 {
                panic!("`Word::from_string` fail: need less than 17.")
            } else {
                i + 1
            };
        }
        if i == 16 {
            instruction
        } else {
            panic!("`Word::from_string` fail: need more than 15")
        }
    }
}

impl From<&str> for Word {
    fn from(s: &str) -> Self {
        let s: String = s.split_terminator(' ').collect();
        let mut instruction = Word::new([O; 16]);
        let mut i = 0usize;
        for bytes in s.bytes() {
            instruction[i] = match bytes {
                48 => O,
                49 => I,
                _ => panic!("`Word::from_string` fail: canot find 0 or 1.")
            };
            i = if i == 16 {
                panic!("`Word::from_string` fail: need less than 17.")
            } else {
                i + 1
            };
        }
        if i == 16 {
            instruction
        } else {
            panic!("`Word::from_string` fail: need more than 15")
        }
    }
}

以上によりROM32Kは要件を満たすことができます。

Keyboard

今回作成するComputerはキーボードからの入力を受け付けます。ただ、普通のキーボードにはないようなend、pageup、insert等の謎な入力も受け付けられるようにしないといけません(これはnand2tetrisの仕様に則っています)。よって、特殊な入力、0~9までの数字、a~zおよびA~Zまでの英字を標準入力から受け付けて処理できるように、各キーの文字コードと、各入力を表す16bitの値を対応させました。

以下、ひたすら長いコードが続きます。それぞれの入力の文字コードは単純に入力をそのまま文字コードとして表示する簡単なプログラムを書いて調べました。精神的に一番辛かったのはここの実装です。

keyboard.rs

struct Keyboard {
    word: Word
}

impl Keyboard {
    pub fn new() -> Self {
        Keyboard { word: Word::new([O; 16])}
    }

    // This function work only when Tick start
    pub fn input(&mut self, clock: &Clock) {
        if clock.state() == Tick {
            let stdin = io::stdin();
            for line_result in stdin.lock().lines() {
                let line = line_result.expect("line error");
                if let Some(word) = Keyboard::matching(line) {
                    self.word = word;
                    break;
                }
            }
        }
    }

    fn matching(line: String) -> Option<Word>{
        match line.as_bytes() {
            // nothing
            [] => Some(Word::new([O; 16])),

            // 0 ~ 9
            [48] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, O, O, O])),
            [49] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, O, O, I])),
            [50] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, O, I, O])),
            [51] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, O, I, I])),
            [52] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, I, O, O])),
            [53] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, I, O, I])),
            [54] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, I, I, O])),
            [55] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, O, I, I, I])),
            [56] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, I, O, O, O])),
            [57] => Some(Word::new([O, O, O, O, O, O, O, O, O, O, I, I, I, O, O, I])),

            // A ~ Z
            [65] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, O, O, I])),
            [66] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, O, I, O])),
            [67] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, O, I, I])),
            [68] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, I, O, O])),
            [69] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, I, O, I])),
            [70] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, I, I, O])),
            [71] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, O, I, I, I])),
            [72] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, O, O, O])),
            [73] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, O, O, I])),
            [74] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, O, I, O])),
            [75] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, O, I, I])),
            [76] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, I, O, O])),
            [77] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, I, O, I])),
            [78] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, I, I, O])),
            [79] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, O, I, I, I, I])),
            [80] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, O, O, O])),
            [81] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, O, O, I])),
            [82] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, O, I, O])),
            [83] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, O, I, I])),
            [84] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, I, O, O])),
            [85] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, I, O, I])),
            [86] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, I, I, O])),
            [87] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, O, I, I, I])),
            [88] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, I, O, O, O])),
            [89] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, I, O, O, I])),
            [90] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, O, I, I, O, I, O])),

            // a ~ z
            [97] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, O, O, I])),
            [98] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, O, I, O])),
            [99] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, O, I, I])),
            [100] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, I, O, O])),
            [101] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, I, O, I])),
            [102] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, I, I, O])),
            [103] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, O, I, I, I])),
            [104] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, O, O, O])),
            [105] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, O, O, I])),
            [106] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, O, I, O])),
            [107] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, O, I, I])),
            [108] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, I, O, O])),
            [109] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, I, O, I])),
            [110] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, I, I, O])),
            [111] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, O, I, I, I, I])),
            [112] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, O, O, O])),
            [113] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, O, O, I])),
            [114] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, O, I, O])),
            [115] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, O, I, I])),
            [116] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, I, O, O])),
            [117] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, I, O, I])),
            [118] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, I, I, O])),
            [119] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, O, I, I, I])),
            [120] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, I, O, O, O])),
            [121] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, I, O, O, I])),
            [122] => Some(Word::new([O, O, O, O, O, O, O, O, O, I, I, I, I, O, I, O])),

            // newline
            [110, 101, 119, 108, 105, 110, 101] 
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, O, O])),
            // backspace
            [98, 97, 99, 107, 115, 112, 97, 99, 101]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, O, I])),
            // leftarrow
            [27, 91, 68]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, I, O])), 
            [108, 101, 102, 116, 97, 114, 114, 111, 119]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, I, O])), 
            // uparrow
            [27, 91, 65]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, I, I])),
            [117, 112, 97, 114, 114, 111, 119]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, O, I, I])),
            // rightarrow
            [27, 91, 67]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, O, O])),
            [114, 105, 103, 104, 116, 97, 114, 114, 111, 119]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, O, O])),
            // downarrow
            [27, 91, 66]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, O, I])),
            [100, 111, 119, 110, 97, 114, 114, 111, 119]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, O, I])),
            // home
            [32]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, I, O])),
            [104, 111, 109, 101]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, I, O])),
            // end
            [101, 110, 100]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, O, I, I, I])),
            // pageup
            [112, 97, 103, 101, 117, 112]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, O, O])),
            // pagedown
            [112, 97, 103, 101, 100, 111, 119, 110]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, O, I])),
            // insert
            [105, 110, 115, 101, 114, 116]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, I, O])),
            // delete
            [100, 101, 108, 101, 116, 101]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, I, O])),
            // esc
            [27]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, I, I])),
            [101, 115, 99]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, O, I, I])),
            // f1
            [27, 79, 80]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, O])),
            [102, 49]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, O])),
            [70, 49]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, O])),
            // f2
            [27, 79, 81]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, I])),
            [102, 50]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, I])),
            [70, 50]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, O, I])),
            // f3
            [27, 79, 82]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, O])),
            [102, 51]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, O])),
            [70, 51]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, O])),
            // f4
            [27, 79, 83]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, I])),
            [102, 52]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, I])),
            [70, 52]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, O, I, I, I, I])),
            // f5
            [27, 91, 49, 53, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, O])),
            [102, 53]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, O])),
            [70, 53]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, O])),
            // f6
            [27, 91, 49, 55, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, I])),
            [102, 54]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, I])),
            [70, 54]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, O, I])),
            // f7
            [27, 91, 49, 56, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, I, I])),
            [102, 55]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, I, I])),
            [70, 55]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, O, I, I])),
            // f8
            [27, 91, 49, 57, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, O])),
            [102, 56]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, O])),
            [70, 56]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, O])),
            // f9
            [27, 91, 50, 48, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, I])),
            [102, 57]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, I])),
            [70, 57]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, O, I])),
            // f10
            [27, 91, 50, 49, 126]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, I, O])),
            [102, 49, 48]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, I, O])),
            [70, 49, 48]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, I, O])),
            // f11
            [102, 49, 49]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, I, I])),
            [70, 49, 49]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, O, I, I, I])),
            // f12
            [102, 49, 50]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, I, O, O, O])),
            [70, 49, 50]
                => Some(Word::new([O, O, O, O, O, O, O, O, I, O, O, I, I, O, O, O])),
             
            // Input error
            _ => None
        }
    }

    pub fn output(&self) -> Word {
        self.word
    }
}

Screen

Computerでは、メモリマップドI/OによりKeyboardやScreenとCPUのやり取りを実現しています。そのため、Screenでは各ピクセルにbitが割り振られていて、Iなら黒、Oなら白を表示します。これはnand2tetrisが提供するハードウェアシミュレータには最初から実装されていますが、今回は自分で実装することになりました。

Screenの表示のためのウィンドウの表示と描画にはrust-sdl2という外部ライブラリを用いました。なお、Rustではこのような外部ライブラリのことを外部クレート(crate)と呼びます。このような外部クレートがとても簡単に利用・管理できるのはRustの強みです。

実際に表示したWindowは下のようなものです。まだ動作が安定していないので、これは今後の課題とします。

Scrennの描画・表示されているものに意味はありません

Computer

ここまでで作成したパーツを組み合わせてCPUやMemory、ROM32Kを作り、この3つを組み合わせてComputerを作りました。Computer構造体はnewメソッドで宣言したのちrunメソッドを呼び出せば、標準入力からプログラムがどこにあるか入力するように促し実際にプログラムを実行してくれます。なおこれらにも特筆すべき工夫は必要なかったので説明は割愛します。

computer.rs

pub struct Computer {
    rom: ROM32K,
    cpu: CPU,
    memory: Memory,
    address: [bit; 15],
    inM: Word
}

impl Computer {
    pub fn new() -> Self {
        Computer {
            rom: ROM32K::new(),
            cpu: CPU::new(),
            memory: Memory::new(),
            address: [O; 15],
            inM: Word::new([O; 16])
        }
    }
    pub fn run(&mut self) {
        self.load_program();
        self.memory.screen.canvas.reload_screen();
        // self.execute(1);
        self.compute();
    }
    fn load_program(&mut self) {
        print!("Input program's file name < ");
        stdout().flush().unwrap();
        let stdin = io::stdin();
        let mut filename = "".to_string();
        for line_result in stdin.lock().lines() {
            let line = line_result.expect("fail to read file's name");
            filename = line;
            break;
        }
        self.rom.load(&filename);
    }
    fn compute(&mut self) {
        self.execute(1); 
        let mut i = 0;
        'running: loop {
            for event in self.memory.screen.event_pump().poll_iter() {
                match event {
                    Event::Quit{..} |
                    Event::KeyDown { keycode: Some(Keycode::Escape), ..}=> {
                        break 'running
                    },
                    _ => {}
                }
            }
            self.execute(0);
            i += 1;
            if i > 32 {
                break 'running;
            }
        }
    }
    fn execute(&mut self, reset: u8) {
        let mut clock = Clock::new();
        // Tick

        // ROM
        let instruction = self.rom.output(&clock, self.address);

        // CPU
        self.cpu.input(&clock, self.inM, instruction, bit::from(reset));
        let (outM, writeM, addressM, pc) = self.cpu.output(&clock);

        // Memory
        self.memory.input(&clock, outM, addressM, writeM);
        self.inM = self.memory.output(&clock, addressM);

        clock.next();
        // Tock

        // ROM
        let instruction = self.rom.output(&clock, pc);

        // CPU
        self.cpu.input(&clock, self.inM, instruction, bit::from(reset));
        let (outM, writeM, addressM, pc) = self.cpu.output(&clock);
        // Use Mux when you make real curcuit
        self.address = if bit::from(reset) == I { [O; 15] } else { pc };

        // Memory
        self.memory.input(&clock, outM, addressM, writeM);
        self.inM = if bit::from(reset) == I { Word::new([O; 16]) } else { self.memory.output(&clock, addressM)} ;
    }
}

結び

長くなりましたが、以上によりnand2tetrisのハードウェアパートをRustを用いて実装することができました。残りのソフトウェアパートはそもそも環境に制約はないので、こちらは特に工夫なくRustで書いていこうと思います。nand2tetrisはだいぶ簡略化されたアーキテクチャを扱っており、また各パートにおける最適化に関する話題は全く扱っていないので、nand2tetrisで全体像を掴んだら更に自分で理解を深めていこうと思います。

以上、nand2tetrisをちょっとした工夫で更に楽しむ - 1から全部Rustで書こう - でした。

脚注

1. Rustではコードブロックの最後がセミコロンなしの値で終わる時、そのコードブロックの評価値が最後の値として評価されます。そのため関数の最後がセミコロンなしの値で終わればその関数の返り値はその値になります。

2. 任意の論理関数が論理関数集合Fの要素の複合を繰り返して得られること。完全(complete)あるいは万能(universal)という。