There are many advantages to writing functional programs in a compositional style, such as clarity and modularity. However, the intermediate data structures produced may mean that the resulting program is inefficient in terms of space. These may be removed using deforestation techniques, but whether the space performance is actually improved depends upon the structures being consumed in the same order that they are produced. In this paper we explore this problem for the case when the intermediate structure is a list, and present a solution. We then formalise the space behaviour of our solution by means of program transformation techniques and the use of abstract machines.
Content
Author and article information
Contributors
Catherine Hope
Graham Hutton
Conference
Publication date:
July
2006
Publication date
(Print):
July
2006
Pages: 1-15
Affiliations
[0001]School of Computer Science and IT, University of Nottingham
Jubilee Campus, Wollaton Road, Nottingham NG8 1BB, UK