この記事では、主に型推論の実装方法について書いていきます。 理論的な側面は必要最低限に留めますので、詳しく知りたい方は参考文献を参照してください。 型推論とは何か 型推論とは何かについて軽く説明しておきましょう。 型推論とは、プログラムの変数や引数などの型を、明示的な指定がなくても自動的に推論し、決定する機構のことです。 たとえば、以下のような OCaml プログラムを考えてみましょう。 let f x y = x + y;; このプログラムはxとyを引数として、それらの和を返しています。OCaml の REPL で実行してみると、この関数は引数として整数を 2 つ持ち、整数を返す関数として定義されます。 xとyには何も型を指定していないのに、整数であると決定されるわけです。 val f : int -> int -> int = <fun> このように、型推論は型を周辺状況や文脈などから決定してくれます。 上記の例では、+演算子が左辺と右辺に整数をとり、整数を返す、という情報から関数の型を推論しています。このような単純な型推論は比較的簡単に実装できるでしょう。 今度は少し複雑な例を考えてみましょう。 let a x y z = if x == 2 then y else z(x - 1) この関数は以下の型を持ちます。 val a : int -> 'a -> (int -> 'a) -> 'a = <fun> 整数、任意の型x、引数として整数を持ち、任意の型xを返す関数、これらを引数として、任意の型xを返す関数、という型を持っています。 それぞれの引数について、なぜその型を持つのかについて説明します。 xは整数型を持っています。これは、x == 2の部分から推論されています。==演算子は左辺と右辺に同じ型をとるので、右辺の2と同じ型を持っていなくてはなりません。このことから、xは整数型を持つことがわかります。