Volume 48, Number 3, 191-211, DOI: 10.1007/s00236-011-0136-9

Refined typing to localize the impact of forced strictness on free theorems

Daniel Seidel and Janis Voigtländer

Abstract

Free theorems establish interesting properties of parametrically polymorphic functions, solely from their types, and serve as a nice proof tool. For pure and lazy functional programming languages, they can be used with very few preconditions. Unfortunately, in the presence of selective strictness, as provided in languages like Haskell, their original strength is reduced. In this paper we present an approach for overcoming this weakness in specific situations. Employing a refined type system which tracks the use of enforced strict evaluation, we rule out unnecessary restrictions that otherwise emerge. Additionally, we provide (and implement) an algorithm determining all refined types for a given term.
An earlier version of this paper appeared under the title “Taming Selective Strictness” in the electronic proceedings of the “4. Arbeitstagung Programmiersprachen”, volume 154 of Lecture Notes in Informatics, pages 2916–2930, Gesellschaft für Informatik, 2009.

Fulltext Preview

Image of the first page of the fulltext document