Inside yarv2llvm (その4)

型推論の続きです。RubyType.resolveはRubyTypeのクラスメソッドですべてのRubyTypeのインスタンスの型推論を行います。RubyTypeクラスには@@type_tableというクラス変数があり、それにすべてのRubyTypeのインスタンスが入っています。RubyTypeは@@type_tableから1つづつインスタンスを取り出し、各インスタンスに対して次のような処理を行います。手始めにすべてのインスタンスの@@resolveedをfalseにします。

  1. インスタンス(src)の@resolveedをチェックします。これがtrueなら何もしません。
  2. srcの@same_typeの要素に対して次の処理を行います。@same_typeは前回説明したとおり、同じ型であるはずのRubyTypeのインスタンスが入っています。@same_typeの各要素をdstとします
    • dstの@typeがnilだった場合
      • dstの@typeをsrcの@typeにします
      • dstの@typeがnilでは無くなったら、@resolveedをtrueにします。
    • dstの@typeがnilじゃ無い場合
      • dstの@typeとsrcの@typeを比べて同じなら何もしなくて、違うなら型エラーなのでエラーにします。*1
      • @resolveedをtrueにします。

イメージとしては@typeが確定していたら@same_typeの中にあるRubyTypeオブジェクトの中でまだ確定していないオブジェクトを同じ@typeに設定するという感じです。

実際には型が矛盾した場合(型エラー)や継承関係の処理が入っているのでかなり複雑になっています。resolveメソッドはlib/type.rbに定義されていますが、説明と必ずしも一致しませんので注意してください。

型推論の例を示します。おなじみのフィボナッチ級数です。

def fib(n)
  if n < 2 then
    1
  else
    fib(n - 1) + fib(n - 2)
  end
end

p fib(10)

yarv2llvmに--func-signatureオプションをつけると、型推論の結果を示してくれます。

#fib :(Int32Ty (Fixnum)) -> Int32Ty (Fixnum)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
n : Int32Ty (Fixnum) 
---
# :(VALUE (Object)) -> VALUE (Object)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
---
89

下の# :(VALUE (Object)) -> VALUE (Object)は、def fibの外側のトップレベルです。これも１つの関数としてコンパイルされます。

次にfibのFloat版を見てみます。

def fib(n)
  if n < 2.0 then
    1.0
  else
    fib(n - 1.0) + fib(n - 2.0)
  end
end

p fib(10.0)

ちゃんとFLoatに推論されます。

ruby19 yarv2llvm.rb --func-signature fibf.rb 
#fib :(DoubleTy (Float)) -> DoubleTy (Float)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
n : DoubleTy (Float) 
---
# :(VALUE (Object)) -> VALUE (Object)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
---
89.0

さらに、fibの戻り値の型だけFloatにしてもうまく行きます。

def fib(n)
  if n < 2 then
    1.0
  else
    fib(n - 1) + fib(n - 2)
  end
end

p fib(10)

ruby19 yarv2llvm.rb --func-signature fib.rb 
#fib :(Int32Ty (Fixnum)) -> DoubleTy (Float)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
n : Int32Ty (Fixnum) 
---
# :(VALUE (Object)) -> VALUE (Object)
-- local variable --
Parent frame : P_CHAR () 
Pointer to block : VALUE () 
self : VALUE (Object) 
Exception Status : Int32Ty () 
---
89.0

次はどうしよう？ 多分、イテレータを取り上げようかと思います。

つづく、、、かな？

*1:これで済めばうれしいのですが、Rubyではこうなる場合がしょっちゅうあります。エラーにしてしまうと動かないプログラムもあるので実際にはもうちょっと粘ることができます。オプションでエラーにするか粘るか設定できます。