Type inference based deforestation of functional programs

Chitil, Olaf; Indermark, Klaus

doi:23370

Type inference based deforestation of functional programs

Chitil, Olaf (Author)

2001

Verantwortlichkeitsangabevorgelegt von Olaf Chitil

ImpressumAachen : Publikationsserver der RWTH Aachen University 2001

UmfangIX, 155 S.

Aachen, Techn. Hochsch., Diss., 2000

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Indermark, Klaus (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2000-10-27

Online
URN: urn:nbn:de:hbz:82-opus-1144
URL: https://publications.rwth-aachen.de/record/51897/files/Chitil_Olaf.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; Funktionale Programmierung (frei) ; Deforestation (frei) ; Typinferenz (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In nicht-strikten funktionalen Programmen wird häufig eine Datenstruktur verwendet, um zwei separate Programmteile miteinander zu verbinden. Diese Zwischendatenstruktur wird von dem einen Teil erzeugt und von dem anderen Teil verbraucht. Die gewonnene Modularität wird mit einer Verlängerung der Programmlaufzeit erkauft, da das Aufbauen und Zerlegen der Zwischendatenstruktur Zeit kostet. Deforestation bezeichnet eine Klasse von optimierenden Programmtransformationen, die ein Programm in ein äquivalentes Programm umwandeln, welches diese Zwischendatenstrukturen nicht mehr erzeugt. In dieser Arbeit wird eine neue Deforestation-Methode beschrieben, die eine bekannte Methode, Short Cut Deforestation, mit einer neuen, auf Typinferenz beruhenden Analyse kombiniert. Short Cut Deforestation eliminiert eine Zwischenliste durch eine einzige, lokale Transformation. Im Gegenzug stellt Short Cut Deforestation jedoch hohe Anforderungen an die syntaktische Form des Programms, die dem Ziel von verständlichen Programmen zuwiderlaufen. Es wird ein Algorithmus beschrieben, der einen beliebigen Erzeuger einer Zwischendatenstruktur in die von Short Cut Deforestation geforderte Form bringt. Den Kern des Algorithmus bildet ein effizienter Typinferenzalgorithmus, da das Transformationsproblem auf ein Typinferenzproblem zurückgeführt werden kann.

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.

OpenAccess:
PDF
(additional files)