Hindley Milner型推論に機能を追加していく1 Unit型の追加
前々回、前回の記事でそれなりに実用的なLet多相型推論が実装できた:
型推論を実装・改善していく9 レベルによるLet多相の効率化(前編) - Arantium Maestum
型推論を実装・改善していく10 レベルによるLet多相の効率化(後編) - Arantium Maestum
しかし言語機能としてはSTLCにLetが加わっただけで非常に簡素だ。これから段階的に言語機能をリッチにしていく。
今回はまず非常に簡単にユニット型とユニット式の追加。
型
追加されるのはunit
型のみ:
type ty = ... | TUnit
式
式も同じくユニット・リテラルが追加される:
type exp = ... | EUnit
これはOCamlでいうところの()
(例えば0引数関数の呼び出しの時のf ()
などで渡されている()
)。
型推論
EUnit
の型付けは非常に簡単:
let rec typeof env level = function ... | EUnit -> TUnit
() : unit
だ。
generalize
とinstantiate
TUnit
は汎化しようがない:
let rec generalize level ty = match ty with ... | TUnit -> ty
そして具体化もしようがない:
let instantiate level ty = let id_var_hash = Hashtbl.create 10 in let rec f ty = match ty with ... | TUnit -> ty in f ty
match_fun_ty
、unify
、occursin
、adjustlevel
match_fun_ty
に渡されるのは関数型かそれに単一化できる型変数であるはずなのでTUnit
型が渡された場合はエラー:
let rec match_fun_ty tfunc targ = match tfunc with ... | TUnit -> failwith "Non-arrow type found in function position"
unify
関数にはなんの変化もない。単一化される型が両方TUnitだったら、片方がTUnitでもう片方が型変数だったら、片方がTUnitでもう片方が違う型だったら、というケースが既にワイルドカードによるパターンマッチですべて網羅されている。
TUnit
には型変数は含まれていないのでoccursin
はfalseを返す:
let rec occursin id = function ... | TUnit -> false
同じように、型変数がないのでTUnit
に対するadjustlevel
は何もしないで()
を返す:
let rec adjustlevel level = function ... | TUnit -> ()
まとめ
非常に簡単な更新だった反面、今まで書いた関数のほぼすべて(unify
以外)に多少変更があった。今後の拡張でも同じようにほとんどの関数に少しずつ手を入れていくことになりそう。
次回
次はBool型とIf式を追加する。