Towards Constraint-based Type Inference with Polymorphic Recursion for Functional and Logic Programs

Abstract. Type inference in the context of polymorphic recursion is notoriously difficult. The extensions to the traditional *-calculus type inference algorithm by both Hindley-Milner and Mycroft are not capable of deriving the most general, i.e. principal types for programs with polymorphic recursion. Henglein has proposed a different algorithm, based on arrow graph reweriting, with an extended occurs check that allows for practical principal type inference in a large class of programs. We propose a new constraint-based formulation of Henglein's inference algorithm. Our formulation of the algorithm is simple, elegant and highly declarative in nature. It relates the opertional nature of the type inference more clearly to the formal theory of the type constraints and reveals how to extend the algorithm for logic programs. 1 Introduction Type inference is imporant because it combines the safety properties of typechecking with declaration-less programming. Unfortunately, type inference in the context of polymorphic recursion is notoriously difficult. The extensions tothe traditional *-calculus type inference algorithm by both Hindley-Milner andMycroft are not capable of deriving the most general, i.e. principal types for programs with polymorphic recursion. Henglein has proposed a different algorithm,based on arrow graph reweriting, with an extended occurs check that allows for practical principal type inference in a large class of programs