FactoryHomeArchivesTags型推論を実装してみる2015-11-15#haskell突如として、型推論はどんな風にしたら実装できるのか知りたくなった。型理論とか全く知らないが、実装して動かしてみて原理を知りたいと思った。Haskellという論文を参考にしているらしい。477(2014-06-05)型システム入門という本を元にしているらしい。厚いし多分読んでもムズくて理解できないんだよね...Haskellで実装してみる上記のリンクたちを参考にして、Haskellで構文木を渡すとその型を推論する関数を作ってみる。言語として使えるようになるまでにするには敷居が高いので、ひとまず型の推論だけで、型検査などは行わない。評価したい式の構文木は構築されていて与えられるものとして、パーサなどの実装も行わない(パーサ編はこちら)(内容はほとんど上記の参照したサイトで解説されている内容そのままで、主にHaskellでどうやって型変数を扱うのか、どうやってSTモナドを扱うかと格闘していた気がする。式が持つ型は、整数型TIntと関数型TFun(引数の型と結果の型を持つ)と、型変数TVar(識別番号を持つ)。iTVarは未確定の型を保持する型変数で、後述の単一化(unify)で決定されることになる(決定せずに残る場合もある)。型変数の型が確定した場合にその型を保持するのは別テーブルで管理し、識別番号で参照する。