Imperative Polymorphism by Store-Based Types as Abstract Interpretations

By Casper Bach Poulsen, Peter D. Mosses, and Paolo Torrini


Dealing with polymorphism in the presence of imperative features is a long-standing open problem for Hindley-Milner type systems. A widely adopted approach is the value restriction, which inhibits polymorphic generalisation and unfairly rejects various programs that cannot go wrong. We consider abstract interpretation as a tool for constructing safe and precise type systems, and investigate how to derive store-based types by abstract interpretation. We propose store-based types as a type discipline that holds potential for interesting and flexible alternatives to the value restriction.

Presented at PEPM 2015.

Accompanying material