Skip to main content

Research Repository

Advanced Search

Parametric polymorphism and operational improvement

Hackett, Jennifer; Hutton, Graham

Authors

Jennifer Hackett



Abstract

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.

Presentation Conference Type Conference Paper (unpublished)
Start Date Sep 23, 2018
Publication Date Jul 30, 2018
Peer Reviewed Peer Reviewed
Series Title Proceedings of the ACM on Programming Languages
Series ISSN 2475-1421
APA6 Citation Hackett, J., & Hutton, G. (2018). Parametric polymorphism and operational improvement. doi:10.1145/3236763
DOI https://doi.org/10.1145/3236763
Publisher URL https://dl.acm.org/citation.cfm?id=3236763
Related Public URLs http://www.cs.nott.ac.uk/~pszgmh/ppoi.pdf
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information Published in: Proceedings of the ACM on Programming Languages, volume 2, article no. 68, Issue ICFP, September 2018

Files

ppoi.pdf (701 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;