Tree Transducer Composition as Program Transformation Export

@phdthesis{voi05, 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.}, author = {Voigtl\"{a}nder, Janis}, citeulike-article-id = {315786}, citeulike-linkout-0 = {http://www.amazon.de/exec/obidos/redirect?tag=citeulike01-21&path=ASIN/3899593693}, citeulike-linkout-1 = {http://wwwtcs.inf.tu-dresden.de/~voigt/phdthesis.ps.gz}, keywords = {accumulating-parameters, attribute-grammars, call-by-name, call-by-need, circular-programs, deforestation, functional-programming, haskell, induction-proofs, laziness, lazy-evaluation, multiple-traversals, operational-semantics, optimization, program-transformation, tree-transducers, tupling}, posted-at = {2005-09-12 07:50:09}, priority = {0}, publisher = {Der Andere Verlag}, school = {Technische Universit\"{a}t Dresden}, title = {Tree Transducer Composition as Program Transformation}, url = {http://wwwtcs.inf.tu-dresden.de/~voigt/phdthesis.ps.gz}, year = {2005} }

TY - THES ID - voi05 L3 - citeulike-article-id:315786 N2 - 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. TI - Tree Transducer Composition as Program Transformation PB - Technische Universität Dresden KW - accumulating-parameters KW - attribute-grammars KW - call-by-name KW - call-by-need KW - circular-programs KW - deforestation KW - functional-programming KW - haskell KW - induction-proofs KW - laziness KW - lazy-evaluation KW - multiple-traversals KW - operational-semantics KW - optimization KW - program-transformation KW - tree-transducers KW - tupling AU - Voigtländer, Janis PY - 2005/// UR - http://www.amazon.de/exec/obidos/redirect?tag=citeulike01-21&path=ASIN/3899593693 ER -