Jennifer Hackett
Parametric polymorphism and operational improvement
Hackett, Jennifer; Hutton, Graham
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.
Citation
Hackett, J., & Hutton, G. Parametric polymorphism and operational improvement. Presented at 23rd ACM SIGPLAN International Conference on Functional Programming, St. Louis, Missouri, United States
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 23rd ACM SIGPLAN International Conference on Functional Programming |
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 |
DOI | https://doi.org/10.1145/3236763 |
Public URL | https://nottingham-repository.worktribe.com/output/945535 |
Publisher URL | https://dl.acm.org/citation.cfm?id=3236763 |
Related Public URLs | http://www.cs.nott.ac.uk/~pszgmh/ppoi.pdf |
Additional Information | Conference dates. Sun 23 - Sat 29 September 2018 |
Contract Date | Jul 11, 2018 |
Files
ppoi.pdf
(701 Kb)
PDF
You might also like
Calculating Compilers Effectively (Functional Pearl)
(2024)
Presentation / Conference Contribution
Beyond Trees: Calculating Graph-Based Compilers (Functional Pearl)
(2024)
Journal Article
Quotient Haskell: Lightweight Quotient Types for All
(2024)
Journal Article
Programming language semantics: It’s easy as 1,2,3
(2023)
Journal Article
Calculating Compilers for Concurrency
(2023)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search