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