Type inference based deforestation of functional programs

In lazy functional programs a data structure is often used to combine two separate parts of the program. This intermediate data structure is produced by one part and consumed by another one. The gained modularity has to be payed for in terms of a longer runtime, because construction and destruction of the intermediate data structure costs time. Deforestation is the name for a class of optimising program transformations that transform a program into an equivalent program which does not produce such intermediate data structures. In this thesis a new deforestation method is described which combines a known method, short cut deforestation, with a new analysis based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation places high demands on the syntactic structure of the program which run contrary to the goal of comprehensible programs. We describe an algorithm that transforms an arbitrary producer of an intermediate data structure into the form required by short cut deforestation. The core of the algorithm is an efficient type inference algorithm, because the transformation problem can be reduced to a type inference problem.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2001

Author dc:creator

• Chitil, Olaf

Contributors dc:contributor

• Indermark, Klaus

• info:eu-repo/classification/ddc/004
• Informatik
• Funktionale Programmierung
• Deforestation
• Typinferenz

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A51897