Cheap deforestation for non-strict functional languages

[摘要] In functional languages intermediate data structures are often used as glue toconnect separate parts of a program together. Deforestation is the processof automatically removing intermediate data structures. In this thesis wepresent and analyse a new approach to deforestation. This new approach isboth practical and general.We analyse in detail the problem of list removal rather than the more generalproblem of arbitrary data structure removal. This more limited scope allowsa complete evaluation of the pragmatic aspects of using our deforestationtechnology.We have implemented our list deforestation algorithm in the Glasgow Haskellcompiler. Our implementation has allowed practical feedback. One importantconclusion is that a new analysis is required to infer function aritiesand the linearity of lambda abstractions. This analysis renders the basicdeforestation algorithm far more effective.We give a detailed assessment of our implementation of deforestation. Wemeasure the effectiveness of our deforestation on a suite of real applicationprograms. We also observe the costs of our deforestation algorithm.

[发布机构] University:University of Glasgow;Department:School of Computing Science

[关键词] QA75 Electronic computers. Computer science