| Author: |
J. Voigtländer |
| Published: |
Theory of Computing Systems, volume 41(4), pages 619-689, Springer, 2007. |
| DOI: |
10.1007/s00224-006-1235-9 |
| BibTeX: |
Voi07.bib |
| 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 not 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 are suitable for integration into an optimizing
compiler.
|
| Download: |
FormalEfficiencyAnalysisForTreeTransducerComposition.pdf |
| Rights: |
Copyright held by Springer. The original publication is available from http://dx.doi.org/10.1007/s00224-006-1235-9. |