YARV Maniacs 【第 6 回】 YARV 命令セット (3) メソッドディスパッチ

書いた人：ささだ

はじめに

YARV: Yet Another RubyVM を解説するこの連載。今回は、命令セットの紹介の続きで、Ruby のもっとも重要な概念のひとつであるメソッドディスパッチ (メソッド呼び出し) を行う命令を、Ruby プログラムがどのように YARV 命令列にコンパイルされるか、という例とともに説明します。

メソッドディスパッチは第 4 回 (YARV Maniacs 【第 4 回】 命令セット (1) YARV 命令セットの初歩の初歩) でも簡単に説明しましたが、今回はたっぷり丸ごとメソッドディスパッチです。

その前に - YARV 0.3.3

ところで、先月この連載を休んだので間が空いてしまいましたが、YARV 0.3.3 をリリースしました。おもにバグフィックス版ですが、一部繰り返しのためのブロックをインライン化するなどの最適化機能を追加しました (ただし、デフォルトでは無効になっています)。また、足りなかったいろいろな機能、たとえば define_method に対応しました。

今回のバグフィックスによって、以前のバージョンの YARV では (バグのために) 動かなかった optparse.rb などのライブラリが利用できるようになりました。これによって、optparse.rb を利用していたため出来なかった拡張ライブラリのビルドができるようになりました。0.3.3 ではいくつかの標準の拡張ライブラリも利用できるようになっています。

ぜひこのバージョンを試してみてください (そして、私にバグ報告をください)。

前回紹介した YARV - Compile and Disassemble CGI も 0.3.3 になっています。この記事に書かれている例をお気軽にコンパイルして試してみてください。

RubyConf 2005

去る 10 月に RubyConf 2005 に行ってきたのですが、そこで「YARV Progress Report」と題して YARV について一時間弱話をしてきました。プレゼンは RubyConf2005 Presentation (pdf) に置いてありますが、主に「YARV の目指すもの」、「YARV で新しくサポートされる Ruby の機能」、「YARV の現在の状況」についてしゃべりました。全体的なレポートはRuby Conference 2005 レポートに載せたのであわせてご覧ください。

メソッド呼び出し

メソッド呼び出しのための YARV 命令を説明します。

とりあえず試してみる

具体的なものを見ないとなかなかわからないと思うので、とりあえず単純なメソッド呼び出しを含む Ruby プログラムをコンパイルしてみましょう。

[1, 2].length

レシーバの配列 [1, 2] に対して、その長さを求めるメソッド Array#length を呼び出してみます。これを YARV 命令列で示すと次のようになります。

0000 duparray         [1, 2]
0002 send             :length, 0, nil, 0, <ic>

duparray は前回解説した、配列リテラルを生成する命令でした。今回大事なのは、0002 番地にある実際にメソッドディスパッチを実行する send 命令です。

send 命令

Ruby で一番大事なメソッド呼び出しを実現する send 命令について解説します。

Ruby のメソッド呼び出しがすること

Ruby のメソッド呼び出しは、使う側はとてもお手軽に使えますが、実際には非常に複雑なことを行っています。厳密にはメソッドは以下のような手続きを経て呼び出されます。仮に recv.method(arg) というメソッド呼び出しを行うと考えましょう。

1. レシーバ、引数を特定する。この例ではレシーバは recv、引数は 1 引数で arg。
2. もし引数を展開 (m(*ary) のように配列を引数として展開) する必要があれば展開する。この例では展開はしない。
3. もし Proc オブジェクトをブロックとして渡す場合 (m(&pr) のようなメソッド呼び出し)、それをブロックとして通常の引数としては扱わない。
4. レシーバのクラス (これを klass とする。klass = recv.class) からメソッドの定義を検索する。
5. もし klass で method メソッドが定義されていなければ、klass の親クラスで定義されていないかを検索する。これを method メソッドの定義が見つかるまで繰り返す。 1. もし見つからなかったら method_missing メソッドを呼び出す。
6. メソッドの定義を見て、visibility (private とか protected) などのチェックを行う。
7. private なのにレシーバ指定している、などの場合は NoMethodError 例外を発生する。
8. メソッドの定義を見て、引数の数をチェックする。
9. 引数の数が違ったら ArgumentError 例外を発生する。
10. もしオプショナル引数 (m(a=1) のように指定するやつ) がある場合、そちらを実行する。
11. メソッドフレームを構築する。
12. メソッドを実行する。

