はじめに

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

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

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ではなくコンピュータが直接実行します。

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

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

Intel CPUのマシン語

C言語のHello, worldをコンパイルしたものです¹。左端の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

RubyVMのマシン語

RubyのHello, worldをコンパイルしたものです¹。先程と同じように、putselfやsendなどのRubyVM用の命令とその引数でプログラムが構成されていることがわかります。なんとなく、Rubyな感じがプンプンしますね

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は実行時に次の図のような流れで実行されています。

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

目標

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

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

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

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

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

準備

適当なディレクトリを作ってください。その中で実装していきます。
本記事で使うコードはすべてnownabe/sairaにあります。

逆アセンブラ

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

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

disasm

#!/usr/bin/env ruby

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

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

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

$ chmod +x disasm

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

$ ./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は次のようにします。

Saira::VirtualMachine.new(iseq).run

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

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

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

実行権限をつけます。

$ chmod +x boot

さて、ついでにSairaVMの雛形を作ってしまいます。次のようなlib/saira/virtual_machine.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の中身はまだ何もないので、とりあえずバイトコードを出力するようにしてみました。
試してみましょう。

$ ./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ブランチにあります。

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

メソッド呼び出し

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

具体的には次のプログラムを実行できるようにします。このプログラムはtest/hello.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を使っていきます。

>> 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]]]

それぞれの要素についてはドキュメントを参照してください。重要になるのは最後の要素で、バイトコードの配列になっています。

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

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を実行してみると、命令の中身はありませんが命令実行サイクルは回ってることがわかります。

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

スタック

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

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

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

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

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の初期化部分の変更だけ見てみましょう。

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で初期化しています。³

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

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を実行するとこのような出力が得られます。

$ ./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する命令です。実装はこのようになります。⁴

lib/saira/virtual_machine.rb

case opecode
when :putstring
  push operand[0]
end

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

$ ./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オブジェクトとして得られます。

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

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

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

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

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

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

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メソッドを使ってメソッドを実行しています。

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

$ ./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!」が出力されました！

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

leave

0007 leave

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

case opecode
when :leave:
end

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

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

ここまでのコードはmethod_callブランチにあります。

おまけ1

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

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

lib/saira/virtual_machine.rb

case opecode
when :putstring, :putobject, :duparray
  push operand[0]
end

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

test/omake1.rb

puts 1 + 2 + 3
p [1, 2, 3]

./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]が出力されてますね
debug情報がうるさい場合は次のように実行してください。

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

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

lib/saira/virtual_machine.rb

case opecode
when :pop
  pop
end

ここまでのコードはomake1ブランチにあります。

ローカル変数

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

test/locals.rb

a = 1
puts a

b = 2
puts b

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

["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要素の

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

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

ローカル変数の仕組み

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

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

例えば先程の例

test/locals.rb

a = 1
puts a

b = 2
puts b

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

ここまでわかったところで実装に入ります。⁵

ローカル変数領域の確保

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

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メソッドの末尾で呼び出すようにします。

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命令を実装します。

a = 1

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

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

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

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

lib/saira/virtual_machine.rb

case opecode
when :setlocal
  stack[ep - operand[0]] = pop
end

getlocal

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

lib/saira/virtual_machine.rb

case opecode
when :getlocal
  push stack[ep - operand[0]]
end

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

$ ./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ブランチにあります。

おまけ2

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

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

test/omake2.rb

a = 1
b = String.new("second")
p [a, b]

putnil

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

lib/saira/virtual_machine.rb

case opecode
when :putnil
  push nil
end

newarray

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

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

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する命令です。

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

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からとってくるようにします。

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が実行できるようになってます。実行してみましょう。

$ ./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"]]

実行できてますね！！

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

ここまでのコードはomake2ブランチにあります。

式展開

最後はおなじみの式展開です。具体的には次のようなプログラムが実行できるようになります。このプログラムはtest/interpolation.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命令で連結しています。

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

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

tostring

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

lib/saira/virtual_machine.rb

case opecode
when :tostring
  push pop.to_s
end

単純ですね。

concatstrings

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

lib/saira/virtual_machine.rb

case opecode
when :concatstrings
  push Array.new(operand[0]) { pop }.reverse.join
end

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

$ ./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]

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

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

ここまでのコードはinterpolationブランチにあります。

RubyVMの調べ方

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

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

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

参考にしたもの

ruby/ruby
- Rubyのソースコードです
insns.def
- これもRubyのソースコードで、RubyVMの各命令の定義ファイルです
YARVアーキテクチャ
- YARVの公式？ドキュメント。今のRubyVMとは異なる点も多いですが、とても参考になりました
Rubyist Magazine - YARV Maniacs
- 笹田さんによるYARVの連載です

おわりに

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

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

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

所感

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

正確にはコンパイルして、逆アセンブルしたものです。 ↩
サンマだそうです ↩
mainの定義は、RubyのInit_top_selfという関数にあります。https://github.com/ruby/ruby/blob/v2_3_3/vm.c#L3017 ↩
本家ではコピーします。 ↩
SairaVMではスコープもブロックもないのでローカル変数群をハッシュで作ったりしてもいいのですが、今回はスタックを使ってそれっぽく実装します。 ↩
私も全然理解できてませんが ↩

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

はじめに

注意点

対象読者

まえおき

VMとは

Intel CPUのマシン語

RubyVMのマシン語

Ruby実行の流れ

目標

準備

逆アセンブラ

bootstrap

メソッド呼び出し

InstructionSequence

命令実行サイクル

スタック

putself

putstring

send

leave

おまけ1

ローカル変数

ローカル変数の仕組み

ローカル変数領域の確保

setlocal

getlocal

おまけ2

putnil

newarray

getconstant

式展開

tostring

concatstrings

RubyVMの調べ方

参考にしたもの

おわりに

所感