Functional programming languages are an ideal medium for program optimisations basedon source-to-source transformation techniques. Referential transparency affords opportunitiesfor a wide range of correctness-preserving transformations leading to potent optimisationstrategies.This thesis builds on deforestation, a program transformation technique due to Wadlerthat removes intermediate data structures from first-order functional programs.Our contribution is to reformulate deforestation for higher-order functional programminglanguages, and to show that the resulting algorithm terminates given certain syntactic andtyping constraints on the input. These constraints are entirely reasonable, indeed it ispossible to translate any typed program into the required syntactic form. We show howthis translation can be performed automatically and optimally.The higher-order deforestation algorithm is transparent. That is, it is possible to determineby examination of the source program where the optimisation will be applicable.We also investigate the relationship of deforestation to cut-elimination, the normalisationproperty for the logic of sequent calculus. By combining a cut-elimination algorithm andfirst-order deforestation, we derive an improved higher-order deforestation algorithm.The higher-order deforestation algorithm has been implemented in the Glasgow HaskellCompiler. We describe how deforestation fits into the framework of Haskell, and designa model for the implementation that allows automatic list removal, with additional deforestationbeing performed on the basis of programmer supplied annotations. Results fromapplying the deforestation implementation to several example Haskell programs are given.
【 预 览 】
附件列表
Files
Size
Format
View
Deforestation for higher-order functional programs
PDF
download
878987797
028-85220240
