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

Chitil, Olaf (1999) Type-Inference Based Short Cut Deforestation (nearly) without Inlining. In: Clack, Chris and Koopman, P., eds. Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages. . pp. 17-32.

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 > Sciences > School of Computing > Theoretical Computing Group
Depositing User:	Olaf Chitil
Date Deposited:	07 Dec 2009 15:05 UTC
Last Modified:	28 May 2019 14:01 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/21722 (The current URI for this page, for reference purposes)