ytljitの型推論の説明(その1)

　今、ytljitでうまく推論出来ないプログラムがあっていろいろ直しています。うまくいかないプログラムはこんな感じのものです。

  def f
    yield
  end
  f { 1 + 1}
  f { "abc"}

このバグの話の詳細を書くと訳わからなくなるし、詳細はどんどん変わっいるのでそれは書きません。その代り大元の考え方を書いて考えを整理します。つまり、自分のための日記です。

Rubyの型推論ということで余り型を厳しくしてしまうと使いにくくなってしまいます。ytljitのポリシーとして型によるプログラムの検証は一切無視、できるだけオリジナルのRubyのプログラムを受け入れるとします。そうすると例えば、こんな感じのプログラムは推論したいところです。

  def id(x)
    x
  end

  id(1.0)
  id("abc")

メソッド単位で型付けをすると考えるとidの戻り値の型は決められない(またはObject)となってしまいますが、メソッドの呼び出し単位で型を決めれば型が決まります。この場合、id(1.0)はFloatですし、id("abc")はStringです。こうやってメソッドの引数の型(シグネチャ)をパラメータとする関数として型を定義するわけです。これは関数型言語等の型変数と似ていますが、型チェックは無視している分もっと強力です。例えば、シグネチャに入っていない型を返すような多相型のメソッドでも定義できます。

ytljitは変数の参照・メソッド呼び出しなど基本的な動作を定義するノードと呼んでいる単位の集まりでRubyプログラムを表現します。すべてのノードにはそれぞれ型を持ち、また関連するノードへのリンクを持ちます。各ノードはそれぞれリンク先のノードの型情報をもとに自分の型を推論して、自分を参照しているノードに知らせます。

ノードが推論する際には実はもう１つ情報が渡ります。それが、現在ノードが属しているメソッドが受け取る引数の型情報(シグネチャ)です。こんなものどっから持ってくるんだと思うかもしれませんが、メソッドの定義からではなくメソッド呼び出し経由でシグネチャを渡していきます。例えば、上の例では[Float]というシグネチャをidの定義で渡して推論を行った後、["String"]というシグネチャで同様に推論します。つまり、メソッドの推論はメソッド呼び出し毎に行います。もちろん、同じシグネチャでは同じ型が推論されますのでこの辺は枝刈りして速度を稼ぎます。

ちょっと長くなりそうなのでここで中断します。シグネチャをどう作るのか・使うのか。ブロックはどう扱うのか。メソッドディスパッチはどうするのかとかは今後書きます。

(続く予定　は未定)