School of Computing

Type-inference based short cut deforestation (nearly) without inlining

Olaf Chitil

In Chris Clack and Pieter Koopman, editors, Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages, pages 182-196, 1999 Lochem, Netherlands, September 7th-10th 1999.

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.

Download publication 159 kbytes (PDF)

Bibtex Record

@inproceedings{1910,
author = {Olaf Chitil},
title = {Type-Inference Based Short Cut Deforestation (nearly) without Inlining},
month = {unknown},
year = {1999},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {Lochem, Netherlands, September 7th-10th 1999.},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1999/1910},
    publication_type = {inproceedings},
    submission_id = {24118_1083683004},
    other_year = {1999},
    booktitle = {Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages},
    editor = {Chris Clack and Pieter Koopman},
    refereed = {no},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014