Practical refinement-type checking

authors: Rowan Davies
year: 2005
url: http://www.cs.cmu.edu/afs/cs/user/fp/www/papers/rml97.pdf
abstract: Refinement types allow many more properties of programs to be expressed and statically checked than conventional type systems. We present a practical algorithm for refinement-type checking in a λ-calculus enriched with refinement-type annotations. We prove that our basic algorithm is sound and complete, and show that every term which has a refinement type can be annotated as required by our algorithm. Our positive experience with an implementation of an extension of this algorithm to the full core language of Standard ML demonstrates that refinement types can be a practical program development tool in a realistic programming language. The required refinement type definitions and annotations are not much of a burden and serve as formal, machine-checked explanations of code invariants which otherwise would remain implicit.