Another Type Inference Algorithm for First-Class Implicit Polymorphism

Abstract

We propose yet another approach to type inference with first-class implicit polymorphism, based on the interleaving of an Algorithm M-style constraint-generating elaboration of terms and a solver for the generated constraints. The novelty of our approach is that types include explicit syntactic representations of unknown polymorphic types during type inference. Solving unification constraints with unknown polymorphic types also computes type arguments for the elaborated terms. The resulting system is uniform, simple, extends to support domain-specific constraints, and compares favorably with other approaches to first-class implicit polymorphism.