Skip to main content

Type Inference Builds a Short Cut to Deforestation

Chitil, Olaf (1999) Type Inference Builds a Short Cut to Deforestation. ACM SIGPLAN Notices, 34 (9). pp. 249-260. ISSN 0362-1340. (doi:10.1145/317765.317907) (KAR id:21702)

Language: English
Download (224kB)
[thumbnail of type_inference_builds_chitil.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


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: Article
DOI/Identification number: 10.1145/317765.317907
Additional information: Issue: 9
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Olaf Chitil
Date Deposited: 07 Dec 2009 15:13 UTC
Last Modified: 16 Nov 2021 10:00 UTC
Resource URI: (The current URI for this page, for reference purposes)
Chitil, Olaf:
  • Depositors only (login required):


Downloads per month over past year