An Abstract Interpretation of ML Equality Kinds
| C. A. Gunter |
Elsa 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 a computable equality
relation. 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 which nevertheless have a computable
equality relation. In this paper we introduce a refinement of the
Standard ML system of equality types and prove that our system is
sound and complete with respect to the existence of a computable
equality. Our technique is based on an abstract interpretation of ML
operators as monotone functions over a three point lattice. We show
how the equality relation can be defined (as an ML program) from the
definition of a type with our equality property. We then demonstrate
a sound, efficient algorithm for inferring the equality property which
corrects the limitations of the standard definition in all cases of
practical interest.
Bibtex Entry
@inproceedings{GunterGM91,
author = "Carl A.~Gunter and Elsa L. Gunter and David B. {MacQueen}",
title = "An abstract interpretation for {ML} equality kinds",
booktitle = "Theoretical Aspects of Computer Software International
Conference {TACS} '91",
address = "Sendai, Japan",
year = "1991",
month = "September",
editor = "T. Ito and A. R. Meyer",
pages = "112--130",
series = "Lecture Notes in Computer Science",
volume = 526,
publisher = "Springer"}
Postscript version of paper
Back to
bibliography
Elsa Gunter