School of Computing

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

Olaf Chitil

In Chris Clack and Pieter Koopman, editors, Proceedings of 11th International Workshop on Implementation of Functional Languages (1999), number 1868 in LNCS, pages 182-196, Netherlands, 2000. Springer.

Abstract

Deforestation optimises a functional program by transforming it into another one that does not create certain intermediate data structures. Our type-inference based deforestation algorithm performs extensive inlining, but only limited inlining across module boundaries is practically feasible. Therefore we here present a type-inference based algorithm that splits a function definition into a worker definition and a wrapper definition. For deforestation we only need to inline the small wrappers which transfer the required information. We show that we even can deforest definitions of functions that consume their own result with the worker/wrapper scheme, in contrast to the original algorithm with inlining.

Download publication 170 kbytes (PDF)

Bibtex Record

@inproceedings{1901,
author = {Olaf Chitil},
title = {{Type-Inference Based Short Cut Deforestation (nearly) without Inlining}},
month = {unknown},
year = {2000},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2000/1901},
    publication_type = {inproceedings},
    submission_id = {19944_1083663103},
    other_year = {1999},
    editor = {Chris Clack and Pieter Koopman},
    number = {1868},
    series = {LNCS},
    address = {Netherlands},
    publisher = {Springer},
    booktitle = {Proceedings of 11th International Workshop on Implementation of Functional Languages (1999)},
}

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

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

Last Updated: 21/03/2014