OCaml でも採用されているレベルベースの多相型型推論とは - はやくプログラムになりたい言語実装 Advent Calendar 2017 の16日目の記事です． GoCaml という OCaml のサブセットな言語を実装していて，多相型の型推論を実装するために論文を読んだり OCaml の実装をちょっと追ったりしていたので，その知識を整理する意味でこのエントリを書いています． この記事では OCaml の型推論器のベースになっている「レベルベースの多相型型推論アルゴリズム」について概略を直感的に説明しようと思います． 理論的になぜこのアルゴリズムで正しく動作するのかについてはこの記事で概要を把握した上で論文 のほうを読んでいただければ理解が速いと思います． また，この記事では最もシンプルな単相型のHM型推論については知っている前提で書きます． ご存知でない場合は， 住井先生の MinCaml の型推論実装の解説 五十嵐先生の型推論の解説 20日目の@uint256_t さん
