Formal Efficiency Analysis for Tree Transducer Composition Export

@article{citeulike:2090520, abstract = {We study the question of efficiency improvement or deterioration for a semantics-preserving program transformation technique for (lazy) functional languages, based on composition of restricted macro tree transducers. By annotating programs to reflect the intensional property "computation time" explicitly in the computed output and by manipulating such annotations, we formally prove syntactic conditions under which the composed program is guaranteed to be no less efficient than the original program with respect to the number of call-by-need reduction steps required to reach normal form. The criteria developed can be checked automatically and efficiently, and thus they are suitable for integration into an optimizing compiler.}, author = {Voigtl\"{a}nder, Janis}, citeulike-article-id = {2090520}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00224-006-1235-9}, citeulike-linkout-1 = {http://wwwtcs.inf.tu-dresden.de/~voigt/TOCS.pdf}, doi = {10.1007/s00224-006-1235-9}, journal = {Theory of Computing Systems}, keywords = {accumulating-parameters, call-by-name, deforestation, functional-programming, program-transformation, tree-transducers}, month = {December}, number = {4}, pages = {619--689}, posted-at = {2007-12-11 16:03:04}, priority = {0}, publisher = {Springer-Verlag}, title = {Formal Efficiency Analysis for Tree Transducer Composition}, url = {http://dx.doi.org/10.1007/s00224-006-1235-9}, volume = {41}, year = {2007} }

TY - JOUR ID - citeulike:2090520 L3 - citeulike-article-id:2090520 N2 - We study the question of efficiency improvement or deterioration for a semantics-preserving program transformation technique for (lazy) functional languages, based on composition of restricted macro tree transducers. By annotating programs to reflect the intensional property "computation time" explicitly in the computed output and by manipulating such annotations, we formally prove syntactic conditions under which the composed program is guaranteed to be no less efficient than the original program with respect to the number of call-by-need reduction steps required to reach normal form. The criteria developed can be checked automatically and efficiently, and thus they are suitable for integration into an optimizing compiler. IS - 4 JF - Theory of Computing Systems EP - 689 TI - Formal Efficiency Analysis for Tree Transducer Composition PB - Springer-Verlag VL - 41 SP - 619 KW - accumulating-parameters KW - call-by-name KW - deforestation KW - functional-programming KW - program-transformation KW - tree-transducers AU - Voigtländer, Janis PY - 2007/12/06/ UR - http://dx.doi.org/10.1007/s00224-006-1235-9 ER -