Computing ML equality kinds using abstract interpretation
| C. A. Gunter |
E. L. Gunter |
D. B. MacQueen |
| University of Pennsylvania |
AT&T Bell Labs |
AT&T Bell Labs |
Abstract:
The definition of Standard ML provides a form of generic
equality which is inferred for certain types, called equality
types, on which it is possible to define an equality relation in ML.
However, the standard definition is incomplete in the sense that there
are interesting and useful types which are not inferred to be
equality types but for which an equality relation can be defined in ML
in a uniform manner. In this paper, a refinement of the Standard ML
system of equality types is introduced and is proven sound and
complete with respect to the existence of a definable equality. The
technique used here is based on an abstract interpretation of ML
operators as monotone functions over a three point lattice. It is
shown how the equality relation can be defined (as an ML program) from
the definition of a type with our equality property. Finally, a
sound, efficient algorithm for inferring the equality property which
corrects the limitations of the standard definition in all cases of
practical interest is demonstrated.
Bibtex Entry
@Article{gunter-etal92ic,
author = "C. A. Gunter and E. L. Gunter and D. B. {MacQueen}",
title = "Computing {ML} equality kinds using abstract interpretation",
journal = "Information and Computation",
year = 1993,
volume = 107,
number = 2,
pages = "303--323",
month = "December"
}
Postscript version of paper
Back to
bibliography
Elsa Gunter