YARVのバイトコードをRubyに変換する話

RubyのVMとして知られているYARVのバイトコードをRubyに変換するプログラムを昔書いたことがあるのでその話を書きます。YARVについてはYARV Maniacsを見てもらうのが一番だと思います。

#　なぜそんなものを?
昔、YARV2LLVMなるものを作っていました。YarvのバイトコードをLLVMに変換するというプログラムです。効率を上げるために型推論をやったりとかしているのですが、詳細は今回の話とは関係ないので詳しくは、Ruby会議で発表した資料でも見てください。
YARV2LLVMではRubyが実行時に提供しているメタプログラミングの機能をコンパイル時に提供するためにマクロ機能を実装しました。マクロはたとえば次のように定義します。

YARV2LLVM::define_macro :attr_reader do |arg|
  arg.each do |argele|
    name = argele[0].type.constant
    `def #{name}; @#{name}; end`
  end
end

define_macroは引数で渡されたシンボルの名前のマクロを定義します。シンボルがプログラム中に現れたら「コンパイル時」にブロックが実行されてバッククオート(`)で囲まれた文字列をプログラムの一部としてシンボルの場所に挿入します¹。バッククオート内では#{}による変数やプログラム片の埋め込みが出来ます。

さて、このような機能を実現しようとすると困ることがあります。define_macroを実行する段階では

  arg.each do |argele|
    name = argele[0].type.constant
    `def #{name}; @#{name}; end`
  end

の実行すべきブロックはこのようなプログラム片としてではなく、YARVのバイトコードとしてしか得ることができません²。
この場合つぎの2つの解決策が考えられます。

・　YARVを解釈するインタプリタを作成する
・　YARVをRubyに変換してそれをevalで実行する

そして、YARV2LLVMでは後者、つまりYARVをRubyに変換する方式を選択しました。

YARVのバイトコードをRubyに変換する

YARVのバイトコードをRubyに変換するのは次のような問題があります。
　・　YARVはスタックマシンなのだがRubyはスタックマシンではない。どうやって逆ポーランドを普通の計算式に直すのか。RubyがForthだったらよかったのですが。
　・　YARVはジャンプ命令を多用するが、Rubyにはいまどきの言語らしくgotoがない。さてジャンプ命令をどうやって変換するか

次にこれらをどうやって実装したのか見てみましょう。

スタックマシンをどうするのか

YARVはスタックマシンでRubyの命令列の並び方とは異なります。そのため、YARVの命令列をそのままの順番でRubyの命令列として生成すると正しいRubyのプログラムにはなりません。
変換においてスタックを用意します。スタックはオブジェクトだけではなく変数や命令列も入れられます。直接Rubyの命令列を生成するのではなく、スタックを利用して適切なタイミングで命令列を生成できるようにしています。
命令毎にこんな感じでスタックを使用します。

• オブジェクトをスタックにプッシュする命令(putobject, putnil, getlocalなど)

単にスタックにそのオブジェクトを入れます。getlocalなど変数参照の場合は変数名をプッシュします³。

• スタックからデータをポップして、何かして、再び結果をスタックにプッシュする命令(sendなど)

スタックから値をポップして、Rubyの命令列を組み立てて、再びその命令列をプッシュします。

• スタックからデータをポップして、何もプッシュしない命令(setlocal, popなど)

スタックからデータをポップしてRubyの命令列を組み立てて、それを生成コードとして出力します。

こんな感じのことを繰り返してRubyの命令列を生成します。

goto

FSM、これで分かった人は以下の説明は読まなくていいです。

結局の所でっかい無限ループとcase文の組み合わせでジャンプ(goto)を実装しています。こんな感じです。

__state = nil  #初期状態
while true
case __state
when nil
  なんか処理を行う
  __state = :label_1
  next
when :label_1
　　なんか処理を行う
   __state　= :label_2

when :label_2
   以下略

プログラムを見ればわかるとおり、__stateが現在の状態を示していて、ジャンプしたいときはその場所のラベルを代入します。YARVではジャンプ先にはラベルを付けてくれているのでそのラベルをそのまま使っています。

なお、こういうコードのパターンはVerilogなどハードウエア記述言語では頻出します。それをFSM(有限状態機械)と呼ばれています⁴。

#　プログラム変換例

a = 10
while a > 1 do 
  a = Math.sin(2.0)
  p a
end
[1, 2, 3].each do |n|
    p n
end
  `#{a} ,a`

こんな感じのコードをYARVにコンパイルして、それをRubyに変換するとこうなります。

__state = nil
while true
  case __state
  when nil
    
    a = 10
    __state = :label_36
    next
    __state = :label_12
  when :label_12
    
    nil
    __state = :label_36
    next
    __state = :label_15
  when :label_15
    
    a = Math.sin(2.0)
    
    p(a)
    __state = :label_36
  when :label_36
    if (a.>(1) ) then
      __state = :label_15
      next
    end
    __state = :label_46
  when :label_46
    
    nil
    __state = :label_49
  when :label_49
    __state = :label_53
  when :label_53
    
    [1, 2, 3].each do    |n|
      __state = nil
      while true
        case __state
        when nil
          __state = :label_2
        when :label_2
          __state = :label_10
        when :label_10
          
          break (p(a) )
          break
        end
      end
    end
    
    __lOHash = {:gEN0 => a,}
    __lOStr = " gEN0  ,a"
    if a.is_a?(Symbol) or a.is_a?(String) then
      __lOStr.gsub!(' gEN0 ', a.to_s)
      __lOHash.delete(:gEN0)
    end
    
    break (compile_for_macro(__lOStr, __lOHash, _sender_env)
    )
    break
  end
end

バッククオート(`)メソッドの部分が複雑になっていますが、これはYARV2LLVMがコンパイル時にコードを追加するのに必要な追加情報を得るためです。

おまけ

これを読んで、YARV2LLVMを使ってRuby(っぽい記法)でマクロを書きたい！っていう人が(計算機イプシロンくらいの確率で)いるかもしれません。そういう奇特な人は、

• LLVM 2.4

• Ruby 1.9.3

• llvmruby

をどこからか調達してください。そうすると、ここにあるプログラムが動くと思います。でも、そんなことせずにRuby(っぽい記法)でマクロを書きたいなら、Crystalを使うことを非常に強くお勧めします。

1. 本来Rubyのバッククオート(`)は`と`で囲まれた文字列をシェルコマンドとして実行してその結果を文字列として返すというメソッド(リテラル)ですが、マクロ定義のときだけオーバーライドしています。Common Lispのバッククオート記法からの連想です。 ↩

2. Rubyの機能を駆使するとこのブロックの定義されているファイル名とファイル上の位置が分かりますので、そこからRubyレベルのプログラム片を得ることは可能です。ただし、Rubyのパーサを再実装する必要があるでしょう。 ↩

3. getlocalなどでは変数フレーム上の位置という数値で変数を区別しています。本物の数値と区別するために数値は駄目ですが、そうでなければスタックでは変数名は変数が区別できれば何でもいいのです。しかし、CRubyのRubyVM::InstructionSequence.compileで得られるiseqの情報にローカル変数名も得られますのでこれを利用して実際にRubyレベルで使われている変数名を使用しています。 ↩

4. コードが複雑になると読みにくくなるので、素直にVerilogにgotoを入れればいいのにって思うのですが。 ↩