Type Inference Builds a Short Cut to Deforestation

Chitil, Olaf (1999) Type Inference Builds a Short Cut to Deforestation. In: Proceedings of the 1999 ACM SIGPLAN International Conference on Functional Programming (ICFP '99), September 27 - September 29, 1999 , Paris, France. (Full text available)

PDF
Download (204kB)
[img]
Preview

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.

Item Type: Conference or workshop item (Paper)
Additional information: Issue: 9
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User: Mark Wheadon
Date Deposited: 07 Dec 2009 15:13
Last Modified: 16 Apr 2014 08:09
Resource URI: http://kar.kent.ac.uk/id/eprint/21702 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year