Type Inference with Non-structural Subtyping

Jens Palsberg
Mitchell Wand
Patrick O'Keefe

June 1995


We present an tex2html_wrap_inline20 time type inference algorithm for a type system with a largest type tex2html_wrap_inline22 , a smallest type tex2html_wrap_inline24 , and the usual ordering between function types. The algorithm infers type annotations of minimal size, and it works equally well for recursive types. For the problem of typability, our algorithm is simpler than the one of Kozen, Palsberg, and Schwartzbach for type inference without tex2html_wrap_inline24 . This may be surprising, especially because the system with tex2html_wrap_inline24 is strictly more powerful.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.