Skip to main content

Research Repository

Advanced Search

Parametric polymorphism and operational improvement

Hackett, Jennifer; Hutton, Graham


Jennifer Hackett


Parametricity, in both operational and denotational forms, has long been a useful tool for reasoning about program correctness. However, there is as yet no comparable technique for reasoning about program improvement, that is, when one program uses fewer resources than another. Existing theories of parametricity cannot be used to address this problem as they are agnostic with regard to resource usage. This article addresses this problem by presenting a new operational theory of parametricity that is sensitive to time costs, which can be used to reason about time improvement properties. We demonstrate the applicability of our theory by showing how it can be used to prove that a number of well-known program fusion techniques are time improvements, including fixed point fusion, map fusion and short cut fusion.


Hackett, J., & Hutton, G. (2018). Parametric polymorphism and operational improvement. Proceedings of the ACM on Programming Languages, 2(ICFP), 1-24.

Journal Article Type Conference Paper
Conference Name 23rd ACM SIGPLAN International Conference on Functional Programming
Conference Location St. Louis, Missouri, United States.
Acceptance Date Jul 6, 2018
Online Publication Date Sep 1, 2018
Publication Date Sep 1, 2018
Deposit Date Jul 11, 2018
Publicly Available Date Sep 1, 2018
Electronic ISSN 2475-1421
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 2
Issue ICFP
Article Number 68
Pages 1-24
Public URL
Publisher URL
Related Public URLs
Additional Information Conference dates. Sun 23 - Sat 29 September 2018


You might also like

Downloadable Citations