Higher Order Deforestation

Issue title: Program Transformation: Theoretical Foundations and Basic Techniques. Part 2

Article type: Research Article

Authors: Hamilton, Geoff W.

Affiliations: School of Computer Applications Dublin City University Dublin 9, Ireland. E-mail: hamilton@computing.dcu.ie

Abstract: Deforestation is a well known transformation algorithmwhich can eliminate intermediate structures from functional programs. In previous work, we have shown how the deforestation algorithm can be extended to handle higher order programs. A higher order treeless form of expression was defined to ensure the termination of this algorithm. Our higher order algorithm was further extended by Seidl and Sørensen, and this extension was shown to remove some intermediate structures not removed by our algorithm (although our original algorithm can also remove some intermedi-ate structures not removed by their technique). In this paper, we show how our original definition of higher order treeless form can be extended to allow the intermediate structures in the examples given by Seidl and Sørensen to be removed. We argue that, because our extended algorithm uses an easy to recognise treeless form, there is more transparency for the programmer in terms of the improvements which will be made. We prove that our new algorithm terminates, and we conjecture that it ensures that there is no efficiency loss, which we argue is essential for any optimisation.

Keywords: deforestation, transformation, termination, efficiency

Journal: Fundamenta Informaticae, vol. 69, no. 1-2, pp. 39-61, 2006