なるべく細かく書いたつもりですが、大体こんな感じです。意外にいろいろしていると思いませんか？　これでも少し端折っています。YARV の send 命令は、大体上記のような処理をしています。

余談ですが、Ruby ではメソッド呼び出しが大量に行われます。この処理をいかに軽量化するかが高速化の鍵になります。YARV でも、この処理をいかに高速に行うか、試行錯誤を重ねました。いや、重ねています。

send の命令オペランド

では、send 命令を実際にどうやって使うか見ていきましょう。まずは命令オペランドの詳細です。先ほどの例を利用して説明します。

0002 send             :length, 0, nil, 0, <ic>

1 番目の命令オペランド :length は見てすぐわかりますね。どのメソッドを呼び出すかを示すシグネチャです。この例では length メソッドを呼び出したいのですから、:length というシグネチャになっています。シグネチャは Symbol だということがわかりやすいように :length と表記しています。

2 番目の命令オペランド 0 は、引数の数を表しています。[1, 2].length は引数無し (引数 0 個) で呼び出されているので 0 になっています。

3 番目の命令オペランドは、ブロック付きメソッド呼び出し (m(){ … } のようなメソッド呼び出し) のために利用します。今回はブロックは無いので nil になっています。

4 番目の命令オペランドはフラグになっています。このフラグは次のようなメソッド呼び出しであることを表しています。

• 最後の引数は配列として展開するか？ (r.m(…, *args))
• 最後の引数はブロックとして扱うか？ (r.m(…, &proc_object))
• レシーバ無しの (関数っぽい) メソッド呼び出しであるか？(m())
• レシーバ無しで、引数指定がないか？ (m のこと。変数のように書くメソッド呼び出し)

これらのフラグは一度に複数指定できます (各フラグの bit 和になっています)。

5 番目の <ic> はインラインキャッシュを示しており、インラインメソッドキャッシュで利用する領域を表します。インラインメソッドキャッシュについては後述します。

send 命令のオペランドは 5 つと多いのですが、たいていのメソッド呼び出しで重要なのは 1 番目のメソッドシグネチャ、2 番目の引数の数です。

レシーバと引数

メソッド呼び出しではレシーバと引数が必要になりますが、これらの値はあらかじめ評価しておくことになります。

send メソッドは、スタックにすでにレシーバと引数が積んであることを前提にしています。まず、レシーバを積んで、その上に引数が積んであると想定します。

先ほどの例、[1, 2].length というプログラムをコンパイルすると次のようになりました。このメソッド呼び出しでは、レシーバは [1, 2] で、引数はありません。

0000 duparray         [1, 2]
                      # スタックの状況: [1, 2]
0002 send             :length, 0, nil, 0, <ic>
                      # スタックの状況: 2
                      # ([1, 2].length は 2 を返すから)

レシーバとして、[1, 2] をスタックに積んでいます。この例では引数の数が 0 なので、引数は評価していません。メソッド呼び出しを行ったあと、レシーバの値をスタックから取り除き、代わりにメソッドの返り値をスタックに積みます (この例では 2)。

では、引数の数が 1 個ある例として、[1, 2].index(0) という Ruby プログラムをコンパイルしてみましょう。

0000 duparray         [1, 2] # レシーバ
                      # スタックの状況: [1, 2]
0002 putobject        0      # 引数 1 番目
                      # スタックの状況: [1, 2] 0
0004 send             :index, 1, nil, 0, <ic>
                      # スタックの状況: 1
                      # ([1, 2].index(0) は 1 を返すから)

レシーバとして [1, 2] をスタックに積んだあと、第 1 引数である 0 をスタックに積んでいます。次の send 命令でそれらの値を利用してメソッド呼び出しを行います。引数の値とレシーバの値はメソッド呼出しの後スタックから取り除かれ、代わりにメソッドの返り値 (この場合は 1) がスタックに積まれます。

引数の数が 1 よりも大きい場合も引数の数の値をスタックに積むだけです。

関数っぽいメソッド呼び出し

Ruby ではレシーバを省略して、 func() のようにメソッド呼び出しをすることができます。このとき、レシーバは暗黙に self が渡されます。

YARV では関数っぽいメソッド呼び出しでも putself 命令によって明示的に self をレシーバとしてスタックに積んでおきます。

では、例として p(“abc”) という、p メソッドを関数っぽくメソッド呼び出しする Ruby プログラムをコンパイルしてみましょう。

