archives

HMF: Simple type inference for first-class polymorphism

HMF: Simple type inference for first-class polymorphism - Daan Leijen, Draft April 8, 2008.

HMF is a conservative extension of Hindley-Milner type inference with first-class polymorphism and regular System F types. The system
distinguishes itself from other proposals with simple type rules and a very simple type inference algorithm that is just a small extension
of the usual Damas-Milner algorithm. Given the relative simplicity and expressive power, we feel that HMF can be a very attractive
type system in practice. There is a reference implementation of the type system available at: http://research.microsoft.com/users/daan/pubs.html.

An excellent paper even in its current draft form. I also placed this under the learning category, because Daan's writing style is lucid enough that the concepts can be understood by relative newcomers to the field of type theory

FPH: First-class Polymorphism for Haskell

FPH: First-class Polymorphism for Haskell, by Dimitrios Vytiniotis, Stephanie Weirich and Simon Peyton Jones:

Languages supporting polymorphism typically have ad-hoc restrictions on where polymorphic types may occur. Supporting “firstclass” polymorphism, by lifting those restrictions, is obviously desirable, but it is hard to achieve this without sacrificing type inference. We present a new type system for higher-rank and impredicative polymorphism that improves on earlier proposals: it is an extension of Damas-Milner; it relies only on System F types; it has a simple, declarative specification; it is robust to program transformations; and it enjoys a complete and decidable type inference algorithm.

Under Related Work, the authors provide a detailed comparison of their system with MLF, and HMF.

Flexible types: Robust type inference for first-class polymorphism

Flexible types: Robust type inference for first-class polymorphism, by Dan Leijen:

We present HML, a type inference system that supports full firstclass polymorphism where few annotations are needed: only function parameters with a polymorphic type need to be annotated. HML is a simplification of MLF where only flexibly quantified types are used. This makes the types easier to work with from a programmers perspective, and we found that it simplifies the implementation of the type inference algorithm significantly. Still, HML retains much of the expressiveness of MLF, it is robust with respect to small program transformations, and has a simple specification of the type rules with an effective type inference algorithm that infers principal types. A reference implementation of the type system is available at: http://research.microsoft.com/users/daan/pubs.html.

Seems there's been a flurry of activity on first-class polymorphism recently, with HML, FPH, and HMF as simpler alternatives to full MLF.