YARVソースコード勉強会 (14)
お久しぶりです。週一の勉強会だったはずなのにお久しぶりです。
[YARV] insnhelper.h
insns.defはYARVの命令の実装なので、VMの内部状態をいろいろと操作します。VMは前々回見たようなデータ構造で表現されてるわけですが、これをもう少し抽象化して、簡潔にアクセスするためのマクロが insnhelper.h というファイルに用意されていました。
#define REG_CFP (reg_cfp) #define REG_PC (REG_CFP->pc) #define REG_SP (REG_CFP->sp) #define REG_LFP (REG_CFP->lfp) #define REG_DFP (REG_CFP->dfp)制御フレーム上の重要なアドレスを指す変数達。
#define GET_SP() (USAGE_ANALYSIS_REGISTER_HELPER(1, 0, REG_SP)) #define SET_SP(x) (REG_SP = (USAGE_ANALYSIS_REGISTER_HELPER(1, 1, (x)))) #define GET_LFP() (USAGE_ANALYSIS_REGISTER_HELPER(3, 0, REG_LFP)) #define SET_LFP(x) (REG_LFP = (USAGE_ANALYSIS_REGISTER_HELPER(3, 1, (x)))) #define GET_DFP() (USAGE_ANALYSIS_REGISTER_HELPER(4, 0, REG_DFP)) #define SET_DFP(x) (REG_DFP = (USAGE_ANALYSIS_REGISTER_HELPER(4, 1, (x))))それらへのsetter/getterマクロ。USAGE_ANALYSIS_REGISTER_HELPERマクロは、YARVではオプションによってどのレジスタがどのくらい使われたかなどの統計を取れるようになっているので、その統計作業用マクロです。値としては単にマクロの第3引数の値になります。
#define GET_PC() (USAGE_ANALYSIS_REGISTER_HELPER(0, 0, REG_PC)) #define SET_PC(x) (REG_PC = (USAGE_ANALYSIS_REGISTER_HELPER(0, 1, x))) #define JUMP(dst) (REG_PC += (dst))PCの操作。などなど。他いろいろとマクロが定義されています。
insns.def
insns.defでの命令定義はグループ別にまとまっていて、上から順に
●変数の操作 (getlocal, ...)
●値の操作 (putnil, ...)
●スタック操作 (pop, dup, ...)
●メソッドや別名定義関係 (definemethod, alias, ...)
●クラス/モジュール定義 (defineclass, ...)
●メソッド/イテレータ関係 (send, invokeblock, ...)
●例外関係 (throw, ...)
●ジャンプ (jump, branchif, ...)
●最適化命令 (opt_plus, opt_mult, ...)
こんな感じです。
1個1個精読した結果をここに書いていこうかとも思ったのですが、どの命令もとてもわかりやすく書かれているので、書き始めてみたらひたすらコードの引用を羅列して説明終わり、になってしまいました。それではあんまり意味ないので省略ということにします。
おまけ: Scheme on YARV
これで今日のYARV勉強会はおしまいです。
って、これではやけに短くなってしまったので、おまけとして、るびま で触れられていた
本当は、今回何か簡単な言語のコンパイラを作ろうと思っていたのですが、間に合いませんでした。誰か Scheme あたりで挑戦してみませんか。かなり簡単だと思いますよ。
これをやってみようと思います。
yasm.rb
記事で紹介されているyasmモジュールがRubyのtrunkに見つからなかったので、旧YARVのレポジトリ
から拾ってきて適当に修正して使っています。変えたのは、YARVの仮想マシンオブジェクトを表すクラス名と
- module YARVCore + class VM - YARVCore:: + VM::
メソッド名としてSymbolを渡すと怒られるみたいだったのでStringにしたところと
def initialize type, name, filename, args, vars, lopt, parent @type = type - @name = name + @name = name.to_s @filename = filename
関数形式のメソッド呼び出しを表すフラグが1<<2から1<<3になっているようなのでその反映
def call id, argc, block = nil - @body << [:send, id, argc, block, 0x04, nil] + @body << [:send, id, argc, block, 0x08, nil] end
の３カ所です。
目標
SchemeというかLispっぽいコードを文字列で渡したら、それを評価して結果を返すメソッドを作るのを目標とします。もちろん中ではインタープリター形式ではなくて、YARVのマシン語にコンパイルして実行しますよ。
p scheme("(+ (* 2 3) 4)") # ==>10こういう風に動けばいいな、と。 さて、ちゃんとしたものを作るのは大変そうなので、ちゃんとしてないものを作りましょう。えい。
require 'yasm' def scheme(text) # とっても手抜きなS式パーザ # "(+ (* 2 3) 4)" ==> [:+, [:*, 2, 3], 4] s = eval text.gsub( /(\()|(\))|(\d+)|([^()\s]+)/ ) { case when $1 then "[" when $2 then $'[/\S/] ? "]," : "]" when $3 then "#$3," else ":#$4," end } # コンパイル iseq = YASM.toplevel { scm_compile s leave } # 実行 iseq.eval endまずSchemeのプログラムをとても適当に構文解析︵？︶して、再帰的な配列とSymbolの形に変換します。それを、scm_compileメソッドに渡してYARVのマシン語にコンパイル。で、実行。scm_compile関数はこれから書きます。
scm_compile : 四則演算
面倒なのでYASM::SimpleDataBuilderのメソッドにしちゃいました。とりあえず数字と四則演算だけの場合を考えよう。
class YASM::SimpleDataBuilder def scm_compile(s) caseswhen Array op,*arg = s caseopwhen :+ scm_compile arg[0] arg[1..-1].each{|a| scm_compile a; send :+,1} when :- scm_compile arg[0] arg[1..-1].each{|a| scm_compile a; send :-,1} when :* scm_compile arg[0] arg[1..-1].each{|a| scm_compile a; send :*,1} when :/ scm_compile arg[0] arg[1..-1].each{|a| scm_compile a; send :/,1} end else putobject s end end endsが配列の場合は、たとえば (+ 1 2 3 4) みたいなS式なので、
putobject 1 putobject 2 send :+, 1 putobject 3 send :+, 1 putobject 4 send :+, 1という命令列にコンパイルしたいのです、というコードになっています。sが配列でない場合は、ただの数値と仮定してしまって、そのままputobjectしています。ええと、これだけで
p scheme("(+ (* 2 3) 4)") # ==>10これは動くようになってしまいました。簡単だ！
scm_compile : 関数定義
次は、関数を定義できるようにしてみます。こんな構文で
(define (norm x y) (+ (* x x) (* y y)))normという名前の関数を定義します。ここまでの勉強会で読んだ内容を思い返してみると、YARVで新しく関数︵メソッド︶を定義するには、命令列オブジェクトを作成してから、それを引数にdefinemethod命令を実行すればいいのでした。そんな風にコンパイルします。
when :define mname, *mparam = arg[0] putnil definemethod mname, YASM.method(mname, mparam) { scm_compile arg[1] leave } putnil一個目のputnilは、トップレベルオブジェクトのメソッドとして定義する指定です。二個目のputnilは、とりあえずdefineの式の値はnilとするということにして、nilをスタックに置いているものです。 あと、式の中で引数を参照できるようにしないといけません。S式がシンボルだった場合は、その名前のローカル変数を参照するということにします。
caseswhen Array ... when Symbol getlocal s else ... endこれで関数定義ができました。Rubyからも簡単に呼び出せます。
scheme <<EOS (define (norm x y) (+ (* x x) (* y y))) EOS p norm(3,4) # ==> 25
scm_compile : 関数呼び出し
って、まだ、Schemeの中から関数を呼び出せるようになってませんでした。さて。
when :+ ... when :- ... when :* ... when :/ ... when :define ... else putnil arg.each{|a| scm_compile a} call op, arg.size配列の先頭要素が特別な値でなかったら、全部その名前の関数呼び出しと見なすことにします。今回はselfはnilで、引数を全部スタックにおいて、yasmのシンタックスシュガーであるcall疑似命令で関数を呼び出します。
p scheme("(/ (norm 5 12) 13)") # ==>13できました。
def cube(x) x * x * x end p scheme("(cube 11)") # ==> 1331Rubyの関数をSchemeから呼び出したりもできました。
scm_compile: 条件分岐
(if 条件 then部 else部)
条件分岐がないとプログラミング言語っぽくないですよね。というわけでif文やってみました。Rubyのif文をコンパイルするのと何もかわりません。
when :if scm_compile arg[0] branchunless :else_part scm_compile arg[1] jump :end _ :else_part scm_compile arg[2] _ :endこれだけです。これだけだと四則演算しかないので条件判定とかができませんので、比較演算も足しておきます。
when :== scm_compile arg[0]; scm_compile arg[1]; send :==, 1 when :< scm_compile arg[0]; scm_compile arg[1]; send :<, 1 when :> scm_compile arg[0]; scm_compile arg[1]; send :>, 1 when :<= scm_compile arg[0]; scm_compile arg[1]; send :<=, 1 when :>= scm_compile arg[0]; scm_compile arg[1]; send :>=, 1こんな感じで。これで、
scheme <<EOS (define (fib x) (if (<= x 1) 1 (+ (fib (- x 2)) (fib (- x 1))))) EOS p scheme("(fib 10)") # ==>89フィボナッチできました。
scheme <<EOS (define (facs x) (if (== x 0) 1 (* x (facr (- x 1))))) EOS def facr(x) if x == 0 then 1 else x * facs(x-1) end end p facs(10), facr(10) # 3628800 \n 3628800RubyとSchemeで相互再帰する階乗計算！
scm_compile: 速度比較
あまりにもサクサクできてしまったので、ほんとにちゃんとコンパイルされているか心配になってきました。Rubyで書いたものと比較ベンチマークしてみましょう。
def fibr(x) if x <= 1 1 else fibr(x-2) + fibr(x-1) end end require 'benchmark' 3.times { print "Scheme:", Benchmark.measure { fib(36) } print "Ruby: ", Benchmark.measure { fibr(36) } }とりゃ。
Scheme: 8.942000 0.000000 8.942000 ( 8.973000) Ruby: 8.853000 0.000000 8.853000 ( 8.863000) Scheme: 8.863000 0.000000 8.863000 ( 8.863000) Ruby: 8.873000 0.000000 8.873000 ( 8.872000) Scheme: 8.852000 0.000000 8.852000 ( 8.853000) Ruby: 8.863000 0.000000 8.863000 ( 8.863000)Rubyネイティブのものとほぼ同じパフォーマンスが出ていることがわかります。
まとめ
途中から全然YARVソースコード勉強会じゃなくなってしまいましたが、今日はここまでです。
ささださんが書かれていたとおり、ほんとに簡単にできちゃうんですね。これはかなり楽しかったです。もう少しマジメに作ってみるともっと楽しいかもしれません。
今回作ったソースコードは
●yasm.rb (yasmdata.rb は YARV をビルドしたときに生成されたもの =~ s/module YARVCore/class VM/)
●scheme.rb
にまとめておきます。
※11/17 http://d.hatena.ne.jp/shinichiro_h/20071113#1194884481 shinichiro.hさんの復元バージョンが！ありがたやありがたや。
※10/23 間違って消してしまいました。しかも手元に残っていない…困った…orz
※3/23 12:53 コメントで指摘いただいた点を修正したバージョンに差し替えました
