Back to search

University of Glasgow

Cheap deforestation for non-strict functional languages

Abstract

dc:description.abstract

In functional languages intermediate data structures are often used as glue to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm.

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
1996

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gill, Andrew John

Subjects

dc:subject × 1

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gill, Andrew John. Cheap deforestation for non-strict functional languages. PhD thesis, University of Glasgow, 1996.