Abstract

Type-Inference Based Deforestation of Functional Programs

In nicht-striken 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 Program in ein äquivalentes Programm umwandeln, welches diese Zwischendatenstrukturen nicht mehr erzeugt.

In diesem Vortrag wird eine neue Deforestation-Methode vorgestellt, 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 Schreiben von verständlichen Programmen zuwiderlaufen. Im Vortrag 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.