Type Inference with Nonstructural Subtyping

Forfattere

  • Jens Palsberg
  • Mitchell Wand
  • Patrick O'Keefe

DOI:

https://doi.org/10.7146/brics.v2i33.19936

Resumé

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.

Downloads

Publiceret

1995-06-03

Citation/Eksport

Palsberg, J., Wand, M., & O’Keefe, P. (1995). Type Inference with Nonstructural Subtyping. BRICS Report Series, 2(33). https://doi.org/10.7146/brics.v2i33.19936