Shiika/型推論
昔やったやつの拡張でいけないかな
現在のskc_ast2hir
astを根から順に見ていき、順にHirに変換
HirExpressionがtyをもつ
型推論するには
いったん木全体を舐めないといけない?
typed astみたいなものをつくるのかな
ASTとほぼ同じだけど型が入っている
型が自明なものは型を入れられる
リテラル
関数の引数の参照
しかしあれだな
論文を読んだ。
先に、何を推論したいのか整理したほうがよさそう
現在のShiika
ローカル変数の型は、右辺の型で決まる
メソッドの引数・返り値の型は型注釈が必須
推論したいところ
a = Array<Int>.new を、a = [] (= a = Array.new) と書きたい
型引数の推論
たとえばa.push(3)があればIntだとわかる
隣にa.push("b")があればObjectだが…
たとえば return a があってメソッドの返り値がArray<Int>ならIntだとわかる
たとえばArray<Int>を受け取るメソッドに渡していたらIntだとわかる
pair = Pair<Int, Bool>.new(3, true) の型引数部分を推論してほしい
引数の型からわかるはず
ary.each do |i: Int| のIntを推論してほしい
ary.map<Bool>{|i: Int| i.odd?} のBoolを推論してほしい
HM風:等式をたくさん用意してそれを解く
bidi風:わからないところを^αと置いて推論を進める
例
code:sk
a = Array<^0>.new # ^0=Int
a.push(1)
Array<^0>.push(item: ^0) で、itemがInt
code:sk
pair = Pair<^1, ^2>.new(3, true) # ^1=Int ^2=Bool
Pair<^1, ^2>.new(a: ^1, b: ^2) で、aがInt, bがBool
code:sk
nums.each{|i: ^6| p i}
Array<Int>.each(f: Fn1<Int, Void>) で、
code:sk
nums.map<^4>{|i: ^5| i.to_s} # ^4=String ^5=Int
Array<Int>.map<^4>(f: Fn1<Int, ^4>) で、
作戦
わからない型パラメータを^αとおく。下限がNever、上限がObjectとしておく
手がかりがあれば下限・上限を更新する
あてはまらなければtype error
推論単位(メソッド)の最後まで来たら、下限を採用して後段(コード生成)に渡す
これだけだとブロックパラメータがだめそう
ブロック付き呼び出しは、特別扱いする
ブロック
code:sk
nums.each{|i: ^6| p i}
numsはArray<Int>とわかっているものとする
このときeachのシグネチャは Array<Int>#each(f: Fn1<Int, Void>) -> Void
このfの型を、ブロックを処理する際にヒントとして渡す
convert_lambda_exprはこのヒントからブロックパラメータの型を得る
code:sk
nums.map<^4>{|i: ^5| i.to_s} # ^4=String ^5=Int
numsはArray<Int>とわかっているものとする
このときmapのシグネチャは Array<Int>#map<U>(f: Fn1<Int, U>) -> Array<U>
ヒントとして^Uがわたってくるので、ブロックの最後の式の型で^Uの上限/下限(どっちだっけ)を更新する
引数の型が^Xになることはあるのかな?
code:sk
def foo<X>(x: X, f: Fn1<X, Array<X>>)
p f(X).len
end
人工的だが書けなくはない
この場合の処理
fooの呼び出しを見つけたので^Xを作成
引数の型チェックの際に^Xの上限がIntとわかる
その状態でヒントとして^X <= Intがブロックの処理時に渡される
Intは+(other: Int)をもつので ^X <= Intに合致
ブロックの返り値の型は Array<^X <= Int>
これはArray<X>に合致
ところで
a = Pair.new(1,2)はどういう説明をするのか
Pair.new<A, B>(a: A, b: B) -> Pair<A, B> というメソッドがあるということにするか。
まとめると
以下の3種類を順に実装する
1. ブロックパラメータの型の推定
2. メソッドの型引数の推定
3. レシーバの型引数の推定
レシーバの型引数とは??
Pair.new(1,2) は3.ではなく2.として回収できそう
a = Array.new がむずかしい
これはまあだいぶ後回しだなあ