0000 putself
0001 putstring        "abc"
0003 send             :p, 1, nil, 4, <ic>

レシーバが putself によって詰まれる self、引数として “abc” を積み、引数の数を 1 つとして p メソッドを呼び出しています。ここで、send 命令の 3 番目の命令オペランド (フラグ) が 4 になっていますが、これが関数っぽいメソッド呼び出しであったということを示すフラグになっています (より正確には、フラグの 3 bit 目が 1 になっていることがそれを示しています)。このフラグは private メソッドの呼び出し制限を実現するために利用します。

演算子っぽいメソッド呼び出し

Ruby では 1+2 のような、足し算などの演算子もすべてメソッド呼び出しとして扱われ、1.+(2) とまったく同じです。YARV でもそのようにコンパイルされます。

実際に 1+2 (つまり、1.+(2)) という Ruby プログラムを YARV 命令列にしてみると次のようになります。

0000 putobject        1
0002 putobject        2
0004 send             :+, 1, nil, 0, <ic>

このように、1 をレシーバ、2 を引数として、1 引数で :+ というメソッドを呼び出すという YARV 命令列になりました。

ただし、YARV の最適化 (OPT_BASIC_OPERATIONS) を有効にすると、いくつかのメソッド呼び出しは特別な命令に置き換えられます。たとえば、この例 1+2 は send 命令ではなく opt_plus という命令に置き換えられるのですが (そして、この最適化は数値計算系のアプリケーションでは速度向上に結構効果がある)、この話はいつかしたいと思います。

引数の展開

Ruby では配列オブジェクトを引数に展開する機能があります。例えば p(*[1, 2, 3]) というプログラムは p(1, 2, 3) というプログラムとまったく同じ意味です。

YARV では send 命令のフラグで、最後の引数を展開することを示します。

p(0, *[1, 2, 3]) というプログラムを YARV 命令列にコンパイルしてみましょう。

0000 putself
0001 putobject        0
0003 duparray         [1, 2, 3]
0005 send             :p, 2, nil, 5, <ic>
0011 end

send 命令では引数の数が 2 個になっており、スタック上にも引数として 0 と [1, 2, 3] というオブジェクトしか詰まれて居ませんが、フラグが 5 になっています。このとき、フラグの 1 ビット目が 1 なので、最後の引数を展開する、というふうに示しています (3 ビット目が 1 なのは、関数っぽいメソッド呼び出しだから)。send 命令は最後の引数を展開し、スタック上には 0, 1, 2, 3 という値を積んで 4 引数で p メソッドを呼ぶ、という処理を行います。

インラインメソッドキャッシュ

先ほど、Ruby のメソッド呼び出しの処理内容を示しましたが、その中でメソッド定義の検索、というものがありました。

• レシーバのクラス (これを klass とする。klass = recv.class) からメソッドの定義を検索する。
  • もし klass で method メソッドが定義されていなければ、klass の親クラスで定義されていないかを検索する。これを method メソッドの定義が見つかるまで繰り返す。

これです。

この検索は、見てのとおり負荷が大きい (最悪、ハッシュの計算を何度もやることになります) ため、現在の Ruby 処理系ではグローバルメソッドキャッシュという最適化をしています。これについての詳細は RHG を読んでいただくとして (第15章 メソッド)、要するに「以前にそのクラス klass で検索したメソッド method の定義は再定義されない限り変わらない」という事実を利用して、キャッシュ表に検索した結果を書き込んでおき、あとでその結果を利用する、というものです。

で、これをもっと高速化したいなぁ、と思って作ったのがインラインメソッドキャッシュです。

前回、定数アクセスを高速化するためにインラインキャッシュを利用しましたが、まったく同様のことをメソッド検索結果にも適用しています。

たとえば、

 num.times{
   recv.method()
 }

という繰り返しを行うプログラムがあった場合、num 回実行される recv.method() で呼び出すメソッドの定義は毎回同じだろう、と推測されます。それならば、毎回ここでメソッド検索を行うのは無駄なので、その send 命令に検索結果をキャッシュしてあげればいいのではないか、と思うのは人間として当然ですね。そこで、これを行うのがインラインメソッドキャッシュ、というわけです。

このインラインメソッドキャッシュはたいていうまくいってます。

これについての詳細な情報 (実装方法とその評価) は私の情報処理大会、全国大会の予稿 (プログラム言語Ruby におけるメソッドキャッシング手法の検討 (PDF)) をご参照ください。

