RubyでRubyVMを実装してRubyVMの気持ちになってみる

# はじめに
この記事は「ほんのちょっとだけRubyが動くVMをRubyで実装してみて、Rubyが実行される仕組みを理解しよう」という趣旨のゆるふわな記事です。

こんなコードを実行できるVMを実装します。

```rb
a = 1 + "string".length

puts "result: #{a}"
```

この記事ではRuby 2.3.3を使います。

## 注意点
* 本記事にでてくる用語は厳密な定義とかは気にせずゆるくふんわりと使ってます
* VMの実装はRubyを使うので結構ずるい感じです
* 構文解析、コンパイルはしません
* クラス定義、メソッド探索、コントロールフレームなどの概念はでてきません
* なのでRubyを題材にしてますが、Rubyの特徴的な機能にはあまり触れていません

## 対象読者
* Rubyが好き
* 普段Webプログラミングとかしてる
* プログラミング言語の処理系としてのVMが気になる

# まえおき
## VMとは
RubyはJavaやErlangなどと同じようにRuby用のVM(仮想マシン)上で実行されます。
C言語やGo言語などはマシン語へコンパイルされ、VMではなくコンピュータが直接実行します。

<img width="350" alt="26827a14-999b-4339-a96d-673da18b6928.png" src="https://qiita-image-store.s3.amazonaws.com/0/43208/29b05292-81ad-74fc-ff74-23a09bd1eb8d.png">

仮想マシン、VM、Virtual Machineというと、VirtualBoxやVMwareのような現実世界の物理的なコンピュータをソフトウェアで仮想化したものが一般的です。RubyVMもそれらと同じようにコンピュータ(のようなもの)をソフトウェアとして実現したものです。RubyVMがVirtualBoxなどと違う点は、Rubyを実行するためだけに設計され、実装されているところです。Rubyを実行するためだけの架空のコンピュータがあり、それを仮想化した仮想マシン、というイメージに近いかもしれません。RubyVMも現実世界のコンピュータと同じように、命令群が用意されていてレジスタやスタックを持っています。

RubyVMはRubyVM用のマシン語を実行します。RubyVMのマシン語とIntel CPUのマシン語を比較してみましょう。

