next up previous contents
Next: Unifying Record Types Up: Type Inference Previous: Type Inference   Contents

Basic Unification

Type-checkers for languages based on the Hindley-Milner type discipline, like ML and Haskell, take advantage of principal typing properties, making complete type inference relatively straightforward. Inference algorithms are traditionally implemented using type unification variables, at various points asserting equalities between types, in the process discovering the values of type variables. The Ur/Web compiler uses the same basic strategy, but the complexity of the type system rules out easy completeness.

Type-checking can require evaluating recursive functional programs, thanks to the type-level $ \mathsf{map}$ operator. When a unification variable appears in such a type, the next step of computation can be undetermined. The value of that variable might be determined later, but this would be ``too late'' for the unification problems generated at the first occurrence. This is the essential source of incompleteness.

Nonetheless, the unification engine tends to do reasonably well. Unlike in ML, polymorphism is never inferred in definitions; it must be indicated explicitly by writing out constructor-level parameters. By writing these and other annotations, the programmer can generally get the type inference engine to do most of the type reconstruction work.


next up previous contents
Next: Unifying Record Types Up: Type Inference Previous: Type Inference   Contents
2014-07-14