YARV ではグローバルメソッドキャッシュも併用しており、インラインメソッドキャッシュにひっかからなかった場合にはそちらを利用することになります。たとえば、Ruby C API 経由でメソッド呼び出しを行った場合は、グローバルメソッドキャッシュだけを利用することになります。

余談ですが、メソッド定義検索の高速化はオブジェクト指向言語の処理系で研究テーマのひとつとなっており、他にもさまざまな手法が提案されています。

ブロック付メソッド呼び出し

さて、Ruby のメソッド呼び出しの大きな特徴のひとつにブロック付メソッド呼び出しがあります。よく、イテレータとか言われるアレです。

たとえば、

3.times{
   ... # ブロックの内容
 }

というプログラムは、3 回ブロックの内容を繰り返します。

渡したブロックは、その呼ばれたメソッド中で yield を利用することで実行されます。

では、実際に 3.times{} というブロックを YARV 命令列にコンパイルしてみましょう。

== disasm: <ISeq:<main>@../yarv/test.rb>================================
== catch table
| catch type: retry  st: 0000 ed: 0008 sp: 0000 cont: 0000
|------------------------------------------------------------------------
local scope table (size: 1, argc: 0)

0000 putobject        3                                               (   1)
0002 send             :times, 0, block in <main>, 0, <ic>
0008 end
== disasm: <ISeq:block in <main>@../yarv/test.rb>=======================
== catch table
| catch type: redo   st: 0000 ed: 0001 sp: 0000 cont: 0000
| catch type: next   st: 0000 ed: 0001 sp: 0000 cont: 0001
|------------------------------------------------------------------------
0000 putnil
0001 end

これまでの例ではヘッダは省略してましたが、今回はヘッダ付きで全部載せました。

コンパイル結果を見てみると、2 つの命令列が生成されたのがわかるかと思います。これは、トップレベルの命令列の他に、ブロックの処理を示す命令列オブジェクトを作っているからです。つまり、ブロックは別の命令列として生成されます。

send 命令を見てみると、3 個目の命令オペランドに block in <main> というものが指定されていますが、これがブロックとして渡された命令列、ということになります。block in <main> の実体は、<ISeq:block in <main>@../yarv/test.rb> として示されている命令列です。

YARV のブロック付メソッド呼び出しは send 命令の命令オペランドにブロックを指定するだけ、ということがわかって頂けたと思います。

Proc オブジェクトを利用したブロック付きメソッド呼び出し

Ruby では Proc オブジェクトをブロックとして渡すメソッド呼び出しが可能です。たとえば、3.times(&Proc.new{…}) は、3.times{…} とほぼ同じ意味です。

では、3.times(&proc.new{}) というプログラムを YARV 命令列にコンパイルしてみましょう。

== disasm: <ISeq:<main>@../yarv/test.rb>================================
== catch table
| catch type: retry  st: 0002 ed: 0009 sp: 0000 cont: 0002
| catch type: retry  st: 0000 ed: 0015 sp: 0000 cont: 0000
|------------------------------------------------------------------------
local scope table (size: 1, argc: 0)

0000 putobject        3                                               (   1)
0002 putself
0003 send             :proc, 0, block in <main>, 4, <ic>
0009 send             :times, 0, nil, 2, <ic>
0015 end
== disasm: <ISeq:block in <main>@../yarv/test.rb>=======================
== catch table
| catch type: redo   st: 0000 ed: 0001 sp: 0000 cont: 0000
| catch type: next   st: 0000 ed: 0001 sp: 0000 cont: 0001
|------------------------------------------------------------------------
0000 putnil
0001 end

このようなコンパイル結果になりました。ちょっと複雑ですね。細かく見ていきましょう。

0002 putself
0003 send             :proc, 0, block in <main>, 4, <ic>

この部分は proc{} というプログラムをコンパイルした結果で、Proc オブジェクトを作るプログラムです。先ほど紹介したブロック付メソッド呼び出しですね。

では、全体を見てみましょう。

0000 putobject        3
                      # スタックの状態: 3
0002 putself          # proc メソッドのレシーバ
                      # スタックの状態: 3 self
0003 send             :proc, 0, block in <main>, 4, <ic>
                      # スタックの状態: 3 Procオブジェクト
0009 send             :times, 0, nil, 2, <ic>
                      # スタックの状態: 3 (3.times メソッドの返り値)
