Shiikaの型推論
このエントリは言語実装のカレンダー | Advent Calendar 2023 - Qiitaの2日目の記事です。前日の記事はabo_junghichiさんの9キロバイトのコードで関数型言語を実装 - 自作言語revappの理由 - 一人一党党でした。
Shiikaは私が作っている、Ruby風文法の静的型付け言語です。今日は10月に行った型推論周りの整理を解説します。
Shiikaの型推論
型推論が行われるのは以下の2つのケースです。
ブロックパラメータの型
[1, 2, 3].each{|i: Int| p i} は、以下のように書ける [1, 2, 3].each{|i| p i}メソッドの型引数
[1, 2, 3].map<String>{|i| i.to_s} は、以下のように書ける [1, 2, 3].map{|i| i.to_s} 特に、 Pair.new<Int, Bool>(1, true) は以下のように書ける。 Pair.new(1, true)
推論単位
いずれも、型は各メソッド呼び出しの単位で推論します。メソッド定義単位での推論、つまり「未知の型に出会うたびに変数としておき、メソッド末尾でまとめて解決する」みたいな方法も考えたのですが、
ary.each do |x|
y = x.foo
y.bar
end
みたいなコードがあったときにxの型が確定しなくて（fooというメソッドがあるということしかわからない)そうするとyの型もわからなくて…みたいに未知の型だらけになるんじゃないか？と思ってやらなかったんですけど、どうなんですかね。この場合だとaryの型から最終的にはすべて確定するのか。ただけっこう大きい改修が必要になるなあ。
推論手順
というのはおいといて、推論の手順を解説します。大枠は、昔(１０年前…！)調べていたHM型推論を参考にしています。わからない部分を変数とし、等式を立て、最後にそれを解く、というやつですね。
例として以下を考えます。
class A
def foo<B, C, D>(b: B, f: Fn1<B, C>) -> D
...
end
end
...
a.foo(1){|b| b + 1}
ここではfooの型変数B,C,Dと、ブロックパラメータbの型が省略されています。
まずB,C,Dをそれぞれ'1, '2, '3とおきます。実引数(ブロックは除く)と仮引数を照らし合わせることで、'1はIntだと分かります。
次にブロックを処理します。ここでヒューリスティックが入るのですが、基本的にここまででブロックパラメータの型は明らかになっていると考えます。というのはブロックはfooの内部で呼び出すために受け取っているわけで、であればブロックに渡す値というのは無から発生することはないので、Aが事前に持っているか、ブロック以外の引数という形で手に入るはずです。もしこの時点でブロックパラメータの型が明らかにならなかった場合はエラーとし、ユーザに型注釈を促します。
ブロックパラメータの型がわかれば、ブロックの中身を通常通り処理することでブロックの返り値の型が確定します。これで'2がわかります。
あとはメソッドの中身を処理して、返り値の型である'3が確定します。これで未知の型がすべて推論できました。
PRについて
という2種類の型推論ですが、以前は別々に実装していたのでコードがかなりカオスでした。これをまとめてやるように整理したのが冒頭のpull requestなのでした。
