型推論はどのようにして実装されているか - ラムダプラス+の紹介 -この記事は Haskell Advent Calendar jp 2010 のために書かれた物です。(20日目) 型推論は簡単 ML や Haskell のような言語の型推論は、型推論を知らないみなさんが考えているよりは遥かに簡単な物です。大雑把に言ってしまえば、構文木全体を探索して、同一である事が明らかな型同士の単一化をしていけば型推論できてしまうのです。 型推論の難しい所その1 - 多相型 しかし、型推論にも難しい事が無いわけではありません。まず最初の難関としては多相型が挙げられます。 ML や Haskell では let などの変数束縛に対して多相型が導入されています。式の中でこれらの変数が出現すると、その型の型変数(確定していない部分)を全て付け替える操作が発生します。 しかし、確定していない部分を付け替えるという事は、最終的に元の型が確定した後にその操作をしなければ、型を正しく
