© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Type Inference Builds a Short Cut to Deforestation
Olaf Chitil
In Proceedings of the 1999 ACM SIGPLAN International Conference on Functional Programming (ICFP '99), pages 182-196. ACM Sigplan Notices, 34(9), 1999.Abstract
Deforestation optimises a functional program by transforming it into another one that does not create certain intermediate data structures. Short cut deforestation is a deforestation method which is based on a single, local transformation rule. In return, short cut deforestation expects both producer and consumer of the intermediate structure in a certain form. Warm fusion was proposed to automatically transform functions into this form. Unfortunately, it is costly and hard to implement. Starting from the fact that short cut deforestation is based on a parametricity theorem of the second-order typed lambda-calculus, we show how the required form of a list producer can be derived through the use of type inference. Typability for the second-order typed lambda-calculus is undecidable. However, we present a linear-time algorithm that solves a partial type inference problem and that, together with controlled inlining and polymorphic type instantiation, suffices for deforestation. The resulting new short cut deforestation algorithm is efficient and removes more intermediate lists than the original.
Download publication 199 kbytes (PDF)Bibtex Record
@inproceedings{1903,
author = {Olaf Chitil},
title = {{Type Inference Builds a Short Cut to Deforestation}},
month = {unknown},
year = {1999},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1999/1903},
publication_type = {inproceedings},
submission_id = {20687_1083666759},
other_year = {1999},
booktitle = {Proceedings of the 1999 ACM SIGPLAN International Conference on Functional Programming (ICFP '99)},
organization = {ACM Sigplan Notices, 34(9)},
}