Scalable and Precise Refinement Types for Imperative Languages

In formal verification, there is a dichotomy between tools which are scalable and easy to use but imprecise, like most pluggable type systems, and tools which are expressive and precise but badly scalable and difficult to use, like deductive verification. Our previous research to create a formal link between refinement types and deductive verification allows programmers to use a scalable type system for most of the program, while automatically generating specifications for a deductive verifier for the difficult-to-prove parts. However, this is currently limited to immutable objects. In this work, we thus present an approach which combines uniqueness and refinement type systems in an imperative language. Unlike existing similar approaches, which limit refinements such that they cannot contain any reference-typed program variables, our approach allows more general refinements, because even if a type constraint is not provable in the type system itself, it can be translated and proven by a deductive verifier.