Tree Transducer Composition as Program Transformation
| Author: | J. Voigtländer |
|---|---|
| Published: | PhD thesis, Technische Universität Dresden, defended in January 2005. |
| BibTeX: | Voi05.bib |
| Abstract: | Nonstrict, purely functional programming languages offer a high potential for the modularization of software. But beside their advantages with respect to reliability and reusability, modularly specified programs often have the disadvantage of low execution efficiency, caused in particular by the creation and consumption of structured intermediate results. One possible approach to cure this conflict is the automatic, semantics-preserving optimization of programs, for which purely functional languages are again particularly suited due to their mathematical foundation. This dissertation studies a specific transformation for the elimination of intermediate results (for so called deforestation) regarding its impact on the program efficiency under nonstrict evaluation. The formal framework is provided by concepts from the theory of tree transducers. One special feature of the transformation under consideration is the successful handling of accumulating parameters, which find frequent use in functional programs. The core of the thesis is the derivation of effectively decidable, syntactic conditions on the original program under which the transformed program is to be preferred over it with respect to efficiency. |
| Download: | TreeTransducerCompositionAsProgramTransformation.ps.gz |
This thesis is also available as a book.