0015 end

times メソッド呼び出しのための send 命令 (9 番地) の 3 個目の命令オペランド、つまりブロックの指定は nil になっていますが、フラグが 2 (2 bit 目がたっている) なので、最後の引数は Proc オブジェクトであり、これをブロックとして利用する、ということになります。

super() と super

super はオーバーライドしたメソッドから上位のメソッドを呼び出す、という、ある意味メソッドディスパッチの親戚みたいな機能です。また、引数無しで super とだけ指定した場合、呼び出し元のメソッドと同じ引数がわたる、という意味になります¹。

これを実現するために YARV には super という命令があります。命令オペランドは send 命令とほぼ同様ですが、super 命令ではメソッドシグネチャを指定する send 命令の 3 個目の命令オペランドとインラインキャッシュがありません。

では、ちょっと例を見てみましょう。

 def m a, b
   super(1)
   super    # super(a, b) と一緒
 end

super() と super を対比するために、両方使ってみました。メソッドの定義部分はすっ飛ばしています。

# super(1)
0000 putnil             # レシーバはないのでとりあえず nil
0001 putobject        1 # 引数 1 番目
0003 super            1, nil, 0
0007 pop                # send の結果を pop (使わないから)
# super
0008 putnil             # レシーバはないのでとりあえず nil
0009 getlocal         3 # ローカル変数 a の値をとる
0011 getlocal         2 # ローカル変数 b の値をとる
0013 super            2, nil, 0
0017 end

send 命令ではレシーバを積んでいたところで、今度は (putnil 命令によって) nil を積んでいます。super にはレシーバは必要ないのですが、実装の都合上スタックに何か積んでおかないとまずい (send 命令の処理の大部分を流用するため) のでとりあえず nil を積んでいる、というわけです。

super(1) のほうは、send 命令とほぼ同様ですね。

super のほうは、super の引数として仮引数の a と b をスタックに積んでいます。コンパイル時に super が super(a, b) だということがわかるので、そのようにコンパイルされます。引数無し super のための特別な命令はありません。

おわりに

今回は Ruby で一番重要な要素であるメソッド呼び出しを YARV 命令列ではどのように表現されるか、ということを説明しました。

メソッドの呼び出し命令の設計はいろんな選択肢があって、いろいろ試行錯誤したのですが、「作りやすさ」「性能」を考えて今の形に落ち着きました。まぁ、もっといい方法を思いついたら、もしかしたら変わるかもしれないですけど。

しかし、今回の内容ですが、簡単すぎてつまんなかったですかね。説明するのが大変で、なかなか先に進まない、というのが実情なんですが。本当は今回はスタックフレームについての解説からメソッドディスパッチの話に持って行こうと思ったんですが、説明がとても大変で諦めてしまいました (図とか用意してたんだけど)。

さて、次回はメソッドの定義やクラスの定義なんかを行うための命令を説明しようかなぁと思っています。気が変わったら他のことをやるかもしれません。分岐 (if文など) とか、例外処理についても解説したいんですけどね。というか、YARV の実装についての話がなかなか出てこない。これはまずい。

まぁ、お楽しみに。

著者について

ささだこういち。学生。就職活動中。

今月の 24 日は予定通り暇でしょうがありません。まぁいいか。メリークリスマス。

YARV Maniacs 連載一覧

• YARV Maniacs 【第 13 回】 事前コンパイルへの道

• YARV Maniacs 【第 12 回】 インクリメンタル GC の導入

• YARV Maniacs 【第 11 回】 最近の YARV の事情

• YARV Maniacs 【第 10 回】 例外処理（初級編）

• YARV Maniacs 【第 9 回】 特化命令

• YARV Maniacs 【第 8 回】 命令列のシリアライズ

• YARV Maniacs 【第 7 回】 YARV 命令セット (4) 分岐

• YARV Maniacs 【第 6 回】 YARV 命令セット (3) メソッドディスパッチ

• YARV Maniacs 【第 5 回】 命令セット (2) リテラル・変数・定数

• YARV Maniacs 【第 4 回】 命令セット (1) YARV 命令セットの初歩の初歩

• YARV Maniacs 【第 3 回】 命令ディスパッチの高速化

• YARV Maniacs 【第 2 回】 VM ってなんだろう

• YARV Maniacs 【第 1 回】 『Ruby ソースコード完全解説』不完全解説