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

# はじめに

これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第7章 バーチャルマシン#1スタック操作のプロジェクトに対するレポートである。

Qiitaでは、画像の利用に制約があるため、フローチャートなど掲載することは省いている。

# プロジェクトに対するレポート

## 目標
* VMをHackコンピュータで動作させる
* 「スタック算術」と「メモリアクセス」を実装する
 
## 材料
* Nand2Tetrisで定義しているアセンブラのAPI(仕様)
* Nand2Tetrisで定義しているVM仕様
* Ruby
* アセンブラ
* CPUエミュレータ
* ハードウェアエミュレータ

## 実装
Nand2Tetrisのアセンブラは文字列の変換のため、スクリプト言語が適していると考え、Rubyにより作成することとする。

### Parserモジュール

* Rubyのクラスにより実装する
* API仕様のルーチンは、メソッドにより実装する

###コンストラクタ
アセンブラせ作成したときのメソッドを再利用している。
File.openによりファイルハンドルを取得する。

```Ruby:Parser.rb
  def initialize(filename)
    @vmFile = File.open(filename, "r")
  end
```

### hasMoreCommands
アセンブラせ作成したときのメソッドを再利用している。
File.eof?メソッドによりチェックを行う。

```Ruby:Parser.rb
  def hasMoreCommands
    return !@vmFile.eof?
  end
```

### advance
アセンブラせ作成したときのメソッドを再利用している。
File.readlineメソッドにより一行分取り出し文字の配列にする。
今回同じメソッドを複数回呼び出すことが有るためパース状態を定義する。

```Ruby:Parser.rb
  def advance  
    rl = @vmFile.readline
    rl.strip!
    @chars = rl.split(//)
    @parseState = S_COMMAND
    rl
  end
```
### commandType
アセンブラせ作成したときのメソッドを再利用している。
文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。
パース状態はS_COMMANDのときのみパース処理を行う
それ以外のパース状態のときは返り値処理のみ実行する。

```Ruby:Parser.rb
  def commandType
    if @parseState == S_COMMAND 
      field = ""
      while c = @chars.shift
        if c == " "
          break
        else
          field.concat c
        end
      end
      @command = field
      @parseState = S_ARG1
    end
    case @command
      when "push" 
        return C_PUSH
      when "pop"
        return C_POP
      when "label"
        return C_LABEL
      when "goto"
        return C_GOTO
      when "if-goto"
        return C_IF
      when "function"
        return C_FUNCTION
      when "call"
        return C_CALL
      when "return"
        return C_RETURN
      else
        return C_ARITHMETRIC
    end

```

### arg1
パース状態はS_ARG1のときのみパース処理を行う
C_ARITHMETRICのときはコマンドの文字列を返す
それ以外のときは文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。

```Ruby:Parser.rb
  def arg1
    if @parseState == S_ARG1
      if commandType == C_ARITHMETRIC
        @parseState = S_ARG2
        return @command
      else
        field = ""
        while c = @chars.shift
          if c == " "
            break
          else
            field.concat c
          end
        end
        @parseState = S_ARG2
        return field
      end
    end
  end
```
### arg2
パース状態はS_ARG2のときのみパース処理を行う
文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。

```Ruby:Parser.rb
  def arg2
    if @parseState == S_ARG2
      field = ""
      while c = @chars.shift
        if c == " "
          break
        else
          field.concat c
        end
      end
      return field  
    end
  end
```

### CodeWriterモジュール

* Rubyのクラスにより実装する
* API仕様のルーチンは、メソッドにより実装する

###コンストラクタ
File.openによりファイルハンドルを取得する。

```Ruby:Parser.rb
  def initialize(filename)
    @asmFile = File.open(filename, "w+");
  end
```

###setFileName
staticのときに使うVMファイル名をセットする。

```Ruby:Parser.rb
  def setFileName(filename)
    @currentFile = filename
    @cnt = 0
  end
```

###writeArithmetric
addなどの二項演算子のときは、２回ポップ処理を行い、計算後プッシュする。例えば、addのときは以下の通りである

```Ruby:Parser.rb
  def writeArithmetric(command)
    field = ""
    case command
    when "add"
        field = field + Indent + "@SP\n"
        field = field + Indent + "AM=M-1\n"
        field = field + Indent + "D=M\n"
        field = field + Indent + "@SP\n"
        field = field + Indent + "AM=M-1\n"
        field = field + Indent + "M=D+M\n"
        field = field + Indent + "@SP\n"
        field = field + Indent + "M=M+1\n" 
    end
    @cnt = @cnt + 1
    @asmFile.print field
  end
```
###writePushPop
まずconstantを実装する。インデックスの値をスタックにプッシュしている。

```Ruby:Parser.rb
  def writePushPop(command, segment, index)
    field = ""
    case command
    when C_PUSH
      case segment
      when "constant"
        field = field + Indent + "@"+index+"\n"
        field = field + Indent + "D=A\n"
        field = field + Indent + "@SP\n"
        field = field + Indent + "A=M\n"
        field = field + Indent + "M=D\n"
        field = field + Indent + "@SP\n"
        field = field + Indent + "M=M+1\n"
      end
    end
    @asmFile.print field  
  end
```

###テスト
ここまで実装後、SimpleAddを行い、動作することを確認する。

###残りの実装
スタック算術とメモリアクセスについて残りの部分を作成する。
基本的なコードはaddやconstantと同じである。
比較のときはHackでは、JMP命令を使うため、そのためのラベルなどを追加している。
またPOPのときはポップ先のアドレスの計算とスタックの取り出し後のデータのアドレス衝突があるため、一度R13にポップ先のアドレスを保存している。

###テスト
以下の通り、いずれのテストも問題なく完了することができた

| Test | OK/NG |
|:-:|:-:|
| SimpleAdd | OK |
| StackTest | OK |
| BasicTest | OK |
| PointerTest | OK |
| StaticTest | OK |

###考察
今回のコード生成において、同じ処理をまとめず、各コマンドにより同じことを繰り返している。それはVMにしたときどれくらいの命令が必要になるかを示すためである。

スタック算術については以下の通りの命令数であった

| スタック算術 | 命令数 |
|:-:|:-:|
| add | 8 |
| sub | 8 |
| and | 8 |
| or | 8 |
| eq | 24 |
| gt | 24 |
| lt | 24 |
| neg | 6 |
| not | 6 |

PUSHについては以下の通りの命令数であった

| スタック算術 | 命令数 |
|:-:|:-:|
| constant | 7 |
| local | 10 |
| argument | 10 |
| this | 10 |
| that | 10 |
| pointer | 10 |
| temp | 10 |
| static | 7 |

POPについては以下の通りの命令数であった

| スタック算術 | 命令数 |
|:-:|:-:|
| constant | - |
| local | 12 |
| argument | 12 |
| this | 12 |
| that | 12 |
| pointer | 12 |
| temp | 12 |
| static | 5 |