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. In dem Vortrag beschreiben wir einen Algorithmus, der einen beliebigen Erzeuger einer Zwischendatenstruktur in die von Short Cut Deforestation geforderte Form bringt. Wir zeigen, wie dieses Problem auf ein Typinferenzproblem zurückgeführt werden kann, das durch einen effizienten Typinferenzalgorithmus gelöst wird.
Schließlich beschäftigen wir uns noch mit dem Problem, Deforestation über Modulgrenzen hinweg durchzuführen. Deforestation scheint intensives Inlinen von Funktionen zu benötigen, was dem Ziel der getrennten Compilation von Modulen zuwiderläuft. Es zeigt sich jedoch, daß eine Erweiterung des vorher vorgestellten Algorithmus eine Funktionsdefinition in eine sogenannte Worker- und eine Wrapper-Definition aufteilen kann. Nur die kleine Wrapper-Definition muß inlined werden, um Deforestation zu ermöglichen.
Vortrag im Rahmen des Seminars zum Forschungsschwerpunkt Intelligente Formale Systeme. Technische Universität Dresden, 26. Januar 2000.
Abstract,
Folien (323 KB)