### Intel CPUのマシン語
C言語の[Hello, world](https://gist.github.com/nownabe/d4af7d933fea096ddfcd9020121dcfda#file-hello-c)をコンパイルしたものです[^1]。左端の16進数の数字はアドレス、真ん中の16進数の列がマシン語、右側はマシン語に対応するアセンブリです。

アセンブリを見ると`push`や`mov`などのIntel CPUの命令とその引数でプログラムが構成されていることがわかります。

```
   0:   55                      push   rbp
   1:   48 89 e5                mov    rbp,rsp
   4:   48 83 ec 10             sub    rsp,0x10
   8:   48 8d 3d 1b 00 00 00    lea    rdi,[rip+0x1b]        # 2a <_main+0x2a>
   f:   c7 45 fc 00 00 00 00    mov    DWORD PTR [rbp-0x4],0x0
  16:   b0 00                   mov    al,0x0
  18:   e8 00 00 00 00          call   1d <_main+0x1d>
  1d:   31 c9                   xor    ecx,ecx
  1f:   89 45 f8                mov    DWORD PTR [rbp-0x8],eax
  22:   89 c8                   mov    eax,ecx
  24:   48 83 c4 10             add    rsp,0x10
  28:   5d                      pop    rbp
  29:   c3                      ret
```

[^1]: 正確にはコンパイルして、逆アセンブルしたものです。

### RubyVMのマシン語
Rubyの[Hello, world](https://gist.github.com/nownabe/d4af7d933fea096ddfcd9020121dcfda#file-hello-rb)をコンパイルしたものです[^1]。先程と同じように、`putself`や`send`などのRubyVM用の命令とその引数でプログラムが構成されていることがわかります。なんとなく、Rubyな感じがプンプンしますね :relaxed: 

```
0000 putself                                                          (   1)
0001 putstring        "Hello, world!"
0003 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0007 leave
```

RubyVMとはこのような命令列を実行することができる仮想コンピュータということになります。

ここまでは比較しやすいようにマシン語という言葉を使いましたが、今後はRubyVMのマシン語で表現されるプログラムを**バイトコード**と呼ぶことにします。

## Ruby実行の流れ
VMを作り始める前に、Rubyがどういう流れで実行されているかを簡単に説明します。

Rubyは実行時に次の図のような流れで実行されています。

<img width="450" alt="46714a39-ed09-4295-b814-dd1a581673f1.png" src="https://qiita-image-store.s3.amazonaws.com/0/43208/e4d216e7-dbf6-4e11-c862-0c3cc7093dd5.png">

各工程の細い内容は説明しませんが、ソースコードをいろいろ解析してコンパイルしてバイトコードを生成し、RubyVMがそれを実行しています。

# 目標
本記事では字句解析や構文解析、コンパイルには言及しません。RubyVMの部分だけを新しく実装します。
つまり、Rubyのバイトコードを受け取ってそれを実行するプログラムをRubyで書きます。

しかしRubyの全機能が使えるようなVMを作るにはかなりの労力が必要なので、今回は次のような機能が使えるVMを実装します。

* 組み込みクラスが使える
* 数値や文字列、配列のリテラルが一部使える
* 単純な引数付きでメソッドを呼び出せる
* ローカル変数が使える
* 式展開が使える

とても少ないですが、きっと次のようなプログラムが動くはずです。

```rb
puts 1 + "string".length
a = "world!"
puts "Hello, #{a}"
```

# 準備
適当なディレクトリを作ってください。その中で実装していきます。
本記事で使うコードはすべて[nownabe/saira](https://github.com/nownabe/saira)にあります。

## 逆アセンブラ
何かとバイトコードを眺めることになるので、任意のRubyプログラムのバイトコードを出力できるスクリプトを作成しておきます。

次のような`disasm`ファイルを作成してください。

```rb:disasm
#!/usr/bin/env ruby

puts RubyVM::InstructionSequence.compile_file(ARGV[0], false).disasm
```

`compile_file`の第2引数の`false`は最適化をしないというオプションです。
最適化すると複雑になってしまうので、本記事では常に最適化しない状態で説明します。

次のコマンドでスクリプトに実行権限をつけます。

```bash
$ chmod +x disasm
```

試しに使ってみます。引数に任意のプログラムのパスを与えるとそのプログラムのバイトコードを出力できます。

```bash
$ ./disasm disasm
== disasm: #<ISeq:<main>@disasm>========================================
0000 putself                                                          (   3)
0001 putnil
0002 getconstant      :RubyVM
0004 getconstant      :InstructionSequence
0006 putnil
0007 getconstant      :ARGV
0009 putobject        0
0011 send             <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>, nil
0015 putobject        false
0017 send             <callinfo!mid:compile_file, argc:2, ARGS_SIMPLE>, <callcache>, nil
0021 send             <callinfo!mid:disasm, argc:0, ARGS_SIMPLE>, <callcache>, nil
0025 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0029 leave
```

## bootstrap
任意のRubyプログラムを今から作るVMで実行するようなbootstrapスクリプトを作成します。

VMを実行するAPIは次のようにします。

```rb
Saira::VirtualMachine.new(iseq).run
```

名前がないと困るので、適当に`Saira`[^2]と名付けました。`iseq`は`RubyVM::InstructionSequence`のインスタンスです。

[^2]: サンマだそうです :fish:

次のような`boot`ファイルを作ってください。

```rb:boot
#!/usr/bin/env ruby

$LOAD_PATH.unshift File.expand_path("../lib", __FILE__)

require "saira/virtual_machine"

iseq = RubyVM::InstructionSequence.compile_file(ARGV[0], false)
Saira::VirtualMachine.new(iseq).run
```

実行権限をつけます。

```bash
$ chmod +x boot
```

さて、ついでにSairaVMの雛形を作ってしまいます。次のような`lib/saira/virtual_machine.rb`を作成してください。

```rb:lib/saira/virtual_machine.rb
module Saira
  class VirtualMachine
    attr_reader :iseq

    def initialize(iseq)
      @iseq = iseq
    end

    def run
      puts iseq.disasm
    end
  end
end
```

`run`の中身はまだ何もないので、とりあえずバイトコードを出力するようにしてみました。
試してみましょう。

```bash
$ ./boot lib/saira/virtual_machine.rb
== disasm: #<ISeq:<main>@lib/saira/virtual_machine.rb>==================
0000 putspecialobject 3                                               (   1)
0002 putnil
0003 defineclass      :Saira, <module:Saira>, 2
0007 leave
== disasm: #<ISeq:<module:Saira>@lib/saira/virtual_machine.rb>==========
0000 putspecialobject 3                                               (   2)
...
```

準備は以上です。

ここまでのコードは[prepareブランチ](https://github.com/nownabe/saira/tree/prepare)にあります。

次からは、ちゃんとバイトコードからプログラムを実行できるように`run`メソッドを実装していきます。

# メソッド呼び出し
まずはHello, worldできるようにしましょう。ここで重要になるのはメソッド呼び出しです。

具体的には次のプログラムを実行できるようにします。このプログラムは`test/hello.rb`に保存しておいてください。

```rb:test/hello.rb
puts "Hello, world!"
```

これのバイトコードは次のようになります。

```
0000 putself                                                          (   1)
0001 putstring        "Hello, world!"
0003 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0007 leave
```

VMのベース機能を実装し、この4つの命令を実装していきます。

## InstructionSequence
これまで何気なく`RubyVM::InstructionSequence#disasm`というメソッドでバイトコードをみてきました。`#disasm`メソッドでは文字列でバイトコードが得られますが、`#to_a`メソッドを使えばRubyのオブジェクトとしてバイトコードを得られるのでSairaVM内では`#to_a`を使っていきます。

```rb
>> RubyVM::InstructionSequence.compile_file("test/hello.rb", false).to_a
=> ["YARVInstructionSequence/SimpleDataFormat",
 2,
 3,
 1,
 {:arg_size=>0, :local_size=>1, :stack_max=>2},
 "<main>",
 "test/hello.rb",
 "/Users/nownabe/src/github.com/nownabe/qiita-rubyvm/test/hello.rb",
 1,
 :top,
 [],
 {},
 [],
 [1, [:putself], [:putstring, "Hello, world!"], [:send, {:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil], [:leave]]]
```

それぞれの要素については[ドキュメント](https://docs.ruby-lang.org/ja/latest/class/RubyVM=3a=3aInstructionSequence.html#I_TO_A)を参照してください。重要になるのは最後の要素で、バイトコードの配列になっています。

```rb
>> RubyVM::InstructionSequence.compile_file("test/hello.rb", false).to_a.last
=> [1, [:putself], [:putstring, "Hello, world!"], [:send, {:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil], [:leave]]
```

## 命令実行サイクル
ではいよいよSairaVMの実装を進めていきます。

VMはとても単純で、突き詰めるとバイトコードの命令を順番に実行していくだけです。イメージとしてはこんな感じです。

```rb
loop do
  instruction = get_next_instruction
  execute(instruction)
end
```

これを具体的に実装してきます。

```lib/saira/virtual_machine.rb
module Saira
  class VirtualMachine
    attr_reader :iseq

    def initialize(iseq)
      @iseq = iseq
    end

    def run
      iseq.to_a.last.each do |instruction|
        next unless instruction.is_a?(Array)
        execute(instruction)
      end
    end

    def execute(instruction)
      opecode = instruction.first
      operand = instruction[1..-1]
      $stderr.puts "==== #{opecode}(#{operand.map(&:inspect).join(', ')})"
    end
  end
end
```

`run`メソッドの`each`が命令実行サイクルになります。`iseq.to_a.last`にはRubyプログラム中の行番号を表す整数なども含まれるので、`Array`かどうかをみてそれらは無視するようにしています。`instruction`が命令を表す`Array`の場合はそれを引数として`execute`メソッドを実行します。

`instruction`は第1要素に命令の名前、第2要素以降が命令の引数になっています。命令の実体はまだないので、それらをとりあえず出力しています。

この命令名と引数の対応ですが、

```
0000 putself                                                          (   1)
0001 putstring        "Hello, world!"
0003 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0007 leave
```

ならば、

* 1つ目の命令: 命令名は`putself`で引数はなし
* 2つ目の命令: 命令名は`putstring`で引数は`"Hello, world!"`
* ...

といった具合です。

この段階でSairaVMを実行してみると、命令の中身はありませんが命令実行サイクルは回ってることがわかります。

```bash
$ ./boot test/hello.rb
==== putself()
==== putstring("Hello, world!")
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
==== leave()
```

## スタック
RubyVMはスタックマシンと呼ばれるタイプのVMで、スタックに値を積み上げていって逆ポーランド的に計算を行います。

雑なイメージですが`1 + 2`を計算するときは下の図のように計算することになります。

<img width="250" alt="4bdeb438-42c9-416d-a06f-d96b8ad386ce.png" src="https://qiita-image-store.s3.amazonaws.com/0/43208/259d9969-8664-5df6-ce84-8b281ade1725.png">

1、2、+を命令実行サイクルで順に処理していきます。1をスタックにpushし、2をpushし、+の場合はスタックから2回popしてそれらを足し算した結果をスタックにpushします。

では、SairaVMにスタックを準備しましょう。SairaVMのスタックにはRubyの`Array`をそのまま使います。

```rb:lib/saira/virtual_machine.rb
module Saira
  class VirtualMachine
    attr_reader :iseq, :stack

    def initialize(iseq)
      @iseq = iseq
      @stack = []
    end

    def run
      iseq.to_a.last.each do |instruction|
        next unless instruction.is_a?(Array)
        execute(instruction)
      end
    end

    def execute(instruction)
      opecode = instruction.first
      operand = instruction[1..-1]
      $stderr.puts "==== #{opecode}(#{operand.map(&:inspect).join(', ')})"
      $stderr.puts "======== Stack: #{stack}"
    end

    def push(val)
      stack.push(val)
    end

    def pop
      stack.pop
    end
  end
end
```

`initialize`で`@stack`に空の`Array`を代入しています。そして、スタックへ値をpush/popするためのAPIである`push`メソッドと`pop`メソッドを定義しました。また、各命令実行後のスタックの内容を確認できるようにしました。

これでVMの基本機能は実装できました。次から各命令を実装していきましょう。

## putself
```
0000 putself 
```

その名の通り`self`をスタックにpushする命令です。SairaVMではクラス定義やメソッド定義ができない(スコープがない)ので`self`は常に`main`です。`Saira::VirtualMachine#initialize`で`main`を初期化し、それをpushするようにします。

まずは`main`の初期化部分の変更だけ見てみましょう。


```rb:lib/saira/virtual_machine.rb
module Saira
  class VirtualMachine
    attr_reader :iseq, :stack, :main

    def initialize(iseq)
      @iseq = iseq
      @stack = []
      @main = generate_main
    end

    # ...

    private

    def generate_main
      main = Object.new
      class << main
        def to_s
          "main"
        end
        alias inspect to_s
      end
      main
    end
  end
end
```

`main`を生成する`generate_main`メソッドを定義して`initialize`で初期化しています。[^3]

[^3]: `main`の定義は、Rubyの`Init_top_self`という関数にあります。https://github.com/ruby/ruby/blob/v2_3_3/vm.c#L3017

次に`putself`を`execute`メソッドの中に定義します。

```rb:lib/saira/virtual_machine.rb
def execute(instruction)
  opecode = instruction.first
  operand = instruction[1..-1]
  $stderr.puts "==== #{opecode}(#{operand.map(&:inspect).join(', ')})"
  case opecode
  when :putself
    push main
  end
  $stderr.puts "======== Stack: #{stack}"
end
```

とても単純ですね。`opecode`には命令名が入るので`case`で分岐するようにしました。`puself`の場合、SairaVMでは必ず`self`が`main`なので`main`をスタックにpushしています。

今後、命令の定義は`when`節のみを掲載します。

この段階で`test/hello.rb`を実行するとこのような出力が得られます。

```bash
$ ./boot test/hello.rb
==== putself()
======== Stack: [main]
==== putstring("Hello, world!")
======== Stack: [main]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
======== Stack: [main]
==== leave()
======== Stack: [main]
```

`main`がスタックに積まれていることがわかります。

## putstring
```
0001 putstring        "Hello, world!"
```

putstringは文字列を引数にとり、それをスタックにpushする命令です。実装はこのようになります。[^4]

[^4]: 本家ではコピーします。

```rb:lib/saira/virtual_machine.rb
case opecode
when :putstring
  push operand[0]
end
```

実行結果は次のようになります。

```bash
$ ./boot test/hello.rb
==== putself()
======== Stack: [main]
==== putstring("Hello, world!")
======== Stack: [main, "Hello, world!"]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
======== Stack: [main, "Hello, world!"]
==== leave()
======== Stack: [main, "Hello, world!"]
```

## send
```
0003 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
```

いよいよメソッド呼び出しの主役、`send`命令です。名前からして想像がつきますがほぼRubyの`send`です。RubyVMではスタックを使ってレシーバや引数のやりとりしています。

引数は3つとりますが今回必要になるのは第1引数の`callinfo`だけです。`callinfo`は次のような`Hash`オブジェクトとして得られます。

```rb
{:mid=>:puts, :flag=>20, :orig_argc=>1}
```

`mid`がメソッド名、`orig_argc`は引数の数になります。`flag`はメソッド呼び出しについてのフラグで、引数展開をしたりキーワード引数を使ったりするときに必要になりますが今回は無視します。

`send`命令は引数とレシーバをスタックからpopし、返り値を新たにpushします。次の図は

```rb
"abcde".sub("bcd", "BCD")
```

というプログラムの`send`命令の前後でのスタックの状態を表しています。

<img width="400" alt="send命令前後のスタック" src="https://qiita-image-store.s3.amazonaws.com/0/43208/a8755b8d-d477-24c1-1a14-5f2f4f840fbf.png">

これを実装すると次のようになります。

```rb:lib/saira/virtual_machine.rb
case opecode
when :send
  call_info = operand[0]
  args = Array.new(call_info[:orig_argc]) { pop }.reverse
  receiver = pop
  push receiver.send(call_info[:mid], *args)
end
```

まず、引数を引数の数だけpopします。そして次はレシーバをpopします。レシーバと引数が得られれば、そのレシーバのメソッドを呼び出せばいいのでRubyの`send`メソッドを使ってメソッドを実行しています。

実行結果は次のようになります。

```bash
$ ./boot test/hello.rb
==== putself()
======== Stack: [main]
==== putstring("Hello, world!")
======== Stack: [main, "Hello, world!"]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
Hello, world!
======== Stack: [nil]
==== leave()
======== Stack: [nil]
```

おっ！ついに「Hello, world!」が出力されました！:tada:

`send`命令では`main`と`"Hello, world!"`がpopされ、`puts`メソッドの返り値である`nil`がスタックに積まれていることが確認できます。

## leave
```
0007 leave
```

最後の`leave`命令は今のスコープから抜けるという命令ですが、SairaVMではスコープがないので無視します :sweat_smile: 

```rb
case opecode
when :leave:
end
```

実行結果は先程と変わりません。

これで、メソッド呼び出しができるようになりました。

ここまでのコードは[method_callブランチ](https://github.com/nownabe/saira/tree/method_call)にあります。

# おまけ1
`putobject`命令と`duparray`命令を実装してもうちょっと遊べるようにしてみましょう。せっかくメソッド呼び出しができるようになりましたが、push系の命令が`putself`と`putstring`しかないので`main`と文字列のメソッドしか呼び出せません。実はこれらの命令は`putstring`をそのまま流用できます。`dup`じゃねーのかという些細ことはここでは無視します :hear_no_evil: 

SairaVMを次のように修正してください。

```rb:lib/saira/virtual_machine.rb
case opecode
when :putstring, :putobject, :duparray
  push operand[0]
end
```

これで、例えば次のようなプログラムが実行できるようになります。

```rb:test/omake1.rb
puts 1 + 2 + 3
p [1, 2, 3]
```

```bash
./boot test/omake1.rb
==== putself()
======== Stack: [main]
==== putobject(1)
======== Stack: [main, 1]
==== putobject(2)
======== Stack: [main, 1, 2]
==== send({:mid=>:+, :flag=>16, :orig_argc=>1}, false, nil)
======== Stack: [main, 3]
==== putobject(3)
======== Stack: [main, 3, 3]
==== send({:mid=>:+, :flag=>16, :orig_argc=>1}, false, nil)
======== Stack: [main, 6]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
6
======== Stack: [nil]
==== pop()
======== Stack: [nil]
==== putself()
======== Stack: [nil, main]
==== duparray([1, 2, 3])
======== Stack: [nil, main, [1, 2, 3]]
==== send({:mid=>:p, :flag=>20, :orig_argc=>1}, false, nil)
[1, 2, 3]
======== Stack: [nil, [1, 2, 3]]
==== leave()
======== Stack: [nil, [1, 2, 3]]
```

`6`と`[1, 2, 3]`が出力されてますね :smile: 
debug情報がうるさい場合は次のように実行してください。

```bash
$ ./boot test/omake1.rb 2> /dev/null
6
[1, 2, 3]
```

ひとつだけ、`pop`命令が実行できていないのでついでに実装してしまいましょう。これは単純にスタックから1つ値を取り出す命令です。ここではスタックの値を1つ捨てているんですね。

```rb:lib/saira/virtual_machine.rb
case opecode
when :pop
  pop
end
```

ここまでのコードは[omake1ブランチ](https://github.com/nownabe/saira/tree/omake1)にあります。

# ローカル変数
次は、ローカル変数を使えるようにします。具体的には次のプログラムを実行できるようにします。このプログラムは`test/locals.rb`に保存しておいてください。

```rb:test/locals.rb
a = 1
puts a

b = 2
puts b
```

Iseqは次のようになります。

```rb
["YARVInstructionSequence/SimpleDataFormat",
 2,
 3,
 1,
 {:arg_size=>0, :local_size=>3, :stack_max=>2},
 "<main>",
 "test/locals.rb",
 "/Users/nownabe/src/github.com/nownabe/saira/test/locals.rb",
 1,
 :top,
 [:a, :b],
 {},
 [],
 [1,
  [:putobject, 1],
  [:setlocal, 3, 0],
  2,
  [:putself],
  [:getlocal, 3, 0],
  [:send, {:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil],
  [:pop],
  4,
  [:putobject, 2],
  [:setlocal, 2, 0],
  5,
  [:putself],
  [:getlocal, 2, 0],
  [:send, {:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil],
  [:leave]]]
```

`setlocal`や`getlocal`などローカル変数関係っぽい命令が新しく登場してます。また、第5要素の

```rb
{:arg_size=>0, :local_size=>3, :stack_max=>2}
```

というハッシュも使うことになります。

## ローカル変数の仕組み
ローカル変数もスタックが使われます。ただし、プログラム中で使われる領域とは分けて使われます。

<img width="350" alt="ローカル変数の仕組み1" src="https://qiita-image-store.s3.amazonaws.com/0/43208/581bceee-08b6-4c30-66e4-387c4b35c46f.png">

`ep`というのは雑に言えば、ローカル変数領域とプログラム実行中に使うスタック領域の境目を表すポインタです。ローカル変数は`ep`からの差で表現されます。

例えば先程の例

```rb:test/locals.rb
a = 1
puts a

b = 2
puts b
```

だと、変数`a`は`-3`、変数`b`は`-2`と対応しています。

<img width="400" alt="ローカル変数の仕組み2" src="https://qiita-image-store.s3.amazonaws.com/0/43208/a6fd8f94-c362-46b9-4881-67d16cfe861d.png">


ここまでわかったところで実装に入ります。[^5]

[^5]: SairaVMではスコープもブロックもないのでローカル変数群をハッシュで作ったりしてもいいのですが、今回はスタックを使ってそれっぽく実装します。

## ローカル変数領域の確保
まずはSairaVMの初期化時にローカル変数領域を確保して`ep`を設定する処理を追加します。簡単にするためSairaVMではローカル変数を`nil`で初期化することにします。

```rb:lib/saira/virtual_machine.rb
module Saira
  class VirtualMachine
    attr_reader :iseq, :stack, :main, :ep

    def initialize(iseq)
      @iseq = iseq
      @stack = []
      @main = generate_main
      iseq.to_a[4][:local_size].times { push nil }
      @ep = stack.size
    end

    # ...
  end
end
```

`iseq.to_a[4]`には`{:arg_size=>0, :local_size=>3, :stack_max=>2}`のような`Hash`オブジェクトが入ります。`local_size`にはローカル変数の数 + 1が入っているので、この数だけスタックに`nil`をpushしてローカル変数領域を初期化します。`ep`も忘れずに設定しておきます。

ついでにスタックのデバッグ出力にローカル変数領域の区切りを表示するようにしましょう。つぎのようなメソッドを追加して、`execute`メソッドの末尾で呼び出すようにします。

```rb:lib/saira/virtual_machine.rb
def print_stack
  $stderr.print "======== Stack: "
  $stderr.print stack[0...ep]
  $stderr.print " | "
  $stderr.puts stack[ep..-1].inspect
end
```

## setlocal
ローカル変数に値を代入する`setlocal`命令を実装します。

```rb
a = 1
```

というRubyプログラムは次のようなバイトコードになります。

```rb
[:putobject, 1],
[:setlocal, 3, 0]
```

`setlocal`命令はスタックからpopした値を引数と対応するローカル変数領域に突っ込むということをします。第1引数が`ep`からの差です。第2引数はブロックを使うときに必要になりますがSairaVMでは必要ないので無視します。

次のように実装できます。

```rb:lib/saira/virtual_machine.rb
case opecode
when :setlocal
  stack[ep - operand[0]] = pop
end
```

## getlocal
`getlocal`命令はローカル変数領域から取得した値をスタックにpushするという処理を行います。`setlocal`命令と同じように第1引数が`ep`との差になっています。

```rb:lib/saira/virtual_machine.rb
case opecode
when :getlocal
  push stack[ep - operand[0]]
end
```

これで`test/locals.rb`が実行できるようになりました。実行してみるとこんな感じになります。

```bash
$ ./boot test/locals.rb
==== putobject(1)
======== Stack: [nil, nil, nil] | [1]
==== setlocal(3, 0)
======== Stack: [1, nil, nil] | []
==== putself()
======== Stack: [1, nil, nil] | [main]
==== getlocal(3, 0)
======== Stack: [1, nil, nil] | [main, 1]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
1
======== Stack: [1, nil, nil] | [nil]
==== pop()
======== Stack: [1, nil, nil] | []
==== putobject(2)
======== Stack: [1, nil, nil] | [2]
==== setlocal(2, 0)
======== Stack: [1, 2, nil] | []
==== putself()
======== Stack: [1, 2, nil] | [main]
==== getlocal(2, 0)
======== Stack: [1, 2, nil] | [main, 2]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
2
======== Stack: [1, 2, nil] | [nil]
==== leave()
======== Stack: [1, 2, nil] | [nil]
```

`setlocal`でローカル変数領域に値が入ったり、`getlocal`でローカル変数の値がスタックに積まれたりしているのが確認できます。

ここまでのコードは[localsブランチ](https://github.com/nownabe/saira/tree/locals)にあります。

# おまけ2
`putnil`命令、`newarray`命令と、`getconstant`命令の3つを実装しましょう。なんとなく、あったら色々楽しめそうだなーということで。

これらを実装すると、次のようなプログラムが実行できるようになります。

```rb:test/omake2.rb
a = 1
b = String.new("second")
p [a, b]
```

## putnil
`putnil`命令は`nil`をpushする命令です。そのままですね。RubyVM内ではいろいろな場面で使われていて、`getconstant`命令でも必要になります。

```rb:lib/saira/virtual_machine.rb
case opecode
when :putnil
  push nil
end
```

## newarray
`newarray`命令は変数を含む配列リテラルを使ったときなどに必要になります。

例えばこのようなプログラムは

```rb
a = 1
p [a, 2]
```

次のようなバイトコードになります。

```
0000 putobject        1                                               (   1)
0002 setlocal         a, 0
0005 putself
0006 getlocal         a, 0
0009 putobject        2
0011 newarray         2
0013 send             <callinfo!mid:p, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0017 leave
```

`newarray`は引数で指定された数の値をpopして、それらから新しく`Array`オブジェクトを作りpushする命令です。

実装するとこんな感じです。

```rb:lib/saira/virtual_machine.rb
case opecode
when :newarray
  push Array.new(operand[0]) { pop }.reverse
end
```

## getconstant
`getconstant`命令は定数をスタックにpushする命令です。popした値が`nil`ならそのスコープで得られる定数を、`nil`でなければその値の下で得られる定数をpushします。

SairaVMにスコープはないので`nil`の場合は常に`Module`からとってくるようにします。

```rb:lib/saira/virtual_machine.rb
case opecode
when :getconstant
  klass = pop
  if klass.nil?
    push Module.const_get(operand[0])
  else
    push klass.const_get(operand[0])
  end
end
```

さて、ここまで実装できたら`test/omake2.rb`が実行できるようになってます。実行してみましょう。

```bash
$ ./boot test/omake2.rb
==== putobject(1)
======== Stack: [nil, nil, nil] | [1]
==== setlocal(3, 0)
======== Stack: [1, nil, nil] | []
==== putnil()
======== Stack: [1, nil, nil] | [nil]
==== getconstant(:String)
======== Stack: [1, nil, nil] | [String]
==== putstring("second")
======== Stack: [1, nil, nil] | [String, "second"]
==== send({:mid=>:new, :flag=>16, :orig_argc=>1}, false, nil)
======== Stack: [1, nil, nil] | ["second"]
==== setlocal(2, 0)
======== Stack: [1, "second", nil] | []
==== putself()
======== Stack: [1, "second", nil] | [main]
==== getlocal(3, 0)
======== Stack: [1, "second", nil] | [main, 1]
==== getlocal(2, 0)
======== Stack: [1, "second", nil] | [main, 1, "second"]
==== newarray(2)
======== Stack: [1, "second", nil] | [main, [1, "second"]]
==== send({:mid=>:p, :flag=>20, :orig_argc=>1}, false, nil)
[1, "second"]
======== Stack: [1, "second", nil] | [[1, "second"]]
==== leave()
======== Stack: [1, "second", nil] | [[1, "second"]]
```

実行できてますね！！ :satisfied: 

実はここまで実装すると`./disasm`もSairaVM上で動くようになっています。ぜひ`$ ./boot disasm`を実行してみてください :blush: 

ここまでのコードは[omake2ブランチ](https://github.com/nownabe/saira/tree/omake2)にあります。

# 式展開
最後はおなじみの式展開です。具体的には次のようなプログラムが実行できるようになります。このプログラムは`test/interpolation.rb`に保存してください。

```rb:test/interpolation.rb
a = 1
puts "#{a} + 2 = #{a + 2}"
```

バイトコードはこちらになります。

```
0000 putobject        1                                               (   1)
0002 setlocal         a, 0
0005 putself                                                          (   2)
0006 getlocal         a, 0
0009 tostring
0010 putobject        " + 2 = "
0012 getlocal         a, 0
0015 putobject        2
0017 send             <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache>, nil
0021 tostring
0022 concatstrings    3
0024 send             <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>, nil
0028 leave
```

新しい命令が2つあります。`tostring`命令と`concatstrings`命令です。命令列を眺めればなんとなくわかってきますが、式展開は`#{}`の中を計算して`to_s`し、それを`concatstrings`命令で連結しています。

<img width="400" alt="concatstrings" src="https://qiita-image-store.s3.amazonaws.com/0/43208/c45108fb-30c6-473f-a0c7-a9f33ad2ba7e.png">

Rubyで文字列を`+`でつなぐより式展開を使ったほうが良いのは、式展開だと`+`メソッドを呼び出さずにRubyVMの命令レベルで連結処理が行われているから速い、ってことみたいですね。

では実装していきましょう。

## tostring
`tostring`命令には引数はなく、スタックの値を1つpopしてそれを文字列に変換し、結果をスタックにpushします。

```rb:lib/saira/virtual_machine.rb
case opecode
when :tostring
  push pop.to_s
end
```

単純ですね。

## concatstrings
`concatstrings`命令は連結する文字列の数を引数としてとります。その数だけpopして連結し、結果をスタックにpushします。

```rb:lib/saira/virtual_machine.rb
case opecode
when :concatstrings
  push Array.new(operand[0]) { pop }.reverse.join
end
```

これで`test/interpolation.rb`を実行するとこうなります。

```bash
$ ./boot test/interpolation.rb
==== putobject(1)
======== Stack: [nil, nil] | [1]
==== setlocal(2, 0)
======== Stack: [1, nil] | []
==== putself()
======== Stack: [1, nil] | [main]
==== getlocal(2, 0)
======== Stack: [1, nil] | [main, 1]
==== tostring()
======== Stack: [1, nil] | [main, "1"]
==== putobject(" + 2 = ")
======== Stack: [1, nil] | [main, "1", " + 2 = "]
==== getlocal(2, 0)
======== Stack: [1, nil] | [main, "1", " + 2 = ", 1]
==== putobject(2)
======== Stack: [1, nil] | [main, "1", " + 2 = ", 1, 2]
==== send({:mid=>:+, :flag=>16, :orig_argc=>1}, false, nil)
======== Stack: [1, nil] | [main, "1", " + 2 = ", 3]
==== tostring()
======== Stack: [1, nil] | [main, "1", " + 2 = ", "3"]
==== concatstrings(3)
======== Stack: [1, nil] | [main, "1 + 2 = 3"]
==== send({:mid=>:puts, :flag=>20, :orig_argc=>1}, false, nil)
1 + 2 = 3
======== Stack: [1, nil] | [nil]
==== leave()
======== Stack: [1, nil] | [nil]
```

ちゃんと結果が出力されてますね！！ :heart_eyes: 

以上でSairaVMの実装は終了です！！:tada::sparkles:
長かった。。。

ここまでのコードは[interpolationブランチ](https://github.com/nownabe/saira/tree/interpolation)にあります。

# RubyVMの調べ方
もっといい方法があるかもしれませんが、私はこんな感じで調べてました。

調べたいRubyプログラムを用意して、

* disasmした結果を眺める
* [insns.def](https://github.com/ruby/ruby/blob/v2_3_3/insns.def)を読む
* Rubyのソースを読む
* スタックとコントロールフレームを確認しながらRubyVMの命令単位で実行する
    * http://qiita.com/nownabe/items/b18a7d4a3fd4f1543f1d

# 参考にしたもの
* [ruby/ruby](https://github.com/ruby/ruby)
    * Rubyのソースコードです
* [insns.def](https://github.com/ruby/ruby/blob/v2_3_3/insns.def)
    * これもRubyのソースコードで、RubyVMの各命令の定義ファイルです
* [YARVアーキテクチャ](http://www.atdot.net/yarv/yarvarch.ja.html)
    * YARVの公式？ドキュメント。今のRubyVMとは異なる点も多いですが、とても参考になりました
* [Rubyist Magazine - YARV Maniacs](http://magazine.rubyist.net/?0006-YarvManiacs)
    * 笹田さんによるYARVの連載です

# おわりに
実際のRubyVMはこれよりもかなり複雑なことをしていますが[^6]、今回はRubyVMのバイトコード実行という部分にフォーカスを当ててみました。
Rubyの機能を完全再現するには程遠いですが、なんとなくVMがどう動いているのかを感じていただけたのであれば幸いです :sparkles:

これだけでもいろいろ実行できると思うので、いろんなプログラムを実行してみて足りない命令があったら追加してみてください。

記事の内容ですが、私はRubyのコミッターでもなんでもないのでもし何か間違ってたら申し訳ありません :bow:

# 所感
アドベントカレンダーのネタとして調べ始めたんですが、とても良い勉強になりました :grin: (おかげでめっちゃ長くなったけど)
いつかRailsを動かせるようなVMを作りたいですね…:joy:

[^6]: 私も全然理解できてませんが :sweat_smile: