Open AccessType Inference with Nonstructural Subtyping
Author(s) -
Jens Palsberg,
Mitchell Wand,
Patrick O'Keefe
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i33.19936
Subject(s) - subtyping , type (biology) , type inference , inference , function (biology) , mathematics , algorithm , discrete mathematics , computer science , combinatorics , programming language , artificial intelligence , biology , genetics , ecology
We present an O(n^3) time type inference algorithm for a type system with a largest type !, a smallest type ?, 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 ?. This may be surprising, especially because the system with ? is strictly more powerful.