Imperative Polymorphism by Store-Based Types as Abstract Interpretations

Casper Bach Poulsen and Peter D. Mosses and Paolo Torrini

Abstract

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.

DOI

PDF

Accompanying material