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

はじめに

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

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

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

目標

• VMをHackコンピュータで動作させる
• 「スタック算術」と「メモリアクセス」を実装する

材料

• Nand2Tetrisで定義しているアセンブラのAPI(仕様)
• Nand2Tetrisで定義しているVM仕様
• Ruby
• アセンブラ
• CPUエミュレータ
• ハードウェアエミュレータ

実装

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

Parserモジュール

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

コンストラクタ

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

Parser.rb

  def initialize(filename)
    @vmFile = File.open(filename, "r")
  end

hasMoreCommands

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

Parser.rb

  def hasMoreCommands
    return !@vmFile.eof?
  end

advance

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

Parser.rb

  def advance  
    rl = @vmFile.readline
    rl.strip!
    @chars = rl.split(//)
    @parseState = S_COMMAND
    rl
  end

commandType

アセンブラせ作成したときのメソッドを再利用している。
文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。
パース状態はS_COMMANDのときのみパース処理を行う
それ以外のパース状態のときは返り値処理のみ実行する。

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のときはコマンドの文字列を返す
それ以外のときは文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。

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のときのみパース処理を行う
文字の配列から一文字ずつ取り出し、空白文字までを抜き出している。

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によりファイルハンドルを取得する。

Parser.rb

  def initialize(filename)
    @asmFile = File.open(filename, "w+");
  end

setFileName

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

Parser.rb

  def setFileName(filename)
    @currentFile = filename
    @cnt = 0
  end

writeArithmetric

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

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を実装する。インデックスの値をスタックにプッシュしている。

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