Inside yarv2llvm (その3)
今回は型推論の話の簡単なところです。Rubyは素直に型推論できるようにできていないので、yarv2llvmではいろいろad-hocな例外を組み込んでいますが、今回はそれらは一切無視です。素直に型が一意に決まり、決まらないときはエラーで弾く場合を想定しています。
型の管理を行うため、yarv2llvmでは扱うすべてのデータに対して、１つづつRubyTypeクラスのオブジェクトを用意しています。扱うデータとは、例えば変数、リテラル、引数、戻り値などがありますが、それだけではなくブロック、if、whileの値などもそうです。RubyTypeは次のようなインスタンス変数・クラス変数を持っています。
@name データの名前(変数名とかリテラルの値そのものとか)、デバッグ・エラーメッセージ用 @line_no データが定義されたファイル名・行番号、デバッグ・エラーメッセージ用 @type 型オブジェクト @same_type 同じ型のRubyTypeオブジェクト @resolved 後述 @@type_table RubyTypeオブジェクトの配列。RubyTypeオブジェクトは必ずここに登録する
ほかにもインスタンス変数がありますが、説明が非常に面倒で今回の範囲では関係ないので省略します。
型推論で、重要なのは@type, @same_type, @resolvedです。特に型情報を直接RubyTypeに持たず、１段インスタンス変数を咬ましてあるのがミソです。
@typeには型を表現するオブジェクトが入ります。型を表現するオブジェクトは大きく分けてPrimitiveTypeとComplexType(とそのサブクラス)に分けられます。PrimitiveTypeは数や論理値、ポインタなどこれ以上分解できない型、ComplexTypeは配列やハッシュテーブル*1などPrimitiveTypeの集合になっている型です。これらの型を表現するオブジェクトはクラスによって細かい差がありますが、次のようなメソッド、インスタンス変数を持っています。
inspect2 型を判りやすい表現で表示する(デバッグ用) llvm 型のLLVM表現を返す、例えばType::Int32Ty klass 型のRubyの表現を返す、例えばFixnum
それでは具体的に型推論の手順をその２のときと同じように1 + 1を例に説明します。
1+1は、次のようなYARVバイトコードになります。
こんな感じのYARVコードになります。
putobject 1 putobject 1 opt_plus
ここまでは一緒ですが、次に@expstackにpushするデータにコード生成関数だけではなく、RubyTypeオブジェクトもpushします。その２つの情報は配列でまとめます。また、1の型は明らかにFixnumなので型推論するまでも無くRubyTypeオブジェクトの@type変数にFixnumを表現するオブジェクトを入れておきます。
[RubyType.new({:type => PrimitiveType(Fixnum, Type::Int32Ty), :name => 1}),
lambda {|b, context| 1.llvm}]
これで、@expstackをpopしてその結果を[0]で参照すると、型情報が得られます。次にopt_plusの説明をおこう前にRubyType#add_same_typeというメソッドを導入します。これは、引数に１つのRubyTypeオブジェクトを取り、そのオブジェクトがレシーバと同じ型だよということをyarv2llvmに知らせます。実際にやることは@same_type変数に引数をpushするだけです。
opt_plusの場合を考えてみます。
a = b + c
という式を考えると、a, b, cは整数、浮動小数点数、文字列など色々ありますがすべて同じ型になります。メソッドがオーバライドされたときは？、暗黙の型変換は無いの？とか疑問はあるとは思いますが、今回は考えません*2
追記:2009/1/26 そういえば、%で第１パラメータが文字列のときは同じ型にならないです。%については、1パス目に文字列ではないと判るときだけa,b,cが同じ型であるとして、そうでないときは(型が決定できないときは)、１パス目で型についての制約を加えられないで、２パス目で制約を加えるという形になります。まだ、実装していないので詳しくはわかりませんが、多分これで型推論ができなくなることは少ないと思うけど不完全になりそうです。・・・とこんな例外処理がそこらじゅうでなされています。
それではopt_plusの定義を見てみます。ここでadd_same_typeは対称律は成り立たないことに注意が必要です。つまり、a1[0].add_same_type a0[0]はa0[0]がa1[0]と同じ型であることは言っていますが、a1[0]とa0[0]が同じ型であるとはいっていないのです。そのため、双方同じ型であるというためには２つのadd_same_typeがいります。何でこうなっているんだと思われるかもしれないですが、これが必要な場合もあります。
a1 = @expstack.pop a0 = @expstack.pop # plusの２つの引数は同じ型 a1[0].add_same_type a0[0] a0[0].add_same_type a1[0] # rettypeがopt_plusの結果の型 rettype = RubyType({:type => nil}) # rettypeと引数(代表してa0)は同じ型 rettype.add_same_type a0[0] a0[0].add_same_type rettype @expstack.push [rettype, lambda {|b, context| # rettypeの型で分岐 case rettype.type.klass Fixnum, Float: val1 = a1.call(b, context) val0 = a0.call(b, context) # 整数も浮動小数点数もaddでOK b.add(val1, val0) String: 文字列の処理 }]
rettype.typeはnilだったはずなのにcaseでklassメソッドを呼んでいます。こんなのエラーだよと思われるかもしれないですが、ちゃんとrettpye.typeには正しい型が入っています。もちろん、add_same_typeの結果が効いているのですが、実際にはRubyType.resolveメソッドが型推論を行っています。RubyType.resolveは簡単な仕組みなのですが、長くなってきたのでRubyType.resolveの説明は次回にします。ここまで読んでくださってありがとうございます。
つづく
