Type-Inference Based Short Cut Deforestation (nearly) without Inlining

Chitil, Olaf (1999) Type-Inference Based Short Cut Deforestation (nearly) without Inlining. In: 11th International Workshop on Implementation of Functional Languages, September 7th-10th 1999, Lochem, Netherlands. (Full text available)

PDF
Download (163kB)	Preview

Abstract

Deforestation optimises a functional program by transforming it into another one that does not create certain intermediate data structures. In [ICFP'99] we presented a type-inference based deforestation algorithm which performs extensive inlining. However, across module boundaries only limited inlining is practically feasible. Furthermore, inlining is a non-trivial transformation which is therefore best implemented as a separate optimisation pass. To perform short cut deforestation (nearly) without inlining, Gill suggested to split definitions into workers and wrappers and inline only the small wrappers, which transfer the information needed for deforestation. We show that Gill's use of a function build limits deforestation and note that his reasons for using build do not apply to our approach. Hence we develop a more general worker/wrapper scheme without build. We give a type-inference based algorithm which splits definitions into workers and wrappers. Finally, we show that we can deforest more expressions with the worker/wrapper scheme than the algorithm with inlining.

Item Type:	Conference or workshop item (Paper)
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:05
Last Modified:	30 Jun 2014 08:34
Resource URI:	https://kar.kent.ac.uk/id/eprint/21722 (The current URI for this page, for reference purposes)